Okay, so what receivers do they use? The computation they should invoke is the same computation that
was awaiting the result of evaluating the conditional. The receiver k represents exactly this computation.
Therefore, we can replace both sets of ellipses with k:
[if0 (test truth falsity)
(interp test env
(lambda (tv)
(if (num-zero? tv)
(interp truth env k)
(interp falsity env k))))]
That leaves only the rule for application. The first few lines of the transformed version will look familiar,
since we applied the same transformation in the case of addition:
[app (fun-expr arg-expr)
(interp fun-expr env
(lambda (fun-val)
(interp arg-expr env
(lambda (arg-val)
((closureV-p fun-val) arg-val) ))))]
All we have to determine is what to write in place of the box.
Is the code in the box still valid? Well, the reason we write interpreters is so that we can experiment!
How about we just try it on a few expressions and see what happens?
3Using our Web analogy, the question is which primitives might arguably invoke a Web interaction. Ones that use the Web must
be transformed and be given receivers to stash on the server, while ones that don’t can remain unmolested. Arithmetic, clearly,
computes entirely locally.
196
CHAPTER 20. IMPLEMENTING CONTINUATIONS
>
(interp-test ’5 5)
#t
> (interp-test ’{+ 5 5} 10)
#t
> (interp-test ’{with {x {+ 5 5}} {+ x x}} 20)
procedure interp: expects 3 arguments, given 2 ...
Oops! DrScheme highlights the interpretation of the body in the rule for fun.
Well, of course! The interpreter expects three arguments, and we’re supplying it only two. What should
the third argument be? It needs to be a receiver, but which one? In fact, it has to be whatever receiver is
active at the time of the procedure invocation. This is eerily reminiscent of the store: while the environment
stays static, we have to pass this extra value that reflects the current state of the dynamic computation. That
is, we really want the rule for functions to read
[fun (param body)
(k (closureV (lambda (arg-val dyn-k)
(interp body (aSub param arg-val env) dyn-k))))]
(What happens if we use k instead of dyn-k in the invocation of the interpreter? Try it and find out!)
Correspondingly, application becomes
[app (fun-expr arg-expr)
(interp fun-expr env
(lambda (fun-val)
(interp arg-expr env
(lambda (arg-val)
((closureV-p fun-val)
arg-val k)))))]
The core of the interpreter is in Figure 20.1.
What, incidentally, is the type of the interpreter? Obviously it now has one extra argument. More
interestingly, what is its return type? It used to return values, but now. . . it doesn’t return! That’s right:
whenever the interpreter has a value, it passes the value off to a receiver.
20.2
Adding Continuations to the Language
At this point, we have most of the machinery we need to add continuations explicitly as values in the
language. The receivers we have been implementing are quite similar to the actual continuations we need.
They appear to differ in two ways:
1. They capture what’s left to be done in the interpreter, not in the user’s program.
2. They are regular Scheme procedures, not lambda↑ procedures.
However,
20.2. ADDING CONTINUATIONS TO THE LANGUAGE
197
1. They capture what’s left to be done in the interpreter, not in the user’s program. Because the interpreter
closes over the expressions of the user’s program, invocations of the interpreter simulate the execution
of the user’s program. Therefore, the receivers effectively do capture the continuations of the user’s
program.
2. They are regular Scheme procedures, not lambda↑ procedures. We have taken care of this through
the judicious use of a programming pattern. Recall our discussion of the type of the revised inter-
preter? The interpreter never returns—thereby making sure that no computation awaits the value of
the receiver, which is effectively the same as computation terminating when the receiver is done.
In other words, we’ve very carefully set up the interpreter to truly represent the continuations, making it
easy to add continuations to the language.
Adding Continuations to Languages
Different languages take different approaches to adding continuations. Scheme’s is the most spar-
tan. It add just one primitive procedure, call/cc. The resulting continuations can be treated as if
they were procedures, so that procedure application does double duty. DrScheme slightly enriches
the language by also providing let/cc, which is a binding construct, but it continues to overload
procedure application.
The language SML uses callcc (which is not a binding construct) to capture continuations, and adds
a throw construct to invoke continuations. Consequently, in SML, procedure application invokes
only procedures, and throw invokes only continuations, making it possible for a type-checker to
distinguish between the two cases.
It’s possible that a language could have both a binding construct like let/cc and a separate throw-like
construct for continuation invocation, but there don’t appear to be any.
To implement continuations, we will take the DrScheme approach of adding a binding construct but
overloading procedural application:
<KCFAE> ::= ...
| {<KCFAE> <KCFAE>}
| {bindcc <id> <KCFAE>}
(This grammar is just for purposes of illustration. It would be easy to add a throw construct instead of
overloading application.)
To implement continuations, we need to add one new rule to the interpreter, and update the existing rule
for application. We’ll also add a new kind of type, called contV.
How does bindcc evaluate? Clearly, we must interpret the body in an extended environment:
[bindcc (cont-var body)
(interp body
(aSub cont-var
(contV ??? )
env)
k)]
198
CHAPTER 20. IMPLEMENTING CONTINUATIONS
The receiver used for the body is the same as the receiver of the bindcc expression. This captures the
intended behavior when the continuation is not used: namely, that evaluation proceeds as if the continuation
were never captured.
What kind of value should represent a continuation? Clearly it needs to be a Scheme procedure, so we
can apply it later. Functions are represented by procedures of two values: the parameter and the receiver
of the application. Clearly a continuation must also take the value of the parameter. However, the whole
point of having continuations in the language is to ignore the receiver at the point of invocation and instead
employ the one stored in the continuation value. Therefore, we can just ignore the receiver at the point
of application. The invoked continuation instead uses, as its own receiver, that captured at the point of its
creation:
[bindcc (cont-var body)
(interp body
(aSub cont-var
(contV (lambda (val)
(k val)))
env)
k)]
(Note again the reliance on Scheme’s static scope to close over the value of k.) This makes the modification
to the application clause very easy:
[app (fun-expr arg-expr)
(interp fun-expr env
(lambda (fun-val)
(interp arg-expr env
(lambda (arg-val)
(type-case KCFAE-Value fun-val
[closureV (c) (c arg-val k)]
[contV (c) (c arg-val)]
[else (error ”not an applicable value”)])))))]
Notice the very clear contrast between function and continuation application: function application employs
the receiver at the point of application, whereas continuation application employs the receiver at the point
of creation. This difference is dramatically highlighted by this code.
One last matter: what is the initial value of k? If we want to be utterly pedantic, it should be all
the computation we want to perform with the result of interpretation—i.e., a representation of “the rest of
DrScheme”. In practice, it’s perfectly okay to use the identity function. Then, when the interpreter finishes
its task, it invokes the identity function, which returns the value to DrScheme. For the purpose of testing,
it’s even better to use a procedure that prints a value and then halts the program entirely (as we discussed in
Section 16.3)—that lets us test whether we converted the interpreter into CPS properly.
And that’s it! In these few lines, we have captured the essence of continuations. (The heart of the
interpreter is in Figure 20.2.) Note in particular two properties of continuations that are reflected by, but perhaps not obvious from, this implementation:
20.3. ON STACKS
199
• To reiterate: we ignore the continuation at the point of application, and instead use the continuation
from the point of creation. This is the semantic representation of the intuition we gave earlier for
understanding continuation programs: “replace the entire let/cc expression with the value supplied
to the continuation”. Note, however, that the captured continuation is itself a dynamic object—it
depends on the entire history of calls—and thus cannot be computed purely from the program source
without evaluation. In this sense, it is different from the environment in a closure, which can partially
be determined entirely statically (that is, we can determine which identifiers are in the environment,
though it is undecidable what their values will be.)
• The continuation closes over the environment; in particular, its body is scoped statically, not dynami-
cally.
Exercise 20.2.1 Add web-read to KCFAE.
20.3
On Stacks
Let’s re-examine the procedure application rule in the interpreter:
[app (fun-expr arg-expr)
(interp fun-expr env
(lambda (fun-val)
(interp arg-expr env
(lambda (arg-val)
((closureV-p fun-val)
arg-val k)))))]
Observe how the receiver of the value of the function position, and that of the value of the argument position,
are both new procedures, whereas when the procedure application finally happens (in the latter receiver),
the third argument is just k.
Given that the receivers represent the stack at every point, this should seem rather strange: wasn’t the
stack meant to hold a record of procedure invocations? And if so, why is the receiver “growing” when
evaluating the function and the argument, but “shrinking” back to its original size when the application
actually happens?
We have said that the receiver corresponds directly to the stack. In particular, the receiver is a procedure
that may refer to another procedure (that it closes over), which may refer to another procedure (that it closes
over), and so on. Each of these procedures represents one stack frame (sometimes called an activation
record, because it records an extant activation of a procedure in the running program). Returning a value
“pops” the stack; since we have made the stack explicit, the equivalent operation is to pass the value to be
returned to the receiver.
We therefore see, from this pattern, that the stack is used solely to store intermediate results. It plays no
part in the actual invocation of a function. This probably sets on its head everything you have been taught
about stacks until now. This is an important and, perhaps, startling point:
Stacks are not necessary for invoking functions.
200
CHAPTER 20. IMPLEMENTING CONTINUATIONS
The stack only plays a role in evaluating the argument to the function (and, in a language with first-class
functions, evaluating the function position itself); once that argument has been reduced to a value (in an
eager language), the stack has no further role with respect to invoking a function. The actual invocation is
merely a jump to an address holding the code of the function: it’s a goto.
Converting a program to CPS thus accomplishes two things. First, it exposes something—the stack—
normally hidden during the evaluation process; this is an instance of reflection. The transformation also
makes this a value that a programmer can manipulate directly (even changing the meaning of the program
as a result); this is known as reification.
Reflection and Reification
Reflection and reification are very powerful programming concepts. Most programmers encounter
them only very informally or in a fairly weak setting. For instance, Java offers a very limited
form of reflection (a programmer can, for instance, query the names of methods of an object),
and some languages reify very low-level implementation details (such as memory addresses in C).
Few languages reify truly powerful computational features; the ones that do enable entirely new
programming patterns that programmers accustomed only to more traditional languages usually
can’t imagine. Truly smart programmers sometimes create their own languages with the express
purpose of reifying some useful hidden element, and implement their solution in the new language,
to create a very powerful kind of reusable abstraction. A classic instance of this is Web programmers
who have reified stacks to enable a more direct programming style.
20.4
Tail Calls
Converting the program to CPS helps us clearly see which calls are just gotos, and which ones need stack
build-up. The ones that are just gotos are those invocations that use the same receiver argument as the one
they received. Those that build a more complex receiver are relying on the stack.
Procedure calls that do not place any burden on the stack are called tail calls. Converting a program
to CPS helps us identify tail calls, though it’s possible to identify them from the program source itself. An
invocation of g in a procedure f is a tail call if, in the control path that leads to the invocation of g, the
value of f is determined by the invocation of g. In that case, g can send its value directly to whoever is
expecting f ’s value; this verbal description is captured precisely in the CPSed version (since f passes along
its receiver to g, which sends its value to that receiver). This insight is employed by compilers to perform
tail call optimization (abbreviated TCO, and sometimes referred to as last call optimization), whereby they
ensure that tail calls incur no stack growth.
Here are some consequences of TCO:
• With TCO, it no longer becomes necessary for a language to provide looping constructs. Whatever
was previously written using a custom-purpose loop can now be written as a recursive procedure. So
long as all recursive calls are tail calls, the compiler will convert the calls into gotos, accomplishing
the same efficiency as the loop version. For instance, here’s a very simple version of a for loop,
written using tail calls:
20.4. TAIL CALLS
201
(define (for init condition change body result)
(if (condition init)
(for (change init)
condition
change
body
(body init result))
result))
By factoring out the invariant arguments, we can write this more readably as
(define (for init condition change body result)
(local [(define (loop init result)
(if (condition init)
(loop (change init)
(body init result))
result))]
(loop init result)))
To use this as a loop, write
(for 10 positive? sub1 + 0)
which evaluates to 55. It’s possible to make this look more like a traditional for loop using macros,
which we will discuss in Section 36. That aside, notice how similar this is to a fold operator! Indeed,
foldl employs a tail call in its recursion, meaning it is just as efficient as looping constructs in more
traditional languages.
• Put differently, thanks to TCO, the set of looping constructs is extensible, not limited by the imagina-
tion of the language designer. In particular, with care it becomes easy to create loops (or iterators)
over new data structures without suffering an undue performance penalty.
• While TCO is traditionally associated with languages such as Scheme and ML, there’s no reason they
must be. It’s perfectly possible to have TCO in any language. Indeed, as our analysis above has
demonstrated, TCO is the natural consequence of understanding the true meaning of function calls.
A languages that deprives you of TCO is cheating you of what is rightfully yours—stand up for your
rights! Because so many language designers and implementors habitually mistreat their users by
failing to support TCO, however, programmers have become conditioned to think of all function calls
as inherently expensive, even when they are not.
• A special case of a tail call is known as tail recursion, which occurs when the tail call within a
procedure is to the same procedure. This is the behavior we see in the procedure for above. Keep in
mind, however, that tail recursion optimization is only a special case. While it is an important special
case (since it enables the implementation of linear loops), it is neither the most interesting case nor,
more importantly, the only useful one.
202
CHAPTER 20. IMPLEMENTING CONTINUATIONS
Sometimes, programmers will find it natural to split a computation across two procedures, and use tail
calls to communicate between them.4 This leads to very natural program structures. A programmer
using a language like Java is, however, forced into an unpleasant decision. If they split code across
methods, they pay the penalty of method invocations that use the stack needlessly. But even if they
combine the code into a single procedure, it’s not clear that they can easily turn the two code bodies
into a single loop. Even if they do, the structure of the code has now been altered irrevocably. Consider
the following example:
(define (even? n)
(if (zero? n)
true
(odd? (sub1 n))))
(define (odd? n)
(if (zero? n)
false
(even? (sub1 n))))
Try writing this entirely through loops and compare the resulting structure.
Therefore, even if a language gives you tail recursion optimization, remember that you are getting less
than you deserve. Indeed, it sometimes suggests an implementor who realized that the true nature of
function calls permitted calls that consumed no new stack space but, due to ignorance or a failure of
imagination, restricted this power to tail recursion only. The primitive you really want a language to
support is tail call optimization. With it, you can express solutions more naturally, and can also build
very interesting abstractions of control flow patterns.
• Note that CPS converts every program into a form where every call is a tail call!
Exercise 20.4.1 If, in CPS, every call is a tail call, and the underlying language supports TCO (as Scheme
does), does the CPS version of a program run in constant stack space even if the original does not? Discuss.
Exercise 20.4.2 Java does not support TCO. Investigate why not.
20.5
Testing
You might think, from last time’s extended example of continuation use, that it’s absolutely necessary to
have state to write any interesting continuation programs. While it’s true that most practical uses of the full
power of continuations (as opposed to merely exceptions, say) do use state, it’s possible to write some fairly
complicated continuation programs without state for the purposes of testing our interpreter. Here are some
4They may not even communicate mutually. In the second version of the loop above, for invokes loop to initiate the loop. That
call is a tail call, and well it should be, otherwise the entire loop will have consumed stack space. Because Scheme has tail calls,
notice how effortlessly we were able to create this abstraction. If the language supprted only tail recursion optimization, the latter
version of the loop, which is more pleasant to read and maintain, would actually consume stack space against our will.
20.5. TESTING
203
such programs. You should, of course, first determine their value by hand (by writing the continuations in
the form of lambda↑ procedures, substituting, and evaluating).
First, a few old favorites, just to make sure the easy cases work correctly:
1. {bindcc k 3}
2. {bindcc k {k 3}}
3. {bindcc k {+ 1 {k 3}}}
4. {+ 1 {bindcc k {+ 1 {k 3}}}}
And now for some classic examples from the continuations lore:
1. {{bindcc k
{k {fun {dummy}
3}}}
1729}
2. {bindcc k
{k
{k
{k 3}}}}
3. {{{bindcc k k}
{fun {x} x}}
3}
4. {{{{bindcc k k}
{fun {x} x}}
{fun {x} x}}
3}
The answer in each case is fairly obvious, but you would be cheating yourself if you didn’t hand-evaluate
each of these first. This is painful, but there’s no royal road to understanding! (If in doubt, of course, run
their counterpart in Scheme.)
204
CHAPTER 20. IMPLEMENTING CONTINUATIONS
(define-type CFAE-Value
[numV (n number?)]
[closureV (p procedure?)])
;; interp : CFAE Env receiver → doesn’t return
(define (interp expr env k)
(type-case CFAE expr
[num (n) (k (numV n))]
[add (l r) (interp l env
(lambda (lv)
(interp r env
(lambda (rv)
(k (num+ lv rv))))))]
[if0 (test truth falsity)
(interp test env
(lambda (tv)
(if (num-zero? tv)
(interp truth env k)
(interp falsity env k))))]
[id (v) (k (lookup v env))]
[fun (param body)
(k (closureV (lambda (arg-val dyn-k)
(interp body (aSub param arg-val env) dyn-k))))]
[app (fun-expr arg-expr)
(interp fun-expr env
(lambda (fun-val)
(interp arg-expr env
(lambda (arg-val)
((closureV-p fun-val)
arg-val k)))))]))
Figure 20.1: Making Continuations Explicit
20.5. TESTING
205
(define-type KCFAE-Value
[numV (n number?)]
[closureV (p procedure?)]
[contV (c procedure?)])
;; interp : KCFAE Env receiver → doesn’t return
(define (interp expr env k)
(type-case KCFAE expr
[num (n) (k (numV n))]
[add (l r) (interp l env
(lambda (lv)
(interp r env
(lambda (rv)
(k (num+ lv rv))))))]
[if0 (test truth falsity)
(interp test env
(lambda (tv)
(if (num-zero? tv)
(interp truth env k)
(interp falsity env k))))]
[id (v) (k (lookup v env))]
[fun (param body)
(k (closureV (lambda (arg-val dyn-k)
(interp body (aSub param arg-val env) dyn-k))))]
[app (fun-expr arg-expr)
(interp fun-expr env
(lambda (fun-val)
(interp arg-expr env
(lambda (arg-val)
(type-case KCFAE-Value fun-val
[closureV (c) (c arg-val k)]
[contV (c) (c arg-val)]
[else (error ”not an applicable value”)])))))]
[bindcc (cont-var body)
(interp body
(aSub cont-var
(contV (lambda (val)
(k val)))
env)
k)]))
Figure 20.2: Adding Continuations as Language Constructs
206
CHAPTER 20. IMPLEMENTING CONTINUATIONS
Part VIII
Memory Management
207
Chapter 21
Automatic Memory Management
21.1
Motivation
We have seen in Section 13 that, when making data structures explicit in the store, the store (or heap) has allocated data that are no longer necessary. Ideally, we would like this space reclaimed automatically. This
would enable us to program as if we had an infinite amount of memory yet, so long as we never exceed the
actual virtual memory capacity at any instant, the program would never halt with an out-of-memory error.
Whose responsibility is it to reclaim these locations? It can’t be the responsibility