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 though early allusions to composable and delimited continuations can be found in Carolyn Talcott's Stanford 1984 dissertation, Felleisen and Friedman's PARL 1987 paper, and Felleisen's 1987 dissertation.
Delimited continuations were first introduced by Felleisen in 1988 with an operator called , first introduced in a tech report in 87, 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
fcontrol, and others.
Various operators for delimited continuations have been proposed in the research literature.
One proposal offers two control operators:
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 (shift k (k 5)))))
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 (+ 1 5))
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
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. For example, in this Scheme code:
(reset (* 2 (shift k CODE)))
(* 2 N) is evaluated and returned.
This is equivalent to the following:
(let ((k (lambda (x) (* 2 x)))) CODE)
Furthermore, once the entire computation within
shift is completed, the continuation is discarded, and execution restarts outside
(reset (* 2 (shift k (k (k 4)))))
(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 (shift k (k (k 4))))))
Delimited continuations were first described independently by Felleisen et al. and Johnson. They have since been used in a large number of domains, particularly in defining new control operators; see Queinnec for a survey.
Let's take a look at a more complicated example. Let
null be the empty list:
(reset (begin (shift k (cons 1 (k (void)))) ;; (1) null))
The context captured by
(begin [*] null), where
[*] is the hole where
k's parameter will be injected. The first call of
shift evaluates to this context with
#<void> replacing the hole, so the value of
(k (void)) is
(begin #<void> null) =
null. The body of
(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 (shift k (cons 1 (k (void)))) (shift k (cons 2 (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 (shift k (cons 1 (k (void)))) (list 2)))
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 (yield 1) (yield 2) (yield 3) null)) ;; (list 1 2 3)
If we replace
stream-cons, we can build lazy streams:
(define (stream-yield x) (shift k (stream-cons x (k (void))))) (define lazy-example (reset (begin (stream-yield 1) (stream-yield 2) (stream-yield 3) stream-null)))
We can generalize this and convert lists to stream, in one fell swoop:
(define (list->stream xs) (reset (begin (for-each stream-yield xs) 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-maker for-each) (stream-lambda (collection) (reset (begin (for-each (lambda (element) (shift k (stream-cons element (k 'ignored)))) collection) stream-null))))
The part between
shift includes control functions like
for-each; this is impossible to rephrase using lambdas[why?].
- Matthias Felleisen (1988). "The theory and practice of first-class prompts". Principles of Programming Languages: 180–190. ISBN 0-89791-252-7. doi:10.1145/73560.73576.
- Felleisen; Friedman; Duba; Merrill (1987). Beyond Continuations (Technical report). Indiana University. 87-216.
- Matthias Felleisen (1987). The Calculi of Lambda-v-CS Conversion: A Syntactic Theory of Control and State in Imperative Higher-Order Programming Languages (PDF) (Thesis).
- Sitaram, Dorai; Felleisen, Matthias (1990). "Control Delimiters and their Hierarchies" (PDF). Lisp and Symbolic Computation.
- Olivier Danvy; Andrzej Filinski (1990). "Abstracting Control". LISP and Functional Programming: 151–160. ISBN 0-89791-368-X. doi:10.1145/91556.91622.
- Gunter; Rémy; Riecke (1995). "A generalization of exceptions and control in ML-like languages". Functional programming languages and computer architecture.
- See for instance the operators offered by the
racket/controlRacket library ; the following examples can run in Racket using
- Gasbichler, Martin; Sperber, Michael (2002). "Final Shift for Call/cc: Direct Implementation of Shift and Reset". CiteSeerX .
- Felleisen, Matthias; Friedman, Daniel P.; Duba, Bruce; Marrill, John (February 1987). "Beyond continuations" (PDF). Technical Report 216. Computer Science Department, Indiana University.
- Johnson, Gregory F. (June 1987). "GL: a denotational testbed with continuations and partial continuations". Proc. SIGPLAN '87 Symposium on Interpreters and Interpretive Techniques. pp. 218–225.
- Queinnec, Christian (April 1994). "A library of high-level control operators". École Polytechnique and INRIA-Rocquencourt. CiteSeerX .
- Composable continuations tutorial at SchemeWiki
- Delimited continuations in operating systems, by Oleg Kiselyov and Chung-chieh Shan
- Native delimited continuations in (byte-code and native-code) OCaml
- Shift/reset для самых маленьких (in Russian)
- Some nice papers on delimited continuations and first-class macros