5

我不确定我是否理解分隔的延续运算符对prompt/control和reset/shift. 我了解一些基本的使用示例，但在这些示例中，它们的行为是相同的。

我在Dariusz Biernacki 和 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))

racket/control我已将其翻译成 Scheme 并使用库在 Racket 中以预期结果成功运行：

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

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

他们的解释是，

在第一种情况下，当k被应用时，表达式在可以在功能上表示为的上下文中以及在可以表示为的元上下文中shift (fn kk => 1)进行评估；此上下文被捕获并丢弃，中间答案是；这个中间答案从元上下文插入到顶层上下文中，即 应用于; 下一个中间答案是 ；这是最终的答案，因为元上下文是空的。fn v => 100 + v(fn v => 10 + v) :: nil1fn v => 10 + v111

在第二种情况下，当k被应用时，表达式控件 在由组合和（因此可以在功能上表示为）产生的上下文中以及在为空的元上下文中(fn kk => 1)进行评估 ；此上下文被捕获并丢弃，中间答案是；这是最终的答案，因为元上下文是空的。fn v => 10 + vfn v => 100 + vfn v => 10 + (100 + v)1

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

直观地说，评估上下文表示直到
最近的封闭分隔符的其余计算，而元上下文表示所有剩余的计算。

我在这里没有得到“所有剩余计算”的想法，我不确定为什么会出现(fn v => 10 + v) :: nil在第一个示例中（为什么是那段代码？）

我想知道是否还有更多的例子，可能有更多的细节，说明这两对操作符之间的差异，可能没有太多使用形式语义，这真的让我头疼。

编辑：我还看到两个shift被包围的表达式的顺序确实有所不同：如果我交换它们，那么结果1对于两者都是controland reset。

4

1 回答 1

5

首先，让我们回顾一下 和 的归约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]可以捕获的范围shiftE[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减少了 context 可以捕获的范围E'。

于 2020-12-30T15:52:49.783 回答