在 JavaScript 中实现定界延续 monad - `reset` 幂等错误

Question

这是一个艰难的过程。我一直在尝试编写各种单子，这是唯一一个我在任何地方都找不到简洁示例的单子，所以我尝试使用 this test suite (JS) and this question 编写自己的 shift 和 reset（阿格达）作为参考。特别是，

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)

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

// 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，我的有两个。过去我很难过。任何正确方向的提示都将不胜感激！

Answer 1

问题来了。

定界延续的 Adga 实现不考虑区域。
定界延续的 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 implementation 没有区域的定界延续，这更简单。

区域的定界延续

现在，考虑使用带有区域的定界延续的同一个程序。

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.

的原始论文

在 JavaScript 中实现定界延续 monad - `reset` 幂等错误

Implementing the delimited continuation monad in JavaScript - `reset` idempotence bug

javascript

monads

continuations

functional-programming

delimited-continuations

没有区域的定界延续

区域的定界延续