如何理解 JavaScript 中的蹦床？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/25228871/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
How to understand trampoline in JavaScript?
提问by Zhen Zhang
Here is the code:
这是代码：
function repeat(operation, num) {
return function() {
if (num <= 0) return
operation()
return repeat(operation, --num)
}
}
function trampoline(fn) {
while(fn && typeof fn === 'function') {
fn = fn()
}
}
module.exports = function(operation, num) {
trampoline(function() {
return repeat(operation, num)
})
}
I have read that the trampoline is used to deal with overflow problem, so the function would not just keep call itself and the stack up.
我读过蹦床是用来处理溢出问题的，所以该函数不会只是保持调用自身和堆栈。
But how does this snippet function? Especially the trampolinefunction? What did it exactly do by whileand how did it accomplish its goal?
但是这个片段是如何起作用的呢？特别是trampoline功能？它究竟做了什么while以及它是如何实现其目标的？
Thank you for any help :)
感谢您的任何帮助 ：）
采纳答案by SLaks
The whileloop will keep running until the condition is falsy.
该while循环将继续运行，直到条件falsy。
fn && typeof fn === 'function'will be falsy either if fnitself is falsy, or if fnis anything other than a function.
fn && typeof fn === 'function'如果fn它本身是假的，或者如果fn不是函数，则将是假的。
The first half is actually redundant, since falsy values are also not functions.
前半部分实际上是多余的，因为假值也不是函数。
回答by Faris Zacina
The trampoline is just a technique to optimize recursionand prevent stack-overflow exceptions in languages that don't support tail call optimizationlike Javascript ES5 implementation and C#. However, ES6 will probably have support for tail call optimization.
蹦床只是一种在不支持Javascript ES5 实现和 C# 等语言中优化递归和防止堆栈溢出异常的技术tail call optimization。但是，ES6 可能会支持尾调用优化。
The problem with regular recursion is that every recursive call adds a stack frame to the call stack, which you can visualize as a pyramidof calls. Here is a visualization of calling a factorial function recursively:
常规递归的问题在于每次递归调用都会向调用堆栈添加一个堆栈框架，您可以将其可视化为调用金字塔。这是递归调用阶乘函数的可视化：
(factorial 3)
(* 3 (factorial 2))
(* 3 (* 2 (factorial 1)))
(* 3 (* 2 (* 1 (factorial 0))))
(* 3 (* 2 (* 1 1)))
(* 3 (* 2 1))
(* 3 2)
6
Here is a visualization of the stack where each vertical dash is a stack frame:
这是堆栈的可视化，其中每个垂直破折号是一个堆栈框架：
---|---
---| |---
---| |---
--- ---
The problem is that the stack has limited size, and stacking up these stack frames can overflow the stack. Depending on the stack size, a calculation of a larger factorial would overflow the stack. That is why regular recursion in C#, Javascript etc. could be considered dangerous.
问题是堆栈的大小有限，将这些堆栈帧堆叠起来可能会导致堆栈溢出。根据堆栈大小，较大阶乘的计算会溢出堆栈。这就是为什么 C#、Javascript 等中的常规递归可能被认为是危险的。
An optimal execution model would be something like a trampolineinstead of a pyramid, where each recursive call is executed in place, and does not stack up on the call stack. That execution in languages supporting tail call optimization could look like:
最佳执行模型类似于蹦床而不是金字塔，其中每个递归调用都在原地执行，并且不会堆积在调用堆栈上。在支持尾调用优化的语言中的执行可能如下所示：
(fact 3)
(fact-tail 3 1)
(fact-tail 2 3)
(fact-tail 1 6)
(fact-tail 0 6)
6
You can visualize the stack like a bouncing trampoline:
您可以像弹跳蹦床一样将堆栈可视化：
---|--- ---|--- ---|---
--- --- ---
This is clearly better since the stack has always only one frame, and from the visualization you can also see why it is called a trampoline. This prevents the stack from overflowing.
这显然更好，因为堆栈始终只有一帧，从可视化中您还可以看到为什么它被称为蹦床。这可以防止堆栈溢出。
Since we don't have the luxury of tail call optimizationin Javascript, we need to figure out a way to turn regular recursion into an optimized version that will execute in trampoline-fashion.
由于我们没有tail call optimizationJavascript的奢侈，我们需要想办法将常规递归转换为以蹦床方式执行的优化版本。
One obvious way is to get rid of recursion, and rewrite the code to be iterative.
一种明显的方法是摆脱递归，并重写代码以进行迭代。
When that is not possible we need a bit more complex code where instead of executing directly the recursive steps, we will utilize higher order functionsto return a wrapper function instead of executing the recursive step directly, and let another function control the execution.
如果这是不可能的，我们需要更复杂的代码，而不是直接执行递归步骤，我们将利用higher order functions返回包装函数而不是直接执行递归步骤，并让另一个函数控制执行。
In your example, the repeatfunction wraps the regular recursive call with a function, and it returns that function instead of executing the recursive call:
在您的示例中，repeat函数用一个函数包装常规递归调用，并返回该函数而不是执行递归调用：
function repeat(operation, num) {
return function() {
if (num <= 0) return
operation()
return repeat(operation, --num)
}
}
The returned function is the next step of recursive execution and the trampoline is a mechanism to execute these steps in a controlled and iterative fashion in the while loop:
返回的函数是递归执行的下一步，trampoline 是一种在 while 循环中以受控和迭代方式执行这些步骤的机制：
function trampoline(fn) {
while(fn && typeof fn === 'function') {
fn = fn()
}
}
So the sole purpose of the trampoline function is to control the execution in an iterative way, and that ensures the stack to have only a single stack frame on the stack at any given time.
因此，trampoline 函数的唯一目的是以迭代方式控制执行，并确保堆栈在任何给定时间在堆栈上只有一个堆栈帧。
Using a trampoline is obviously less performant than simple recursion, since you are "blocking" the normal recursive flow, but it is much safer.
使用蹦床显然比简单递归的性能低，因为您“阻塞”了正常的递归流，但它更安全。
http://en.wikipedia.org/wiki/Tail_call
http://en.wikipedia.org/wiki/Tail_call
回答by SLaks
The other replies describe how a trampoline works. The given implementation has two drawbacks though, one of which is even harmful:
其他回复描述了蹦床的工作原理。但是，给定的实现有两个缺点，其中之一甚至是有害的：
- The trampoline protocol depends only on functions. What if the result of the recursive operation is a function as well?
- You have to apply the recursive function with the trampoline function throughout your calling code. This is an implementation detail that should be hidden.
- 蹦床协议仅取决于功能。如果递归操作的结果也是一个函数呢？
- 您必须在整个调用代码中使用带有trampoline 函数的递归函数。这是一个应该隐藏的实现细节。
Essentially, the trampoline technique deals with lazy evaluation in an eagerly evaluated language. Here is an approach that avoids the drawbacks mentioned above:
本质上，trampoline 技术在急切求值的语言中处理惰性求值。这是一种避免上述缺点的方法：
// a tag to uniquely identify thunks (zero-argument functions)
const $thunk = Symbol.for("thunk");
// eagerly evaluate a lazy function until the final result
const eager = f => (...args) => {
let g = f(...args);
while (g && g[$thunk]) g = g();
return g;
};
// lift a normal binary function into the lazy context
const lazy2 = f => (x, y) => {
const thunk = () => f(x, y);
return (thunk[$thunk] = true, thunk);
};
// the stack-safe iterative function in recursive style
const repeat = n => f => x => {
const aux = lazy2((n, x) => n === 0 ? x : aux(n - 1, f(x)));
return eager(aux) (n, x);
};
const inc = x => x + 1;
// and run...
console.log(repeat(1e6) (inc) (0)); // 1000000The lazy evaluation takes place locally inside repeat. Hence your calling code doesn't need to worry about it.
惰性求值发生在本地内部repeat。因此，您的调用代码无需担心。
