In Joy and Sorrow with Continuations

Continuations is one of those topics that tend to crop up now and again. This is not strange, of course, since they happen to be one of the more powerful features of certain languages, but also is one of the most confusing one. I would like to stick my head out and say that continuations are probably up there besides real macros in power. The reason for this is that you can implement so many language features in terms of them.

Since there still seem to be some confusion about them, I'll write my piece on the. Not just for you readers of course, but more importantly for myself. I intend to get a good grip on continuations in Ruby by writing this (and this is incidentally one of the best ways to learn about something confusing; try to write about).

First of all, exactly what is a continuation? Basically, at every point in the evaluation of an expression, there will be one or more continuations lurking. For example, if we take the very simple expression foo = 13 * (10 - 7). In this place there is 4 interesting continuations waiting. (There are actually 8 of them all in all, but only 4 interesting.) We start by looking at the expression 10 - 7. If we look at the rest of the expression like this: foo = 13 * [] where the square brackets is the place where the result of the expression 10 - 7 will go. What's actually happening is that those square brackets is the continuation of the complete expression. The result of evaluating 10 - 7 will be injected into the rest of the expression, and that is what the continuation is.

Until now, I have spoken about continuations as a concept. Those of you who know the Ruby interpreter knows that it isn't coded in continuation-passing style. But it could be, and it doesn't really matter, since we still have a way to get at the current continuation. So, how should a continuation be represented, though? The way most languages choose to do it, a continuation is nothing but an anonymous closure, which takes one parameter, which is the result to return to the evaluation. In the example above, if we inject the callcc-primitive into the mix, we will have code that looks like this:

foo = 13 * callcc {|c| c.call(10-7) }

His doesn't really look that spectacular, of course. The above code will have exactly the same effect as the first example, namely binding the variable 'foo' with the value 39.

If you want to, you can look at every computation like this. It sometimes helps to imagine that you just wring the evaluation inside out.

So. What can you do with them? Mostly anything, actually. Many parts of Scheme is implemented in CPS (continuation passing style). But for a few concrete things that can be implemented easily: exceptions, throw/catches, breaks, returns, coroutines, generators and much more. As an example, we can implement a return like this:

 def val
  callcc do |ret|
    1000.times do |v|
      if v == 13
        ret.call(v+1)
      end
    end 
  end
end
bar = val
puts bar

What happens here is exactly the same result as if we had used the keyword return. Most of the other flow control primitives can be implemented this way too.

What has made continuations trendy lately is something called continuation web servers. The idea is to make the statelessness of the web totally transparent by hiding the client round trips inside methods, and these methods save the current continuation, and then breaks of evaluation. When the result from the server arrives, the continuation will be looked up from some session storage, and then restarted again, where it was. Basically, this allows web applications to work more or less exactly the same as a console application. This is very powerful, but as I hope this small post have shown, continuations have much more to give.