((lambda (k2)
(web-read/k ”First number: ” k2))
(lambda (l-val)
((lambda (k3)
(web-read/k ”Second number: ” k3))
(lambda (r-val)
(k1 (+ l-val r-val)))))))
This may look rather more complicated than we are used to. However, we merely need to perform the inner
procedure applications, substituting the known receivers for k2 and k3. Doing this yields:
(lambda (k1)
(web-read/k ”First number: ”
(lambda (l-val)
(web-read/k ”Second number: ”
(lambda (r-val)
(k1 (+ l-val r-val)))))))
which is exactly what we expect!
18.3. TESTING
175
The Fischer CPS Transformation
The CPS transformer we have studied here is one of the very oldest, due to Michael Fischer. In
the three decades since Fischer defined this transformation, there has been considerable research
into building a better CPS transformation. Why? This version, while easy to understand, introduces
a considerable amount of overhead: look at all the procedures in the output that weren’t in the
source program! In principle, we would like a transformer that approximates the cleanliness of
hand-translation: this would be useful both to humans who must read the output and to programs
that must process it. This is what the better transformers strive to achieve.
18.3
Testing
The code in Figure 18.1 also defines define-cps so you can write top-level definitions that are translated into CPS. Thus, you can write the following program, reminiscent of the cascading transformation we discussed
in Section 17.6:
(define-cps (g x) (+ x x))
(define-cps (h f ) (lambda (x) (f x)))
(define-cps (dummy x) ((h g) 10))
It also defines the run construct, which is useful for testing code converted to CPS. You can use it to execute
(run (dummy 1729))
and observe the computation terminate with the value 20.
Exercise 18.3.1 Suppose, instead, the CPS rule for a procedure were
[(cps (lambda (a) body))
(lambda (k)
(k (lambda (a dyn-k)
((cps body) k))))]
i.e., the transformed procedure ignored the dynamic receiver and used the static one instead. What impact
would this have on program behavior? Predict, then run and check!
176
CHAPTER 18. CONVERSION INTO CONTINUATION-PASSING STYLE
(define-syntax define-cps
(syntax-rules ()
[(define-cps (f arg) body)
(define-cps f (lambda (arg) body))]
[(define-cps v val)
(define v ((cps val) (lambda (x) x)))]))
(define-syntax cps
(syntax-rules (+ lambda web-read)
[(cps (+ e1 e2))
(lambda (k)
((cps e1) (lambda (l-val)
((cps e2) (lambda (r-val)
(k (+ l-val r-val)))))))]
[(cps (lambda (a) body))
(lambda (k)
(k (lambda (a dyn-k)
((cps body) dyn-k))))]
[(cps (web-read prompt))
(lambda (k)
(web-read/k prompt k))]
[(cps (f a))
(lambda (k)
((cps f ) (lambda (f-val)
((cps a) (lambda (a-val)
(f-val a-val k))))))]
[(cps v)
(lambda (k) (k v))]))
(define-syntax run
(syntax-rules ()
[(run e) ((cps e)
(lambda (x)
(error ”terminating with value” x)))]))
Figure 18.1: Implementation of CPS Converter
Chapter 19
Programming with Continuations
For this material, please switch to the PLAI - Pretty Big language level.
In Section 18 we saw how conversion to CPS restores the Web programming interface we desire: pro-
grammers can use web-read and not have to “invert” the structure of the program. While in principle this
accomplishes the task, in practice conversion to CPS has several disadvantages:
1. It requires access to the source of the entire program. If a procedure is defined in a library for which
we don’t have access to the source, or is perhaps written in a different language (as map often is), then
the CPS translator will either fail to run or will produce potentially erroneous output (i.e., code that
does not properly restore the state of the computation).
2. By replacing the machine’s stack with an explicit representation in the form of receivers, it inhibits
optimizations built into compilers and microprocessor architectures.
3. As we will see in Section 20.4, executing a program in CPS also assumes that the run-time system
will not needlessly create stack frames (since the stack is entirely represented by the receiver). Since
many languages (such as C and Java) do anyway, the program consumes memory unnecessarily. In
an extreme case, a Java or C program that would have executed without exhausting memory will run
out of memory after conversion into CPS.
The first of these problems is particularly compelling, since it affects not only performance but even cor-
rectness. We would benefit from an operation that automatically constructs the receiver at any point during
the program’s execution, instead of expecting it to have already been created through a static compilation
process.
Some programming languages, notably Scheme, have such an operation. This operation creates a rep-
resentation of the “rest of the computation” (which is what the receiver represented) as a procedure of one
argument. Giving that procedure a value causes the remaining computation to resume with that value. This
procedure is called a continuation. This explains where CPS obtains its name, but note that the program does
not need to be transformed a priori; the continuation is created automatically and on-the-fly. As you might
imagine, creating (or “capturing”) a continuation simply involves copying the stack, though there are less
and more efficient ways of obtaining the same effect.
177
178
CHAPTER 19. PROGRAMMING WITH CONTINUATIONS
Adding continuations to a language makes it easy to create a better Web programming protocol, as we
shall see. But just as laziness—which was already present in the shell but was essentially an extra-lingual
feature (since programmers could not explicitly control it)—, once exposed as a feature in a programming
language, gave programmers immense power in numerous contexts, so do continuations. We will explore
this power in greater detail.
19.1
Capturing Continuations
In Scheme, we create a value representing the continuation using one of two related constructs. The tradi-
tional form is called call/cc, short for “call with current continuation”. call/cc consumes a procedure as an
argument, and invokes this procedure with a continuation. That is, uses of call/cc typically look like
(call/cc
(lambda (k)
· · · k · · ·))
;; k is the continuation
Because the extra lambda is extremely tiresome, however, Scheme provides a nicer interface to capturing
the current continuation: you may instead equivalently write
(let/cc k
· · · k · · ·))
;; k is bound to the continuation
Note that let/cc is a binding construct: it introduces a new scope, binding the named identifier (k, above) in
that context. For the rest of this material, we’ll use let/cc rather than call/cc.1
19.2
Escapers
Let’s write some programs using continuations. What is the value of this program?
(let/cc k
(k 3))
We must first determine the continuation bound to k. This is the same procedure as the value of the receiver
in CPS. Since in this case, there is no computation waiting to be done outside the let/cc expression, the
receiver would be the initial receiver, namely the identity function. Therefore, this receiver is
(lambda (•)
•)
Applying this to 3 produces the answer 3.
Consider this program:
(+ 1
(let/cc k
1So why does Scheme offer call/cc, ghastly as it looks? Historically, the original standards writers were loath to add new binding
forms, and the use of lambda meant they didn’t need to create one. Also, call/cc lets us create some incredibly clever programming
puzzles that we can’t write quite as nicely with let/cc alone! Ask us for some.
19.3. EXCEPTIONS
179
(k 3)))
What is the continuation this time? It’s
(lambda (•)
(+ 1 •))
(all the code “outside the parens”). This procedure, when invoked, yields the value 4. Because the contin-
uation is the rest of the computation, we want to halt with the value 4. But this looks confusing, because
substitution gives
(+ 1
(k 3)) ;; where k is bound to (lambda (•) (+ 1 •))
= (+ 1
((lambda (•)
(+ 1 •))
3))
= (+ 1
(+ 1 3))
which performs the addition twice, producing the answer 5. The problem is that we’re effectively applying
the continuation twice, whereas computation should halt after it has been applied once. We will use a special
notation to reflect this: lambda↑ will represent a procedure that, when its body finishes computing, halts
the entire computation. We’ll call these escaper procedures, for obvious reasons. That is, the continuation
is really
(lambda↑ (•)
(+ 1 •))
so the expression
(+ 1
((lambda↑ (•)
(+ 1 •))
3))
evaluates to 4, with the outermost addition ignored (because we invoked an escaper).
19.3
Exceptions
Let’s consider a similar, but slightly more involved, example. Suppose we are deep in the midst of a com-
putation when we realize we are about to divide by zero. At that point, we realize that we want the value of
the entire expression to be one. We can use continuations to represent this pattern of code:
(define (f n)
(+ 10
(∗ 5
(let/cc k
180
CHAPTER 19. PROGRAMMING WITH CONTINUATIONS
(/ 1 n)))))
(+ 3 (f 0))
The continuation bound to k is
(lambda↑ (•)
(+ 3
(+ 10
(∗ 5
•))))
but oops, we’re about to divide by zero! Instead, we want the entire division expression to evaluate to one.
Here’s how we can do it:
(define (f n)
(+ 10
(∗ 5
(let/cc k
(/ 1 (if (zero? n)
(k 1)
n))))))
so that • in the continuation is substituted with 1, we bypass the division entirely, and the program can
continue to evaluate.
Have you seen such a pattern of programming before? But of course: k here is acting as an exception
handler, and the invocation of k is raising the exception. A better name for k might be esc:
(define (f n)
(+ 10
(∗ 5
(let/cc esc
(/ 1 (if (zero? n)
(esc 1)
n))))))
which makes pretty clear what’s happening: when you invoke the continuation, it’s as if the entire let/cc
expression that binds esc should be cut out of the program and replaced with the value passed to esc, i.e., its
as if the actual code for f is really this:
(define (f n)
(+ 10
(∗ 5
1)))
In general, this “cut-and-paste” semantics for continuations is the simplest way (in conjunction with escaper
procedures) of understanding a program that uses continuations.
There was, incidentally, something sneaky about the program above: it featured an expression in the
body of a let/cc that did not invoke the continuation. That is, if you can be sure the user of f will never pass
an argument of 0, it’s as if the body of the procedure is really
19.4. WEB PROGRAMMING
181
(define (f n)
(+ 10
(∗ 5
(let/cc esc
(/ 1 n)))))
but we haven’t talked about what happens in programs that don’t invoke the continuation. In fact, that’s
quite easy: the value of the entire let/cc expression is exactly that of the value of its body, just as when you
don’t actually raise an exception.
19.4
Web Programming
Now that we’re getting a handle on continuations, it’s easy to see how they apply to the Web. We no longer
need the procedure web-read/k; now, web-read can be implemented directly to do the same thing that web-
read/k was expected to do. web-read captures the current continuation, which corresponds to the second
argument supplied to web-read/k (except the continuation is now captured automatically, instead of having
to be supplied as an explicit second argument).
The rest of the implementation is just as before: it stores the continuation in a fresh hash table entry,
and generates a URL containing that hash table entry’s key. The launcher extracts the continuation from the
hash table and applies it to the user’s input. As a result, all the programs we have written using web-read
are now directly executable, without the need for the CPS transformation.
19.5
Producers and Consumers
A number of programs follow a producer-consumer metaphor: one process generates (possibly an infinite
number of) values, while another consumes them as it needs new ones. We saw several examples of this
form in Haskell, for instance. Many client-server programs are like this. Web programs have this form (we,
the user, are the supplier of inputs—and on some Web sites, the number really does seem quite close to
infinite . . . ). I/O, in general, works this way. So it’s worth understanding these processes at a deeper level.
To avoid wrangling with the complexities of these APIs, we’ll reduce this to a simpler problem. We’d
like to define a producer of symbols (representing a sequence of cities to visit) that takes one argument,
send, which masks the details of the API, and sends a sequence of city names on demand:
(define (route-producer send)
(begin
(send ’providence)
(send ’houston)
(send ’bangalore)))
That is, when we first invoke route-producer, it invokes send with the value ’providence—and halts. When
we invoke it again, it sends ’houston. The third time we invoke it, it sends the value ’bangalore. (For now,
let’s not worry about what happens if we invoke it additional times.)
What do we supply as a parameter to elicit this behavior? Clearly, we can’t simply supply an argument
such as (lambda (x) x). This would cause all three send operations to happen in succession, returning the
182
CHAPTER 19. PROGRAMMING WITH CONTINUATIONS
value of the third one, namely ’bangalore. Not only is this the wrong value on the first invocation, it also
produces the same answer no matter how many times we invoke route-producer—no good.
In fact, if we want to somehow suspend the computation, it’s clear we need one of these exception-like
operations so that the computation halts prematurely. So a simple thing to try would be this:
(let/cc k (route-producer k))
What does this do? The continuation bound to k is
(lambda↑ (•) •)
Substituting it in the body results in the following program:
(begin
((lambda↑ (•) •)
’providence)
((lambda↑ (•) •)
’houston)
((lambda↑ (•) •)
’bangalore))
(all we’ve done is substitute send three times). When we evaluate the first escaper, the entire computation
reduces to ’providence—and computation halts! In other words, we see the following interaction:
> (let/cc k (route-producer k))
’providence
This is great—we’ve managed to get the program to suspend after the first send! So let’s try doing this a
few more times:
> (let/cc k (route-producer k))
’providence
> (let/cc k (route-producer k))
’providence
> (let/cc k (route-producer k))
’providence
Hmm—that should dampen our euphoria a little.
What’s the problem? We really want route-producer to “remember” where it was when it sent a value
so it can send us the next value when we invoke it again. But to resume, we must first capture a snapshot of
our computation before we sent a value. That sounds familiar. . . .
Going back to route-producer, let’s think about what the continuation is at the point of invoking send
the first time. The continuation is
(lambda↑ (•)
(begin
•
(send ’houston)
(send ’bangalore)))
19.5. PRODUCERS AND CONSUMERS
183
(with send substituted appropriately). Well, this looks promising! If we could somehow hang on to this
continuation, we could use it to resume the producer by sending ’houston, and so forth.
To hang on to the computation, we need to store it somewhere (say in a box), and invoke it when we run
the procedure the next time. What is the initial value to place in the box? Well, initially we don’t know what
the continuation is going to be, and anyway we don’t need to worry because we know how to get a value out
the first time (we just saw how, above). So we’ll make the box initially contain a flag value, such as false.
Examining what’s in the box will let us decide whether we’re coming through the first time or not. If we are
we proceed as before, otherwise we need to capture continuations and what-not.
Based on this, we can already tell that the procedure is going to look roughly like this:
(define route-producer
(local ([define resume (box false)])
(lambda (send)
(if (unbox resume)
;; then
there’s a continuation present—do something!
;; else
(begin
(send ’providence)
(send ’houston)
(send ’bangalore)))))))
where the box bound to resume stores the continuation. Note that resume is outside the lambda but in its
scope, so the identifier is defined only once and all invocations of the procedure share it.
If (unbox resume) doesn’t evaluate to false,2 that means the box contains a continuation. What can we
do with continuations? Well, really only one thing: invoke them. So we must have something like this if the
test succeeds:
((unbox resume) · · ·)
But what is that continuation? It’s one that goes into the midst of the begin (recall we wrote it down above).
Since we really don’t care about the value, we may as well pass the continuation some kind of dummy value.
Better to pass something like ’dummy, which can’t be confused for the name of a city. So the procedure
now looks like
(define route-producer
(local ([define resume (box false)])
(lambda (send)
(if (unbox resume)
((unbox resume) ’dummy)
(begin
(send ’providence)
(send ’houston)
(send ’bangalore))))))
2In Scheme, only false fails a conditional test; all other values succeed.
184
CHAPTER 19. PROGRAMMING WITH CONTINUATIONS
Of course, we haven’t actually done any of the hard work yet. Recall that we said we want to capture
the continuation of send, but because send is given as a parameter by the user, we can’t be sure it’ll do the
right thing. Instead, we’ll locally define a version of send that does the right thing. That is, we’ll rename the
send given by the user to real-send, and define a send of our own that invokes real-send.
What does our send need to do? Obviously it needs to capture its continuation. Thus:
(define route-producer
(local ([define resume (box false)])
(lambda (real-send)
(local ([define send (lambda (value-to-send)
(let/cc k
· · ·))])
(if (unbox resume)
((unbox resume) ’dummy)
(begin
(send ’providence)
(send ’houston)
(send ’bangalore)))))))
What do we do with k? It’s the continuation that we want to store in resume:
(set-box! resume k)
But we also want to pass a value off to real-send:
(real-send value-to-send)
So we just want to do this in sequence (observe that we can’t do these in the other order):
(begin
(set-box! resume k)
(real-send value-to-send))
When the client next invokes route-producer, the continuation stored in the box bound to resume is that of
invoking (our locally defined) send within the body. . . which is exactly where we want to resume computa-
tion! Here’s our entire procedure:
(define route-producer
(local ([define resume (box false)])
(lambda (real-send)
(local ([define send (lambda (value-to-send)
(let/cc k
(begin
(set-box! resume k)
(real-send value-to-send))))])
(if (unbox resume)
((unbox resume) ’dummy)
(begin
19.5. PRODUCERS AND CONSUMERS
185
(send ’providence)
(send ’houston)
(send ’bangalore)))))))
Here’s the interaction we wanted:3
> (let/cc k (route-producer k))
’providence
> (let/cc k (route-producer k))
’houston
> (let/cc k (route-producer k))
’bangalore
It’s a bit unwieldy to keep writing these let/ccs, so we can make our lives easier as follows:
(define (get producer)
(let/cc k (producer k)))
(we could equivalently just define this as (define get call/cc)) so that
> (get route-producer)
’providence
> (get route-producer)
’houston
> (get route-producer)
’bangalore
Exercise 19.5.1 How would you define the same operators in Haskell?
Exercise 19.5.2 Before you read further: do you see the subtle bug lurking in the definitions above?
Hint: We would expect to be able to invoke (get route-producer) three times and combine the result into a
list.
3It’s critical that you work through the actual continuations by hand.
186
CHAPTER 19. PROGRAMMING WITH CONTINUATIONS
Continuations and “Goto” Statements
What we’re doing here has already gone far beyond the simple exception pattern we saw earlier.
There, we used continuations only to ignore partial computations. Now we’re doing something
much richer. We’re first executing part of a computation in a producer. At some point, we’re
binding a continuation and storing it in a persistent data structure. Then we switch to performing
some completely different computation (in this case, the top-level requests for the next city). At
this point, the partial computation of the producer has seemingly gone away, because we invoked
an escaper to return to the top-level. But by accessing the continuation in the data structure, we are
able to resume a prior computation: that is, we can not only jump “out”, as in exceptions, but we
can even jump back “in”! We do “jump back in” in the Web computations, but that’s a much tamer
form of resumption. What we’re doing here is resuming between two separate computations!
Some people compare continuations to “goto” statements, but we should think this through. Goto
statements can usually jump to an arbitrary line, which means they may continue execution with
nonsensical state (e.g., variables may not be properly initialized). In contrast, a continuation only
allows you to resume a computational state you have visited before. By being more controlled in
that sense, continuations avoid the worst perils of gotos.
On the other hand, continuations are far more powerful than typical goto statements. Usually, a
goto statement can only transfer control to a lexically proximate statement (due to how compilers
work). In contrast, a computation can represent any arbitrary prior computation and, irrespective of
lexical proximity, the programmer can resurrect this computation. In short, continuations are more
structured, yet much more powerful, than goto statements.
19.6
A B