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 "et al.", Felleisen's 1987 dissertation, 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.
History.
Delimited continuations were first introduced by Felleisen in 1988 with an operator called formula_1, first introduced in a tech report in 1987, along with a prompt construct formula_2. The operator was designed to be a generalization of control operators that had been described in the literature such as codice_1 from Scheme, ISWIM's J operator, John C. Reynolds' codice_2 operator, and others. Subsequently, many competing delimited control operators were invented by the programming languages research community such as codice_3 and codice_4, codice_5 and codice_6,codice_7, codice_8, and others.
Examples.
Various operators for delimited continuations have been proposed in the research literature.
One independent proposal is based on continuation-passing style (CPS) -- i.e., not on continuation frames—and offers two control operators, codice_5 and codice_6, that give rise to static rather than to dynamic delimited continuations.
The codice_6 operator sets the limit for the continuation while the codice_5 operator captures or reifies the current continuation up to the innermost enclosing codice_6. For example, consider the following snippet in Scheme:
 (* 2 (reset (+ 1 (shift k (k 5)))))
The codice_6 delimits the continuation that codice_5 captures (named by codice_16 in this example). When this snippet is executed, the use of codice_5 will bind codice_16 to the continuation codice_19 where codice_20 represents the part of the computation that is to be filled with a value. This continuation directly corresponds to the code that surrounds the codice_5 up to the codice_6. Because the body of shift (i.e., codice_23) 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 codice_16 as a value or invoking codice_16 multiple times. The codice_5 operator passes the captured continuation codice_16 to the code in its body, which can either invoke it, produce it as a result, or ignore it entirely. Whatever result that codice_5 produces is provided to the innermost codice_6, discarding the continuation in between the codice_6 and codice_5. However, if the continuation is invoked, then it effectively re-installs the continuation after returning to the codice_6. When the entire computation within codice_6 is completed, the result is returned by the delimited continuation. For example, in this Scheme code:
 (reset (* 2 (shift k CODE)))
whenever codice_34 invokes codice_35, codice_36 is evaluated and returned.
This is equivalent to the following:
 (let ((k (lambda (x) (* 2 x)))) CODE)
Furthermore, once the entire computation within codice_5 is completed, the continuation is discarded, and execution restarts outside codice_6. Therefore,
 (reset (* 2 (shift k (k (k 4)))))
invokes codice_39 first (which returns 8), and then codice_40 (which returns 16). At this point, the codice_5 expression has terminated, and the rest of the codice_6 expression is discarded. Therefore, the final result is 16.
Everything that happens outside the codice_6 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 codice_44 be the empty list:
 (reset
 (begin
 (shift k (cons 1 (k (void)))) ;; (1)
 null))
The context captured by codice_5 is codice_46, where codice_47 is the hole where codice_16's parameter will be injected. The first call of codice_16 inside codice_5 evaluates to this context with codice_51 = codice_52 replacing the hole, so the value of codice_53 is codice_54 = codice_44. The body of codice_5, namely codice_57 = codice_58, becomes the overall value of the codice_6 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 codice_5, we already know the result, it is codice_61; 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 codice_62, that is, codice_63.
We can define codice_64 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 codice_65 with codice_66, 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) 
 (lambda (collection) 
 (reset (begin 
 (for-each (lambda (element) 
 (shift k 
 (stream-cons element (k 'ignored)))) 
 collection) 
 stream-null))))
The part between codice_6 and codice_5 includes control functions like codice_69 and codice_70; this is impossible to rephrase using lambdas.
Delimited continuations are also useful in linguistics: see Continuations in linguistics for details.
A worked-out illustration of the codice_71 idiom: the generalized curry function.
The generalized curry function is given an uncurried function codice_72 and its arity (say, 3),
and it returns the value of codice_73.
This example is due to Olivier Danvy and was worked out in the mid-1980s.
Here is a unit-test function to illustrate what the generalized curry function is expected to do:
(define test-curry
 (lambda (candidate)
 (and (= (candidate + 0)
 (= ((candidate + 1) 1)
 (+ 1))
 (= (((candidate + 2) 1) 10)
 (+ 1 10))
 (= ((((candidate + 3) 1) 10) 100)
 (+ 1 10 100)))
 (= (((((candidate + 4) 1) 10) 100) 1000)
 (+ 1 10 100 1000))))
These unit tests verify whether currying the variadic function codice_74 into an n-ary curried function and applying the result to n arguments yields the same result as applying codice_74 to these n arguments, for n = 0, 1, 2, 3, and 4.
The following recursive function is accumulator-based and eventually reverses the accumulator before applying the given uncurried function.
In each instance of the induction step, the function codice_76 is explicitly applied to an argument in the curried application:
(define curry_a
 (lambda (f n)
 (if ( ; n 0)
 (error 'curry_a "negative input: ~s" n)
 (letrec ([visit (lambda (i a)
 (if (= i 0)
 (apply f (reverse a))
 (lambda (v)
 (visit (- i 1) (cons v a)))))])
 (visit n '())))))
For example, evaluating
reduces to evaluating
which reduces to evaluating
which beta-reduces to evaluating
which reduces to evaluating
which beta-reduces to evaluating
which reduces to evaluating
which reduces to evaluating
which is equivalent to
which delta-reduces to the result, codice_77.
The following recursive function is continuation-based and involves no list reversal.
Likewise, in each instance of the induction step, the function codice_76 is explicitly applied to an argument in the curried application:
(define curry_c
 (lambda (f n)
 (if ( ; n 0)
 (error 'curry_c "negative input: ~s" n)
 (letrec ([visit (lambda (i c)
 (if (= i 0)
 (c '())
 (lambda (v)
 (visit (- i 1) (lambda (vs)
 (c (cons v vs)))))))])
 (visit n (lambda (vs)
 (apply f vs)))))))
So evaluating
reduces to evaluating
which reduces to evaluating
which beta-reduces to evaluating
which reduces to evaluating
which beta-reduces to evaluating
which reduces to evaluating
which beta-reduces to evaluating
which beta-reduces to evaluating
which beta-reduces to evaluating
which is equivalent to
which delta-reduces to the result, codice_77.
The following recursive function, codice_80, is the direct-style counterpart of codice_81 and features the codice_71 idiom, using Andrzej Filinski's implementation of shift and reset in terms of a global mutable cell and of codice_1.
In each instance of the induction step, the continuation abstraction is implicitly applied to an argument in the curried application:
(define curry_d
 (lambda (f n)
 (if ( ; n 0)
 (error 'curry_d "negative input: ~s" n)
 (letrec ([visit (lambda (i)
 (if (= i 0)
 (cons (shift k k)
 (visit (- i 1)))))])
 (reset (apply f (visit n)))))))
The heart of the matter is the observational equivalence between
codice_84
and
codice_85
where codice_86 is fresh and the ellipses represent a pure context,
i.e., one without control effects.
So evaluating
reduces to evaluating
which reduces to evaluating
which is observationally equivalent to
which beta-reduces to evaluating
which reduces to evaluating
which is observationally equivalent to
which beta-reduces to evaluating
which reduces to evaluating
which is equivalent to
which delta-reduces to evaluating
which yields the result, codice_77.
The definition of codice_80 also illustrates static delimited continuations.
This static extent needs to be explicitly encoded if one wants to use codice_4
and codice_3:
(define curry_cp
 (lambda (f n)
 (if ( ; n 0)
 (error 'curry_cp "negative input: ~s" n)
 (letrec ([visit (lambda (i)
 (if (= i 0)
 (cons (control k (lambda (x) (prompt (k x))))
 (visit (- i 1)))))])
 (prompt (apply f (visit n)))))))
References.
 ;templatestyles src="Reflist/styles.css" / ;