Product Code Database
In computer science, a continuation is an abstract representation of the Control flow of a computer program. A continuation implements (reifies) the program control state, i.e. the continuation is a data structure that represents the computational process at a given point in the process's execution; the created data structure can be accessed by the programming language, instead of being hidden in the Run-time system. Continuations are useful for encoding other control mechanisms in programming languages such as exceptions, generators, , and so on.
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.
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.
Steve Russell 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 invented the continuation in his second Lisp implementation for the IBM 704, though he did not name it.
gives a complete history of the discovery of continuations.
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. :-)
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" and then call/cc. Bruce Duba introduced call/cc into Standard ML.
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 can be a highly complex undertaking (but see 'continuation-passing style' below).
More complex constructs for which "continuations provide an elegant description" also exist. For example, in C, longjmp can be used to jump from the middle of one function to another, provided the second function lies deeper in the stack (if it is waiting for the first function to return, possibly among others). Other more complex examples include in Simula, Lua, and Perl; 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; monads in functional programming; and threads.
(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.
;;; 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
...
In any language which supports closures and tail recursion, it is possible to write programs in continuation-passing style and manually implement call/cc. (In continuation-passing style, call/cc becomes a simple function that can be written with lambda calculus.) 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). The support for tail recursion is needed because in continuation-passing style no function ever returns; all calls are tail calls.
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 stack unwinding. Escape continuations can also be used to implement tail call elimination.
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.
some linguistic expressions (in particular, QNPs quantificational) have denotations that manipulate their own continuations.Chris Barker, Continuations and the nature of quantification, 2002 Natural Language Semantics 10:211-242.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 Montague grammar 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.See for example Chris Barker, Continuations in Natural Language (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).
|
|
