Continuation Passing Style in Ruby

I foolishly volunteered to talk about continuations at a meeting of the Grand Rapid Ruby User Group. I had played around with continuations in Scheme back in my grad school days, and I was curious about how continuations and call/cc would look in Ruby. In preparing my talk, I discovered a few interesting things which I'll spread over the course of a few blog entries.

The first interesting thing was that call/cc and continuations made more sense to me in the context of continuation passing style (CPS). One way to think of CPS is that it makes explicit what would normally be accumulated on a runtime stack. So consider this factorial method:

class Integer
  def factorial
    if self == 0
      1
    else
      self * (self-1).factorial
    end
  end
end

This is more or less what one would write based on the mathematical definition of the factorial function. For CPS, the first key is the recursive call: those self * accumulate on the runtime stack (so to speak), so that when the base case is finally triggered, the recursion unwinds and the factorial is actually computed.

Those self *s on the runtime stack are the continuation. Taking "continuation passing style" literally, we should pass that continuation as an argument to the function. That's exactly what we do to end up with this final result:

class Integer
  def factorial_cps(k = lambda { |v| v })
    if self == 0
      k.call(1)
    else
      (self-1).factorial_cps(lambda { |v|
        k.call(self * v)
      })
    end
  end
end

So, it doesn't appear to be a simple transformation. It turns out that the transformation is simple when taken in small steps, but I'm not interested in exploring those steps here. (Check out Essentials of Programming Languages by Friedman, Wand, and Haynes for the transformation process; other resources on the Internet abound.) For this blog entry, I'll justify the new code.

First, a new argument means a new parameter. This argument/parameter needs to be some of an object that can be executed. This could be anything at all, but Ruby comes with its own Proc class for encapsulating computations saving its outside context, including self, with the computation—otherwise known as a closure. (To use a different representation would mean more heavy lifting for us: saving the context when the continuation is built and providing a means to execute the continuation later on. A closure is too easy a representation to pass up!)

So in declaring the parameter ("k" for "continuation"?), I set its default value to be a closure which implements the identity function—it returns whatever you give it. Imagine calling this method in an irb session; there's nothing (relevant) on the runtime stack at that top level, so there shouldn't be anything significant in our explicit continuation.

Second, let's consider the base case. Suppose we're computing 5.factorial_cps. By the time this turns into 0.factorial_cps(k0), that k0 is an interesting collection of closures (whose details we'll study a bit later) which we have to apply the continuation in order to complete the computation. So returning a value means applying the continuation to that return value.

Invoking the base case from the top level, 0.factorial_cps, yields the right result: 1. k will be bound to { |v| v } by default, and we get the right result when that's called on the return value:

lambda { |v| v }.call(1)

Third, we consider the general case (which happens to be recursive). This is where the CPS transformation is a bit more interesting. I am assuming that primitive operations, like integer subtraction, are free; that is, they don't need to be transformed into CPS. (This could be a huge assumption in Ruby and perhaps implementation dependent. I may return to this issue in another blog entry.)

However, why do I do the subtraction self-1 outside the continuation but do the multiplication self * v in the continuation? It's all relative to the function call. The subtraction must be done before the function call; the multiplication is coded to happen after the function call. Recall that a continuation is supposed to encode the computations that happen after a function call.

The continuation will receive, as a parameter, the result of the function call, and we'll call that result v ("v" for "value"). Based on the original code, we know that this result is multiplied by self, so self * v is our starting point for the new continuation. However, this general case was already given a continuation. More than likely, for this method, it's a bunch of other multiplications, but it really doesn't matter. What does matter (and the "other multiplication" view inspires this) is that we have to use it.

Recall the lesson learned from the base case: whatever we return must be fed to the continuation. So, we feed self * v to the continuation that we were given: k.call(self * v).

I think some computational pictures might help. Consider first this sequence of method calls:

5.factorial
5 * 4.factorial
5 * 4 * 3.factorial
5 * 4 * 3 * 2.factorial
5 * 4 * 3 * 2 * 1.factorial
5 * 4 * 3 * 2 * 1 * 0.factorial
5 * 4 * 3 * 2 * 1 * 1

Boldface represents computation saved implicitly on the runtime stack. Contrast this with the CPS version:

5.factorial_cps
4.factorial_cps({5 * v})
3.factorial_cps({5 * v}.call({4 * v}))
2.factorial_cps({5 * v}.call({4 * v}.call({3 * v})))
1.factorial_cps({5 * v}.call({4 * v}.call({3 * v}.call({2 * v}))))
0.factorial_cps({5 * v}.call({4 * v}.call({3 * v}.call({2 * v}.call{1 * v})))))
{5 * v}.call({4 * v}.call({3 * v}.call({2 * v}.call{1 * v}.call(1)))))))

The continuations are greatly simplified. First of all, I inlined them all (so that there weren't multiple ks floating about). Second, I dropped the lambda keyword and the |v| declaration (and that prevents these lines from being valid Ruby). Third, I ignored the identity continuation (which would be tacked on at the front of the continuation chain).

At this point, if this is the first time you're seeing CPS, your head is probably ready to explode. Even if you've seen it, then you're wondering why anyone would ever use it—it appears to be more work and seems more expensive. Read some of the resources that I've linked to, and come at this material from multiple angles. Then come back here for some more of my blogging.