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:
call-with-current-continuation.
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.
call-with-current-continuation