代码之家 › 专栏 › 技术社区 › user6445533

如何为continuation monad实现堆栈安全chainRec操作符?

continuation-passing tail-recursion monads functional-programming javascript

user6445533 · 技术社区 · 7 年前

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

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

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 带a的typeclass tailRecM 对某些单子启用尾部递归一元计算的运算符。所以我试着实施 chainRec 在Javascript中,主要根据fantasy land规范:

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
);

这是可行的,但看起来很像作弊,因为它似乎绕过了一元链,因此 继续 的上下文。在这种情况下,上下文只是“计算的其余部分”,即相反的函数组合,因此返回预期值。但它对任何单子都有效吗?

为了弄清楚我的意思,请看下面的代码片段 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 在某种程度上被合并到递归算法中,即可以发生一元效应。不幸的是,我无法破译此运算符,也无法将其与堆栈不安全版本进行协调( Bounce(g(x)._runCont, k) 似乎是 f(x) (k) 部分)。

最终,我的问题是,如果我把 chainRec公司 或者误解了FL规范,或者两者都误解了,或者根本没有误解?

[编辑]

从不同的角度来看问题,给出的两个答案都非常有用,值得接受。因为我只能接受一个——嘿,stackoverflow,世界不是那么简单!!!-我什么都不接受。

2 回复 | 直到 7 年前

Mulan 7 年前

致以最良好的祝愿,

我想这可能就是你要找的,

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

实施 repeat 与您的情况一样,只有两个例外(感谢@Bergi抓住了这个细节)。1. loop 和 done 是链接函数,以及 chainRec 回调必须返回延续。第二,我们必须标签具有的函数 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_ . 我们可以定义 重复 直接地

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级 标记为 跑 ,那么是时候在 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 咬那个 扁平化 结构。使用的JS对象编码,此任务很简单 Cont 我们只需阅读 ._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))) 
   })

在我们的新编码中,我们使用作用代表 继续 ,除非我们提供另一个特殊信号 跑 ),无法访问 f 外部 继续 一旦部分应用,请查看 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 (something) ),但这意味着整个 继续 函数可以无限嵌套。而不是 继续 -已包装 something 我们只有希望 某物 .

我花在这个答案上的时间中,至少有50%的时间都在想出各种方法来将部分应用的 继续 . 这个解决方案并不是特别优雅,但它确实完成了工作,并精确地强调了需要发生的事情。我真的很想知道你可能会在其他编码中发现什么变化 大胆的

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)))

所有系统都在线,舰长

使用 继续 将补丁平整到位,其他一切都能正常工作。现在请参见 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的演变

当我们介绍 继续 在上面的代码中,还不清楚这种编码是如何派生出来的。我希望对此有所了解。我们从如何希望我们可以定义 继续

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

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

在此表格中, 继续 将无休止地推迟评估。这个只有我们可以做的就是申请 g级 哪一个总是创建另一个 继续 推迟我们的行动。我们加了一个逃生舱, 跑 ,它向 继续 我们不想再拖延了。

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

在上面,我们可以开始了解 继续 能表达美丽纯净的节目。然而 在没有尾部调用消除的环境中 ,这仍然允许程序构建超出计算器堆栈限制的延迟函数序列。 comp 直接链接函数,因此这是不可能的。相反,我们将使用 呼叫 我们自己制造的机制。当程序发出信号时 跑 ,我们使用 蹦床 .

下面,我们得到了应用展平修复之前的表单

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 或 跑 马上,但我可以稍后再弄清楚。我用同样的一厢情愿 蹦床 和 呼叫 .

我指出这一点是因为这意味着我可以避免所有的复杂性 继续 只关注它的基本结构。我最终得到了一组函数,这些函数赋予了我这种“标记”行为

// 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 })

一厢情愿就是写下你想要的程序,让你的愿望成真。一旦你实现了所有的愿望,你的程序就会神奇地工作!

Bergi 7 年前

我是否搞砸了 chainRec 或者误解了幻想世界的规格,或者两者都误解了,或者两者都没有?

可能两者都有,或者至少第一个。请注意 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)
  );

甚至放弃完成/循环

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) 返回一个延续。

我将离开 重复 作为对读者的练习:D
(提示:如果您有重复的函数,它可能会变得更有用,也更容易得到正确的结果。) f 已使用延续)