Continuation
Encyclopedia
In computer science
and programming, a continuation is an abstract representation
of the control state
of a computer program
. A continuation 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' execution; the created data structure can be accessed by the programming language, instead of being hidden in the runtime environment
. It contains information such as the process' current stack (including all data whose lifetime is within the process e.g. "local variables"), as well as the process' point in the computation. An instance of continuation can be later used as a control structure; upon invocation, it will resume execution from the control point that it represents. 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.
Programs 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. There are also programming languages that use a heap for this, which allows for flexibility but with a higher cost for allocating and deallocating memory. These two different implementations both have benefits and drawbacks in the context of continuations.
Almost all languages have a means for manipulating the order of execution steps (i.e. manipulating the continuation of a computation step). The goto
is the most basic form of this. Control structures such as if statements, loops, return statements, break statements, and exit
are more structured (and limited) ways to manipulate the order of executing instructions and are essentially limited goto statements.
More complex constructs exist as well, for which "continuations provide an elegant description". For example in C
, setjmp can be used to jump from the middle of one function to another function, 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 coroutine
s in Simula 67
and Lua, 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
.
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.
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.
A complete history of the discovery of continuations is given by .
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 is a highly complex undertaking.
s (aka green threads), and exception handling
. Continuations provide the basic, low-level primitive unifying these otherwise seemingly unconnected patterns. Continuations can provide elegant solutions to some difficult high-level problems, in particular the problem of programming a web server that supports multiple pages, accessed by the user's use of the forward and back buttons and by following links. The Seaside web framework in Smalltalk
uses continuations to great effect, allowing one to program the web server in procedural style, by switching continuations when switching pages.
(abbreviated as: call/cc) with which a Scheme program can manipulate the flow of control:
Defines a function
For a gentler introduction to this mechanism, see call-with-current-continuation
.
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 previous code will produce this exit:
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 proper tail calls, 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
.) This is a particularly common strategy in Haskell
, where it is easy to construct a "continuation-passing monad" (for example, the
no function ever returns; all calls are tail calls.
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. Inverting back the inversion 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 Racket Web Server, the UnCommon Web Framework and Weblocks Web framework for Common Lisp
, the Seaside framework for Smalltalk
, Ocsigen/Eliom
for OCaml, Continuity for Perl
, Wee for Ruby
, and the Nagare framework for Python
. The Apache Cocoon
Web application framework
also provides continuations (see the Cocoon manual).
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 Racket language. However this use of the term "re-entrant" can be easily confused with its use in discussions of multithreading
.
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
statement, and the same caveats apply. While 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.
.
Informally speaking, continuations can account for the similarity between such sentences as "Alice sees Bob"—formally, —and "Alice sees everyone", i.e. .
See Chris Barker's paper Continuations in Natural Language for details. See also Montague grammar
.
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
and programming, a continuation is an abstract representation
Abstraction (computer science)
In computer science, abstraction is the process by which data and programs are defined with a representation similar to its pictorial meaning as rooted in the more complex realm of human life and language with their higher need of summarization and categorization , while hiding away the...
of the control state
Control flow
In computer science, control flow refers to the order in which the individual statements, instructions, or function calls of an imperative or a declarative program are executed or evaluated....
of a computer program
Computer program
A computer program is a sequence of instructions written to perform a specified task with a computer. A computer requires programs to function, typically executing the program's instructions in a central processor. The program has an executable form that the computer can use directly to execute...
. A continuation reifies
Reification (computer science)
Reification is the process by which an abstract idea about a computer program is turned into an explicit data model or other object created in a programming language. A computable/addressable object — a resource — is created in a system as a proxy for a non computable/addressable object...
the program control state, i.e. the continuation is a data structure that represents the computational process at a given point in the process' execution; the created data structure can be accessed by the programming language, instead of being hidden in the runtime environment
Run-time system
A run-time system is a software component designed to support the execution of computer programs written in some computer language...
. It contains information such as the process' current stack (including all data whose lifetime is within the process e.g. "local variables"), as well as the process' point in the computation. An instance of continuation can be later used as a control structure; upon invocation, it will resume execution from the control point that it represents. 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
Programming language
A programming language is an artificial language designed to communicate instructions to a machine, particularly a computer. Programming languages can be used to create programs that control the behavior of a machine and/or to express algorithms precisely....
the ability to save the execution state at any point and return to that point at a later point in the program.
Programs must allocate space in memory for the variables its functions use. Most programming languages use a call stack
Call stack
In computer science, a call stack is a stack data structure that stores information about the active subroutines of a computer program. This kind of stack is also known as an execution stack, control stack, run-time stack, or machine stack, and is often shortened to just "the stack"...
for storing the variables needed because it allows for fast and simple allocating and automatic deallocation of memory. There are also programming languages that use a heap for this, which allows for flexibility but with a higher cost for allocating and deallocating memory. These two different implementations both have benefits and drawbacks in the context of continuations.
Almost all languages have a means for manipulating the order of execution steps (i.e. manipulating the continuation of a computation step). The goto
Goto
goto is a statement found in many computer programming languages. It is a combination of the English words go and to. It performs a one-way transfer of control to another line of code; in contrast a function call normally returns control...
is the most basic form of this. Control structures such as if statements, loops, return statements, break statements, and exit
Exit (operating system)
On many computer operating systems, a computer process terminates its execution by making an exit system call. More generally, an exit in a multithreading environment means that a thread of execution has stopped running. The operating system reclaims resources that were used by the process...
are more structured (and limited) ways to manipulate the order of executing instructions and are essentially limited goto statements.
More complex constructs exist as well, for which "continuations provide an elegant description". For example in C
C (programming language)
C is a general-purpose computer programming language developed between 1969 and 1973 by Dennis Ritchie at the Bell Telephone Laboratories for use with the Unix operating system....
, setjmp can be used to jump from the middle of one function to another function, 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 coroutine
Coroutine
Coroutines are computer program components that generalize subroutines to allow multiple entry points for suspending and resuming execution at certain locations...
s in Simula 67
Simula
Simula is a name for two programming languages, Simula I and Simula 67, developed in the 1960s at the Norwegian Computing Center in Oslo, by Ole-Johan Dahl and Kristen Nygaard...
and Lua, tasklets in Stackless Python
Stackless Python
Stackless Python, or Stackless, is a Python programming language interpreter, so named because it avoids depending on the C call stack for its own stack. The most prominent feature of Stackless is microthreads, which avoid much of the overhead associated with usual operating system threads...
, generators
Generator (computer science)
In computer science, a generator is a special routine that can be used to control the iteration behaviour of a loop. A generator is very similar to a function that returns an array, in that a generator has parameters, can be called, and generates a sequence of values...
in Icon and Python
Python (programming language)
Python is a general-purpose, high-level programming language whose design philosophy emphasizes code readability. Python claims to "[combine] remarkable power with very clear syntax", and its standard library is large and comprehensive...
, continuations in Scala (starting in 2.8), fibers
Fiber (computer science)
In computer science, a fiber is a particularly lightweight thread of execution.Like threads, fibers share address space. However, fibers use co-operative multitasking while threads use pre-emptive multitasking. Threads often depend on the kernel's thread scheduler to preempt a busy thread and...
in Ruby
Ruby (programming language)
Ruby is a dynamic, reflective, general-purpose object-oriented programming language that combines syntax inspired by Perl with Smalltalk-like features. Ruby originated in Japan during the mid-1990s and was first developed and designed by Yukihiro "Matz" Matsumoto...
(starting in 1.9.1), the backtracking
Backtracking
Backtracking is a general algorithm for finding all solutions to some computational problem, that incrementally builds candidates to the solutions, and abandons each partial candidate c as soon as it determines that c cannot possibly be completed to a valid solution.The classic textbook example...
mechanism in Prolog
Prolog
Prolog is a general purpose logic programming language associated with artificial intelligence and computational linguistics.Prolog has its roots in first-order logic, a formal logic, and unlike many other programming languages, Prolog is declarative: the program logic is expressed in terms of...
, monads in functional programming
Functional programming
In computer science, functional programming is a programming paradigm that treats computation as the evaluation of mathematical functions and avoids state and mutable data. It emphasizes the application of functions, in contrast to the imperative programming style, which emphasizes changes in state...
, and threads
Thread (computer science)
In computer science, a thread of execution is the smallest unit of processing that can be scheduled by an operating system. The implementation of threads and processes differs from one operating system to another, but in most cases, a thread is contained inside a process...
.
History
The earliest description of continuations was made by Adriaan van WijngaardenAdriaan van Wijngaarden
Adriaan van Wijngaarden was an important mathematician and computer scientist who is considered by many to have been the founding father of informatica in the Netherlands...
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
ALGOL 60
ALGOL 60 is a member of the ALGOL family of computer programming languages. It gave rise to many other programming languages, including BCPL, B, Pascal, Simula, C, and many others. ALGOL 58 introduced code blocks and the begin and end pairs for delimiting them...
preprocessor, he called for a transformation of proper procedures into continuation-passing style.
Christopher Strachey
Christopher Strachey
Christopher Strachey was a British computer scientist. He was one of the founders of denotational semantics, and a pioneer in programming language design...
, Christopher P. Wadsworth and John C. Reynolds
John C. Reynolds
John C. Reynolds is an American computer scientist.John Reynolds studied at Purdue University and then earned a PhD in theoretical physics from Harvard University in 1961. He was Professor of Information science at Syracuse University from 1970 to 1986. Since then he has been Professor of Computer...
brought the term continuation into prominence in their work in the field of denotational semantics
Denotational semantics
In computer science, denotational semantics is an approach to formalizing the meanings of programming languages by constructing mathematical objects which describe the meanings of expressions from the languages...
that makes extensive use of continuations to allow sequential programs to be analysed in terms of functional programming
Functional programming
In computer science, functional programming is a programming paradigm that treats computation as the evaluation of mathematical functions and avoids state and mutable data. It emphasizes the application of functions, in contrast to the imperative programming style, which emphasizes changes in state...
semantics.
Steve Russell
Steve Russell
Steve "Slug" Russell is a programmer and computer scientist most famous for creating Spacewar!, one of the earliest videogames, in 1961 with the fellow members of the Tech Model Railroad Club at MIT working on a DEC Digital PDP-1...
invented the continuation in his second Lisp implementation for the IBM 704
IBM 704
The IBM 704, the first mass-produced computer with floating point arithmetic hardware, was introduced by IBM in 1954. The 704 was significantly improved over the IBM 701 in terms of architecture as well as implementations which were not compatible with its predecessor.Changes from the 701 included...
, though he did not name it.
A complete history of the discovery of continuations is given by .
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 state of the program. However, it is important to note that true first-class continuations do not save program data, 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. :-)
Scheme was the first full production system, providing first "catch" and then call/cc
Call-with-current-continuation
In functional programming, the function call-with-current-continuation, commonly abbreviated call/cc, is a control operator that originated in its current form in the Scheme programming language and now exists in several other programming languages....
. Bruce Duba introduced call/cc into SML
Standard ML
Standard ML is a general-purpose, modular, functional programming language with compile-time type checking and type inference. It is popular among compiler writers and programming language researchers, as well as in the development of theorem provers.SML is a modern descendant of the ML...
.
Continuations are also used in models of computation including denotational semantics
Denotational semantics
In computer science, denotational semantics is an approach to formalizing the meanings of programming languages by constructing mathematical objects which describe the meanings of expressions from the languages...
, the Actor model
Actor model
In computer science, the Actor model is a mathematical model of concurrent computation that treats "actors" as the universal primitives of concurrent digital computation: in response to a message that it receives, an actor can make local decisions, create more actors, send more messages, and...
, process calculi, and lambda calculus
Lambda calculus
In mathematical logic and computer science, lambda calculus, also written as λ-calculus, is a formal system for function definition, function application and recursion. The portion of lambda calculus relevant to computation is now called the untyped lambda calculus...
. These models rely on programmers or semantics engineers to write mathematical functions in the so-called continuation-passing style
Continuation-passing style
In functional programming, continuation-passing style is a style of programming in which control is passed explicitly in the form of a continuation. Gerald Jay Sussman and Guy L. Steele, Jr...
. 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
Continuation-passing style
In functional programming, continuation-passing style is a style of programming in which control is passed explicitly in the form of a continuation. Gerald Jay Sussman and Guy L. Steele, Jr...
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.
Uses
Continuations are useful because they simplify and clarify the implementation of several other common programming design patterns, including coroutineCoroutine
Coroutines are computer program components that generalize subroutines to allow multiple entry points for suspending and resuming execution at certain locations...
s (aka green threads), and exception handling
Exception handling
Exception handling is a programming language construct or computer hardware mechanism designed to handle the occurrence of exceptions, special conditions that change the normal flow of program execution....
. Continuations provide the basic, low-level primitive unifying these otherwise seemingly unconnected patterns. Continuations can provide elegant solutions to some difficult high-level problems, in particular the problem of programming a web server that supports multiple pages, accessed by the user's use of the forward and back buttons and by following links. The Seaside web framework in Smalltalk
Smalltalk
Smalltalk is an object-oriented, dynamically typed, reflective programming language. Smalltalk was created as the language to underpin the "new world" of computing exemplified by "human–computer symbiosis." It was designed and created in part for educational use, more so for constructionist...
uses continuations to great effect, allowing one to program the web server in procedural style, by switching continuations when switching pages.
Examples
The Scheme programming language includes the control operator call-with-current-continuationCall-with-current-continuation
In functional programming, the function call-with-current-continuation, commonly abbreviated call/cc, is a control operator that originated in its current form in the Scheme programming language and now exists in several other programming languages....
(abbreviated as: call/cc) with which a Scheme program can manipulate the flow of control:
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
Call-with-current-continuation
In functional programming, the function call-with-current-continuation, commonly abbreviated call/cc, is a control operator that originated in its current form in the Scheme programming language and now exists in several other programming languages....
.
Coroutines
This example shows a possible usage of continuations to implement coroutines as separate threads.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 previous code will produce this exit:
This is AAA 0
Hello from BBB 0
This is AAA 1
Hello from BBB 1
This is AAA 2
Hello from BBB 2
...
Programming language support
Many programming languages exhibit first-class continuations under various names; specifically:- CC (programming language)C is a general-purpose computer programming language developed between 1969 and 1973 by Dennis Ritchie at the Bell Telephone Laboratories for use with the Unix operating system....
:setcontext
et al. (POSIXSetcontextsetcontext is one of a family of C library functions used for context control. The setcontext family allows the implementation in C of advanced control flow patterns such as iterators, fibers, and coroutines...POSIXPOSIX , an acronym for "Portable Operating System Interface", is a family of standards specified by the IEEE for maintaining compatibility between operating systems...
) - JavaJava (programming language)Java is a programming language originally developed by James Gosling at Sun Microsystems and released in 1995 as a core component of Sun Microsystems' Java platform. The language derives much of its syntax from C and C++ but has a simpler object model and fewer low-level facilities...
: Lightwolf - FactorFactor (programming language)Factor is a stack-oriented programming language created by Slava Pestov. Factor is dynamically typed and has automatic memory management, as well as powerful metaprogramming features. The language has a single implementation featuring a self-hosted optimizing compiler and an interactive development...
:callcc0
andcallcc1
- HaskellHaskell (programming language)Haskell is a standardized, general-purpose purely functional programming language, with non-strict semantics and strong static typing. It is named after logician Haskell Curry. In Haskell, "a function is a first-class citizen" of the programming language. As a functional programming language, the...
: The Continuation Monad inControl.Monad.Cont
- Icon, Unicon :
create, suspend, @
operator: coexpressions - ParrotParrot virtual machineParrot is a register-based process virtual machine designed to run dynamic languages efficiently. It uses just-in-time compilation for speed to reduce the interpretation overhead. It is currently possible to compile Parrot assembly language and PIR to Parrot bytecode and execute it...
:Continuation
PMC; uses continuation-passing styleContinuation-passing styleIn functional programming, continuation-passing style is a style of programming in which control is passed explicitly in the form of a continuation. Gerald Jay Sussman and Guy L. Steele, Jr...
for all control flow - PerlPerlPerl is a high-level, general-purpose, interpreted, dynamic programming language. Perl was originally developed by Larry Wall in 1987 as a general-purpose Unix scripting language to make report processing easier. Since then, it has undergone many changes and revisions and become widely popular...
: Coro and Continuity - Pico:
call(exp)
andcontinue(aContinuation, anyValue)
- JavaScript RhinoRhino (JavaScript engine)Rhino is an open source JavaScript engine. It is developed entirely in Java and managed by the Mozilla Foundation. The Foundation also provides another implementation of JavaScript engine written in C known as SpiderMonkey....
:Continuation
- RubyRuby (programming language)Ruby is a dynamic, reflective, general-purpose object-oriented programming language that combines syntax inspired by Perl with Smalltalk-like features. Ruby originated in Japan during the mid-1990s and was first developed and designed by Yukihiro "Matz" Matsumoto...
:callcc
- Scala:
Responder
- Scheme:
call-with-current-continuation
(commonly shortened toCall-with-current-continuationIn functional programming, the function call-with-current-continuation, commonly abbreviated call/cc, is a control operator that originated in its current form in the Scheme programming language and now exists in several other programming languages....call/cc
) - SmalltalkSmalltalkSmalltalk is an object-oriented, dynamically typed, reflective programming language. Smalltalk was created as the language to underpin the "new world" of computing exemplified by "human–computer symbiosis." It was designed and created in part for educational use, more so for constructionist...
:Continuation currentDo:
, in most modern Smalltalk environments continuations can be implemented without additional VM support. - Standard ML of New JerseyStandard ML of New JerseyStandard ML of New Jersey is a compiler and programming environment for Standard ML. Aside from its runtime system, which is written in C, SML/NJ is written in Standard ML...
:SMLofNJ.Cont.callcc
- UnlambdaUnlambdaUnlambda is a minimal, "nearly pure" functional programming language invented by David Madore. It is based on combinatory logic, a version of the lambda calculus that omits the lambda operator. It relies mainly on two built-in functions and an "apply" operator...
:c
, the flow control operation for call with current continuation - C#:
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#
In any language which supports closures
Closure (computer science)
In computer science, a closure is a function together with a referencing environment for the non-local variables of that function. A closure allows a function to access variables outside its typical scope. Such a function is said to be "closed over" its free variables...
and proper tail calls, it is possible to write programs in continuation-passing style
Continuation-passing style
In functional programming, continuation-passing style is a style of programming in which control is passed explicitly in the form of a continuation. Gerald Jay Sussman and Guy L. Steele, Jr...
and manually implement call/cc. (In continuation-passing style
Continuation-passing style
In functional programming, continuation-passing style is a style of programming in which control is passed explicitly in the form of a continuation. Gerald Jay Sussman and Guy L. Steele, Jr...
, call/cc becomes a simple function that can be written with lambda
Lambda calculus
In mathematical logic and computer science, lambda calculus, also written as λ-calculus, is a formal system for function definition, function application and recursion. The portion of lambda calculus relevant to computation is now called the untyped lambda calculus...
.) This is a particularly common strategy in Haskell
Haskell (programming language)
Haskell is a standardized, general-purpose purely functional programming language, with non-strict semantics and strong static typing. It is named after logician Haskell Curry. In Haskell, "a function is a first-class citizen" of the programming language. As a functional programming language, the...
, 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 proper tail calls is needed because in continuation-passing styleContinuation-passing style
In functional programming, continuation-passing style is a style of programming in which control is passed explicitly in the form of a continuation. Gerald Jay Sussman and Guy L. Steele, Jr...
no function ever returns; all calls are tail calls.
Continuations in Web development
One area that has seen practical use of continuations is in Web programming. The use of continuations shields the programmer from the statelessStateless server
In computing, a stateless protocol is a communications protocol that treats each request as an independent transaction that is unrelated to any previous request so that the communication consists of independent pairs of requests and responses...
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
Inversion of Control
In software engineering, Inversion of Control is an abstract principle describing an aspect of some software architecture designs in which the flow of control of a system is inverted in comparison to procedural programming....
, while avoiding its problems. Inverting back the inversion is a paper that provides a good introduction to continuations applied to web programming.
Some of the more popular continuation-aware Web server
Web server
Web server can refer to either the hardware or the software that helps to deliver content that can be accessed through the Internet....
s are the Racket Web Server, the UnCommon Web Framework and Weblocks Web framework for Common Lisp
Common Lisp
Common Lisp, commonly abbreviated CL, is a dialect of the Lisp programming language, published in ANSI standard document ANSI INCITS 226-1994 , . From the ANSI Common Lisp standard the Common Lisp HyperSpec has been derived for use with web browsers...
, the Seaside framework for Smalltalk
Smalltalk
Smalltalk is an object-oriented, dynamically typed, reflective programming language. Smalltalk was created as the language to underpin the "new world" of computing exemplified by "human–computer symbiosis." It was designed and created in part for educational use, more so for constructionist...
, Ocsigen/Eliom
Ocsigen
Ocsigen is a Web application framework based on concepts derived from recent research in the field of programming languages, namely that of continuation-based web programming...
for OCaml, Continuity for Perl
Perl
Perl is a high-level, general-purpose, interpreted, dynamic programming language. Perl was originally developed by Larry Wall in 1987 as a general-purpose Unix scripting language to make report processing easier. Since then, it has undergone many changes and revisions and become widely popular...
, Wee for Ruby
Ruby (programming language)
Ruby is a dynamic, reflective, general-purpose object-oriented programming language that combines syntax inspired by Perl with Smalltalk-like features. Ruby originated in Japan during the mid-1990s and was first developed and designed by Yukihiro "Matz" Matsumoto...
, and the Nagare framework for Python
Python (programming language)
Python is a general-purpose, high-level programming language whose design philosophy emphasizes code readability. Python claims to "[combine] remarkable power with very clear syntax", and its standard library is large and comprehensive...
. The Apache Cocoon
Apache Cocoon
Apache Cocoon, usually just called Cocoon, is a web application framework built around the concepts of pipeline, separation of concerns and component-based web development. The framework focuses on XML and XSLT publishing and is built using the Java programming language...
Web application framework
Web application framework
A web application framework is a software framework that is designed to support the development of dynamic websites, web applications and web services. The framework aims to alleviate the overhead associated with common activities performed in Web development...
also provides continuations (see the Cocoon manual).
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. LandinPeter J. Landin
Peter John Landin was a British computer scientist. He was one of the first to realize that the lambda calculus could be used to model a programming language, an insight that is essential to development of both functional programming and denotational semantics.- Academic :Landin was born in...
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 Racket language. However this use of the term "re-entrant" can be easily confused with its use in discussions of multithreading
Thread (computer science)
In computer science, a thread of execution is the smallest unit of processing that can be scheduled by an operating system. The implementation of threads and processes differs from one operating system to another, but in most cases, a thread is contained inside a process...
.
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
Exception handling
Exception handling is a programming language construct or computer hardware mechanism designed to handle the occurrence of exceptions, special conditions that change the normal flow of program execution....
, 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 unwind the stack. Escape continuations can also be used to implement tail-call optimization.Disadvantages
Continuations are the functional expression of the GOTOGoto
goto is a statement found in many computer programming languages. It is a combination of the English words go and to. It performs a one-way transfer of control to another line of code; in contrast a function call normally returns control...
statement, and the same caveats apply. While 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
Esoteric programming language
An esoteric programming language is a programming language designed as a test of the boundaries of computer programming language design, as a proof of concept, or as a joke...
Unlambda
Unlambda
Unlambda is a minimal, "nearly pure" functional programming language invented by David Madore. It is based on combinatory logic, a version of the lambda calculus that omits the lambda operator. It relies mainly on two built-in functions and an "apply" operator...
includes call-with-current-continuation
Call-with-current-continuation
In functional programming, the function call-with-current-continuation, commonly abbreviated call/cc, is a control operator that originated in its current form in the Scheme programming language and now exists in several other programming languages....
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 have been described using the notion of delimited continuationDelimited continuation
In programming languages, a delimited continuation, composable continuation or partial continuation, is a "slice" of a continuation frame that has been reified into a function...
.
Informally speaking, continuations can account for the similarity between such sentences as "Alice sees Bob"—formally, —and "Alice sees everyone", i.e. .
See Chris Barker's paper Continuations in Natural Language for details. See also Montague grammar
Montague grammar
Montague grammar is an approach to natural language semantics, named after American logician Richard Montague. The Montague grammar is based on formal logic, especially higher order predicate logic and lambda calculus, and makes use of the notions of intensional logic, via Kripke models...
.
See also
- Call-with-current-continuationCall-with-current-continuationIn functional programming, the function call-with-current-continuation, commonly abbreviated call/cc, is a control operator that originated in its current form in the Scheme programming language and now exists in several other programming languages....
- ClosureClosure (computer science)In computer science, a closure is a function together with a referencing environment for the non-local variables of that function. A closure allows a function to access variables outside its typical scope. Such a function is said to be "closed over" its free variables...
- COMEFROMCOMEFROMIn computer programming, COMEFROM is an obscure control flow structure used in some programming languages, originally as a joke....
- Continuation-passing styleContinuation-passing styleIn functional programming, continuation-passing style is a style of programming in which control is passed explicitly in the form of a continuation. Gerald Jay Sussman and Guy L. Steele, Jr...
- Control flowControl flowIn computer science, control flow refers to the order in which the individual statements, instructions, or function calls of an imperative or a declarative program are executed or evaluated....
- CoroutineCoroutineCoroutines are computer program components that generalize subroutines to allow multiple entry points for suspending and resuming execution at certain locations...
- Delimited continuationDelimited continuationIn programming languages, a delimited continuation, composable continuation or partial continuation, is a "slice" of a continuation frame that has been reified into a function...
- Denotational semanticsDenotational semanticsIn computer science, denotational semantics is an approach to formalizing the meanings of programming languages by constructing mathematical objects which describe the meanings of expressions from the languages...
- GOTOGotogoto is a statement found in many computer programming languages. It is a combination of the English words go and to. It performs a one-way transfer of control to another line of code; in contrast a function call normally returns control...
- Spaghetti stackSpaghetti stackA spaghetti stack in computer science is an N-ary tree data structure in which child nodes have pointers to the parent nodes . When a list of nodes is traversed from a leaf node to the root node by chasing these parent pointers, the structure looks like a linked list stack...
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.
- Drew McDermottDrew McDermottDrew McDermott is a Professor of Computer Science at Yale University. He was born in 1949, and lived in the Midwestern United States , for four years, and in Brazil .-Education:...
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 HewittCarl HewittCarl Hewitt is Board Chair of the International Society for Inconsistency Robustness. He has been a Visiting Professor at Stanford University and the University of Keio. In 2000, he became emeritus in the EECS department at MIT....
, Peter BishopPeter BishopPeter Bishop is a fictional character on the Fox television series Fringe. He is portrayed by Joshua Jackson.-Fictional character biography:...
and Richard Steiger. A Universal Modular Actor Formalism for Artificial Intelligence IJCAI 1973. - Christopher StracheyChristopher StracheyChristopher Strachey was a British computer scientist. He was one of the founders of denotational semantics, and a pioneer in programming language design...
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. ReynoldsJohn C. ReynoldsJohn C. Reynolds is an American computer scientist.John Reynolds studied at Purdue University and then earned a PhD in theoretical physics from Harvard University in 1961. He was Professor of Information science at Syracuse University from 1970 to 1986. Since then he has been Professor of Computer...
. 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.
- 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 DybvigR. Kent DybvigR. Kent Dybvig is a professor of Computer Science at Indiana University in Bloomington, Indiana.His research focuses on programming languages, and he is known in the Lisp community as the principal developer of the Chez Scheme compiler and run-time system. Together with Daniel P...
, 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
- ACMAssociation for Computing MachineryThe Association for Computing Machinery is a learned society for computing. It was founded in 1947 as the world's first scientific and educational computing society. Its membership is more than 92,000 as of 2009...
SIGPLANSIGPLANSIGPLAN is the Association for Computing Machinery's Special Interest Group on programming languages.- Conferences :* Principles of Programming Languages * Programming Language Design and Implementation...
Workshop on Continuations 2011 at the 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
- On-line proceedings of the Second ACM SIGPLAN Workshop on Continuations
- Continuation, functions and jumps
- http://okmij.org/ftp/continuations/ by Oleg Kiselyov
- Rhino With Continuations
- Continuations in pure Java from the RIFERIFERIFE is a content management framework designed for rapid web application development in Java, without using J2EE.RIFE's design blends together in a consistent component object model two approaches, request-based and component-based...
web application framework - Debugging continuations in pure Java from the RIFERIFERIFE is a content management framework designed for rapid web application development in Java, without using J2EE.RIFE's design blends together in a consistent component object model two approaches, request-based and component-based...
web application framework - Comparison of generators, coroutines, and continuations, source of the above example