Continuation
This article needs additional citations for verification. (July 2010) |
In
The "current continuation" or "continuation of the computation step" is the continuation that, from the perspective of running code, would be derived from the current point in a program's execution. 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, possibly multiple times.
History
The earliest description of continuations was made by
Christopher Strachey, Christopher P. 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[2] invented the continuation in his second Lisp implementation for the IBM 704, though he did not name it.[3]
Reynolds (1993) gives a complete history of the discovery of continuations.
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 execution state of the program. It is important to note that true first-class continuations do not save program data – unlike a
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. :-)[4]
In this description, the sandwich is part of the program data (e.g., an object on the heap), and rather than calling a "make sandwich" routine and then returning, the person called a "make sandwich with current continuation" routine, which creates the sandwich and then continues where execution left off.
Scheme was the first full production system providing first "catch"[1] and then call/cc. Bruce Duba introduced call/cc into SML.
Continuations are also used in models of computation including
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 can be a highly complex undertaking (but see 'continuation-passing style' below).
Uses
Continuations simplify and clarify the implementation of several common design patterns, including coroutines/green threads and exception handling, by providing the basic, low-level primitive which unifies these seemingly unconnected patterns. Continuations can provide elegant solutions to some difficult high-level problems, like programming a web server that supports multiple pages, accessed by the use of the forward and back buttons and by following links. The Smalltalk Seaside web framework uses continuations to great effect, allowing one to program the web server in procedural style, by switching continuations when switching pages.
More complex constructs for which "continuations provide an elegant description"
Examples
The Scheme programming language includes the control operator call-with-current-continuation (abbreviated as: 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))
Using the above, the following code block defines a function test
that sets the-continuation
to the future execution state of itself:
> (test)
1
> (the-continuation)
2
> (the-continuation)
3
> ; stores the current continuation (which will print 4 next) away
> (define another-continuation the-continuation)
> (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.
Coroutines
This example shows a possible usage of continuations to implement
;;; A naive queue for thread scheduling.
;;; It holds a list of continuations "waiting to run".
(define *queue* '())
(define (empty-queue?)
(null? *queue*))
(define (enqueue x)
(set! *queue* (append *queue* (list x))))
(define (dequeue)
(let ((x (car *queue*)))
(set! *queue* (cdr *queue*))
x))
;;; This starts a new thread running (proc).
(define (fork proc)
(call/cc
(lambda (k)
(enqueue k)
(proc))))
;;; This yields the processor to another thread, if there is one.
(define (yield)
(call/cc
(lambda (k)
(enqueue k)
((dequeue)))))
;;; This terminates the current thread, or the entire program
;;; if there are no other threads left.
(define (thread-exit)
(if (empty-queue?)
(exit)
((dequeue))))
The functions defined above allow for defining and executing threads through cooperative multitasking, i.e. threads that yield control to the next one in a queue:
;;; The body of some typical Scheme thread that does stuff:
(define (do-stuff-n-print str)
(lambda ()
(let loop ((n 0))
(format #t "~A ~A\n" str n)
(yield)
(loop (+ n 1)))))
;;; Create two threads, and start them running.
(fork (do-stuff-n-print "This is AAA"))
(fork (do-stuff-n-print "Hello from BBB"))
(thread-exit)
The previous code will produce this output:
This is AAA 0 Hello from BBB 0 This is AAA 1 Hello from BBB 1 This is AAA 2 Hello from BBB 2 ...
Implementation
A program must allocate space in memory for the variables its functions use. Most programming languages use a
Programming language support
Many programming languages exhibit first-class continuations under various names; specifically:
- Common Lisp: cl-cont. One can also use custom macros
- VB.NET:
async
andawait
: "sign up the rest of method as the continuation, and then return to your caller immediately; the task will invoke the continuation when it completes." Asynchronous Programming for C# - Factor:
callcc0
andcallcc1
- Haskell: The Continuation monad in
Control.Monad.Cont
- Haxe: haxe-continuation
- Icon, Unicon :
create, suspend, @
operator: coexpressions - Java: Lightwolf javaflow (requires bytecode manipulation at runtime or compile time)
- Kotlin :
Continuation
- JavaScript Rhino :
Continuation
- Parrot:
Continuation
PMC; uses continuation-passing style for all control flow - Perl: Coro and Continuity
- Pico:
call(exp())
andcontinue(aContinuation, anyValue)
- Python: PyPy's
_continuation.continulets
- Racket:
call-with-current-continuation
(commonly shortened tocall/cc
) - Ruby:
callcc
- Scala:
scala.util.continuations
providesshift
/reset
- Scheme:
call-with-current-continuation
(commonly shortened tocall/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
In Web development
One area that has seen practical use of continuations is in
Kinds
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
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
One generalization of continuations are delimited continuations. Continuation operators like call/cc
capture the entire remaining computation at a given point in the program and provide no way of delimiting this capture. Delimited continuation operators address this by providing two separate control mechanisms: a prompt that delimits a continuation operation and a reification operator such as shift
or control
. Continuations captured using delimited operators thus only represent a slice of the program context.
Disadvantages
Continuations are the functional expression of the
Linguistics
In "Continuations and the nature of quantification", Chris Barker introduced the "continuation hypothesis", that
some linguistic expressions (in particular, QNPs [quantificational noun phrases]) have denotations that manipulate their own continuations.[12]
Barker argued that this hypothesis could be used to explain phenomena such as duality of NP meaning (e.g., the fact that the QNP "everyone" behaves very differently from the non-quantificational noun phrase "Bob" in contributing towards the meaning of a sentence like "Alice sees [Bob/everyone]"), scope displacement (e.g., that "a raindrop fell on every car" is interpreted typically as rather than as ), and scope ambiguity (that a sentence like "someone saw everyone" may be ambiguous between and ). He also observed that this idea is in a way just a natural extension of Richard Montague's approach in "The Proper Treatment of Quantification in Ordinary English" (PTQ), writing that "with the benefit of hindsight, a limited form of continuation-passing is clearly discernible at the core of Montague’s (1973) PTQ treatment of NPs as generalized quantifiers".
The extent to which continuations can be used to explain other general phenomena in natural language is a topic of current research.[13]
See also
- Call-with-current-continuation
- Closure
- COMEFROM
- Continuation-passing style
- Control flow
- Coroutine
- Delimited continuation
- Denotational semantics
- GOTO
- Spaghetti stack
- Dependency Injection.
References
- ^ a b c d Reynolds 1993
- ^ S.R. Russell noticed that eval could serve as an interpreter for LISP, promptly hand coded it, and we now had a programming language with an interpreter. —John McCarthy, History of LISP
- ^ "Steve "Slug" Russell". Computer History.
- ^ Palmer, Luke (June 29, 2004). "undo()? ("continuation sandwich" example)". perl.perl6.language (newsgroup). Retrieved 2009-10-04.
- ^ Haynes, C. T., Friedman, D. P., and Wand, M. 1984. Continuations and coroutines. In Proceedings of the 1984 ACM Symposium on LISP and Functional Programming (Austin, Texas, United States, August 06–08, 1984). LFP '84. ACM, New York, NY, 293-298.
- ^ "Call with current continuation for C programmers". Community-Scheme-Wiki. 12 October 2008.
- ^ "Reading list on XML and Web Programming". Archived from the original on 2010-06-14. Retrieved 2006-08-03.
- ^ "Web Programming with Continuations" (PDF). Archived from the original (PDF) on 2012-09-05. Retrieved 2012-09-05.
- ^ Christian.Queinnec (2003) Inverting back the inversion of control or, Continuations versus page-centric programming
- ^ Quigley, John (September 2007). "Computational Continuations" (PDF). p. 38.
- ^ Madore, David. "The Unlambda Programming Language". www.madore.org. Retrieved 19 June 2021.
- ^ Chris Barker, Continuations and the nature of quantification, 2002 Natural Language Semantics 10:211-242.
- ^ See for example Chris Barker, Continuations in Natural Language Archived 2007-08-24 at the Wayback Machine (Continuations Workshop 2004), or Chung-chieh Shan, Linguistic Side Effects (in "Direct compositionality, ed. Chris Barker and Pauline Jacobson, pp. 132-163, Oxford University Press, 2007).
Further reading
- 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.
- 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 C. 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 C. 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.
- Reynolds, John C. (1993). "The discoveries of continuations" (PDF). LISP and Symbolic Computation. 6 (3/4): 233–248.
- 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.
- Christian Queinnec. Inverting back the inversion of control or, Continuations versus page-centric programming SIGPLAN Notices 38(2), pp. 57–64, 2003.
External links
- ICFP.
- 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 Archived 2010-12-02 at the Wayback Machine
- On-line proceedings of the Second ACM SIGPLAN Workshop on Continuations
- Continuation, functions and jumps Archived 2010-12-02 at the Wayback Machine
- http://okmij.org/ftp/continuations/ by Oleg Kiselyov
- https://wiki.haskell.org/Continuations[permanent dead link]
- Rhino With Continuations
- Continuations in pure Java from the RIFE web application framework
- Debugging continuations in pure Java Archived 2021-05-16 at the Wayback Machine from the RIFE web application framework
- Comparison of generators, coroutines, and continuations, source of the above example