Examples of the difference between `prompt/control` and `shift/reset`

Question

I am not sure I understand the difference between the delimited continuation operator pairs prompt/control and reset/shift. I understand some basic examples of use, but in those examples their behavior is the same.

I have found this example in "On the Dynamic Extent of Delimited Continuations", by Dariusz Biernacki and Olivier Danvy:

reset
  (fn () => shift (fn k => 10 + (k 100))
          + shift (fn k’ => 1))

prompt 
  (fn () => control (fn k => 10 + (k 100))
          + control (fn k’ => 1))

which I have translated into Scheme and ran successfully with the expected results in Racket using the racket/control library:

(reset  (+ (shift   k  (+ 10 (k 100)))
           (shift   kk 1))) 
   ;; ==> 11

(prompt (+ (control k  (+ 10 (k 100)))
           (control kk 1))) 
   ;; ==> 1

Their explanation is that,

In the first case, when k is applied, the expression shift (fn kk => 1) is evaluated in a context that could be represented functionally as fn v => 100 + v and in a meta-context that could be represented as (fn v => 10 + v) :: nil; this context is captured and discarded and the intermediate answer is 1; this intermediate answer is plugged into the top context from the meta-context, i.e., fn v => 10 + v is applied to 1; the next intermediate answer is 11; and it is the final answer since the meta-context is empty.

In the second case, when k is applied, the expression control (fn kk => 1) is evaluated in a context that results from composing fn v => 10 + v and fn v => 100 + v (and therefore could be represented functionally as fn v => 10 + (100 + v)), and in a meta-context which is empty; this context is captured and discarded and the intermediate answer is 1; and it is the final answer since the meta-context is empty.

I was confused by the "meta-context" idea, which they define as

Intuitively, an evaluation context represents the rest of the computation up to the
nearest enclosing delimiter, and a meta-context represents all of the remaining computation.

I didn't get the idea of "all of the remaining computation" here, I'm not sure why it would be (fn v => 10 + v) :: nil in the first example (why exactly that piece of code?)

I was wondering if there is any more examples, possible with more details, of the differences between those two pairs of operators, possibly without too much use of formal semantics, which is a really above my head.

edit: I also see that the order of the two shift-surrounded expressions does make a difference: if I swap them, then the result is 1 for both control and reset.

Answer 1

First, let's recall the reduction rules of both prompt/control and reset/shift.

(prompt val) => val
(prompt E[control k expr]) => (prompt ((λk. expr) (λv. E[v])))
; E is free from prompt

(reset val) => val
(reset E[shift k expr]) => (reset ((λk. expr) (λv. (reset E[v]))))
; E is free from reset

We can see that reset and prompt are the same. However, the second rule is subtly different. The reset/shift pair introduces a reset around E[v] which limits the scope of what can be captured by the shift inside E[v]

Let's now reduce both expressions step by step.

First, shift/reduce:

(reset (+ (shift k (+ 10 (k 100))) (shift kk 1)))
=> (reset ((λk. (+ 10 (k 100))) (λv. (reset (+ v (shift kk 1))))))
; Here, E[v] = (+ v (shift kk 1))
=> (reset ((λk. (+ 10 (k 100))) (λv. (reset ((λkk. 1) (λw. (+ v w)))))))
; Here, E'[w] = (+ v w)
; Because of the reset, `E'[w]` catches only `(+ v w)`
; which gets discarded right away.
=> (reset ((λk. (+ 10 (k 100))) (λv. (reset 1))))
=> (reset ((λk. (+ 10 (k 100))) (λv. 1)))
=> (reset (+ 10 ((λv. 1) 100)))
=> (reset (+ 10 1))
=> (reset 11)
=> 11

Secondly, prompt/control:

(prompt  (+ (control k (+ 10 (k 100))) (control kk 1)))
=> (prompt ((λk. (+ 10 (k 100))) (λv. (+ v (control kk 1)))))
; Here, E[v] = (+ v (control kk 1))
=> (prompt ((λkk. 1) (λw. ((λk. (+ 10 (k 100))) (λv. (+ v w))))))
; Here, E'[w] = ((λk. (+ 10 (k 100))) (λv. (+ v w)))
; Because there is no `prompt` the scope of `E'[w]` is much larger and
; everything in it get discarded right away
=> (prompt 1)
=> 1

In conclusion, there is a difference only if there are at least 2 control/shift operators and shift reduces the scope of what can be captured by the context E'.