Continuations in Scheme

The only way to create a continuation object in Scheme is to use call-with-current-continuation or call/cc for short. This is a function built right into Scheme. What it does is to take a snapshot of the current state of the program and wrap it in a continuation object. The argument of call/cc must be a function f that takes one argument. call/cc calls f with the continuation object it has created. We now effectively have two continuations, as illustrated in the figure below:

• One continuation is the "normal" progression of the program. Since we just called f, this continuation starts by executing f and all the functions that f itself calls. At some point f returns and the program continues from the point where we called f using call/cc. We don't have an explicit value that represents this continuation, but it is what happens if we just run our program normally.

• The other continuation is the one captured by the continuation object created by call/cc and passed to f. This continuation captures the computation starting from the point after we invoke call/cc, that is, the same part of the program that gets executed after f returns in the "normal" continuation.

Now f has two choices: It can just run to completion without ever doing anything with the continuation object it was given. This leads to the normal progression as if we had made an ordinary function call. The other choice is to call the continuation it was given. In that case, f aborts and the computation continues immediately after call/cc. The following figure illustrates this.

In this example, (f) uses call/cc to call g. The red continuation is the future of the computation after (call/cc g) returns. This is the continuation that call/cc passes to g as an argument, that is, it is the continuation that gets bound to g's parameter k. (g k) performs some computation until it decides whether to invoke k or not. If it doesn't, the blue continuation is the future of the computation still to be executed. This may include some steps that g executes before it returns; g may even call other functions recursively; then g returns, and the computation continues after the call (call/cc g), that is, the remainder of the blue continuation is the same as the red continuation. If g does invoke k, this abandons the blue continuation and make (call/cc g) return immediately, as indicated by the red dashed arrow. In effect, the blue continuation gets replaced with the red one.

In this figure, this choice between having g return early or not could have been implemented with an ordinary return statement. However, g may choose to pass the continuation k on to other functions it calls. If any of those functions invokes k, then once again, (call/cc g) returns immediately; the red continuation becomes the future of the computation. This cannot be achieved using only return statements because any function called by g returns to g, not to f.

In effect, we can think about calling a continuation as a glorified goto statement. Since deep down, at assembly level, all programs are composed of function calls and goto statements, it shouldn't come as a surprise that continuations as first-class objects are an extremely powerful tool that allows us to build many different abstractions by hand. Let's look at a few examples.