Lecture
Continuation is an abstract representation of the state of a program at a particular moment, which can be saved and used to return to that state. Continuations contain all the information needed to continue program execution from a particular point; the state of global variables is usually not saved, but for functional languages this is immaterial (for example, selective saving and restoring of the values of global objects in Scheme is achieved by a separate mechanism, dynamic-wind). Continuations are similar to the goto of BASIC or the setjmp and longjmp macros in C, since they also allow jumping to any place in the program. But continuations, unlike goto, allow jumping only to a program location with a particular state that must be saved in advance, whereas goto allows jumping to a program location with uninitialized variables.
The first language to implement the concept of continuations was Scheme; later, built-in support for continuations appeared in a number of other languages.
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 the corresponding procedures into continuation-passing style, although he did not use that name, and his intention was to simplify the program and thereby make its result cleaner.
Christopher Strachey, Christopher P. Wadsworth and John C. Reynolds brought the term "continuation" to prominence in their work on denotational semantics, which makes extensive use of continuations to allow sequential programs to be analyzed in terms of functional programming semantics.
Steve Russell invented the continuation in his second Lisp implementation for the IBM 704, although he did not name it.
Reynolds (1993) gives a complete history of the discovery of continuations.
Formally, callcc is a higher-order function that makes it possible to abstract the dynamic context of an existing function as another function, which is called a "continuation".
More intuitively, a continuation is "the entire remaining part of the program from a given point", or "a function that never returns control to the point of its call" . In functional programming courses, the explanation of the concept of a continuation often boils down to "an extension (complication) of the concept of a coroutine", but in a didactic sense such an explanation is considered useless . The reason the concept is hard to explain is that continuations are in fact an alternative foundation for the notion of "behavior" ("call" in the broadest sense), that is, they carry a different semantic model, and in this sense the initial transition from "ordinary" functional programming to programming with intensive use of continuations can be compared to the initial transition from imperative programming to functional programming.
Continuations provide a mathematical foundation for the entire order of program execution, from goto and loops to recursion, exceptions, generators, coroutines and backtracking . As a consequence, they make it possible to implement all of these elements in a language by means of a single construct.
First-class continuations are the ability of a language to fully control the order in which instructions are executed. They can be used to jump to the function that invoked 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 process image - 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. :-)
In this description, the sandwich is part of the program data (for example, an object on the heap), and instead of calling a "make a sandwich" routine and then returning, the person calls a "make a sandwich with the current continuation" routine, which creates the sandwich and then continues from where execution was stopped.
Scheme was the first full production system (1969-1970) to provide first "catch" , and then call/cc. Bruce Duba introduced call/cc into SML.
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 semanticists writing 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 that function call. To return a value, a function calls this "continuation function" with the 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 control flow in arbitrary ways. The price is that they must maintain the control and continuation invariants by hand, which can be very difficult (but see "Continuation-passing style" below).
Continuation-passing style (CPS) is a programming style in which control is transferred through the mechanism of continuations. CPS was first introduced by Gerald Jay Sussman and Guy Steele Jr. , simultaneously with the Scheme language.
A program in the "classical style" can often be rewritten in continuation-passing style. For example, consider the task of computing the hypotenuse of a right triangle, with "classical" code in Haskell:
pow2 :: Float -> Float pow2 a = a ** 2 add :: Float -> Float -> Float add a b = a + b pyth :: Float -> Float -> Float pyth a b = sqrt (add (pow2 a) (pow2 b))
one can add an argument of type F, where F stands for a function from the return value of the original function to an arbitrary type x, and make the return value this arbitrary type x:
pow2' :: Float -> (Float -> a) -> a pow2' a cont = cont (a ** 2) add' :: Float -> Float -> (Float -> a) -> a add' a b cont = cont (a + b) -- the types a -> (b -> c) and a -> b -> c are equivalent, so a CPS function can be -- regarded as a higher-order function of one argument sqrt' :: Float -> ((Float -> a) -> a) sqrt' a = \cont -> cont (sqrt a) pyth' :: Float -> Float -> (Float -> a) -> a pyth' a b cont = pow2' a (\a2 -> pow2' b (\b2 -> add' a2 b2 (\anb -> sqrt' anb cont)))
In the function pyth', the square of a is computed, and a function (a lambda expression) that takes as its single argument a squared is passed as the continuation. All the subsequent intermediate values are then computed in the same way. To carry out the computation, a function of one argument must be passed as the continuation, for example the function id, which returns any value passed to it. Thus the expression pyth' 3 4 id is equivalent to 5.0.
The standard Haskell library module Control.Monad.Cont contains the type Cont, which makes it possible to use CPS functions in a monad. The function pyth' will look as follows:
pow2_m :: Float -> Cont a Float pow2_m a = return (a ** 2) -- the cont function lifts ordinary CPS functions into the monad pyth_m :: Float -> Float -> Cont a Float pyth_m a b = do a2 <- pow2_m a b2 <- pow2_m b anb <- cont (add' a2 b2) r <- cont (sqrt' anb) return r
This module also contains the function callCC, which has the type MonadCont m => ((a -> m b) -> m a) -> m a. The type shows that it takes as its single argument a function which in turn also takes a single argument, a function that aborts further computation. For example, we can abort further computation if at least one of the arguments is negative:
pyth_m :: Float -> Float -> Cont a Float pyth_m a b = callCC $ \exitF -> do when (b < 0 || a < 0) (exitF 0.0) -- when :: Applicative f => Bool -> f () -> f () a2 <- pow2_m a b2 <- pow2_m b anb <- cont (add' a2 b2) r <- cont (sqrt' anb) return r
Examples of CPS in Scheme:
|
Direct style |
Continuation passing style |
|---|---|
(define (pyth x y) (sqrt (+ (* x x) (* y y)))) |
(define (pyth& x y k) (*& x x (lambda (x2) (*& y y (lambda (y2) (+& x2 y2 (lambda (x2py2) (sqrt& x2py2 k)))))))) |
(define (factorial n) (if (= n 0) 1 ; NOT tail-recursive (* n (factorial (- n 1))))) |
(define (factorial& n k) (=& n 0 (lambda (b) (if b ; the continuation grows (k 1) ; in the recursive call (-& n 1 (lambda (nm1) (factorial& nm1 (lambda (f) (*& n f k))))))))) |
(define (factorial n) (f-aux n 1)) (define (f-aux n a) (if (= n 0) a ; tail-recursive (f-aux (- n 1) (* n a)))) |
(define (factorial& n k) (f-aux& n 1 k)) (define (f-aux& n a k) (=& n 0 (lambda (b) (if b ; the continuation is preserved (k a) ; in the recursive call (-& n 1 (lambda (nm1) (*& n a (lambda (nta) (f-aux& nm1 nta k))))))))) |
In "pure" CPS there are in fact no continuations as such - every call is a tail call. If the language does not guarantee tail call optimization (TCO), then with each nested call of callcc both the continuation itself and the call stack grow. This is usually undesirable, but is sometimes used in interesting ways (for example, in the Chicken Scheme compiler[en]). Using TCO and CPS strategies together makes it possible to eliminate the dynamic stack from an executable program entirely. A number of functional language compilers work exactly this way, for example the SML/NJ compiler for the Standard ML language.
There are several kinds of continuations. The most common are undelimited continuations, implemented with the call/cc function or its analogues. Such continuations really do represent the state of the whole program (or of a single thread of it) at a particular moment. Invoking such a continuation is unlike calling a function, because it corresponds to a "jump" to the saved program state and returns no value; such a continuation usually cannot be invoked more than once. Delimited continuations abstract the dependence of the result of some block of the program on the result of some subexpression of that block. In a certain sense they correspond to a segment of the call stack rather than the whole stack. Such continuations can be used as functions, invoked multiple times, and so on. They are abstracted with the shift/reset mechanism: reset wraps the outer block, and shift acts like call/cc, but receives as its argument not the global continuation but a delimited one - the dependence of the value of the reset block on the value at the position of the shift block. There are also other varieties, for example prompt/control.
One area of practical use for continuations is web programming. Using 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 structure of the program, which leads to code based on a model that is very poorly suited to expressing computational problems. Continuations thus allow code that has the useful properties associated with inversion of control while avoiding its problems. Inverting the Inversion of Control, or Continuations versus Page-Centric Programming is an article that is a good introduction to continuations applied to web programming.
Some of the most popular web servers and frameworks that support continuations are the Racket Web Server, UnCommon Web Framework and the Weblocks Web framework for Common Lisp, the Seaside framework for Smalltalk, Ocsigen / Eliom for OCaml, Continuity for Perl, Wee for Ruby, the Tales Framework for Fantom and the Nagare framework for Python, Wt for C++, and MFlow for Haskell. The Apache Cocoon web application framework also provides continuations (see the Cocoon flowscript).
Many programming languages provide this capability under various names, for example:
call/cc (short for call-with-current-continuation);SMLofNJ.Cont.callcc, also implemented in Concurrent ML;setcontext and analogues (UNIX System V and GNU libc);callcc;Continuation currentDo:; in most modern implementations, continuations can be implemented in pure Smalltalk without requiring special support in the virtual machine;await and yield;Continuation;callCC (in the Control.Monad.Cont module);callcc0 and callcc1;yield;_continuation.continulet;suspend, on the basis of which async, await, yield and some other coroutine constructs are implemented.yield;yield return and await.In any language that supports closures, it is possible to write programs in continuation-passing style and to implement call/cc by hand. In particular, this is accepted practice in Haskell, where it is easy to build "continuation-passing monads" (for example, the Cont monad and the ContT monad transformer of the mtl library).
Support for continuations varies greatly. A programming language supports re-entrant continuations if a continuation can be invoked repeatedly (even after it has already returned). Re-entrant continuations were introduced by Peter J. Landin using his J operator (for "jump"), which could transfer control back into the middle of a procedure call. Re-entrant continuations are also called "returnable" in Racket. However, this use of the term "re-entrant" can easily be confused with its use in discussions of multithreading.
A more limited kind is the escape continuation, which can be used to escape from the current context to a surrounding one. Many languages that do not explicitly support continuations support exception handling, which is equivalent to escape continuations and can be used for the same purposes. C setjmp/longjmp are also equivalent: they can only be used to unwind the stack. Escape continuations can also be used to implement tail call elimination.
One generalization of continuations is delimited continuations. Continuation operators such as call/cc capture all of the remaining computation at a given point in the program, and offer no way to limit that capture. Delimited continuation operators solve this problem by providing two separate control mechanisms: a prompt, which delimits the continuation operation, and a reification operator such as shift or control. Continuations recorded using delimited operators therefore represent only a portion of the program context.
Continuations are the functional expression of the GOTO statement, and the same caveats apply. Although they are a sensible option in some special cases, such as web programming, the use of continuations can lead to 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. [ citation needed ] The external links below illustrate the concept in more detail.
In the paper "Continuations and the Nature of Quantification", Chris Barker introduced the "continuation hypothesis", according to which
some linguistic expressions (in particular, QNPs [quantificational noun phrases]) have denotations that manipulate their own continuations. [10]
Barker argued that this hypothesis can be used to explain phenomena such as the duality of NP meaning (for example, the fact that the QNP "everyone" behaves very differently from the non-quantificational noun phrase "Bob" in contributing to the meaning of a sentence such as "Alice sees [Bob/everyone]"), scope displacement (for example, "a raindrop fell on every car" is usually interpreted as
and not as 
) and scope ambiguity (a sentence such as "someone saw everyone" can be ambiguous between
and 
). He also observed that this idea is in some ways 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 restricted 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 subject of ongoing research.
Comments