Continuation 505189 222457585 2008-06-29T12:58:27Z 66.170.46.244 Dan Friedman didn't invent call/cc {{otheruses}} {{Original research|date=April 2008}} In [[computing]], a '''continuation''' represents the rest of the computation given a point in the computation. Another word for "rest of the computation" is control state, meaning the data structures and code needed to complete a computation. Most languages implement the data structure as a variant of the stack and the code as just a pointer to the current instructions. There are also programming languages that represent the control data as a heap-allocated object. Almost all programming languages have means for manipulating the continuation of a computation step. Early [[Imperative programming|imperative language]]s provided the "[[goto]]" feature (in different guises, e.g. [[setjmp]] in [[C (programming language)|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|Simula 67's]] [[coroutine]]s, [[Icon (programming language)|Icon's]] [[Icon (programming language)#Generators|generators]], [[Prolog]]'s [[backtracking]] mechanism, and [[Thread (computer science)|threads]]. 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" and then via [[call-with-current-continuation]]. Bruce Duba, an [[Indiana University]] trained Schemer who held a post-doctoral position at Bell Labs, introduced them into [[Standard ML|SML]] of New Jersey. Some [[Smalltalk]] and [[Python (programming language)|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)|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: <source lang="scheme"> (define theContinuation #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 theContinuation. ; (call/cc (lambda (k) (set! theContinuation k))) ; ; The next time theContinuation is called, we start here. (set! i (+ i 1)) i)) </source> Defines a function <code>test</code> that sets <code>theContinuation</code> to the future execution state of itself: <code> > (test) 1 > (theContinuation) 2 > (theContinuation) 3 > (define anotherContinuation theContinuation) > (test) 1 > (theContinuation) 2 > (anotherContinuation) 4 </code> For a gentler introduction to this mechanism, see [[call-with-current-continuation]]. ==Continuations in Web development== One area that has seen practical use of continuations is in [[Web programming]].[http://readscheme.org/xml-web/][http://www.double.co.nz/pdf/continuations.pdf] The use of continuations shields the programmer from the [[stateless server|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. <cite>[http://www.double.co.nz/pdf/inverting-back-the-inversion.pdf Inverting back the inversion]</cite> is a paper that provides a good introduction to continuations applied to web programming. Some of the more popular continuation-aware [[Web server]]s are the [http://download.plt-scheme.org/doc/372/html/web-server/ PLT Scheme Web Server(documentation)], the [http://common-lisp.net/project/ucw UnCommon Web Framework] and [http://common-lisp.net/project/cl-weblocks/ Weblocks Web framework] for [[Common Lisp]], and the [[Seaside (software)|Seaside Web Server]] for [[Smalltalk]]. The [[Apache Cocoon]] [[Web application framework]] also provides continuations (see the [http://cocoon.apache.org/2.1/userdocs/flow/continuations.html Cocoon manual]). ==Programming language support== Many programming languages exhibit such a feature under various names; specifically: *[[C (programming language)|C]]: <code>[[setcontext]]</code> et al. ([[UNIX System V]] and [[GNU]] libc) *[[Factor programming language|Factor]] : <code>callcc0</code> and <code>callcc1</code> *[[Parrot virtual machine|Parrot]]: <code>Continuation</code> PMC; uses [[continuation passing style]] for all control flow *[[Perl]]: Coro and Continuity *[[Rhino (JavaScript engine)|Rhino]] : <code>Continuation</code> *[[Ruby programming language|Ruby]]: <code>callcc</code> *[[Scala (programming language)|Scala]]: <code>Responder</code> *[[Scheme (programming language)|Scheme]]: <code>[[call-with-current-continuation]]</code> (commonly shortened to <code>call/cc</code>) *[[Smalltalk programming language|Smalltalk]]: <code>Continuation currentDo:</code>, in most modern Smalltalk environments continuations can be implemented without additional VM support. *[[SML programming language|Standard ML of New Jersey]]: <code>SMLofNJ.Cont.callcc</code> *[[Unlambda]]: <code>c</code>, the flow control operation for call with current continuation *[[Pico (programming language)|Pico]]: <code>call(exp())</code> and <code>continue(aContinuation, anyValue)</code> <!-- Please do not re-add the following entries: * Python: generators are not continuations * Stackless Python: provides tasklets/coroutines only; first-class continuations were a target for the first implementation, but dropped --> In any language which supports [[closure (computer science)|closures]], it is possible to write programs in [[continuation passing style]] and manually implement call/cc. This is a particularly common strategy in [[Haskell (programming language)|Haskell]], where it is easy to construct a "continuation passing [[Monad (functional programming)|monad]]" (for example, the <code>Cont</code> monad and <code>ContT</code> monad transformer in the <code>mtl</code> library). ==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" is too easily confused with its use in discussions of [[Thread (computer science)|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 programming language|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 (programming language)|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 <code>[[setjmp/longjmp]]</code> are also equivalent: they can only be used to unwind the stack. Escape continuations can also be used to implement [[tail recursion|tail-call optimization]]. ==Disadvantages== Continuations are the functional expression of the [[GOTO]] statement, and the same [http://www.acm.org/classics/oct95/ 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 continuation. See Chris Barker's paper [http://www.cs.bham.ac.uk/~hxt/cw04/barker.pdf Continuations in Natural Language] for details. See also [[Montague grammar]]. ==See also== *[[call-with-current-continuation]] *[[Closure (computer science)|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== *[http://www.intertwingly.net/blog/2005/04/13/Continuations-for-Curmudgeons Continuations for Curmudgeons] by Sam Ruby *[http://www.ccs.neu.edu/home/dorai/t-y-scheme/t-y-scheme-Z-H-15.html#node_chap_13 Teach Yourself Scheme in Fixnum Days] by Dorai Sitaram features a nice chapter on continuations. *[http://www.stackless.com/spcpaper.htm Continuations and Stackless Python] by Christian Tismer *[http://www.cs.bham.ac.uk/~hxt/cw04/cw04-program.html On-line proceedings of the Fourth ACM SIGPLAN Workshop on Continuations] *[http://www.brics.dk/~cw97/ On-line proceedings of the Second ACM SIGPLAN Workshop on Continuations] *[http://www.cs.bham.ac.uk/~hxt/research/Logiccolumn8.pdf Continuation, functions and jumps] *[http://wiki.apache.org/cocoon/RhinoWithContinuations Rhino With Continuations] *[http://rifers.org/wiki/display/RIFE/Web+continuations Continuations in pure Java] from the [[RIFE]] web application framework *[http://rifers.org/theater/debugging_continuations Debugging continuations in pure Java] from the [[RIFE]] web application framework * [http://www.3kings.dk/code/phpcontinuation-0_1.zip PHP implementation of continuations] * [http://mail.python.org/pipermail/python-dev/1999-July/000467.html Comparison of generators, coroutines, and continuations, source of the above example] [[Category:Control flow]] [[Category:Articles with example Scheme code]] [[cs:Continuation]] [[de:Continuation]] [[fr:Continuation]] [[it:Continuazione]] [[ja:継続]] [[ru:Продолжение]] [[uk:Продовження (програмування)]]