Delimited continuation

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.

Examples

Various operators for delimited continuations have been proposed in the research literature.^[1]

One proposal^[2] offers two operators, shift and reset, to work with such continuations. reset sets the limit for the continuation. shift captures the current continuation up to the innermost enclosing reset limit, takes a function argument and passes the captured continuation to it. If the delimited continuation is invoked with parameter p^{[clarification needed]}, the computation is suspended and p is returned by shift. However, if the function passed to shift returns normally (without invoking the delimited continuation), then its value becomes the return value of reset. When the entire computation within reset is completed, the result is returned by the delimited continuation.^[3] For example, in this Scheme code:

(reset (* 2 (shift k CODE)))

whenever CODE invokes (k N), (* 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. Therefore,

(reset (* 2 (shift k (k (k 4)))))

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 (shift k (k (k 4))))))

Delimited continuations were first described independently by Felleisen et al.^[4] and Johnson.^[5] They have since been used in a large number of domains, particularly in defining new control operators; see Queinnec^[6] for a survey.

The examples above are simple cases where the continuation can be safely wrapped into a body of a lambda, and be used as such; actually, continuations are much more than that. Look at this example:

(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 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: see Continuations in linguistics for details.

References

1. ^ See for instance the operators offered by the racket/control Racket library [1]; the following examples can run in Racket using (require racket/control)
2. ^ Olivier Danvy and Andre Filinski (1990). "Abstracting Control". LISP and Functional Programming: 151–160. doi:10.1145/91556.91622. 
3. ^ Gasbichler, Martin; Sperber, Michael (2002). Final Shift for Call/cc: Direct Implementation of Shift and Reset. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.11.3425. 
4. ^ Felleisen, Matthias; Friedman, Daniel P.; Duba, Bruce; Marrill, John (February 1987). Beyond continuations. Technical Report 216. Computer Science Department, Indiana University. http://www.ccs.neu.edu/scheme/pubs/felleisen-beyond.pdf. 
5. ^ 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. 
6. ^ Queinnec, Christian (April 1994). A library of high-level control operators. École Polytechnique and INRIA-Rocquencourt. http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.29.4790. 

External links

• Composable continuations tutorial at SchemeWiki
• Delimited continuations in operating systems
• Native delimited continuations in (byte-code and native-code) OCaml