History
Delimited continuations were first introduced by Felleisen in 1988 with an operator called , first introduced in a tech report in 1987, along with a prompt construct . The operator was designed to be a generalization of control operators that had been described in the literature such ascall/cc
from escape
operator, and others. Subsequently, many competing delimited control operators were invented by the programming languages research community such as prompt
and control
, shift
and reset
, cupto
, fcontrol
, and others.
Examples
Various operators for delimited continuations have been proposed in the research literature.See for instance the operators offered by theracket/control
Racket librar(require racket/control)
One proposal offers two control operators: shift
and reset
. 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 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:
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. For example, in this CODE
invokes (k N)
, (* 2 N)
is evaluated and returned.
This is equivalent to the following:
shift
is completed, the continuation is discarded, and execution restarts outside reset
. Therefore,
(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:
null
be the empty list:
shift
is (begin null)
, where /code> is the hole where k
's parameter will be injected. The first call of k
inside shift
evaluates to this context with (void)
= #
replacing the hole, so the value of (k (void))
is (begin # 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
(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 cons
with 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)
(lambda (collection)
(reset (begin
(for-each (lambda (element)
(shift k
(stream-cons element (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.
Delimited continuations are also useful in linguistics
Linguistics is the scientific study of human language. It is called a scientific study because it entails a comprehensive, systematic, objective, and precise analysis of all aspects of language, particularly its nature and structure. Linguis ...
: see Continuations in linguistics for details.
References
External links
Composable continuations tutorial at SchemeWiki
Delimited continuations in operating systems, by Oleg Kiselyov and Chung-chieh Shan
* ttps://archive.today/20121205215033/http://palm-mute.livejournal.com/12291.html Shift/reset для самых маленьких
Some nice papers on delimited continuations and first-class macros
{{DEFAULTSORT:Delimited Continuation
Control flow
Continuations
Articles with example Racket code