Almost all programming languages have means for manipulating the continuation of a computation step. Early imperative languages provided the "goto" feature (in different guises, e.g. setjmp in C), which would force the computation to continue at some designated label. In the 1970s, people supplemented "goto" with additional control constructs that encapsulated frequently repeated control patterns. Simple examples are function returns, loop exits, and loop iteration breaks. Complex examples include Simula 67's coroutines, Icon's generators, Prolog's backtracking mechanism, and threads.

Only a few programming languages provide full, unrestrained access to the continuation of a computation step. Scheme was the first full production system, providing first "catch" and then call-with-current-continuation. Bruce Duba, an Indiana-University–trained Schemer who held a post-doctoral position at Bell Labs, introduced them into SML of New Jersey. Some Smalltalk and Python implementations provide similar access to continuations, though nothing as systematic as Scheme.

Continuations are also used in models of computation including denotational semantics, the Actor model, process calculi, and the lambda calculus. Steve Russell invented the continuation in his second Lisp implementation for the IBM 704, though he did not name it. Christopher Strachey, Christopher F. Wadsworth and John C. Reynolds brought the term continuation into prominence in their work in the field of denotational semantics that makes extensive use of continuations to allow sequential programs to be analysed in terms of functional programming semantics.

These models rely on programmers or semantics engineers to write mathematical functions in the so-called continuation-passing style. This means that each function consumes a function that represents the rest of the computation relative to this function call. To return a value, the function calls this "continuation function" with a return value; to abort the computation it returns a value.

Functional programmers who write their programs in continuation-passing style gain the expressive power to manipulate the flow of control in arbitrary ways. The cost is that they must maintain the invariants of control and continuations by hand, which is a highly complex undertaking.

Example

The Scheme programming language includes the control operator call-with-current-continuation (short: call/cc) which a Scheme program can manipulate the flow of control with:

(define the-continuation #f)

(define (test)

  (let ((i 0))

    ; call/cc calls its first function argument, passing

    ; a continuation variable representing this point in

    ; the program as the argument to that function.

    ;

    ; In this case, the function argument assigns that

    ; continuation to the variable the-continuation.

    ;

    (call/cc (lambda (k) (set! the-continuation k)))

    ;

    ; The next time the-continuation is called, we start here.

    (set! i (+ i 1))

    i))

Defines a function test that sets the-continuation to the future execution state of itself:

> (test)

1

> (the-continuation)

2

> (the-continuation)

3

> (define another-continuation the-continuation)

> (test)

1

> (the-continuation)

2

> (another-continuation)

4

For a gentler introduction to this mechanism, see call-with-current-continuation.

Continuations in Web development

Some of the more popular continuation-aware Web servers are the PLT Scheme Web Server(documentation), the UnCommon Web Framework and Weblocks Web framework for Common Lisp, and the Seaside Web Server for Smalltalk. The Apache Cocoon Web application framework also provides continuations (see the Cocoon manual).

Programming language support

• C: setcontext et al. (UNIX System V and GNU libc)
• C# implementation of iterators in C#
• Factor : callcc0 and callcc1
• Parrot: Continuation PMC; uses continuation passing style for all control flow
• Perl: Coro and Continuity
• Rhino : Continuation
• Ruby: callcc
• Scala: Responder
• Scheme: call-with-current-continuation (commonly shortened to call/cc)
• Smalltalk: Continuation currentDo:, in most modern Smalltalk environments continuations can be implemented without additional VM support.
• Standard ML of New Jersey: SMLofNJ.Cont.callcc
• Unlambda: c, the flow control operation for call with current continuation
• Pico: call(exp()) and continue(aContinuation, anyValue)

In any language which supports closures, it is possible to write programs in continuation passing style and manually implement call/cc. This is a particularly common strategy in Haskell, where it is easy to construct a "continuation passing monad" (for example, the Cont monad and ContT monad transformer in the mtl library).

Kinds of continuations

At one time Gerry Sussman and Drew McDermott thought that using re-invocable continuations (which they called "Hairy Control Structure") was the solution to the AI control structure problems that had originated in Planner. Carl Hewitt et al. developed message passing as an alternative solution in the Actor model. Guy Steele and Gerry Sussman then developed the continuations in Scheme in their attempt to understand the Actor model.

A more limited kind is the escape continuation that may be used to escape the current context to a surrounding one. Many languages which do not explicitly support continuations support exception handling, which is equivalent to escape continuations and can be used for the same purposes. C's setjmp/longjmp are also equivalent: they can only be used to unwind the stack. Escape continuations can also be used to implement tail-call optimization.

Disadvantages

Linguistics

Some phenomena in natural languages can be grasped using the notion of continuation. See Chris Barker's paper Continuations in Natural Language for details. See also Montague grammar.

See also

• call-with-current-continuation
• Closure
• COMEFROM
• Continuation passing style
• Control flow
• Coroutine
• Denotational semantics
• GOTO
• Spaghetti stack

References

• Peter Landin. A Generalization of Jumps and Labels Report. UNIVAC Systems Programming Research. August 1965. Reprinted in Higher Order and Symbolic Computation, 11(2):125-143, 1998, with a foreword by Hayo Thielecke.
• Drew McDermott and Gerry Sussman. The Conniver Reference Manual MIT AI Memo 259. May 1972.
• Daniel Bobrow: A Model for Control Structures for Artificial Intelligence Programming Languages IJCAI 1973.
• Carl Hewitt, Peter Bishop and Richard Steiger. A Universal Modular Actor Formalism for Artificial Intelligence IJCAI 1973.
• Christopher Strachey and Christopher P. Wadsworth. Continuations: a Mathematical semantics for handling full jumps Technical Monograph PRG-11. Oxford University Computing Laboratory. January 1974. Reprinted in Higher Order and Symbolic Computation, 13(1/2):135--152, 2000, with a foreword by Christopher P. Wadsworth.
• John Reynolds. Definitional Interpreters for Higher-Order Programming Languages Proceedings of 25th ACM National Conference, pp. 717-740, 1972. Reprinted in Higher-Order and Symbolic Computation 11(4):363-397, 1998, with a foreword.
• John Reynolds. On the Relation between Direct and Continuation Semantics Proceedings of Second Colloquium on Automata, Languages, and Programming. LNCS Vol. 14, pp. 141-156, 1974.
• Gerald Sussman and Guy Steele. SCHEME: An Interpreter for Extended Lambda Calculus AI Memo 349, MIT Artificial Intelligence Laboratory, Cambridge, Massachusetts, December 1975. Reprinted in Higher-Order and Symbolic Computation 11(4):405-439, 1998, with a foreword.
• Robert Hieb, R. Kent Dybvig, Carl Bruggeman. Representing Control in the Presence of First-Class Continuations Proceedings of the ACM SIGPLAN '90 Conference on Programming Language Design and Implementation, pp. 66-77.
• Will Clinger, Anne Hartheimer, Eric Ost. Implementation Strategies for Continuations Proceedings of the 1988 ACM conference on LISP and Functional Programming, pp. 124-131, 1988. Journal version: Higher-Order and Symbolic Computation, 12(1):7-45, 1999.

External links

• Continuations for Curmudgeons by Sam Ruby
• Teach Yourself Scheme in Fixnum Days by Dorai Sitaram features a nice chapter on continuations.
• Continuations and Stackless Python by Christian Tismer
• On-line proceedings of the Fourth ACM SIGPLAN Workshop on Continuations
• On-line proceedings of the Second ACM SIGPLAN Workshop on Continuations
• Continuation, functions and jumps
• Rhino With Continuations
• Continuations in pure Java from the RIFE web application framework
• Debugging continuations in pure Java from the RIFE web application framework
• PHP implementation of continuations
• Comparison of generators, coroutines, and continuations, source of the above example