scheme - `prompt/control` 和 `shift/reset` 之间的差异示例

Question

我不确定我是否理解分隔连续运算符对之间的区别 prompt/control和 reset/shift .我了解一些基本的使用示例，但在这些示例中，它们的行为是相同的。
我在 Dariusz Biernacki 和 Olivier Danvy 的“On the Dynamic Extent of Delimited Continuations”中找到了这个例子:

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

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

我已将其翻译成 Scheme 并使用 racket/control 在 Racket 中成功运行并达到预期结果。图书馆:

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

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

他们的解释是，

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 couldbe represented as (fn v => 10 + v) :: nil; this context is capturedand discarded and the intermediate answer is 1; this intermediateanswer is plugged into the top context from the meta-context, i.e.,fn v => 10 + v is applied to 1; the next intermediate answer is11; 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 composingfn v => 10 + v and fn v => 100 + v (and therefore could berepresented functionally as fn v => 10 + (100 + v)), and in ameta-context which is empty; this context is captured and discardedand the intermediate answer is 1; and it is the final answersince the meta-context is empty.

我对“元上下文”的想法感到困惑，他们将其定义为

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.

我没有在这里得到“所有剩余计算”的想法，我不确定
为什么会是 (fn v => 10 + v) :: nil在第一个例子中(为什么是那段代码？)
我想知道是否有更多的例子，可能有更多的细节，
这两对运算符之间的差异，可能没有过多使用形式语义，
这真是超出我的想象。
编辑:我也看到了 shift的两个顺序-surrounded 表达式确实有所作为:如果我交换它们，那么结果是 1两者都适用 control和 reset .

Answer 1

首先，让我们记忆一下 prompt/control 的约简规则和 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

我们可以看到 reset和 prompt是相同的。但是，第二条规则略有不同。 reset/shift对在 E[v] 附近引入了重置这限制了 shift 可以捕获的范围内 E[v]现在让我们逐步减少这两个表达式。
一、 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

其次， 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

总之，只有至少有 2 control 才有区别。/ shift运算符和 shift减少上下文可以捕获的范围 E' .