Continuations

A continuation is the future of a computation. At any given time, a computation can conceptually be thought of as having a past (values already computed) and a future (what these values will be used for). In the case of function application in an applicative-order language like Scheme, all the arguments are evaluated before the function is applied to the results. Thus, when the last argument is being evaluated, the continuation of that computation is the application of the function to the arguments.

The Scheme function call-with-current-continuation, often abbreviated as just call/cc is a way of running some code with an additional function in the environment that represents the so-called current continuation; that is, whatever is waiting on the call-cc code to finish running. If this function representing the current continuation is ever applied, it has the effect of escaping from the body of the code call-cc is applied to. This is a bit hard to state in words such that it is easy to understand, so some examples will help:

Example: Non-local Escape

Here we have some code that finds all the keys (first elements) in a list of pairs (an alist). There's only one problem: what should we do when the list doesn't contain all pairs? In this case, we've decided to have the whole thing return #f when we find a non-pair. The keys function is actually a wrapper around the real work, which happens in a function we've called f.

(define (keys l)
  (letrec ((f (lambda (l k)
                (cond ((null? l)
                       '())
                      ((pair? (car l))
                       (cons (car (car l)) (f (cdr l) k)))
                      (else
                       (k #f))))))
    (call/cc (lambda (k) (f l k)))))

When the list is empty, we return the empty list. This is the "base case" in induction-speak. Otherwise, if the first element is a pair, we put it's car onto the list of keys found in the rest of the list. Finally if it's not a pair, we invoke the continuation with the argument #f. Notice that in the tail position of the function definition we have an application of call/cc which establishes the current continuation which is sent through the calls to f. Since call/cc is in the tail position, the current continuation will be the current continuation of keys, which may be some function call or perhaps a REPL when running interactively. The important thing is, that when k is applied deep down inside recursive calls to f, execution moves to whatever called the keys function and continues from there.

(keys '((a . 1) (b . 2) (c . 3))) ⇒ (a b c)
(keys '(7 (b . 2) (c . 3)))       ⇒ #f
(keys '((a . 1) (b . 2) 7))       ⇒ #f

Repeatable Continuations

Some languages only support what are called one-shot continuations which can only be invoked once. Others, like Scheme, support continuations which can be invoked as many times as desired. As expected, this forces execution to jump to the same state (both in code location and environment) multiple times. For example, if we execute the following in order:

(let ((x 1))
  (+ x (call/cc (lambda (k)
                  (set! *CONT* k) (k 0))))) ⇒ 1
(*CONT* 5)                                  ⇒ 6
(*CONT* 100)                                ⇒ 101
(list (*CONT* 1) (*CONT* 5) (*CONT* 100))   ⇒ 2      ; escape from list function

Here you can see that each time *CONT* is invoked, we add one to it's argument. Whenever we invoke the continuation the environment that existed when it was created is restored, so the variable x is bound to 1 again. In the last line, we attempt to make a list of the results of invoking the continuations. But when the continuation was stored, the call stack consisted of the REPL waiting on let waiting on + (the current continuation which call/cc captured). As a result, the first invocation of *CONT* goes back to that point, which returns (+ 1 1) to the REPL. This is another example of a non-local escape using continuations.

Order Matters

Because arguments are evaluated in order in certain Scheme implementations, this can be used to our advantage in using continuations. Anything which has already been evaluated is captured with the current continuation, so the following always uses 10 for *VALUE* rather than whatever the value is at the time the continuation is invoked.

(define *VALUE* 10)                            ⇒ 10
(+ *VALUE* (call/cc (lambda (k)
                      (set! *CONT* k) (k 1)))) ⇒ 11
(*CONT* 5)                                     ⇒ 15
(set! *VALUE* 1)                               ⇒ 1
(*CONT* 5)                                     ⇒ 15

If we were to reverse the order in the addition, forcing the continuation to evaluate *VALUE* before doing the addition, we get different results. The first time *VALUE* is 10 and the second time it turns out to be 1. This is probably more along the lines of what the little Schemer expects from the above.

(define *VALUE* 10)                            ⇒ 10
(+ (call/cc (lambda (k)
              (set! *CONT* k) (k 1))) *VALUE*) ⇒ 11
(*CONT* 5)                                     ⇒ 15
(set! *VALUE* 1)                               ⇒ 1
(*CONT* 5)                                     ⇒ 6

Do note, however, that this feature should not be relied upon. R5RS §4.1.3 states that "operand expressions are evaluated (in an unspecified order)" so there may be no way to tell from the order of the operands whether something like *VALUE* is already bound in environment of the continuation or not. [TODO: make sure this is correct.]