Continuations

1  Introduction

These notes cover continuations and their applications, with a particular emphasis on web applications using continuations. We start by looking the basics of continuations, touch on a few classic uses of continuations and then dive into their application to web applications. There isn't the space to cover everything about continuations. At the end of the document are a number of references to papers that explore topics in more depth.

2  Setting Up

To use continuations in DrScheme you much change your language setting to one of the languages listed under the PLT tab.

3  What Is A Continuation?

A continuation is simply ``what happens next''. Consider a simple scheme expression:

(+ 1 (+ 2 3))

Scheme is an eager language, which means the expression (+ 2 3) gets evaluated first, yielding

(+ 1 5)

which is then evaluated to

6

At the time when we are evaluating (+ 2 3) the continuation is (+ 1 #), where the # indicates that the continuation is waiting for a value in that place to complete its computation.

Scheme allows us to capture the current continuation using call-with-current-continuation often abbreviated to call/cc. call/cc takes a procedure of a single argument, and calls this procedure with a continuation. The continuation is itself a procedure of one argument. A typical use of call/cc looks like:

(call/cc
  (lambda (k)
   ... k ...))

It's often more convenient to use let/cc which simply binds a name to the current continuation

(let/cc k
   ... k ...)

3.1  Exercises

What is the continuation that is captured below? What is the value the program?

(+ 1 
   (let/cc k
     (k 5)))

What about

(+ 1 
   (let/cc k
     5))

where we don't call the captured continuation?

4  Escaping Procedures

Lets consider a slightly more involved example:

(+ 1 
   (let/cc k
     (- 5 (k 5))))

The continuation k is (lambda (#) (+ 1 #)). When we evaluate this code the continuation is called with the value 5 and the result of the entire expression is (+ 1 5) or 6. However if we substitute in the continuation, we get

(+ 1 
   (- 5 
     ((lambda (#) (+ 1 #)) 5)))

which evaluates to 0.

When k finishes evaluating it halts the computation, instead of returning a value to the surrounding expression. This type of procedure is called an escaping procedure. If we denote escaping procedures with lambda^ we can use substitution to write

(+ 1 
   (- 5
     ((lambda^ (#) (+ 1 #)) 5)))

which evalutes to 6 as it should do.

5  Classic Uses of Continuations

5.1  Loops

Using continuations we can write an infinite loop that allows its body expression to exit:

(define (cycle body)
  (let/cc k
    (define (loop)
      (body k)
      (loop))
    (loop)))

We call it like this:

(cycle 
  (lambda (exit) 
    (if (= (random 3) 0) 
        (exit 'done))))

5.2  Coroutines

Many computations have a producer-consumer model, in which one process generates data, while another consumes the data. Web sites are a good example of this: the users create inputs that the web server consumes to turn into web pages (more on this later). Many text processing tasks also have this form.

We want to write a procedure similar to

(define (number-producer send)
  (begin
    (send 1)
    (send 2)
    (send 3)))

where the first time we call number-producer is returns 1, the next time it returns 2, and the third time 3.

The procedure make-producer takes a function of one argument, and returns a coroutine that returns values to a given continuation. Note that we use a box. This is a location in which we can store a value using set-box! and retrieve the value using unbox.

(define (make-producer body)
  (define resume (box #f))
  (lambda (real-send)
    (define send-to (box real-send))
    (define (send value-to-send)
      (set-box! send-to
                (let/cc k
                  (begin
                    (set-box! resume k)
                    ((unbox send-to) value-to-send)))))
    (if (unbox resume)
        ((unbox resume) real-send)
        (body send))))

We can now define number-producer and get

(define number-producer 
  (make-producer 
    (lambda (send) 
      (begin 
        (send 1)
        (send 2)
        (send 3)))))
(define get call/cc)

(get number-producer)

1

(get number-producer)

2

(get number-producer)

3

Space precludes discussion of the derivation of make-producer. Luckily I ripped it straight out of Shriram Krishnamurthi's lecture notes on Continuations, which have far more discussion. They are referenced at the end of this document.

Some languages have special support for coroutines. The Icon language is one. Python added a yield keyword in version 2.x, to allow people to write coroutines. Scheme requires no special support for coroutines, as we have seen.

5.3  Other Uses of Exceptions

Continuations are useful wherever we want to alter the control flow of a computation. Examples include:

• Exceptions, including exceptions that allow you to resume the computation having fixed the problem

• Backtracking as in Prolog

• Non-deterministic programming

• Cooperative Threading

See section 9.1 for links to papers that discuss these uses.

5.4  Continuations vs Goto

Continuations are similar to goto statements, as both allow arbitrary control flow. However there are important differences. Continuations jump to program states, whereas goto statements jump to labelled positions in code. Goto statements can thus jump into non-sensical program states where variables haven't been initialised and so forth. Continuations don't allow this - you can only go back to an already visited program state. In this way continuations are more controlled than goto statements.

6  Continuation Passing Style

Do we really need continuations? We can write in a programming style called continuation passing style (CPS) where every function takes an extra argument, a function to call with its result. In CPS no function ever returns; it always calls its continuation. If we write code in this style we don't need continuations. However it isn't very convenient to write in CPS.

7  Web Applications Using Continuations

Web applications are essentially coroutines between the user and the web server. Lots has already been written about the use of continuations in web applications. To save my wrists I refer you to the existing literature. See section 9.2

8  Implementing Continuations

There are three main implementation strategies for continuations.

1. Heap-allocated continuations. Fast continuations but slow function calls. Used by SIC, the SML/NJ compiler, and the Ruby language.

2. Stack-allocated continuations. Fast function calls but slow continuations. Used by just about every Scheme system that compiles to C.

3. Segmented-stack approaches. Fast function calls and continuations. Used by Chex Scheme.

See section 9.3 for further reading.

9  Further Reading

9.1  General Information

Shriram Krishnamurthi's Lecture Notes on Continuations

Applications of Continuations

ReadScheme Library section on Continuations and Continuation Passing Style

9.2  Web Applications

November 20th, 2002 Meeting: Continuations and Web Apps

PLT NEU Publications

9.3  Implementation Techniques

Representing Control in the Presence of First Class Continuations