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.
For example, consider the following snippet in Scheme: 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.
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.
When the entire computation within reset is completed, the result is returned by the delimited continuation.
This is equivalent to the following: Furthermore, once the entire computation within shift is completed, the continuation is discarded, and execution restarts outside reset.
The body of shift, namely (cons 1 null) = (1), becomes the overall value of the reset expression as the final result.
We can define yield using this trick: and use it in building lists: If we replace cons with stream-cons, we can build lazy streams: We can generalize this and convert lists to stream, in one fell swoop: In a more complicated example below the continuation can be safely wrapped into a body of a lambda, and be used as such: The part between reset and shift includes control functions like lambda and for-each; this is impossible to rephrase using lambdas[why?].
[14] In each instance of the induction step, the continuation abstraction is implicitly applied to an argument in the curried application: The heart of the matter is the observational equivalence between (reset (... (shift k k) ...)) and (lambda (x) (reset (... x ...))) where x is fresh and the ellipses represent a pure context, i.e., one without control effects.