2

这是困难的一个。我一直在尝试编写各种 monad，这是唯一一个我在任何地方都找不到简洁示例的代码，所以我尝试编写自己的代码shift并reset使用这个测试套件（JS）和这个问题（Agda）作为参考。尤其是，

shift        : ∀ {r o i j a} → ((a → DCont i i o) → DCont r j j) → DCont r o a
shift f      = λ k → f (λ x → λ k′ → k′ (k x)) id

reset        : ∀ {r i a} → DCont a i i → DCont r r a
reset a      = λ k → k (a id)

我遇到的问题是，当我测试通过多个resets 中止时，我的实现失败了：

// Delimited continuation monad
class DCont {
  static of (x) { return new DCont(resolve => resolve(x)) }
  constructor (run) { this.run = run }
  chain (fn) { return new DCont(resolve => this.run(x => fn(x).run(resolve))) }
  map (fn) { return this.chain(x => DCont.of(fn(x))) }
  ap (dc) { return this.chain(fn => dc.map(fn)) }
  shift (subc) { return new DCont(resolve => subc(dc => dc.map(resolve)).run(x => x)) }
  static reset (comp) { return DCont.of(comp(DCont.of(x => x)).run(x => x)) }
}

// Setup tests
let sqr = x => x * x,
    single_shift_reset = DCont
      .reset(p => p
        .shift(k => k(k(DCont.of(5))))
        .map(x => x + 1))
      .map(x => x * 2),
    multi_shift_abort = DCont
      .reset(p => DCont
        .reset(p2 => p
          .shift(k => DCont.of(5))
          .map(x => 1000))
        .map(x => x + 1))
      .map(x => x * 2),
    liftM2 = (f, m1, m2) => m1.chain(x => m2.map(y => f(x, y))),
    listOf = (m1, m2) => liftM2((x, y) => [x, y], m1, m2),
    add = (x, y) => x + y,
    multi_shift_in_reset = DCont
      .reset(p => liftM2(add,
        p.shift(k => listOf( k(DCont.of(1)), k(DCont.of(2)) )),
        p.shift(k => listOf( k(DCont.of(10)), k(DCont.of(20)) ))
      ));

// Run tests
console.log(single_shift_reset.run(sqr)) // Expects 196 = ((5 + 1 + 1) * 2) ^ 2
console.log(multi_shift_abort.run(sqr)) // Expects 100 = (5 * 2) ^ 2
console.log(multi_shift_in_reset.run(x => x)) // Expects [[11, 21], [12, 22]]

我的版本感觉不对——参考文献中只有一个id，我的有两个。过去我很难过。任何正确方向的提示将不胜感激！

4

1 回答 1

3

这就是问题所在。

  1. 分隔延续的 Adga 实现不考虑区域。
  2. 分隔延续的 JavaScript 实现确实考虑了区域。

您正在尝试使用分隔延续的 Adga 实现以及 JavaScript 测试套件，因此您并没有走得太远。

没有区域的定界延续

考虑以下程序。

example = do
    x <- reset $ do
        x <- reset $ do
            shift (\k -> return 5)
            return 1000
        return (x + 1)
    return (x * 2)

result = run example (\x -> x ^ 2)

当使用没有区域的分隔延续时，每个都shift被分隔到最接近的reset. 因此，在上述程序中，结果((5 + 1) * 2) ^ 2为144。

你的实现shift是reset基于 Agda 实现的。因此，它评估为144。还有一个更简单的没有区域的分隔延续的Haskell 实现。

带区域的定界延续

现在，考虑使用带区域的分隔延续的同一程序。

example = do
    x <- reset $ \p -> do
        x <- reset $ \p' -> do
            shift p (\k -> return 5)
            return 1000
        return (x + 1)
    return (x * 2)

result = run example (\x -> x ^ 2)

在这里，我们明确指定shift由外部 分隔reset。因此，结果是(5 * 2) ^ 2计算结果为100。

带区域的定界延续的实现更为复杂。一个好的起点是阅读我的教授 Amr Sabry 等人的原始论文A Monadic Framework for Delimited Continuations。

于 2020-10-03T07:36:13.150 回答