fbpx
Wikipedia

Delimited continuation

August 21, 2023

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[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.

History

Delimited continuations were first introduced by Felleisen in 1988[1] with an operator called  , first introduced in a tech report in 1987,[2] 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 prompt and control,[4] shift and reset,[5][6]cupto,[7] fcontrol, and others.

Examples

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

One independent proposal[5] is based on continuation-passing style (CPS) -- i.e., not on continuation frames—and offers two control operators, shift and reset, that give rise to static rather than to dynamic delimited continuations.[9] 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 Scheme: 

(* 2 (reset (+ 1 (shift k (k 5)))))

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. 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 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.[10] 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.[2] and Johnson.[11] They have since been used in a large number of domains, particularly in defining new control operators; see Queinnec[12] 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 shift is (begin [*] null), where [*] is the hole where k's parameter will be injected. The first call of k inside shift evaluates to this context with (void) = #<void> replacing the hole, so the value of (k (void)) is (begin #<void> 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[why?].

Delimited continuations are also useful in linguistics: see Continuations in linguistics for details.

References

  1. ^ a b Felleisen, Matthias (1988). "The theory and practice of first-class prompts". Principles of Programming Languages. pp. 180–190. doi:10.1145/73560.73576. ISBN 0-89791-252-7. S2CID 16705769.
  2. ^ a b c Felleisen, Matthias; Friedman, Daniel P.; Duba, Bruce; Marrill, John (February 1987). Beyond continuations (PDF) (Technical report). Computer Science Department, Indiana University. 216.
  3. ^ Felleisen, Matthias (1987). The Calculi of Lambda-v-CS Conversion: A Syntactic Theory of Control and State in Imperative Higher-Order Programming Languages (PDF) (Thesis).
  4. ^ Sitaram, Dorai; Felleisen, Matthias (1990). "Control Delimiters and their Hierarchies" (PDF). LISP and Symbolic Computation. 3: 67–99. doi:10.1007/BF01806126. S2CID 31430221.
  5. ^ a b Danvy, Olivier; Filinski, Andrzej (1990). "Abstracting Control". LISP and Functional Programming. pp. 151–160. doi:10.1145/91556.91622. ISBN 0-89791-368-X. S2CID 6426191.
  6. ^ Danvy, Olivier (2006). An Analytical Approach to Programs as Data Objects (Thesis). doi:10.7146/aul.214.152.
  7. ^ Rémy, Didier; Gunter, Carl; Riecke, Jon G. (1995). "A generalization of exceptions and control in ML-like languages". Functional Programming Language and Computer Architecture.
  8. ^ See for instance the operators offered by the racket/control Racket library [1]; the following examples can run in Racket using (require racket/control)
  9. ^ Biernacki, Dariusz; Danvy, Olivier; Shan, Chung-chieh (2006). "On the Static and Dynamic Extents of Delimited Continuations". Science of Computer Programming. 60 (3): 274–297.
  10. ^ Gasbichler, Martin; Sperber, Michael (2002). International Conference on Functional Programming. CiteSeerX 10.1.1.11.3425.
  11. ^ 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.
  12. ^ Queinnec, Christian (April 1994). "A library of high-level control operators". Lisp Pointers, ACM SIGPLAN Special Interest Publ. On Lisp. École Polytechnique and INRIA-Rocquencourt. 6: 11–26. CiteSeerX 10.1.1.29.4790.

External links

  • 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

August 21, 2023
delimited, continuation, programming, languages, delimited, continuation, composable, continuation, partial, continuation, slice, continuation, frame, that, been, reified, into, function, unlike, regular, continuations, delimited, continuations, return, value,. 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 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 Contents 1 History 2 Examples 3 References 4 External linksHistory EditDelimited continuations were first introduced by Felleisen in 1988 1 with an operator called F displaystyle mathcal F first introduced in a tech report in 1987 2 along with a prompt construct displaystyle 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 prompt and control 4 shift and reset 5 6 cupto 7 fcontrol and others Examples EditVarious operators for delimited continuations have been proposed in the research literature 8 One independent proposal 5 is based on continuation passing style CPS i e not on continuation frames and offers two control operators shift and reset that give rise to static rather than to dynamic delimited continuations 9 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 Scheme 2 reset 1 shift k k 5 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 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 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 10 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 2 and Johnson 11 They have since been used in a large number of domains particularly in defining new control operators see Queinnec 12 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 shift is begin null where is the hole where k s parameter will be injected The first call of k inside shift evaluates to this context with void lt void gt replacing the hole so the value of k void is begin lt void gt 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 gt 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 gt 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 why Delimited continuations are also useful in linguistics see Continuations in linguistics for details References Edit a b Felleisen Matthias 1988 The theory and practice of first class prompts Principles of Programming Languages pp 180 190 doi 10 1145 73560 73576 ISBN 0 89791 252 7 S2CID 16705769 a b c Felleisen Matthias Friedman Daniel P Duba Bruce Marrill John February 1987 Beyond continuations PDF Technical report Computer Science Department Indiana University 216 Felleisen Matthias 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 3 67 99 doi 10 1007 BF01806126 S2CID 31430221 a b Danvy Olivier Filinski Andrzej 1990 Abstracting Control LISP and Functional Programming pp 151 160 doi 10 1145 91556 91622 ISBN 0 89791 368 X S2CID 6426191 Danvy Olivier 2006 An Analytical Approach to Programs as Data Objects Thesis doi 10 7146 aul 214 152 Remy Didier Gunter Carl Riecke Jon G 1995 A generalization of exceptions and control in ML like languages Functional Programming Language and Computer Architecture See for instance the operators offered by the racket control Racket library 1 the following examples can run in Racket using require racket control Biernacki Dariusz Danvy Olivier Shan Chung chieh 2006 On the Static and Dynamic Extents of Delimited Continuations Science of Computer Programming 60 3 274 297 Gasbichler Martin Sperber Michael 2002 International Conference on Functional Programming CiteSeerX 10 1 1 11 3425 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 Lisp Pointers ACM SIGPLAN Special Interest Publ On Lisp Ecole Polytechnique and INRIA Rocquencourt 6 11 26 CiteSeerX 10 1 1 29 4790 External links EditComposable 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 dlya samyh malenkih in Russian Some nice papers on delimited continuations and first class macros Retrieved from https en wikipedia org w index php title Delimited continuation amp oldid 1166922082, wikipedia, wiki, book, books, library,

article

, read, download, free, free download, mp3, video, mp4, 3gp, jpg, jpeg, gif, png, picture, music, song, movie, book, game, games.