如何使蹦床适应持续传递风格? [英] How to adapt trampolines to Continuation Passing Style?
问题描述
这是正确折叠的幼稚实现方式:
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标签，以使蹦床中的延迟计算变平.因此，我们将直接编写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)
? call (k, init)
: recur
( i + 1
, r => k (f (r, xs[i]))
, r => call (k, f (r, xs[i]))
)
)我们修改了蹦床，使其作用于带有call标签的值-
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 ...)
糟糕，您建立了自己的评估程序
，recur和call似乎是魔术函数.但实际上，recur和call创建简单的对象{ ... }，而loop正在完成所有工作.这样，loop是一种 evaluator ，它接受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组合器不同，并且不限于仅尾部的位置，例如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))
// => 832040
Y的一个缺点当然是，因为您通过调用一个函数来控制递归，所以与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有效地成为我们自定义语言的评估者.现在您可以忘记所有有关堆栈的信息了-ndash;您现在唯一的限制就是记忆力！
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演算编写了一个正序求值器.它显示了如何编写不受宿主语言的实现效果(评估策略，堆栈模型等)影响的程序.在那里，我们使用教堂编码，这里使用的是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.
PART 2已添加: 循环评估器
替代解决方案
在与此相关的问题与解答中，我们构建了一个堆栈安全的连续单子.
In this related Q&A, we build a stack-safe continuation monad.
这篇关于如何使蹦床适应持续传递风格?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
