call-with-current-continuation

As noted in Tail Recursion, procedure call and return has traditionally been implemented by storing information that needs to be shared between the caller and callee in a FIFO stack. Each procedure invocation corresponds to a stack frame containing the callee’s parameters and the callee’s return address. The run time environments for many programming languages also create storage for other things like local / lexical variables and a function’s return value on the stack.

Since Scheme supports Lexical Closures andf Tail Recursion, there are stringent limits on what it is practical for a Scheme compiler or interpreter to store on the stack. In fact, Scheme takes a very different point of view when it comes to stack frames and recursion than many other programming languages, including most other Lisp dialects. From the point of view of a Scheme program the caller’s “return address” is accessible in many ways as if it were just another parameter stored in the currently executing procedure’s stack frame. In particular, it is possible to take possession of return addresses, and change the flow of control in quite dramatic (and useful!) ways.

The call-with-current-continuation special form (usually abbreviated as call/cc in source code) exists for exactly this purpose. As the simplest example of what can be accomplished using call/cc, consider the return statement that is common in procedural languages like C / C++, Java, C# etc. Invocation of return causes the currently executing function to immediately exit, bypassing any subsequent statements that would be part of its normal flow of control (laying aside statements protected during stack unwinding using special forms like try... finally... or using techniques like C++ destructors). If the currently executing procedure is declared to return a value, the return statement requires that you supply the value to return in this non-linear flow-of-control. Such a return statement is, in fact, simply a very limited form of access to a given procedure’s continuation. Here is an example of a C function with a return statement:

int fn(int n, char* s)
{

    if (n < 1)
    {

        // nothing to do..
        return 0;

    }

    for (int i = 0; i < n; ++i)
    {

        if ('\0' == s[i])
        {

            // reached end of string
            return i;

        }

        // do something with s[i]...

    }

    return n;

}

Scheme does not provide a built-in form that is directly analogous to C’s return statement. It is trivial to implement, however, using call/cc:

(define (fn n s)
    (let* ((size (string-length s))
           (limit (min n size)))
       (call/cc
           (lambda (return)
               (when (< n 1)
                   (return 0))
               (let loop ((i 0))
                   (when (>= i limit)
                       (return i))
                   ;; do something with (string-ref s i)...
                   (loop (+ i 1)))
               n))))

The preceding two functions implement essentially identical logic, one in C and the other in Scheme.

Scheme’s call/cc can be used for far more than simply implementing return. The preceding example works because call/cc invokes the function it is given with a “continuation procedure.” The “continuation procedure” is simply a procedure of one argument that will, when invoked, cause the call/cc form that created it to immediately exit and return the value that was passed to the continuation, as is demonstrated by the preceding example.

Just as return is a simple, special case of a lexically scoped continuation accessor statement, exceptions in languages that support them are another special case of dynamically scoped continuation accessors.

The key difference between call/cc and a simple return mechanism or even a more sophisticated exception handler is that the continuation procedures it creates are first-class objects that can be passed to and returned as values from procedures, stored in data structures etc. What is more, continuations are lexical closures representing snapshots of the execution context in which they were created. This means that Scheme directly and simply supports CPS (“Continuation Passing Style”) in ways that require diligence and caution to apply at the application level in most other programming languages.

For example, while C’s return statement and throw in C++ / Java / C# represent a one way trip out of a given execution context, Scheme continuations can be used to exit and re-enter a given execution context any number of times:

;; call fn2 in a loop as long as it returns a procedure
(define (fn1)
 (let ((i 0))
   (let loop ((k (fn2)))
     (display "fn1 - ")
     (display i)
     (set! i (+ i 1))
     (if (procedure? k)
         (begin
           (display ": received a procedure, calling it in a loop")
           (newline)
           (loop (k i)))
         (begin
           (display ": received ")
           (display k)
           (display ", terminating")
           (newline)
           k)))))

;; return a continuation from within a loop
;;
;; this loops 10 times then exits, assuming that the continuations it
;; returns are always invoked
(define (fn2)
 (call/cc
  (lambda (return)
    (let loop ((i 0))
      (display "fn2 - ")
      (display i)
      (if (< i 10)
          (begin
            (display ": returning a continuation")
            (newline)
            (let ((value (call/cc (lambda (k) (return k)))))
              (display "fn2 - ")
              (display i)
              (display ": resumed, received ")
              (display value)
              (newline)
              (loop (+ i 1))))
          (begin
            (display ": terminating loop, returning 'done")
            (newline)
            'done))))))

Invoking the preceding version of fn1 produces the following on the console:

fn2 - 0: returning a continuation
fn1 - 0: received a procedure, calling it in a loop
fn2 - 0: resumed, received 1
fn2 - 1: returning a continuation
fn1 - 1: received a procedure, calling it in a loop
fn2 - 1: resumed, received 2
fn2 - 2: returning a continuation
fn1 - 2: received a procedure, calling it in a loop
fn2 - 2: resumed, received 3
fn2 - 3: returning a continuation
fn1 - 3: received a procedure, calling it in a loop
fn2 - 3: resumed, received 4
fn2 - 4: returning a continuation
fn1 - 4: received a procedure, calling it in a loop
fn2 - 4: resumed, received 5
fn2 - 5: returning a continuation
fn1 - 5: received a procedure, calling it in a loop
fn2 - 5: resumed, received 6
fn2 - 6: returning a continuation
fn1 - 6: received a procedure, calling it in a loop
fn2 - 6: resumed, received 7
fn2 - 7: returning a continuation
fn1 - 7: received a procedure, calling it in a loop
fn2 - 7: resumed, received 8
fn2 - 8: returning a continuation
fn1 - 8: received a procedure, calling it in a loop
fn2 - 8: resumed, received 9
fn2 - 9: returning a continuation
fn1 - 9: received a procedure, calling it in a loop
fn2 - 9: resumed, received 10
fn2 - 10: terminating loop, returning 'done
fn1 - 10: received done, terminating

The observant reader who thinks through all the implications of call/cc may have already noticed that the loop in fn1 is actually redundant. It was placed there to show how multiple functions, each with their own non-trivial flows-of-control, can employ continuations to use one another as co-routines. Consider the following:

;; demonstrate that the loop in fn2 always returns to the same place
;; in its caller
;;
;; the output to the console is half as verbose as fn1, but fn2 still
;; loops to completion
(define (fn3)
 (let ((k (fn2)))
   (when (procedure? k)
     (k 0))))

As implied by the comment preceding the definition of fn3, here is its output to the console:

fn2 - 0: returning a continuation
fn2 - 0: resumed, received 0
fn2 - 1: returning a continuation
fn2 - 1: resumed, received 0
fn2 - 2: returning a continuation
fn2 - 2: resumed, received 0
fn2 - 3: returning a continuation
fn2 - 3: resumed, received 0
fn2 - 4: returning a continuation
fn2 - 4: resumed, received 0
fn2 - 5: returning a continuation
fn2 - 5: resumed, received 0
fn2 - 6: returning a continuation
fn2 - 6: resumed, received 0
fn2 - 7: returning a continuation
fn2 - 7: resumed, received 0
fn2 - 8: returning a continuation
fn2 - 8: resumed, received 0
fn2 - 9: returning a continuation
fn2 - 9: resumed, received 0
fn2 - 10: terminating loop, returning 'done

This happens because the continuation of the call to call/cc that binds the variable named return in fn2 are the expressions whose values become bound to the variables named k in fn1 and fn3. In other words, the loop in fn2 turns the body of the let in fn3 into a loop, even though the body of fn3 contains no looping construct. This is one of the aspects of programming with continuations that takes getting used to: the same point in a given procedure’s flow-of-control can be reached multiple times if it calls a function that returns a continuation even though the caller, itself, has no explicit loops. See \ref pg-dynamic-wind for more on this topic and mechanisms for addressing issues that can arise as a result.

The preceding versions of fn1, fn2 and fn3 demonstrate a number of features of Scheme continuations:

Continuations can be used to implement arbitrarily complex, non-sequential and non-local flow-of-control
In particular, they can be used to re-enter previously exited execution contexts
When doing so, they can pass information both into and out of an execution context
Since they are lexical closures, they restore an execution context’s environment when it is re-entered

The last three points are worth an entire chapter in their own right (which, helpfully, comes next).