Comprehending first-class continuations

The notion of continuations as first-class values has been a tricky subject for me to understand to a comfortable level of certainty. I think this is probably true for many PLT-laymen like myself. This article represents my attempt at collecting and presenting my thoughts in a coherant manner! I'd be happy to receive corrections and comments.

I will start by defining a few key terms in my own style.

Continuation

We can observe that every expression, regardless of complexity, has the ultimate goal of returning a value to some surrounding execution context. That context is known as a continuation - it represents everything that is left to compute. Therefore, every computation has an associated continuation, which specifies the place from which execution should continue once control has been returned.

As a simple example, consider the following Scheme form:

(lambda (n) (+ n 1))

The continuation associated with the sub-expression "1" is an anonymous function, whose body consists of a call to the + primitive procedure whose first argument is the local variable n and whose second argument is being sought. With this understanding we can say expressions deliver values and continuations receive values.

Current continuation

By "current", we are referring to the continuation that would be derived from the current point in a programs execution. In other words, the current point of execution, lexical environment and state of the call stack (You should be familiar with the stack and the heap).

First-class object

For an object to be a "first-class citizen" in a programming language, it needs a few properties. Specifically, it must support being:

• passed as a parameter to a function;
• returned from a function;
• stored in a variable or within a data structure;
• constructed at runtime.

Things like numbers and strings are first-class in most programming languages. Functions are first-class in all functional programming languages. And in Scheme, my language of choice for this article, nearly everything can be considered first-class - including continuations as we'll see shortly.

OK, now continuations in Scheme

In order to render the abstract notion of the current execution context (the current continuation) to the programmer, Scheme needs some way to represent it. It would have been possible to implement specific objects and syntax into the language to handle this, but it's much easier to simply represent the current continuation as a first-class function. This process of transforming something implicit into something that can be explicitely expressed is known as "reification". So we can say Scheme reifies the current continuation as a function object.

Scheme provides the function call-with-current-continuation (aliased as call/cc) to furnish continuations to the programmer. call/cc is a unary function that accepts a further unary function, f, as it's argument. When invoked, Scheme will reify the current continuation, c, as a function and apply f to c. Therefore:

c(call/cc f) --> c(f c)     ; Not Scheme. c(...) represents the current continuation

When c is applied to an argument, v, the existing continuation is terminated and the one represented by c is reinstated. So program flow will continue on from where the continuation was captured and v will become the overall value of the call/cc invokation.

Confusing? Take a look at this simple example:

(call/cc
  (lambda (return)
    (+ 2 (return 4) 1)))

At first glance, you may think this expression will evaluate to 7, but infact, it will evaluate to 4. This is because we've captured the current continuation in the formal parameter return and then applied it to the number 4. This causes program flow to return instantly to the point at which the continuation was taken. Yep -- when applied, c will never return! We are effectively emulating the "return" control operator that allows early-escape in many popular programming languages.

To demonstrate the concept of early-escape in a more effective manner, let me show you two versions of a small Scheme procedure - one that makes use of continuations and one that does not. The procedure has-sym? accepts as arguments an S-expression (in this case a list of symbols and/or nested lists of symbols) and a symbol. It returns true if the given symbol is present somewhere within the S-expression. First of all, take a look at the non-continuation version:

(define (has-sym? lst s)
  (cond
    ((empty? lst) #f)               ; Nothing left, must not be present.
    ((list? (car lst))              ; Is a sublist, inspect it also.
      (or (has-sym? (car lst) s)
          (has-sym? (cdr lst) s)))
    ((eq? s (car lst)) #t)          ; Found a match, return true to the caller!
    (else
      (has-sym? (cdr lst) s))))     ; Nothing yet, keep looking...

Whilst concise and easy to understand, this implementation (because it's defined as a recursive process) suffers from the slight hassle in that even if we find a match, we need to wait until the call-stack unwinds before the actual result gets back to the continuation in which the has-sym? procedure was called. If, perhaps, we captured the continuation of the has-sym? procedure with call/cc and then defined a local helper procedure (to perform the search) inside our function argument, we'd be able to invoke the continuation object and jump straight out of the procedure as soon as we found a match. For example:

(define (has-sym? lst s)
  (call/cc
    (lambda (return)
      (define (find lst)            ; Helper proc, local to lambda argument of call/cc.
        (cond
          ((empty? lst) #f)
          ((list? (car lst))
            (or (find (car lst))
                (find (cdr lst))))
          ((eq? s (car lst))
            (return #t))            ; A match! Invoke 'return' for an early-escape!
          (else
            (find (cdr lst)))))
      (find lst))))                 ; We end up here when/if 'return' is invoked.

At this point it may be worth pointing out that continuations in Scheme, whilst far more powerful, are also more conservative than the GOTO statement of other languages for we can only revert control back to a place we have already visited (obviously, this is a good thing!). Also note that applying a continuation, unlike lexical closures, does not reinstate the referencing environment! If you change the values of variables - they will remain changed.

Continuations as first-class citizens

So far I've tried to explain the notions of both first-class objects and continuations in Scheme, but when we combine the two and start considering continuations themselves as being of first-class status, we open up a treasure trove of cool ideas. For example, consider the following mind-bender:

(define (fact n)
  (let* ((total n)
         (k (call/cc (lambda (kk) kk))))
    (set! n (- n 1))
    (set! total (* total n))
    (if (<= n 1)
      total
      (k k))))

We can demonstrate the indefinite extent of continuations in Scheme by capturing the continuation (reified as a first-class function) in the local variable k. This definition of factorial works by capturing the continuation object, modifying the parameter n and local variable total in place, and then invoking the continuation with itself as an argument. This causes something of a local GOTO and rebinds the original continuation to the local variable k. This process continues until n reaches 1 at which point we return the total back to the user. The let* ** form is important here as it will expand into a series of nested **let forms. Without this, we'd rebind total to the original value of n on each invokation of the continuation object. With *let ** we can store a running total.

As you can see, we have used our power over control flow to compute factorial without using recursion or any built in looping construct. Of course, this implementation also suffers from two obvious downsides:

• It's somewhat esoteric and hard to understand
• It mutates local state, which makes it harder to prove that this function will maintain referential transparency.

And so...

With the power of first-class continuation handling at our disposal, we have the ability to define several control flow constructs common to other programming languages, such as backtracking, try/catch exception handling and "green" threads.

Studying a topic like continuations helps us to solidify our knowledge of several concepts we may generally grow to take for granted. The idea of managing control flow is so rudimentary to our field that we may never stop to think about how such an implicitely understood idea can be explained effectively.

In terms of further reading, I'd suggest the call-with-current-continuation, Continuation and Call stack articles on Wikipedia. The R5RS standard documents call/cc and other control-handling procedures that are available in Scheme. The discussion on understanding continuations at Lambda the Ultimate also helped me in writing this article.

And, finally, I think when such high-level control of continuations is given to a programmer, the words of the great Uncle Ben must be remembered:

"WITH GREAT POWER THERE MUST ALSO COME - GREAT RESPONSIBILITY!" - Amazing Fantasy #15 (August 1962) - The first Spider-Man story.