Continuation Passing Style Interpreters
In my post on Scheme debuggers, I introduced a simple Scheme interpreter. Unfortunately, the interpreter was structured such that it was hard to make a terribly sophisticated debugger. While we won't improve upon our debugger much today, I do want to look at a different style of interpreter that should enable more advanced debugging features.
This new style is called continuation passing style. You can think of a continuation as what to do next in a program, and so continuation passing style means we make the continuation an explicit argument of a function. This means we can do a lot more with the control flow of the program, which is important in a debugger, for example, since we want to be able to pause and inspect the execution at arbitrary points.
We'll continue with a quick introduction to continuations and
continuation passing style, then look at how to apply this to our
interpreter. Once that is done, we will see how to implement call/cc
in our new interpreter.
What Are Continuations?π
You can think of a continuation as the rest of the program. What I mean is that at any point in a program's execution we can think of it in terms of what has already been done and what still needs to be done. Consider the expression below.
(+ (* 2 3) 5)
This program has two things to do. First, we have to multiply 2 and 3, and then it needs to add 5 to the result. In other words, "add 5 to the result" is the continuation of "multiply 2 and 3." We can see this a little more clearly if we rewrite our program like this:
(let ((v (* 2 3)))
;; This is the continuation of (* 2 3)
(+ v 5))
In this case, the continuation isn't terribly interesting because it's always the same. What if we did this instead?
(define (foo)
(* 2 3))
(define (f1)
(+ (foo) 5))
(define (f2)
(+ (foo) 7))
Functions has an implicit continuation, and the cool thing is that the
continuation can change. In the function foo
above, sometimes the
continuation is to add 5 to the result, and other times the
continuation is to add 7. The continuation is just wherever the
function happens to return to.
If you're used to programming in lower level languages like C and thinking about things like stacks and return addresses, you might notice that stacks and return addresses are really similar to continuations.
So far we can only see continuations by looking at the source code. Sure, we can rewrite the program to make the continuation a little easier to see, but nothing really changes. What if we could make a function that represents a continuation? Starting with our first example, we might end up with something like the program below.
(let ((k (lambda (v) (+ v 5)))
(v (* 2 3)))
(k v))
Here, we've pulled the "add 5 to the result" part of the program into
a function which we can use just like any other function. By
convention, we always call the continuation k
. This process has a
fancy name: reification. To reify something is to take an abstract idea
and make it into something concrete that you can manipulate. In this
case, we took our abstract notion of the continuation of (* 2 3)
and
turned it into a function that we can control. Sure, we haven't done
anything other than apply it in the right place, but instead we could
pass it as an argument to another function. This leads us to
continuation passing style.
Continuation Passing Styleπ
We've seen that any function has an implicit continuation, which is
where the function returns to. What if instead functions never
returned? Well, this wouldn't be very interesting, because the caller
would never be able to do anything with the result of a
function. Fortunately, the caller could also tell the function what to
do when it's done. Let's look at this new version of foo
.
(define (foo k)
(k (* 2 3)))
Here, foo
doesn't return, but calls k
with its result instead. The
caller gets to control what happens next by deciding what function to
pass in as k
.
We'd have to rewrite the callers of foo
to respect this new style:
(define (f1)
(foo (lambda (v) (+ v 5))))
(define (f2)
(foo (lambda (v) (+ v 7))))
This style of passing a continuation into a procedure which never returns but instead calls the continuation is called, as you might expect, continuation passing style (CPS). It's a little harder to read, but it has some nice properties.
- Function calls are always in tail position. Scheme guarantees that tail calls don't grow the stack, so programs written in continuation passing style can never run out of stack space. It sounds nice, but in reality we've moved the stack into the heap with all of the new closures we have to allocate.
- We have a lot more options for control flow because we can save or ignore continuations as we please.
- Since each continuation only receives a single value, we've made the order of evaluation explicit. This is particularly important in programs with side effects.
Revisiting the Interpreterπ
We've made a couple of toy examples so far, but let's look at a more realistic program. First, recall the interpreter from last time:
(define (value-of e env)
(match e
(,x (guard (symbol? x)) (lookup x env))
(,n (guard (number? n)) n)
((lambda (,x) ,e)
(lambda (v) (value-of e (cons (cons x v) env))))
((,op ,[e1] ,[e2]) (guard (memq op '(+ * -)))
((eval op) e1 e2))
((,[e1] ,[e2])
(e1 e2))))
(define (lookup x env)
(if (eq? x (caar env))
(cdar env)
(lookup x (cdr env))))
We'll translate this to CPS one line at a time.
First, we add an extra argument to value-of
which provides the
continuation to invoke once the expression is evaluated:
(define (value-of-cps e env k)
...)
For environment lookup, we'll consider lookup
to be simple,
meaning we aren't going to worry about converting it to CPS. Thus, the
variable line becomes:
(,x (guard (symbol?x)) (k (lookup x env)))
Basically, as soon as we know the value of the expression, we pass it to k
.
Numbers are similar:
(,n (guard (number? n)) (k n))
Lambdas are a bit more involved. If you recall, we evaluated interpreted lambdas into native lambdas, and later the application line just applies this function. Thus, these need to be in CPS as well. Our lambda line, therefore, looks like this:
((lambda (,x) ,e)
(k (lambda (v k) (value-of-cps e (cons (cons x v) env) k))))
Notice a couple of things. First, lambdas immediate evaluate to
values, so we pass the (lambda (v k) ...)
directly to k
. Secondly,
this newly created lambda doesn't know in what context it will be
called, so it needs to receive a continuation argument as well. This
is why it's a two argument lambda instead of just a one argument
lambda like before and like it is in the source language. This is the
continuation we pass into value-of-cps
inside the lambda.
The next line, primitive operators, is a little more tricky as
well. Before we could just recursively call value-of
on the
arguments e1
and e2
. In CPS, however, functions never return, so
if we do that we'll never get a chance to evaluate the second argument
or perform the operation. Instead, we call value-of-cps
on the first
argument, and in the continuation we evaluate the second argument, and
finally in the innermost continuation we actually apply the
operator. Here's the code.
((,op ,e1 ,e2) (guard (memq op '(+ * -)))
(value-of-cps e1 env
(lambda (v1)
(value-of-cps e2 env
(lambda (v2)
(k ((eval op) v1 v2)))))))
Our final line is similar to the primitive operator line, in that we have to do the same sort of sequencing. It looks like this:
((,e1 ,e2)
(value-of-cps e1 env
(lambda (f)
(value-of-cps e2 env
(lambda (v)
(f v k))))))
First we evaluate e1
and the result gets bound to f
when the
(lambda (f) ...)
continuation is invoked. Next we evaluate the
argument, e2
. Finally, we apply the function to its argument. Notice
that we also pass in k
. This is the k
that was passed into
value-of-cps
the first time. Presumably this function call that we
are evaluating is part of a larger expression, and so this k
captures how to integrate that result with the outer expression.
Here's the whole interpreter in continuation passing style:
(define (value-of-cps e env k)
(match e
(,x (guard (symbol? x)) (k (lookup x env)))
(,n (guard (number? n)) (k n))
((lambda (,x) ,e)
(k (lambda (v k) (value-of-cps e (cons (cons x v) env) k))))
((,op ,e1 ,e2) (guard (memq op '(+ * -)))
(value-of-cps e1 env
(lambda (v1)
(value-of-cps e2 env
(lambda (v2)
(k ((eval op) v1 v2)))))))
((,e1 ,e2)
(value-of-cps e1 env
(lambda (f)
(value-of-cps e2 env
(lambda (v)
(f v k))))))))
Adding call/cc
π
At this point, you might be wondering why we did all that. The code is harder to read, and we haven't changed the language that the interpreter understands. In one way, this is a powerful thing about interpreters--the details of how the interpreter is written don't leak into the source language.
Like most programming techniques, sometimes CPS simplifies your program and other times it makes it more complicated. What we'd like is to be able to use CPS where it's convenient and use direct style everywhere else. In all our examples so far, however, we either right the whole thing in CPS or the whole thing in direct style. We don't have a good way to switch styles.
Scheme provides an operation that lets us do just that: call/cc
,
which is short for call-with-current-continuation
. call/cc
takes
one argument, which is a procedure that takes one argument. call/cc
creates a Scheme function that represents the continuation at the
point at which it is called and passes this function into its
argument. Here's a really simple example:
(call/cc (lambda (k) (k 5)))
If you evaluate this expression, you'll realize we could have just as
well written 5 and the result would be the same. The cool this is that
now we have a procedure that we can pass into, for example,
value-of-cps
in order to use the CPS interpreter in a non-CPS
context.
Implementing call/cc
can be a bit magical, but adding it to our
interpreter isn't too hard since we already have continuations. Like
most language features, we just need to add one line to the interpreter:
((call/cc ,e)
(value-of-cps e env
(lambda (f)
(f (lambda (v k^) (k v))))))
This is once again similar to the application line. We evaluate the
argument, which should yield a procedure, and then we apply it to a
new procedure that captures the current continuation. Notice that this
continuation has access to two continuations. k^
represents the
continuation at the point that the procedure is applied and k
represents the continuation that was active when we evaluated
call/cc
. In this case, we ignore k^
and instead apply the
continuation that call/cc
captured.
Wrapping Upπ
We've had a quick introduction to continuations, continuation passing
style and how to use this in a Scheme interpreter. From there, we show
that having a CPS interpreter makes it easy to add
call/cc
. Continuations open up a lot of interesting control flow
possibilities. For example, calling a continuation is not too
different from throwing an exception that is caught
later. Continuations can also be used to interleave the execution of
two threads. I hope to explore some of these options in more depth in
later posts.