Delimited continuations

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

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

1. “Doing stuff” does not get printed (as this part of the term gets discarded.
2. 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"

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