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.