问题描述
这是一个右折叠的简单实现:
Here is a naive implementation of a right fold:
const foldr = f => acc => ([x, ...xs]) =>
x === undefined
? acc
: f(x) (foldkr(f) (acc) (xs));
这是非尾递归，因此我们不能应用蹦床.一种方法是使算法迭代并使用堆栈来模拟函数调用堆栈.
This is non-tail recursion and hence we cannot apply a trampoline. One approach would be to make the algorithm iterative and use a stack to mimick the function call stack.
另一种方法是将递归转换为 CPS:
Another approch would be to transform the recursion into 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_))));
这仍然很幼稚，因为它非常慢.这是一个内存消耗较少的版本:
This is still naive, because it is insanely slow. Here is a less memory consuming version:
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);
};
递归调用现在处于尾部位置，因此我们应该能够应用我们选择的蹦床:
The recursive call is now in tail position hence we should be able to apply a trampoline of our choice:
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 配合使用?
This doesn't work, because the trampoline call is inside the continuation and thus lazily evaluated. How must the trampoline be adapted so that it works with CPS?
推荐答案
尾调用优先(第 1 部分)
首先编写循环，使其在尾部位置重复
First write the loop such that it recurs in tail position
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 -
Given two inputs, small and large, we test 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 ...
But it uses a trampoline, why does it fail for large? The short answer is because we built a huge deferred computation, 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 次函数，从而触发堆栈溢出.
In the terminating condition, we finally call k(init) which fires off the stack of deferred computations, 20,000 function calls deep, which triggers the stack-overflow.
在继续阅读之前，请展开下面的片段以确保我们在同一页面上 -
Before reading on, expand the snippet below to make sure we're on the same page -
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 个函数时可能遇到的问题相同在一起 -
The problem we're seeing here is the same one you might encounter if you were to compose(...) or pipe(...) 20,000 functions together -
// 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 个函数，但是一旦您调用庞大的组合，就有可能炸毁堆栈.现在比较 -
Sure, foldl is stack-safe and it can compose 20,000 functions, but as soon as you call the massive composition, you risk blowing the stack. Now compare that to -
// starting with 1, fold the list; apply one function at each step
foldl ((r, f) => f (r), 1, funcs)
... 不会破坏堆栈，因为计算没有延迟.相反，一步的结果会覆盖上一步的结果，直到到达最后一步.
... which does not blow the stack because the computations are not deferred. Instead the result from one step overwrites the result from the previous step until the final step is reached.
其实我们写的时候——
r => k (f (r, xs[i]))
另一种查看方式是 -
comp (k, r => f (r, xs[i]))
这应该准确地突出问题所在.
This should highlight exactly where the problem is.
可能的解决方案
一个简单的补救措施是添加一个单独的 call 标记，以扁平化蹦床中的延迟计算.所以不是像 f (x) 那样直接调用函数，我们会写 call (f, x) -
One simple remedy is to add a separate call tag that flattens the deferred computation in the trampoline. So instead of calling a function directly like f (x), we'll write 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) rewrite as
? call (k, init)
: recur
( i + 1
// r => k (f (r, xs[i])) rewrite as
, r => call (k, f (r, xs[i]))
)
)
我们修改trampoline 来处理call-tagged 值-
We modify the trampoline to act on call-tagged values -
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输入不再溢出堆栈-
Finally, we see that the large input no longer overflows the stack -
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 ...)wups，您构建了自己的评估器
上面，recur 和 call 似乎是魔术函数.但实际上，recur 和 call 创建了简单的对象 { ... } 而 loop 正在做所有的事情工作.这样，loop是一种求值器，它接受recur和call表达式.这种解决方案的一个缺点是我们希望调用者总是在尾部位置使用 recur 或 call ，否则循环将返回错误的结果.
Above, recur and call appear to be magic functions. But in reality, recur and call create simple objects { ... } and loop is doing all of the work. In this way, loop is a type of evaluator that accepts recur and call expressions. The one down-side to this solution is that we expect the caller always to use recur or call in tail position, otherwise the loop will return an incorrect result.
这不同于将递归机制具体化为参数的Y-combinator，并且不限于仅尾部的位置，比如这里的recur -
This is different than the Y-combinator which reifies the recursion mechanism as a parameter, and is not limited to a tail-only position, such as recur here -
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))
// => 832040Y 的一个缺点当然是，因为你通过调用函数来控制递归，你仍然是堆栈不安全的，就像其他函数一样JS.结果是堆栈溢出 -
The one down-side to Y is, of course, because you control recursion by calling a function, you are still stack-unsafe just like all other functions in JS. The result is a stack-overflow -
console .log (Y (fib) (100))
// (After a long time ...)
// RangeError: Maximum call stack size exceeded
那么是否有可能支持 recur 在非尾部位置 并且 保持堆栈安全?当然，一个足够聪明的 loop 应该能够计算递归表达式 -
So would it be possible to support recur in non-tail position and remain stack-safe? Sure, a sufficiently clever loop should be able evaluate recursive expressions -
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 有效地成为我们自定义语言的评估器.现在你可以忘掉所有关于堆栈的事情——你现在唯一的限制是内存！
loop becomes a CPS tail-recursive function for evaluating the input expressions call, recur, etc. Then we put loop on a trampoline. loop effectively becomes an evaluator for our custom language. Now you can forget all about the stack – your only limitation now is memory!
或者 -
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
在此相关问答中，我为 JavaScript 中的无类型 lambda 演算编写了一个正态序评估器.它展示了如何编写不受宿主语言实现影响(评估策略、堆栈模型等)的程序.我们在那里使用 Church-encoding，这里使用了 call 和 recur，但技术是相同的.
In this related Q&A, I write a normal-order evaluator for untyped lambda calculus in JavaScript. It shows how you can write programs that are freed from the implementation effects (evaluation strategy, stack model, etc) of the host language. There we're using Church-encoding, here were using call and recur, but the technique is the same.
多年前，我使用上述技术编写了一个堆栈安全变体.我会看看我是否可以复活它，然后在这个答案中提供它.现在，我将 loop 评估器留给读者作为练习.
Years back, I wrote a stack-safe variation using the technique I described above. I'll see if I can ressurrect it and later make it available in this answer. For now, I'll leave the loop evaluator as an exercise for the reader.
添加了第 2 部分: 循环评估器
替代解决方案
在这个相关问答中，我们构建了一个堆栈安全的延续单子.
In this related Q&A, we build a stack-safe continuation monad.
这篇关于如何让蹦床适应连续传球风格?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！