Continuations

A contin­u­a­tion is a special kind of func­tion that’s like a book­mark to the loca­tion of an expres­sion. Contin­u­a­tions let you jump back to an earlier point in the program, thereby circum­venting the control flow of the usual eval­u­a­tion model. Like macros, they’re not a tool of first resort. But they have a niche.

When you invoke a contin­u­a­tion, it sends you back to the point in the program where the book­marked expres­sion was eval­u­ated. The contin­u­a­tion takes one argu­ment, which replaces the value of the book­marked expres­sion. Eval­u­a­tion resumes from there.

Consider this math expres­sion:

Suppose we want to capture a contin­u­a­tion at the 4. To do this, we wrap it in let/cc:

let/cc does three things:

What will be the value of (c 20)? When we invoke our contin­u­a­tion c with an argu­ment, it’s equiv­a­lent to replacing the result of the book­marked expres­sion with the argu­ment:

Since a contin­u­a­tion is a func­tion, another way of visu­al­izing how it works is to think of let/cc turning its surrounding expres­sion into a func­tion of x, where x is the former loca­tion of the let/cc expres­sion:

Now a weirder example. What happens if we imme­di­ately invoke the here contin­u­a­tion instead of saving it for later?

We haven’t changed the posi­tion of let/cc, so the contin­u­a­tion here is the same as c in the last example. Thus (here 20) is the same as (c 20), and the result is still 31.

For those who find it strange that invoking the contin­u­a­tion short-circuits the usual order of eval­u­a­tion—right. That’s the point.

Run-time travel

When we use let/cc, the contin­u­a­tion is not (and cannot be) captured until the program actu­ally reaches the let/cc expres­sion. This means that a contin­u­a­tion is strictly a run-time concept. More­over, it captures all the run-time context that applies to the surrounding expres­sion at that point.

Consis­tent with their name, contin­u­a­tions are some­times described as repre­senting “the remaining steps in the compu­ta­tion”. True, but we shouldn’t apply this idea rigidly, as it can lead to faulty intu­itions.

For example, let’s rewrite our previous example as a for/sum loop, which iter­ates over i and returns the sum of its values (in this case 1 to 5). Once again, we’ll use let/cc to capture the contin­u­a­tion when i is 4:

What happens with (c 20) this time? The faulty intu­ition would be that invoking the contin­u­a­tion sends 20 back into the loop when i is 4, so the result is (+ 20 5), or 25, because those are the “remaining steps in the compu­ta­tion”.

But that’s not what happens. The contin­u­a­tion captures every­thing about the run-time context of the surrounding for/sum expres­sion—not just the eval­u­a­tion steps that need to be completed, but the ones that have already been completed, including the values of i that have already been visited. So the result is still 31:

Again, if we think of let/cc turning its surrounding expres­sion into a func­tion of x, it’s clear why 31 is the answer:

What are they good for?

When you need to jump back to an earlier point in your program, a contin­u­a­tion can be the right tool for the job. For instance, errors and excep­tions are imple­mented with contin­u­a­tions, as they allow control to jump from inside an expres­sion to the nearest enclosing with-handlers form.

Along those lines, though Racket has no return state­ment, it can be imple­mented with a contin­u­a­tion:

We can gener­alize this into a define/return macro that adds return to any func­tion:  + Of course, there are better ways to stop a loop. See loops. There are also better ways to write a define macro. See normalize-definition.

More broadly, any algo­rithm that relies on back­tracking—e.g., search, pathfinding, constraint satis­fac­tion, type­set­ting—can work with contin­u­a­tions, because they can be used to set return points. Func­tions that can be suspended and resumed, like gener­a­tors and certain web appli­ca­tions, can also be built with contin­u­a­tions. So can subrou­tines & loops for BASIC.

“So a contin­u­a­tion is just goto in disguise?”

Not quite. The goto state­ment in a language like BASIC lets us jump to an arbi­trary point in the program:

A goto can move anywhere in the program because the possible desti­na­tions are known at compile time. A contin­u­a­tion, by contrast, needs the current eval­u­a­tion context, which is only known at run time. In that sense, a contin­u­a­tion is less flex­ible: it can only repre­sent a loca­tion in the program that’s already been visited. Thus, when you invoke a contin­u­a­tion, you can only travel back­ward, not forward.

Further