Delimited continuation - AbsoluteAstronomy.com

Programming language

A programming language is an artificial language designed to communicate instructions to a machine, particularly a computer. Programming languages can be used to create programs that control the behavior of a machine and/or to express algorithms precisely....

s, a delimited continuation, composable continuation or partial continuation, is a "slice" of a continuation

Continuation

In computer science and programming, a continuation is an abstract representation of the control state of a computer program. A continuation reifies the program control state, i.e...

frame that has been reified

Reification (computer science)

Reification is the process by which an abstract idea about a computer program is turned into an explicit data model or other object created in a programming language. A computable/addressable object — a resource — is created in a system as a proxy for a non computable/addressable object...

into a function. Unlike regular continuations, delimited continuations return

Return statement

In computer programming, a return statement causes execution to leave the current subroutine and resume at the point in the code immediately after where the subroutine was called, known as its return address. The return address is saved, usually on the process's call stack, as part of the operation...

a value, and thus may be reused and composed

Function composition (computer science)

In computer science, function composition is an act or mechanism to combine simple functions to build more complicated ones...

Examples

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

One proposal 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, 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. 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. 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.

(reset
(begin
(shift k (cons 1 (k (void)))) ;; (1)
null))

Since the context captured by shift consists of (begin [*] null) (where [*] is the hole for parameter injection), the first call of k inside shift evaluates to null, and the body of shift determines the value of the expression, we get (1) as a 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)
(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

Linguistics

Linguistics is the scientific study of human language. Linguistics can be broadly broken into three categories or subfields of study: language form, language meaning, and language in context....

: see Continuations in linguistics for details.

External links

The source of this article is wikipedia, the free encyclopedia. The text of this article is licensed under the GFDL.