February 13, 2003
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.
To use continuations in DrScheme you much change your language setting to one of the languages listed under the PLT tab.
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
At the time when we are evaluating
(+ 2 3) the continuation
(+ 1 #), where the
# indicates that the
continuation is waiting for a value in that place to complete its
Scheme allows us to capture the current continuation using
call-with-current-continuation often abbreviated to
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 ...)
What is the continuation that is captured below? What is the value the program?
(+ 1 (let/cc k (k 5)))
(+ 1 (let/cc k 5))
where we don't call the captured continuation?
Lets consider a slightly more involved example:
(+ 1 (let/cc k (- 5 (k 5))))
(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)
6. However if we substitute in the continuation, we get
(+ 1 (- 5 ((lambda (#) (+ 1 #)) 5)))
which evaluates to
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
lambda^ we can use substitution to write
(+ 1 (- 5 ((lambda^ (#) (+ 1 #)) 5)))
which evalutes to
6 as it should do.
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))))
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
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
(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
(define number-producer (make-producer (lambda (send) (begin (send 1) (send 2) (send 3))))) (define get call/cc)
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.
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
See section 9.1 for links to papers that discuss these uses.
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.
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.
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
There are three main implementation strategies for continuations.
Heap-allocated continuations. Fast continuations but slow function calls. Used by SIC, the SML/NJ compiler, and the Ruby language.
Stack-allocated continuations. Fast function calls but slow continuations. Used by just about every Scheme system that compiles to C.
Segmented-stack approaches. Fast function calls and continuations. Used by Chex Scheme.
See section 9.3 for further reading.
Shriram Krishnamurthi's Lecture Notes on Continuations
Applications of Continuations
ReadScheme Library section on Continuations and Continuation Passing Style
November 20th, 2002 Meeting: Continuations and Web Apps
PLT NEU Publications
Representing Control in the Presence of First Class Continuations