Go to the first, previous, next, last section, table of contents.

call-with-current-continuation

call-with-current-continuation is a very powerful control construct, which can be used to create more conventional control constructs, like catch and throw in Lisp (or setjmp and longjmp in C), or coroutines, and many more. It is extremely powerful because it allows a program to manipulate its own control "stack" so that procedure calls and returns needn't follow the normal depth-first textual call ordering.

Recall that we said [ WHERE? ] that Scheme's equivalent of an activation stack is really a chain of partial continuations (suspension records), and this chain is known as a full continuation. And since continuations are immutable, they usually form a tree reflecting the call graph (actually, only the non-tail calls). Normally, the parts of this tree that are not in the current continuation chain are garbage, and can be garbage collected.

If you take a pointer to the current continuation, and put it in a live variable or data structure, however, then that continuation chain will remain live and not be garbage collected. That is, you can "capture" the current state of the stack.

If you keep a captured state of the stack around, and later install the pointer to it in the system's continuation register, then you can return through that continuation chain, just as though it were a normal continuation. That is, rather than returning to your caller in the normal way, you can take some old saved continuation and return into that instead!

You might wonder why anybody would want to do such a weird thing to their "stack," but there are some useful applications. One is coroutines. It is often convenient to structure a computation as an alternation between two different processes, perhaps one that produces items and another that consumes them. It may not be convenient to either of those processes into a subroutine that can be called once to get an item, because each process may have complex state encoded into its control structure.

(You probably wouldn't want to have to structure your program as a bunch of incremental operations that were called by successive calls to a do-next-increment routine. It may be that the program it gets its data from can't easily be structured that way, either. Each program should probably be written with its own natural control structure, each suspending its operation when it needs the other to do its thing.)

Coroutines allow you to structure cooperating subprograms this way, without making one subservient to (and callable piecemeal from) another.

Coroutines can be implmemented as operations on continuations. When a coroutine wants to suspend itself and activate another (co-)routine, it simply pushes a partial continuation to save its state, then captures the value of the continuation register in some way, so that it can be restored later. To resume a suspended routine, the continuation chain is restored and the top partial continuation is popped into the system state registers. Alternation between coroutines is thus accomplished by saving and restoring the routines' continuations.

Note that in this case, we can have two (or more) trees of continuations that represent the course of the computation, and that control flow can alternate back and forth between trees. Usually, computations are structured so that most of the work is done in the usual depth-first procedure calling and returning, with occasional jumps from one routine's depth-first activity to another's.

Another use of continuations is to implement catch and throw, which are roughly like setjmp and longjmp in C. The idea is that you may want to abort a computation without going through the normal nested procedure returns. In a normal stack-based lagnuage (without continuations), this is usually accomplished by storing a pointer into the stack before starting the abortable computation. If it is necessary to abort the computation, all of the activation records above the point of call can be ignored, and the stack pointer can be restored to that point, just as though all of the invocations above it had returned normally.

This can be implemented with call-with-current-continuation by saving the continuation at the point where an abortable computation is begun. Anywhere within that computation, that continuation may be restored (clobbering the "normal" value of the continuation register, etc.) to resume from that point.

But call-with-current-continuation is more powerful than coroutines or catch and throw. Not only can we escape "downward" from a computation (by popping multiple partial continuatons at once without actually returning through them), we can also escape "upwards" back into a computation that we bailed out of before. This can be useful in implementing exception handling, where we may want to transfer control to a special coroutine that may "fix up" an error that was detected, but then resume the procedure that encountered the error, after the problem is fixed.

call-with-current-continuation can also be used to implement backtracking, where the control flow backs up and re-executes from some saved continuation. In this case, we may save the continuation for some computation, but go ahead and return through it normally. Later, we may restore the saved continuation and return through it again.

Note that in general, continuations in Scheme can be used multiple times. The essential idea is that rather than using a stack, which dictates a depth-first call graph, Scheme allows you to view the call graph AS A GRAPH, which may contain cycles, even directed cycles (which represent bactracking).

The syntax of call-with-current-continuation is fairly ugly, but for some good reasons; in its raw form, it is very powerful, but correspondingly hard to use. Typically, it is encapsulated in macros or other procedures to implement other, higher-level control constructs.

call-with-current-continuation is itself a normal first-class procedure, which encapsulates the very low-level continuation munging abilities in something like a civilized package. Since it's a first-class procedure, you can write higher-order procedures that treat it like data, or call it, or both.

call-with-current-continuation is a procedure of exactly one argument, which is another procedure to execute after the current continuation has been captured. The current continuation will be passed to that procedure, which can use it (or not) as it pleases.

The captured continuation is itself packaged up as a procedure, also of one argument. That's so that you can't muck around with the continuation itself in any data-structure-like way. There are only two things you can do with captured continuations--capture them and resume them. Continuations are captured by executing call-with-current-continuation, which creates an escape procedure. They are resumed by calling the escape procedure. When called, the escape procedure abandons whatever computation is going on, restores the saved continuation, and resumes executing the saved computation at the point where call-with-current-continuation occurred.

Note that call-with-current-continuation is a procedure of one argument. We'll call that procedure the abortable procedure. The abortable procedure must also be a procedure of exactly one argument. (If you want to call a procedure that takes a bunch of arguments, and still make it abortable using call-with-current-continuation, you have to use a trick I'll describe below.)

The abortable procedure's argument is the escape procedure that encapsulates the captured continuation.

call-with-current-continuation does the following:

If and when the escape procedure is called, it restores the continuation captured at the point of call to call-with-current-continuation. We refer to this as a nonlocal return---from the point of view of the caller of call-with-current-continuation, it looks as though call-with-current-continuation had returned normally.

The (abortable) procedure we want to call must take one argument, which is the escape procedure that can resume the computation just beyond the call to call-with-current-continuation.

As if this weren't cryptic enough, the escape procedure is also a procedure of exactly one argument. When the escape procedure is used to perform a nonlocal return, it returns a value as the result of the call to call-with-current-continuation.

The argument to the escape procedure is the value that will be returned as the value of the call. Note that if the escape procedure is not called, and the abortable procedure returns normally, the value it returns is returned as the value of the call to call-with-current-continuation.

A call to call-with-current-continuation therefore can return in two ways. Either the abortable procedure returns normally, and call-with-current-continuation simply returns that value, or the escape procedure can be called, and its argument is returned as the value of the call to call-with-current-continuation.

Consider the following example, where I've given line numbers to refer to later:

 0: (define some-flag #f)

 1: (define (my-abortable-proc escape-proc)
 2:   (display "in my-abortable-proc")
 3:   (if some-flag
 4:       (escape-proc "ABORTED"))
 5:   (display "still in my-abortable-proc")
 6:   "NOT ABORTED")

 7: (define (my-resumable-proc)
 8:   (do-something)
 9:   (display (call-with-current-continuation my-abortable-proc))
10:   (do-some-more))

11: (my-resumable-procedure)

At line 11, we call my-resumable-procedure. It calls do-something, and then calls display. But before it calls display it has to evaluate its argument, which is the call to call-with-current-continuation.

call-with-current-continuation saves the continuation at that point, and packages it up as an escape procedure. (Line 9) The escape procedure, if called, will return its argument as the value of the call-with-current-continuation form.

That is, if the escape procedure is called, it will resume execution of the display procedure, which prints that value, and then execution will continue, calling do-some-more.

Once call-with-current-continuation has created the escape procedure, it calls its argument, my-abortable-proc, with the escape procedure as its argument.

my-abortable-proc then displays (prints) "in my-abortable-proc." Then it checks some-flag, which is false, and does not execute the consequent of the if---that is, it doesn't execute the escape procedure. It continues executing, displaying "still inmy-abortable-proc." It then evaluates its last body form, the string "NOT ABORTED", which evaluates to itself, and returns that as the normal return value of the procedure call.

At this point, the value returned from my-abortable-proc is printed by the call to display in line 9.

But suppose we set some-flag to #t, instead of #f.

Then when control reaches line 3, the if does evaluate its consequent. This calls the escape procedure, handing it the string "ABORTED" as its argument. The escape procedure resumes the captured continuation, returning control to the caller of call-with-current-continuation, without executing lines 5 and 6.

The escape procedure returns its argument, the string "ABORTED" as the value of the call-with-current-continuation form. It restores the execution of my-resumable-proc at line 9, handing display the string "ABORTED" (as the value of its argument form). At this point "ABORTED" is displayed, and execution continues at line 10.

Often we want to use call-with-current-continuation to call some procedure that takes arguments other than an escape procedure. For example, we might have a procedure that takes two arguments besides the escape procedure, thus:

(define (foo x y escape)
   ...
   (if (= x 0)
       (escape 'ERROR))
   ...))

We can fix this by currying the procedure, making it a procedure of one argument.

[ An earlier chapter should have a discussion of currying! ]

Suppose we want to pass 0 and 1 as the values of x and y, as well as handing foo the escape procedure. Rather than saying

   (call-with-current-continuation foo)

which doesn't pass enough arguments to the call to foo, we say

   (call-with-current-continuation (lambda (escape) (foo 0 1 escape)))

The lambda expression creates a closure that does exactly what we want. It will call foo with arguments 0, 1, and the escape procedure created by call-with-current-continuation.

Implementing a Better Read-Eval-Print Loop

Implementing Catch and Throw

Implementing Backtracking

Implementing Coroutines

Implementing Cooperative Multitasking

Caveats about call-with-current-continuation


Go to the first, previous, next, last section, table of contents.