Delimited continuations

A continuation can be understood as a context that represents the “rest of the program”. Notice that formulated in this way, continuation is a meta-level abstraction. Ability to manipulate such continuations as functions is obtained using control operators. The Scheme programming language has traditionally been a ripe field for research on control operators such as (call/cc).

Call-with-current-continuation is an example of an unbounded control operator. A different and a more general class of control operators are delimited control operators. The basic idea is that rather to capture the whole rest of the program as a continuation, delimited control operators capture delimited continuations, i.e. some part of the program with a hole.

In order to run the examples from this document in DrRacket make sure to put (require racket/control) in your file.

Prompt/control

One of the first (and simplest) delimited control operations is prompt/control. prompt delimits the continuation, and control captures the current continuation (up to the innermost prompt).

(prompt (+ 1 (control k (k 3))))

The code is evaluated as follows:

(prompt (+ 1 (control k (k 3))))
=> (prompt ((λ (k) (k 3)) (λ (x) (+ 1 x))))
=> (prompt ((λ (x) (+ 1 x)) 3)) 
=> (prompt (+ 1 3)) => (prompt 4) => 4

Here (λ (x) (+ 1 x)) represents the delimited continuation (the program inside prompt without the control part) on an object level. When (control k body) is evaluated inside a prompt, it gets replaced with (λ (k) body) (capturing k inside body) and applied to the continuation. In terms of reduction semantics one would have the following reduction rules:

(prompt v) -> v
(prompt E[(control k body)]) -> (prompt ((λ (k) body) (λ (x) E[x])))

where the evaluation context E does not contain prompt and x is a free variable in E.

In particular, if continuation is not invoked in body, it is just discarded, as in the following example:

(prompt (+ 1 (control k 3)))

A captured delimited continuation can be invoked multiple times:

(prompt
  (+ 1 (control k (let ([x (k 1)] [y (k 2)])
                     (k (* x y))))))

In this case the continuation k = (λ (x) (+ 1 x)), so when it is invoked in the body of control, x and y get set to 2 and 3, respectively. Hence, the final result of that program is 1+2*3=7.

Nested continuations

(prompt
    (+ 2 (control k (+ 1 (control k1 (k1 6))))))
=> (prompt
      ((λ (x) (+ 2 (control k (+ 1 x)))) 6))
=> (prompt
      (+ 2 (control k (+ 1 6))))
=> (prompt
      (+ 2 (control k 7)))
=> (prompt 7) => 7

While loops with breaks

We can utilize the prompt/control operators to implement a simple macro for a while loop with an ability to break out of it, sort of similar to the while/break statements in C.

(define-syntax-rule (break) (control k '()))
(define-syntax-rule (while cond body ...)  
  (prompt
   (let loop ()
     (when cond
       body ...
       (loop)))))

We define the (while) construct as a simple recursive loop with just one caveat – we wrap the whole thing in a prompt. Then (break), when evaluated, just discards the whole continuation with is bound to the (while) loop. We can test this macro by writing a procedure that multiplies all the elements in the list.

(define (multl lst)
  (define i 0)
  (define fin (length lst))
  (define res 1)
  (while (< i fin)
    (let ([val (list-ref lst i)])
      (printf "The value of lst[~a] is ~a\n" i val)
      (set! res (* res val))
      (when (= val 0)
          (begin (set! res 0) (break))))
    (set! i (+ i 1)))
  res)

By running this program we can observe that it finishes early whenever it encounters a zero in the list:

> (multl '(1 2 3))
The value of lst[0] is 1
The value of lst[1] is 2
The value of lst[2] is 3
6
> (multl '(1 2 0 3 4 5))
The value of lst[0] is 1
The value of lst[1] is 2
The value of lst[2] is 0
0
>

The situation with break in C is slightly different; as it has been pointed out to me, break is a statement, whereas in our toy example break is an expression. Due to the dichotomy of statements and expressions in C this example is not very faithful to C semantics.

Prompt tags

The (while) macro that we have is actually buggy. The problem arises when the body of the while loop contains an additional prompt delimiter:

(while (< i 3) (writeln "Hi") (prompt (break)) (set! i (+ i 1)))

When running this example “Hi” is written to the standard output three time. Oops. To circumvent this problem we can use the tagged prompt-at/control-at operators with the following reduction semantics:

(prompt-at tag v) -> v
(prompt-at tag E[(control-at tag' k body)]) -> (prompt-at tag ((λ (k) body) (λ (x) E[x])))

where tag = tag' and E does not contain prompt-at tag. So the only difference between prompt-at/control-at and prompt/control is the presence of prompt tags which allows for a more fine-grained matching between delimiters and control operators.

We can sort of fix our while macro by creating a special tag

(define while-tag (make-continuation-prompt-tag 'tagje))
(define-syntax-rule (break) (control-at while-tag k '()))
(define-syntax-rule (while cond body ...)  
  (prompt-at while-tag
   (let loop ()
     (when cond
       body ...
       (loop)))))

The following program then prints “Hi” only once.

(define i 0)
(while (< i 3) (writeln "Hi") (prompt (break)) (set! i (+ i 1)))

Reset/shift

The other pair of delimited control operators are shift and reset.

The reductions for reset/shift are as follows.

(reset v) -> v
(reset E[(shift k body)]) -> (reset ((λ (k) body) (λ (x) (reset E[x]))))

where the evaluation context E does not contain reset and x is a free variable in E. Contrast this with the reduction rules for prompt/control

(prompt v) -> v
(prompt E[(control k body)]) -> (prompt ((λ (k) body) (λ (x) E[x])))

As you can notice, the difference between the prompt/control reductions is that in the case when the continuation is captured, it is wrapped in an additional reset. Thus, any invocation of a bound delimited continuation k cannot escape to the outer scope.

To observe the practical difference, consider the following example.

(define (skip) '())
(define (bye) (println "Capturing and discarding the continuation...") 42)
(prompt
 (let ([act (control k (begin
                         (k skip)
                         (k (λ () (control _ (bye))))
                         (k skip)))])
   (act)
   (println "Doing stuff")))

If we were to remove the second line (k (λ () (control _ (bye)))) in the begin block, then this program would print “Doing stuff” twice (as invoking (k skip) binds the dummy function skip to act and executes (begin (act) (println "Doing stuff"))). With such a line present, during the invocation of k, act gets bound to (λ () (control _ (bye))). Therefore, when act is evaluated the continuation is of the form (prompt E[(control _ bye)]), which just reduces to (prompt (bye)) and (prompt 42). So, the output of the program above is

"Doing stuff"
"Capturing and discarding the continuation..."
42

If we replace prompt with reset and control with shift, as in the code snippet below, then every invocation of k wraps the continuation in another reset.

(reset
 (let ([act (shift k (begin
                       (k skip)
                       (k (λ () (shift _ (bye))))
                       (k skip)))])
   (act)
   (println "Doing stuff")))

After some reductions, the terms is

(reset 
  ((λ (k) (begin (k skip) (k (λ () (shift _ (bye)))) (K skip))) 
   (λ (x) (reset (begin (x) (println "Doing stuff"))))))

As you can see, the second invocation of k results in (reset (begin (shift _ (bye)) (println "Doing stuff"))), and thus

“Doing stuff” does not get printed (as this part of the term gets discarded.
The shift operator discards the inner continuation, not the outer continuation. In particular, that means that the call to (k (λ () (shift _ (bye)))) returns!

The output of the snippet is thus

"Doing stuff"
"Capturing and discarding the continuation..."
"Doing stuff"

Comments and further reading

See references at https://docs.racket-lang.org/reference/cont.html.

Some interesting papers:

Shift to control by C.C. Shan shows how to express shift/reset and control/prompt in terms of each other.
On the Dynamic Extent of Delimited Continuations by Dariusz Biernacki and Olivier Danvy present the difference between shift and control using breadth-first traversal as an example. It is also explained in which sense shift is a static delimited control operator and control is a dynamic delimited control operator.
A bibliography of Continuations and Continuation Passing Style at the readscheme.org