Continuation: Difference between revisions

Content deleted Content added

Inline

Revision as of 09:13, 19 July 2009

In computing and programming, a continuation is an abstract representation of the control state, or the "rest of computation" or "rest of code to be executed". This is closely linked with what part of the program you are in: which function and which line is being executed. The "current continuation" or "continuation of the computation step" are the instructions that will be executed after the current line of code is executed.

The term continuations can also be used to refer to first-class continuations, which are constructs that give a programming language the ability to save the execution state at any point and return to that point at a later point in the program.

Programs must allocate space in memory for the variables its functions use. Most programming languages use a call stack for storing the variables needed because it allows for fast and simple allocating and automatic deallocation of memory. There are also programming languages that use a heap for this, which allows for flexibility but with a higher cost for allocating and deallocating memory. These two different implementations both have benefits and drawbacks in the context of continuations [1].

Almost all languages have a means for manipulating the order of execution steps (i.e. manipulating the continuation of a computation step). The goto is the most basic form of this. Control structures like if statements, loops, return statements, break statements, and exit are more structured (and limited) ways to manipulate the order of executing instructions and are essentially limited goto statements.

More complex constructs exist as well. For example in C, setjmp can be used to jump from the middle of one function to another function, provided the second function is lower on the stack (if it is waiting for the first function to return, possibly among others). Other more complex examples include coroutines in Simula 67, tasklets in Stackless Python, generators in Icon and Python, continuations in Scala (starting in 2.8), Fibers in Ruby (starting in 1.9.1), the backtracking mechanism in Prolog, and threads.

History

The earliest description of continuations was made by Adriaan van Wijngaarden in September 1964. Wijngaarden spoke at the IFIP Working Conference on Formal Language Description Languages held in Baden bei Wien, Austria. As part of a formulation for an Algol 60 preprocessor, he called for a transformation of proper procedures into continuation-passing style. ^[1]

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.^[1]

Steve Russell invented the continuation in his second Lisp implementation for the IBM 704, though he did not name it. [2]

First-class continuations

First-class continuations are a language's ability to completely control the execution order of instructions. They can be used to jump to a function that produced the call to the current function, or to a function that has previously exited. One can think of a first-class continuation as saving the state of the program. However, it is important to note that true first-class continuations do not save program data, only the execution context. This is illustrated by the "continuation sandwich" description:

Say you're in the kitchen in front of the refrigerator, thinking about a sandwich. You take a continuation right there and stick it in your pocket. Then you get some turkey and bread out of the refrigerator and make yourself a sandwich, which is now sitting on the counter. You invoke the continuation in your pocket, and you find yourself standing in front of the refrigerator again, thinking about a sandwich. But fortunately, there's a sandwich on the counter, and all the materials used to make it are gone. So you eat it. :-)

^{[citation needed]}

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"^[1] and then call/cc. Bruce Duba introduced call/cc into SML. 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 lambda calculus. 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) with which a Scheme program can manipulate the flow of control:

 (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) ; stores the current continuation (which will print 4 next) away
> (test) ; resets the-continuation
1
> (the-continuation)
2
> (another-continuation) ; uses the previously stored continuation
4

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

Programming language support

Many programming languages exhibit first-class continuations under various names; specifically:

C: setcontext et al. (UNIX System V and GNU libc)
Factor: callcc0 and callcc1
Haskell: Control.Monad.Cont (mtl) and MonadLib (monadLib)
Icon, Unicon : create, suspend, @ operator: coexpressions
Parrot: Continuation PMC; uses continuation passing style for all control flow
Perl: Coro and Continuity
Pico: call(exp()) and continue(aContinuation, anyValue)
JavaScript 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

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).

Continuations in Web development

One area that has seen practical use of continuations is in Web programming.[3][4] The use of continuations shields the programmer from the stateless nature of the HTTP protocol. In the traditional model of web programming, the lack of state is reflected in the program's structure, leading to code constructed around a model that lends itself very poorly to expressing computational problems. Thus continuations enable code that has the useful properties associated with inversion of control, while avoiding its problems. Inverting back the inversion is a paper that provides a good introduction to continuations applied to web programming.

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, the Seaside framework for Smalltalk and Ocsigen/Eliom for OCaml. The Apache Cocoon Web application framework also provides continuations (see the Cocoon manual).

Kinds of continuations

Support for continuations varies widely. A programming language supports re-invocable continuations if a continuation may be invoked repeatedly (even after it has already returned). Re-invocable continuations were introduced by Peter J. Landin using his J (for Jump) operator that could transfer the flow of control back into the middle of a procedure invocation. Re-invocable continuations have also been called "re-entrant" in the MzScheme programming language. However this use of the term "re-entrant" can be easily confused with its use in discussions of multithreading.

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

Continuations are the functional expression of the GOTO statement, and the same caveats apply. While many believe that they are a sensible option in some special cases such as web programming, use of continuations can result in code that is difficult to follow. In fact, the esoteric programming language Unlambda includes call-with-current-continuation as one of its features solely because of its resistance to understanding. The external links below illustrate the concept in more detail.

Linguistics

Some phenomena in natural languages can be grasped using the notion of delimited continuation.

Informally speaking, continuations can account for the similarity between such sentences as "Alice sees Bob"—formally, ${\mbox{sees}}\left({\mbox{Alice}},{\mbox{Bob}}\right)$ —and "Alice sees everyone", i.e. ${\mbox{sees}}\left({\mbox{Alice}},everyone\right)\rightsquigarrow \forall {x}\,{\mbox{sees}}\left({\mbox{Alice}},x\right)$ .

See Chris Barker's paper Continuations in Natural Language for details. See also Montague grammar.

References

^ ^a ^b ^c John C. Reynolds. "The discoveries of continuations". Lisp and Symbolic Computation, 6(3-4):233–248, 1993.

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
Comparison of generators, coroutines, and continuations, source of the above example

[history_of_continuations-1] John C. Reynolds. "The discoveries of continuations". Lisp and Symbolic Computation, 6(3-4):233–248, 1993.

[1]

@@ Line 23: / Line 23: @@
 <blockquote>
 ''Say you're in the kitchen in front of the refrigerator, thinking about a sandwich. You take a continuation right there and stick it in your pocket. Then you get some turkey and bread out of the refrigerator and make yourself a sandwich, which is now sitting on the counter. You invoke the continuation in your pocket, and you find yourself standing in front of the refrigerator again, thinking about a sandwich. But fortunately, there's a sandwich on the counter, and all the materials used to make it are gone. So you eat it. :-)''
-</blockquote>
+</blockquote>{{fact}}<!-- need to attribute quote -->
 Only a few programming languages provide full, unrestrained access to the continuation of a computation step. [[Scheme (programming language)|Scheme]] was the first full production system, providing first "catch"<ref name="history_of_continuations"/> and then [[call-with-current-continuation|call/cc]]. Bruce Duba introduced call/cc into [[Standard ML|SML]]. Some [[Smalltalk]] and [[Python (programming language)|Python]] implementations provide similar access to continuations, though nothing as systematic as Scheme.