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 executingf
and all the functions thatf
itself calls. At some pointf
returns and the program continues from the point where we calledf
usingcall/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 tof
. This continuation captures the computation starting from the point after we invokecall/cc
, that is, the same part of the program that gets executed afterf
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.