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. Unlike regular continuations, delimited continuations return a value, and thus may be reused and composed. Control delimiters, the basis of delimited continuations, were introduced by Matthias Felleisen in 1988 [1] though early allusions to composable and delimited continuations can be found in Carolyn Talcott's Stanford 1984 dissertation, Felleisen et al., [2] Felleisen's 1987 dissertation, [3] and algorithms for functional backtracking, e.g., for pattern matching, for parsing, in the Algebraic Logic Functional programming language, and in the functional implementations of Prolog where the failure continuation is often kept implicit and the reason of being for the success continuation is that it is composable.
Delimited continuations were first introduced by Felleisen in 1988 [1] with an operator called , first introduced in a tech report in 1987, [2] along with a prompt construct . The operator was designed to be a generalization of control operators that had been described in the literature such as call/cc
from Scheme, ISWIM's J operator, John C. Reynolds' escape
operator, and others. Subsequently, many competing delimited control operators were invented by the programming languages research community such as prompt
and control
, [4] shift
and reset
, [5] [6] cupto
, [7] fcontrol
, and others.
Various operators for delimited continuations have been proposed in the research literature. [8]
One independent proposal [5] is based on continuation-passing style (CPS) -- i.e., not on continuation frames—and offers two control operators, shift
and reset
, that give rise to static rather than to dynamic delimited continuations. [9] The reset
operator sets the limit for the continuation while the shift
operator captures or reifies the current continuation up to the innermost enclosing reset
. For example, consider the following snippet in Scheme:
(*2(reset(+1(shiftk(k5)))))
The reset
delimits the continuation that shift
captures (named by k
in this example). When this snippet is executed, the use of shift
will bind k
to the continuation (+ 1 [])
where []
represents the part of the computation that is to be filled with a value. This continuation directly corresponds to the code that surrounds the shift
up to the reset
. Because the body of shift (i.e., (k 5)
) immediately invokes the continuation, this code is equivalent to the following:
(*2(+15))
In general, these operators can encode more interesting behavior by, for example, returning the captured continuation k
as a value or invoking k
multiple times. The shift
operator passes the captured continuation k
to the code in its body, which can either invoke it, produce it as a result, or ignore it entirely. Whatever result that shift
produces is provided to the innermost reset
, discarding the continuation in between the reset
and shift
. However, if the continuation is invoked, then it effectively re-installs the continuation after returning to the reset
. When the entire computation within reset
is completed, the result is returned by the delimited continuation. [10] For example, in this Scheme code:
(reset(*2(shiftkCODE)))
whenever CODE
invokes (k N)
, (* 2 N)
is evaluated and returned.
This is equivalent to the following:
(let((k(lambda(x)(*2x))))CODE)
Furthermore, once the entire computation within shift
is completed, the continuation is discarded, and execution restarts outside reset
. Therefore,
(reset(*2(shiftk(k(k4)))))
invokes (k 4)
first (which returns 8), and then (k 8)
(which returns 16). At this point, the shift
expression has terminated, and the rest of the reset
expression is discarded. Therefore, the final result is 16.
Everything that happens outside the reset
expression is hidden, i.e. not influenced by the control transfer. For example, this returns 17:
(+1(reset(*2(shiftk(k(k4))))))
Delimited continuations were first described independently by Felleisen et al. [2] and Johnson. [11] They have since been used in a large number of domains, particularly in defining new control operators; see Queinnec [12] for a survey.
Let's take a look at a more complicated example. Let null
be the empty list:
(reset(begin(shiftk(cons1(k(void))));; (1)null))
The context captured by shift
is (begin [*] null)
, where [*]
is the hole where k
's parameter will be injected. The first call of k
inside shift
evaluates to this context with (void)
= #<void>
replacing the hole, so the value of (k (void))
is (begin #<void> null)
= null
. The body of shift
, namely (cons 1 null)
= (1)
, becomes the overall value of the reset
expression as the final result.
Making this example more complicated, add a line:
(reset(begin(shiftk(cons1(k(void))))(shiftk(cons2(k(void))))null))
If we comment out the first shift
, we already know the result, it is (2)
; so we can as well rewrite the expression like this:
(reset(begin(shiftk(cons1(k(void))))(list2)))
This is pretty familiar, and can be rewritten as (cons 1 (list 2))
, that is, (list 1 2)
.
We can define yield
using this trick:
(define (yield x) (shift k (cons x (k (void)))))
and use it in building lists:
(reset(begin(yield1)(yield2)(yield3)null));; (list 1 2 3)
If we replace cons
with stream-cons
, we can build lazy streams:
(define(stream-yieldx)(shiftk(stream-consx(k(void)))))(definelazy-example(reset(begin(stream-yield1)(stream-yield2)(stream-yield3)stream-null)))
We can generalize this and convert lists to stream, in one fell swoop:
(define(list->streamxs)(reset(begin(for-eachstream-yieldxs)stream-null)))
In a more complicated example below the continuation can be safely wrapped into a body of a lambda, and be used as such:
(define(for-each->stream-makerfor-each)(lambda(collection)(reset(begin(for-each(lambda(element)(shiftk(stream-conselement(k'ignored))))collection)stream-null))))
The part between reset
and shift
includes control functions like lambda
and for-each
; this is impossible to rephrase using lambdas[ why? ].
Delimited continuations are also useful in linguistics: see Continuations in linguistics for details.
Common Lisp (CL) is a dialect of the Lisp programming language, published in American National Standards Institute (ANSI) standard document ANSI INCITS 226-1994 (S20018). The Common Lisp HyperSpec, a hyperlinked HTML version, has been derived from the ANSI Common Lisp standard.
In computer science, functional programming is a programming paradigm where programs are constructed by applying and composing functions. It is a declarative programming paradigm in which function definitions are trees of expressions that map values to other values, rather than a sequence of imperative statements which update the running state of the program.
Lisp is a family of programming languages with a long history and a distinctive, fully parenthesized prefix notation. Originally specified in 1960, Lisp is the second-oldest high-level programming language still in common use, after Fortran. Lisp has changed since its early days, and many dialects have existed over its history. Today, the best-known general-purpose Lisp dialects are Common Lisp, Scheme, Racket and Clojure.
Scheme is a dialect of the Lisp family of programming languages. Scheme was created during the 1970s at the MIT Computer Science and Artificial Intelligence Laboratory and released by its developers, Guy L. Steele and Gerald Jay Sussman, via a series of memos now known as the Lambda Papers. It was the first dialect of Lisp to choose lexical scope and the first to require implementations to perform tail-call optimization, giving stronger support for functional programming and associated techniques such as recursive algorithms. It was also one of the first programming languages to support first-class continuations. It had a significant influence on the effort that led to the development of Common Lisp.
In programming languages, a closure, also lexical closure or function closure, is a technique for implementing lexically scoped name binding in a language with first-class functions. Operationally, a closure is a record storing a function together with an environment. The environment is a mapping associating each free variable of the function with the value or reference to which the name was bound when the closure was created. Unlike a plain function, a closure allows the function to access those captured variables through the closure's copies of their values or references, even when the function is invoked outside their scope.
In computer science, hygienic macros are macros whose expansion is guaranteed not to cause the accidental capture of identifiers. They are a feature of programming languages such as Scheme, Dylan, Rust, Nim, and Julia. The general problem of accidental capture was well known in the Lisp community before the introduction of hygienic macros. Macro writers would use language features that would generate unique identifiers or use obfuscated identifiers to avoid the problem. Hygienic macros are a programmatic solution to the capture problem that is integrated into the macro expander. The term "hygiene" was coined in Kohlbecker et al.'s 1986 paper that introduced hygienic macro expansion, inspired by terminology used in mathematics.
In computer science, a continuation is an abstract representation of the control state 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 runtime environment. Continuations are useful for encoding other control mechanisms in programming languages such as exceptions, generators, coroutines, and so on.
In computer programming, a function object is a construct allowing an object to be invoked or called as if it were an ordinary function, usually with the same syntax. In some languages, particularly C++, function objects are often called functors.
In functional programming, continuation-passing style (CPS) is a style of programming in which control is passed explicitly in the form of a continuation. This is contrasted with direct style, which is the usual style of programming. Gerald Jay Sussman and Guy L. Steele, Jr. coined the phrase in AI Memo 349 (1975), which sets out the first version of the Scheme programming language. John C. Reynolds gives a detailed account of the numerous discoveries of continuations.
In the Scheme computer programming language, the procedure call-with-current-continuation, abbreviated call/cc, is used as a control flow operator. It has been adopted by several other programming languages.
Matthias Felleisen is a German-American computer science professor and author. He grew up in Germany and immigrated to the US in his twenties. He received his PhD from Indiana University under the direction of Daniel P. Friedman.
Daniel Paul Friedman is a professor of Computer Science at Indiana University in Bloomington, Indiana. His research focuses on programming languages, and he is a prominent author in the field.
Racket is a general-purpose, multi-paradigm programming language and a multi-platform distribution that includes the Racket language, compiler, large standard library, IDE, development tools, and a set of additional languages including Typed Racket, Swindle, FrTime, Lazy Racket, R5RS & R6RS Scheme, Scribble, Datalog, Racklog, Algol 60 and several teaching languages.
The ProgramByDesign project is an outreach effort of the PLT research group. The goal is to train college faculty, high school teachers, and possibly even middle school teachers, in programming and computing.
In computer programming, append
is the operation for concatenating linked lists or arrays in some high-level programming languages.
In computing, a meta-circular evaluator (MCE) or meta-circular interpreter (MCI) is an interpreter which defines each feature of the interpreted language using a similar facility of the interpreter's host language. For example, interpreting a lambda application may be implemented using function application. Meta-circular evaluation is most prominent in the context of Lisp. A self-interpreter is a meta-circular interpreter where the interpreted language is nearly identical to the host language; the two terms are often used synonymously.
In computer science, A-normal form is an intermediate representation of programs in functional compilers. In ANF, all arguments to a function must be trivial. That is, evaluation of each argument must halt immediately.
In programming language semantics, normalisation by evaluation (NBE) is a style of obtaining the normal form of terms in the λ-calculus by appealing to their denotational semantics. A term is first interpreted into a denotational model of the λ-term structure, and then a canonical (β-normal and η-long) representative is extracted by reifying the denotation. Such an essentially semantic, reduction-free, approach differs from the more traditional syntactic, reduction-based, description of normalisation as reductions in a term rewrite system where β-reductions are allowed deep inside λ-terms.
A CEK Machine is an abstract machine invented by Matthias Felleisen and Daniel P. Friedman that implements left-to-right call by value. It is generally implemented as an interpreter for functional programming languages, but can also be used to implement simple imperative programming languages. A state in a CEK machine includes a control statement, environment and continuation. The control statement is the term being evaluated at that moment, the environment is (usually) a map from variable names to values, and the continuation stores another state, or a special halt case. It is a simplified form of another abstract machine called the SECD machine.
In computer science, refocusing is a program transformation used to implement a reduction semantics -- i.e., a small-step operational semantics with an explicit representation of the reduction context -- more efficiently. It is a step towards implementing a deterministic semantics as a deterministic abstract machine.
racket/control
Racket library ; the following examples can run in Racket using (require racket/control)