Continuation
In computer science, a continuation is an abstract representation of the control state of a computer program. A continuation implements 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 runtime environment. Continuations are useful for encoding other control mechanisms in programming languages such as exceptions, generators, coroutines, 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.
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, though he did not use this name, and his intention was to simplify a program and thus make its result more clear.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 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.
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. 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, 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 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 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.
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" 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. Other more complex examples include coroutines in Simula 67, Lua, and Perl; tasklets in Stackless Python; generators in Icon and Python; continuations in Scala ; fibers in Ruby ; the backtracking mechanism in Prolog; monads in functional programming; and threads.
Examples
The Scheme programming language includes the control operator call-with-current-continuation with which a Scheme program can manipulate the flow of control:)
; 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.
;
))
;
; The next time the-continuation is called, we start here.
i))
Using the above, the following code block defines a function
test that sets the-continuation to the future execution state of itself:>
1
>
2
>
3
> ; stores the current continuation away
>
> ; resets the-continuation
1
>
2
> ; 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 coroutines as separate threads.;;; A naive queue for thread scheduling.
;;; It holds a list of continuations "waiting to run".
)
)
)
x))
;;; This starts a new thread running.
)))
;;; This yields the processor to another thread, if there is one.
))))
;;; This terminates the current thread, or the entire program
;;; if there are no other threads left.
)))
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:
)
)))
;;; Create two threads, and start them running.
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 call stack for storing the variables needed because it allows for fast and simple allocating and automatic deallocation of memory. Other programming languages use a heap for this, which allows for flexibility at a higher cost for allocating and deallocating memory. Both of these implementations have benefits and drawbacks in the context of continuations.Programming language support
Many programming languages exhibit first-class continuations under various names; specifically:- Common Lisp: . One can also use custom macros
- C# / VB.NET:
asyncandawait: "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". - Factor:
callcc0andcallcc1 - Haskell: The Continuation monad in
- Haxe:
- Icon, Unicon :
create, suspend, @operator: coexpressions - Java:
- Kotlin :
Continuation - JavaScript Rhino :
Continuation - Parrot:
ContinuationPMC; uses continuation-passing style for all control flow - Perl: and
- Pico:
call)andcontinue - Python: PyPy's
- Racket:
call-with-current-continuation - Ruby:
callcc - Scala:
scala.util.continuationsprovidesshift/reset - Scheme:
call-with-current-continuation - 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