13.2 First-Class Continuations

13.2.1 The Concept of a Continuation

The concept of a continuation is an important, yet under-emphasized and -utilized concept in programming languages. Intuitively, a continuation is a promise to do something. While evaluating an expression in any language, the interpreter of that language must keep track of what to do with the return value of the expression it is currently evaluating. The actions entailed in the “what to do with the return value” step are the pending computations or the continuation of the computation (Dybvig 2009, p. 73). Concretely, a continuation is a one-argument function that represents the remainder of a computation from a given point in a program. The argument passed to a continuation is the return value of the prior computation—the one value for which the continuation is waiting to complete the next computation.

Consider the following Scheme expression: (* 2 (+ 1 4)). When the interpreter evaluates the subexpression (+ 1 4) (i.e., the second argument to the * operator), the interpreter must do something with the value 5 that is returned. The something that the interpreter does with the return value is the continuation of the subexpression (+ 1 4). Thus, we can think of a continuation as a pending computation that is awaiting a return value. While the continuation of the expression (+ 1 4) is internal to the interpreter while the interpreter is evaluating the expression (* 2 (+ 1 4)), we can reify the implicit continuation to make it concrete. The definition of the verb reify is “to make (something abstract) more concrete or real” and reification refers to the process of reifying. The reified continuation of the subexpression (+ 1 4) in the example expression (* 2 (+ 1 4)) is

Thus, a continuation is simply a function of one argument that returns a value.

When working with continuations, it is often helpful to reify the internal, implicit continuation as an external, explicit λ-expression:

The Twentieth Commandment: When thinking about a value created with , write down the function that is equivalent but does not forget [its surrounding context]. Then, when you use it, remember to forget [its surrounding context]. (Friedman and Felleisen 1996b, p. 160)

Therefore, in the following examples, we reify the internal continuations where possible and appropriate for clarity. For instance, the continuation of the subexpression (+ 1 4) in the expression is

During evaluation of the expression , eight continuations exist. We present these continuations in an inside-to-out (or right-to-left) order with respect to the expression. The continuations present are the continuations waiting for the value of the following expressions (Dybvig 2009, pp. 73–74):

• (rightmost) +

• (+ 1 4)

• (rightmost) *

• (* 2 (+ 1 4))

• (leftmost) +

• (+ 5 (* 2 (+ 1 4)))

• (leftmost) *

• (* 3 (+ 5 (* 2 (+ 1 4))))

The reified continuation waiting for the value of the rightmost * is

The continuation of the subexpression (+ 1 4) in the expression

is

A continuation represents the pending computations at any point in a program— in this case, as a unary function. We can think of a continuation as the pending control context of a program point.

13.2.2 Capturing First-Class Continuations: call/cc

Some language implementations (e.g., interpreters) manipulate continuations internally, but only some (e.g., Scheme, Ruby, ML, Smalltalk) give the programmer first-class access to them. The Scheme function call-with-current-continuation (canonically abbreviated call/cc) allows a programmer to capture (i.e., reify) the current continuation of any expression in a program. In other words, call/cc gives a programmer access to the underlying continuation used by the interpreter. Since a continuation exists at run-time (in the interpreter) and can be expressed in the source language (through the use of call/cc), continuations are first-class entities in Scheme. In turn, they can be passed to and returned from functions and assigned to variables.

The call/cc function only accepts as an argument a function of one argument f, and captures (i.e., obtains) the current continuation k of the invocation of call/cc (i.e., the computations waiting for the return value of call/cc) and calls f, passing k to it (or, in other words, applies f to k). The captured continuation is represented as the parameter k of function f. The current continuation k is also a function of one argument. If at any time (during the execution of f) the captured continuation k is invoked with an argument v, control returns from the call to call/cc using v as a return value and the pending computations in f are abandoned. The pending computations waiting for call/cc to return proceed with v as the return value to the invocation of call/cc. The call/cc function reifies (i.e., concretizes) the continuation into a function that, when called, transfers control to that captured computation and causes it to resume. If k is not invoked during the execution of f, then the value returned by f becomes the return value of the invocation to call/cc.

We begin with simple examples to help the reader understand which continuation is being captured and how it is being used. Later, once we are comfortable with continuations and have an understanding of the interface for capturing continuations in Scheme, we demonstrate more powerful and practical uses of continuations.

Let us discuss some simple examples of capturing continuations with call/cc.² Consider the expression (+ 2 1). The continuation of the subexpression 2 is (lambda (x) (+ x 1)—expressed in English as “take the result of evaluating 2 and add 1 to it.” Now consider the expression

where the 2 in the previous expression has been replaced with (call/cc (lambda (k) (k 3))). This new subexpression captures the continuation of the first argument to the addition operator in the full expression. We already know that the continuation of the first argument is (lambda (x) (+ x 1). Thus, the invocation of call/cc here captures the continuation (lambda (x) (+ x 1). The semantics of call/cc are to call its function argument with the current continuation captured. Thus, the expression

translates to

The latter expression passes the current continuation , (lambda (x) (+ x 1)), to the function (lambda (k) (k 3)), which is passed to call/cc in the former expression. That expression evaluates to ((lambda (x) (+ x 1)) 3) or (+ 3 1) or 4.

Now let us consider additional examples:

Here, the continuation of the invocation of call/cc is captured and bound to k. Since there are no computations waiting on the return value of call/cc in this case, the continuation being captured is the identity function: (lambda (x) x). However, k is never used in the body of the function passed to call/cc. Thus, the return value of the entire expression is the return value of the body of the function passed to call/cc. Typically, we capture the current continuation because we want to use it. Thus, consider the following slightly revised example:

Now the captured continuation k is being invoked. When k is invoked, the continuation of the invocation of k [i.e., (* 2 returnvalue)] is aborted and the continuation of the invocation to call/cc (which is captured in k and is still the identity function because no computations are waiting for the return value of the invocation to call/cc) is followed with a return value of 20. However, when k is invoked, we do not ever return from the expression (k 20). Instead, invoking k replaces the continuation of the expression (k 20) with the continuation captured in k, which is the identity function. Thus, the value passed to k becomes the return value of the call to call/cc. Since the continuation waiting for the return value of the expression (k 20) is ignored and aborted, we can pass any value of any type to k because, in this case, the continuation stored in k is the identity function, which is polymorphic:

Now we modify the original expression so that the continuation being captured by call/cc is no longer the identity function:

The continuation being captured by call/cc and bound to k is

Again, when k is invoked, we never return from the expression (k 20). Instead, invoking k replaces the continuation of the expression (k 20) with the continuation captured in k, which is (lambda (returnvalue) (/ 100 return value)). Thus, the value passed to k becomes the return value of the call to call/cc. In this case, call/cc returns 20. Since a computation that divides 100 by the return value of the invocation of call/cc is pending, the return value of the entire expression is 5. Now we must pass an integer to k, even though the continuation waiting for the return value of the expression (k 20) is ignored, because it becomes the operand to the pending division operator:

Instead of continuing with the value used as the divisor, we can continue with the value used as the dividend:

Thus, a first-class continuation, like a goto statement, supports an arbitrary transfer of control, but in a more systematic and controlled fashion than a goto statement does. Moreover, unlike a goto statement, when control is transferred with a first-class continuation, the environment—including the run-time stack at the time call/cc was originally invoked—is restored. A continuation represents a captured, not suspended, series of computations awaiting a value.

In summary, we have discussed two ways of working with first-class continuations. One form involves not using (i.e., invoking) the captured continuation in the body of the function passed to call/cc:

When k is not invoked in the body of the function f passed to call/cc, the return value of the call to call/cc is the return value of f. In general, a call to (call/cc (lambda (k) E)), where k is not called in E, is the same as a call to (call/cc (lambda (k) (k E))) (Haynes, Friedman, and Wand 1986, p. 145). In the other form demonstrated, the captured continuation is invoked in the body of the function passed to call/cc:

If the continuation is invoked inside f, then control returns from the call to call/cc using the value passed to the continuation as a return value. Control does not return to the function f and all pending computations are left unfinished—this is called a nonlocal exit and is explored in Section 13.3.1. The examples of continuations in this section demonstrate that, once captured, a programmer can use (i.e., call) the captured continuation to replace the current continuation elsewhere in a program, when desired, to circumvent the normal flow of control and thereby affect, manipulate, and direct control flow. Figure 13.1 illustrates the general process of capturing the current continuation k through call/cc in Scheme and later replacing the current continuation k¹ with k. Figure 13.2 provides an example of the process, and Figure 13.3 depicts the run-time stack during the continuation replacement process from that example.

Conceptual Exercises for Section 13.2

Exercise 13.2.1 Consider the expression (* 2 3). Reify the continuation of each of the following subexpressions:

(a) *

(b) 2

(c) 3

Exercise 13.2.2 Reify the continuation of the expression (+ x 2) in the expression (* 3 (+ x 2)).

Exercise 13.2.3 Predict the output of the following expression:

Exercise 13.2.4 Consider the following Scheme expression:

Explain, by appealing to transfer of control and the run-time stack, why the return value of this expression is 2 and not 3. Also, reify the continuation captured by the call to call/cc in this expression. Does a continuation ever return (like a function)?

Programming Exercises for Section 13.2

Exercise 13.2.5 In the following example, when k is invoked, we do not return from the expression (k 20). Instead, invoking k replaces the continuation of the expression (k 20) with the continuation captured in k, which is the identity function:

Modify this expression to also capture the continuation of the expression (k 20) with call/cc. Name this continuation k2 and use it to complete the entire computation with the default continuation (now captured in k2).

Exercise 13.2.6 The interface for capturing continuations used in The Seasoned Schemer (Friedman and Felleisen 1996b) is called letcc. Although letcc has a slightly different syntax than call/cc, both have approximately the same semantics (i.e., they capture the current continuation). The letcc function only accepts an identifier and an expression, in that order, and it captures the continuation of the expression and binds it to the identifier. For instance, the following two expressions are analogs of each other:

(a) Give a general rewrite rule that can be used to convert an expression using letcc to an equivalent expression using call/cc. In other words, give an expression using only call/cc that can be used as a replacement for every occurrence of the expression (letcc k e).

(b) Assume letcc is a primitive in Scheme. Define call/cc using letcc.

Exercise 13.2.7 Investigate and experiment with the interface for first-class continuations in ML (see the structure SMLofNJ.Cont):

Replicate any three of the examples in Scheme involving call/cc given in this section in ML.

1. The term call/cc in this quote is letcc in Friedman and Felleisen (1996b).

2. While the Scheme function to capture the current continuation is named call-with-current-continuation, for purposes of terse exposition we use the commonly used abbreviation call/cc for it without including the expression (define call/cc call-with-current-continuation) in all of our examples. The function call/cc is defined in Racket Scheme.