javascript - 如何使蹦床适应持续传递风格？

Question

这是一个正确的天真实现:

const foldr = f => acc => ([x, ...xs]) =>
  x === undefined
    ? acc 
    : f(x) (foldkr(f) (acc) (xs));

这是非尾递归，因此我们无法应用蹦床。一种方法是使算法迭代，并使用堆栈来模仿函数调用堆栈。

另一个方法是将递归转换为CPS:

const Cont = k => ({runCont: k});

const foldkr = f => acc => ([x, ...xs]) =>
  Cont(k =>
    x === undefined
      ? k(acc)
      : foldkr(f) (acc) (xs)
          .runCont(acc_ => k(f(x) (acc_))));

这仍然很幼稚，因为它非常缓慢。这是内存消耗较少的版本:

const foldkr = f => acc => xs => {
  const go = i =>
    Cont(k =>
      i === xs.length
        ? k(acc)
        : go(i + 1)
            .runCont(acc_ => k(f(xs[i]) (acc_))));

  return go(0);
};

递归调用现在处于尾部位置，因此我们应该能够应用我们选择的蹦床:

const loop = f => {
  let step = f();

  while (step && step.type === recur)
    step = f(...step.args);

  return step;
};

const recur = (...args) =>
  ({type: recur, args});

const foldkr = f => acc => xs =>
  loop((i = 0) => 
    Cont(k =>
      i === xs.length
        ? k(acc)
        : recur(i + 1)
            .runCont(acc_ => k(f(xs[i]) (acc_)))));

这是行不通的，因为蹦床的调用位于延音内部，因此懒洋洋地被评估。如何调整蹦床使其与CPS配合使用？

Answer 1

尾部调用首先(第1部分)

首先编写循环，使其在尾部位置重复出现

const foldr = (f, init, xs = []) =>
  loop
    ( ( i = 0
      , k = identity
      ) =>
        i >= xs.length 
          ? k (init)
          : recur
              ( i + 1
              , r => k (f (r, xs[i]))
              )
   )

给定两个输入 small和 large，我们测试 foldr-

const small =
  [ 1, 2, 3 ]

const large =
  Array.from (Array (2e4), (_, n) => n + 1)

foldr ((a, b) => `(${a}, ${b})`, 0, small)
// => (((0, 3), 2), 1)

foldr ((a, b) => `(${a}, ${b})`, 0, large)
// => RangeError: Maximum call stack size exceeded

但是它使用蹦床，为什么对 large失败？简短的答案是因为我们构建了一个巨大的延迟计算 k ...

loop
  ( ( i = 0
    , k = identity // base computation
    ) =>
      // ...
      recur // this gets called 20,000 times
        ( i + 1
        , r => k (f (r, xs[i])) // create new k, deferring previous k
        )
  )

在终止条件下，我们最终调用 k(init)，它触发延迟计算的堆栈，深度20,000个函数调用，这触发了堆栈溢出。

在继续阅读之前，请展开以下代码段，以确保我们位于同一页面上-

const identity = x =>
  x
  
const loop = f =>
{ let r = f ()
  while (r && r.recur === recur)
    r = f (...r.values)
  return r
}

const recur = (...values) =>
  ({ recur, values })

const foldr = (f, init, xs = []) =>
  loop
    ( ( i = 0
      , k = identity
      ) =>
        i >= xs.length 
          ? k (init)
          : recur
              ( i + 1
              , r => k (f (r, xs[i]))
              )
   )

const small =
  [ 1, 2, 3 ]

const large =
  Array.from (Array (2e4), (_, n) => n + 1)

console.log(foldr ((a, b) => `(${a}, ${b})`, 0, small))
// (((0, 3), 2), 1)

console.log(foldr ((a, b) => `(${a}, ${b})`, 0, large))
// RangeError: Maximum call stack size exceeded

延迟溢出

如果您同时使用 compose(...)或 pipe(...) 20,000个功能，那么我们在这里看到的问题与您可能遇到的问题相同-

// build the composition, then apply to 1
foldl ((r, f) => (x => f (r (x))), identity, funcs) (1)

或类似的使用 comp-

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

// build the composition, then apply to 1
foldl (comp, identity, funcs) 1

当然， foldl是堆栈安全的，可以组成20,000个函数，但是一旦您调用了庞大的组合，便有冒死堆栈的风险。现在将其与-

// starting with 1, fold the list; apply one function at each step
foldl ((r, f) => f (r), 1, funcs)

...不会使堆栈崩溃，因为不推迟计算。取而代之的是，一步的结果会覆盖上一步的结果，直到达到最后一步。

实际上，当我们写的时候-

r => k (f (r, xs[i]))

另一种看待这种情况的方式是-

comp (k, r => f (r, xs[i]))

这应该突出显示问题所在。

可能的解决方案

一种简单的补救方法是添加一个单独的 call标记，以使蹦床中的延迟计算变平。因此，我们将直接编写 f (x)，而不是直接调用 call (f, x)这样的函数-

const call = (f, ...values) =>
  ({ call, f, values })

const foldr = (f, init, xs = []) =>
  loop
    ( ( i = 0
      , k = identity
      ) =>
        i >= xs.length 
          ? k (init)
          ? call (k, init)
          : recur
              ( i + 1
              , r => k (f (r, xs[i]))
              , r => call (k, f (r, xs[i]))
              )
   )

我们将蹦床修改为对 call-标记的值起作用-

const loop = f =>
{ let r = f ()
  while (r)
    if (r.recur === recur)
      r = f (...r.values)
    else if (r.call === call)
      r = r.f (...r.values)
    else
      break
  return r
}

最后，我们看到 large输入不再溢出堆栈-

foldr ((a, b) => `(${a}, ${b})`, 0, small)
// => (((0, 3), 2), 1)

foldr ((a, b) => `(${a}, ${b})`, 0, large)
// => (Press "Run snippet" below see results ...)

const identity = x =>
  x
  
const loop = f =>
{ let r = f ()
  while (r)
    if (r.recur === recur)
      r = f (...r.values)
    else if (r.call === call)
      r = r.f (...r.values)
    else
      break
  return r
}

const recur = (...values) =>
  ({ recur, values })
  
const call = (f, ...values) =>
  ({ call, f, values })

const foldr = (f, init, xs = []) =>
  loop
    ( ( i = 0
      , k = identity
      ) =>
        i >= xs.length 
          ? call (k, init)
          : recur
              ( i + 1
              , r => call (k, f (r, xs[i]))
              )
   )
   
const small =
  [ 1, 2, 3 ]

const large =
  Array.from (Array (2e4), (_, n) => n + 1)

console.log(foldr ((a, b) => `(${a}, ${b})`, 0, small))
// (((0, 3), 2), 1)

console.log(foldr ((a, b) => `(${a}, ${b})`, 0, large))
// (Press "Run snippet" to see results ...)

糟糕，您建立了自己的评估程序

上面的 recur和 call似乎是魔术函数。但实际上， recur和 call创建了简单的对象 { ... }，而 loop正在完成所有工作。这样， loop是一种接受 recur和 call表达式的评估程序。该解决方案的缺点是，我们希望调用者始终在尾部使用 recur或 call，否则循环将返回错误的结果。

这与将递归机制作为参数的Y组合器不同，并且不限于仅尾部的位置，例如 recur-

const Y = f => f (x => Y (f) (x))

const fib = recur => n =>
  n < 2
    ? n
    : recur (n - 1) + recur (n - 2) // <-- non-tail call supported
    
console .log (Y (fib) (30))
// => 832040

Y的缺点当然是，因为您可以通过调用一个函数来控制递归，所以与JS中的所有其他函数一样，您仍然处于堆栈不安全状态。结果是堆栈溢出-

console .log (Y (fib) (100))
// (After a long time ...)
// RangeError: Maximum call stack size exceeded

那么有可能在非尾部位置支持 recur并保持堆栈安全吗？当然，足够聪明的 loop应该能够评估递归表达式-

const fib = (init = 0) =>
  loop
    ( (n = init) =>
        n < 2
          ? n
          : call
              ( (a, b) => a + b
              , recur (n - 1)
              , recur (n - 2)
              ) 
    )

fib (30)
// expected: 832040

loop成为CPS尾递归函数，用于评估输入表达式 call， recur等。然后将 loop放在蹦床上。 loop有效地成为了我们自定义语言的评估者。现在您可以忘记所有有关堆栈的信息–现在唯一的限制就是内存!

或者 -

const fib = (n = 0) =>
  n < 2
    ? n
    : call
        ( (a, b) => a + b
        , call (fib, n - 1)
        , call (fib, n - 2)
        )

loop (fib (30))
// expected: 832040

在此 related Q&A中，我为JavaScript中的未类型化lambda演算编写了一个正态评估器。它显示了如何编写不受宿主语言的实现效果(评估策略，堆栈模型等)影响的程序。那里我们使用教堂编码，这里使用 call和 recur，但是技术是相同的。

几年前，我使用上述技术编写了一个堆栈安全的变体。我将查看是否可以重新启用它，并稍后在此答案中将其设置为可用。现在，我将 loop评估器作为练习供读者阅读。

第2部分已添加: loop evaluator

替代解决方案

在此 related Q&A中，我们构建了一个堆栈安全的延续monad。