如何为continuation monad实现stack-safe chainRec操作符？

问题描述 投票：2回答：2

我目前正在试验延续monad。 Cont实际上在Javascript中很有用，因为它从回调模式中抽象出来。

当我们处理monadic递归时，总是存在堆栈溢出的风险，因为递归调用不在尾部位置：

const chain = g => f => k =>
  g(x => f(x) (k));

const of = x => k =>
  k(x);
  
const id = x =>
  x;

const inc = x =>
  x + 1;

const repeat = n => f => x => 
  n === 0
    ? of(x)
    : chain(of(f(x))) (repeat(n - 1) (f));

console.log(
  repeat(1e6) (inc) (0) (id) // stack overflow
);

但是，即使我们能够将某些情况转换为尾递归，我们仍然注定要失败，因为Javascript没有TCO。因此，我们必须在某个时刻回到循环。

puresrcipt有一个MonadRec类型类，带有tailRecM运算符，可以为某些monad进行尾递归monadic计算。所以我尝试在Javascript中实现chainRec主要是根据幻想的土地规范：

const chain = g => f => k => g(x => f(x) (k));
const of = x => k => k(x);
const id = x => x;

const Loop = x =>
  ({value: x, done: false});

const Done = x =>
  ({value: x, done: true});

const chainRec = f => x => {
  let step = f(Loop, Done, x);

  while (!step.done) {
    step = f(Loop, Done, step.value);
  }

  return of(step.value);
};

const repeat_ = n => f => x => 
  chainRec((Loop, Done, [n, x]) => n === 0 ? Done(x) : Loop([n - 1, f(x)])) ([n, x]);

console.log(
  repeat_(1e6) (n => n + 1) (0) (id) // 1000000
);

这有效，但它看起来很像作弊，因为它似乎绕过了monadic链接，从而绕过了Cont的背景。在这种情况下，上下文只是“计算的其余部分”，即。反向的函数组成，结果返回预期值。但它对任何单子都有效吗？

为了清楚我的意思，请查看以下outstanding answer的代码片段：

const Bounce = (f,x) => ({ isBounce: true, f, x })

const Cont = f => ({
  _runCont: f,
  chain: g =>
    Cont(k =>
      Bounce(f, x =>
        Bounce(g(x)._runCont, k)))
})

// ...

const repeat = n => f => x => {
  const aux = (n,x) =>
    n === 0 ? Cont.of(x) : Cont.of(f(x)).chain(x => aux(n - 1, x))
  return runCont(aux(n,x), x => x)
}

这里chain以某种方式结合到递归算法中，即可以发生monadic效应。不幸的是，我无法破译此运算符或将其与堆栈不安全版本协调（但Bounce(g(x)._runCont, k)似乎是f(x) (k)部分）。

最后，我的问题是，如果我搞砸了chainRecor的实施，误解了FL规范或者两者都没有，或者都没有？

[编辑]

通过从不同的角度看问题并且值得接受，两个给出的答案都非常有用。因为我只能接受一个 - 嘿stackoverflow，世界并不那么简单！ - 我不接受任何。

javascript functional-programming monads tail-recursion continuation-passing
2个回答
1
投票

我是否搞砸了chainRec的实施，或误解了FantasyLand规格，或两者兼而有之？

可能是两者，或者至少是第一部分。请注意the type should be

chainRec :: ChainRec m => ((a -> c, b -> c, a) -> m c, a) -> m b

其中m是Cont和c是你的完成/循环包装在a或b：

chainRec :: ((a -> DL a b, b -> DL a b, a) -> Cont (DL a b), a) -> Cont b

但是你的chainRec和repeat实现根本不使用连续性！

如果我们只实现那种类型，而不需要它应该需要恒定的堆栈空间，它看起来就像

const chainRec = f => x => k =>
  f(Loop, Done, x)(step =>
    step.done
      ? k(step.value) // of(step.value)(k)
      : chainRec(f)(step.value)(k)
  );

或者如果我们甚至放弃懒惰要求（类似于将chain从g => f => k => g(x => f(x)(k))转换为g => f => g(f)（即g => f => k => g(x => f(x))(k)）），它看起来像

const chainRec = f => x =>
  f(Loop, Done, x)(step =>
    step.done
      ? of(step.value)
      : chainRec(f)(step.value)
  );

甚至掉落Done / Loop

const join = chain(id);
const chainRec = f => x => join(f(chainRec(f), of, x));

（我希望我不会因此而走得太远，但它完美呈现了ChainRec背后的想法）

有了懒惰的延续和非递归的蹦床，我们会写

const chainRec = f => x => k => {
  let step = Loop(x);
  do {
    step = f(Loop, Done, step.value)(id);
//                                  ^^^^ unwrap Cont
  } while (!step.done)
  return k(step.value); // of(step.value)(k)
};

循环语法（初始化step与f调用，do/while而不是do）并不重要，你的也很好，但重要的是f(Loop, Done, v)返回一个延续。

我将把repeat的实现作为练习留给读者：D （提示：如果你有重复的函数f已经使用continuation，它可能会变得更有用，也更容易正确）

3
投票

最好的祝福，

我想这可能就是你要找的东西，

const chainRec = f => x =>
  f ( chainRec (f)
    , of
    , x
    )

实现repeat就像你拥有它一样 - 有两个例外（感谢@Bergi来捕捉这个细节）。 1，loop和done是链接函数，因此chainRec回调必须返回延续。 2，我们必须使用run标记一个函数，所以cont知道什么时候我们可以安全地折叠挂起的延续堆栈 - 粗体更改

const repeat_ = n => f => x =>
  chainRec
    ((loop, done, [n, x]) =>
       n === 0
         ? of (x) (done)                // cont chain done
         : of ([ n - 1, f (x) ]) (loop) // cont chain loop
    ([ n, x ])

const repeat = n => f => x =>
  repeat_ (n) (f) (x) (run (identity))

但是，如果你像我们这里一样使用chainRec，当然没有理由定义中间repeat_。我们可以直接定义repeat

const repeat = n => f => x =>
  chainRec
    ((loop, done, [n, x]) =>
       n === 0
         ? of (x) (done)
         : of ([ n - 1, f (x) ]) (loop)
    ([ n, x ])
    (run (identity))

现在它可以工作，你只需要一个堆栈安全的延续monad - cont (f)构建一个延续，等待行动g。如果g用run标记，那么它是时候在trampoline上反弹了。否则构造函数一个新的延续，为call和f添加连续的g

// not actually stack-safe; we fix this below
const cont = f => g =>
  is (run, g)
    ? trampoline (f (g))
    : cont (k =>
        call (f, x =>
          call (g (x), k)))

const of = x =>
  cont (k => k (x))

在我们进一步讨论之前，我们将验证一切正常

const TAG =
  Symbol ()

const tag = (t, x) =>
  Object.assign (x, { [TAG]: t })
  
const is = (t, x) =>
  x && x [TAG] === t

// ----------------------------------------

const cont = f => g =>
  is (run, g)
    ? trampoline (f (g))
    : cont (k =>
        call (f, x =>
          call (g (x), k)))
  
const of = x =>
  cont (k => k (x))

const chainRec = f => x =>
  f ( chainRec (f)
    , of
    , x
    )
  
const run = x =>
  tag (run, x)
  
const call = (f, x) =>
  tag (call, { f, x })  

const trampoline = t =>
{
  let acc = t
  while (is (call, acc))
    acc = acc.f (acc.x)
  return acc
}

// ----------------------------------------

const identity = x =>
  x
  
const inc = x =>
  x + 1

const repeat = n => f => x =>
  chainRec
    ((loop, done, [n, x]) =>
       n === 0
         ? of (x) (done)
         : of ([ n - 1, f (x) ]) (loop))
    ([ n, x ])
    (run (identity))
      
console.log (repeat (1e3) (inc) (0))
// 1000

console.log (repeat (1e6) (inc) (0))
// Error: Uncaught RangeError: Maximum call stack size exceeded

哪个是虫子？

提供的两个实现包含一个关键的区别。具体来说，它是g(x)._runCont位使结构变平。这个任务使用Cont的JS Object编码是微不足道的，因为我们可以通过简单地读取._runCont的g(x)属性来展平

const Cont = f =>
  ({ _runCont: f
   , chain: g =>
       Cont (k =>
         Bounce (f, x =>
          // g(x) returns a Cont, flatten it
          Bounce (g(x)._runCont, k))) 
   })

在我们的新编码中，我们使用函数来表示cont，除非我们提供另一个特殊信号（就像我们用run做的那样），一旦部分应用了f之外就无法访问cont - 请看下面的g (x)

const cont = f => g =>
  is (run, g)
    ? trampoline (f (g))
    : cont (k =>
        call (f, x =>
          // g (x) returns partially-applied `cont`, how to flatten?
          call (g (x), k)))

在上面，g (x)将返回部分应用的cont（即cont (something)），但这意味着整个cont函数可以无限地嵌套。而不是cont包裹的something，我们只想要something。

我花在这个答案上的时间至少有50％已经提出了各种方法来压缩部分应用的cont。这个解决方案不是特别优雅，但它确实完成了工作并精确地突出了需要发生的事情。我真的很想知道你可能会发现其他编码 - 粗体变化

const FLATTEN =
  Symbol ()

const cont = f => g =>
  g === FLATTEN
    ? f
    : is (run, g)
      ? trampoline (f (g))
      : cont (k =>
          call (f, x =>
            call (g (x) (FLATTEN), k)))

所有系统在线，船长

随着cont展平补丁到位，其他一切都有效。现在看chainRec做了一百万次迭代......

const TAG =
  Symbol ()

const tag = (t, x) =>
  Object.assign (x, { [TAG]: t })
  
const is = (t, x) =>
  x && x [TAG] === t

// ----------------------------------------

const FLATTEN =
  Symbol ()

const cont = f => g =>
  g === FLATTEN
    ? f
    : is (run, g)
      ? trampoline (f (g))
      : cont (k =>
          call (f, x =>
            call (g (x) (FLATTEN), k)))
  
const of = x =>
  cont (k => k (x))

const chainRec = f => x =>
  f ( chainRec (f)
    , of
    , x
    )
  
const run = x =>
  tag (run, x)
  
const call = (f, x) =>
  tag (call, { f, x })  

const trampoline = t =>
{
  let acc = t
  while (is (call, acc))
    acc = acc.f (acc.x)
  return acc
}

// ----------------------------------------

const identity = x =>
  x
  
const inc = x =>
  x + 1

const repeat = n => f => x =>
  chainRec
    ((loop, done, [n, x]) =>
       n === 0
         ? of (x) (done)
         : of ([ n - 1, f (x) ]) (loop))
    ([ n, x ])
    (run (identity))
      
console.log (repeat (1e6) (inc) (0))
// 1000000

持续进化

当我们在上面的代码中引入cont时，如何推导出这样的编码并不是很明显。我希望对此有所了解。我们从如何希望定义cont开始

const cont = f => g =>
  cont (comp (g,f))

const comp = (f, g) =>
  x => f (g (x))

在这种形式下，cont将无休止地推迟评估。我们唯一可以做的就是应用g，它总是创造另一个cont并推迟我们的行动。我们添加了一个逃生舱，run，向cont发出信号，我们不想再推迟了。

const cont = f => g =>
  is (run, g)
    ? f (g)
    : cont (comp (g,f))

const is = ...

const run = ...

const square = x =>
  of (x * x)

of (4) (square) (square) (run (console.log))
// 256

square (4) (square) (run (console.log))
// 256

在上面，我们可以开始看到cont如何表达美丽和纯粹的节目。但是，在没有尾调用消除的环境中，这仍然允许程序构建超出评估程序堆栈限制的延迟函数序列。 comp直接链接功能，所以这是出于图片。相反，我们将使用我们自己制作的call机制对函数进行排序。当程序发出run信号时，我们使用trampoline折叠了一堆调用。

下面，我们将看到应用flatten fix之前的表单

const cont = f => g =>
  is (run, g)
    ? trampoline (f (g))
    : cont (comp (g,f))
    : cont (k =>
        call (f, x =>
          call (g (x), k)))

const trampoline = ...

const call = ...

妄想

我们上面使用的另一种技术是我的最爱之一。当我写is (run, g)时，我不知道我将如何立即代表is或run，但我可以稍后解决。我对trampoline和call使用同样的一厢情愿。

我指出这一点是因为这意味着我可以将所有这些复杂性保留在cont之外并且只关注它的基本结构。我最终得到了一组函数，这些函数给了我这种“标记”行为

// tag contract
// is (t, tag (t, value)) == true

const TAG =
  Symbol ()

const tag = (t, x) =>
  Object.assign (x, { [TAG]: t })

const is = (t, x) =>
  x && x [TAG] === t

const run = x =>
  tag (run, x)

const call = (f, x) =>
  tag (call, { f, x })

一厢情愿的想法就是编写你想要的程序，让你的愿望成真。一旦你实现了所有的愿望，你的程序就会神奇地起作用！

最新问题
© www.soinside.com 2019 - 2024. All rights reserved.