52

这是代码：

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

我读过蹦床是用来处理溢出问题的，所以函数不会只是不断地调用自己并导致堆栈填满。

但是这个片段是如何起作用的呢？特别是trampoline功能？它究竟做了什么，while又是如何实现目标的？

4

3 回答 3

134

蹦床只是一种优化递归并防止在不支持tail call optimizationJavascript ES5 实现和 C# 的语言中出现堆栈溢出异常的技术。但是，ES6 可能会支持尾调用优化。

常规递归的问题在于，每个递归调用都会向调用堆栈添加一个堆栈帧，您可以将其可视化为调用金字塔。这是递归调用阶乘函数的可视化：

(factorial 3)
(* 3 (factorial 2))
(* 3 (* 2 (factorial 1)))
(* 3 (* 2 (* 1 (factorial 0)))) 
(* 3 (* 2 (* 1 1)))
(* 3 (* 2 1))
(* 3 2)
6

这是堆栈的可视化，其中每个垂直破折号都是堆栈帧：

         ---|---
      ---|     |---
   ---|            |--- 
---                    ---

问题是堆栈的大小有限，将这些堆栈帧堆叠起来可能会使堆栈溢出。根据堆栈大小，计算更大的阶乘会溢出堆栈。这就是为什么 C#、Javascript 等中的常规递归可能被认为是危险的。

最佳执行模型类似于蹦床而不是金字塔，其中每个递归调用都在原地执行，并且不会堆叠在调用堆栈上。支持尾调用优化的语言中的执行可能如下所示：

(fact 3)
(fact-tail 3 1)
(fact-tail 2 3)
(fact-tail 1 6)
(fact-tail 0 6)
6

您可以将堆栈可视化为弹跳蹦床：

   ---|---   ---|---   ---|---
---      ---       ---

这显然更好，因为堆栈始终只有一帧，并且从可视化中您还可以看到为什么它被称为蹦床。这可以防止堆栈溢出。

由于我们没有tail call optimizationJavascript 的奢侈，我们需要想办法将常规递归转换为可以以蹦床方式执行的优化版本。

一种明显的方法是摆脱递归，并将代码重写为迭代。

当这不可能时，我们需要更复杂的代码，而不是直接执行递归步骤，我们将利用higher order functions返回一个包装函数而不是直接执行递归步骤，并让另一个函数控制执行。

在您的示例中，repeat函数用一个函数包装了常规递归调用，它返回该函数而不是执行递归调用：

function repeat(operation, num) {
    return function() {
       if (num <= 0) return
       operation()
       return repeat(operation, --num)
    }
}

返回的函数是递归执行的下一步，而蹦床是一种在 while 循环中以受控和迭代方式执行这些步骤的机制：

function trampoline(fn) {
    while(fn && typeof fn === 'function') {
        fn = fn()
    }
}

所以 trampoline 函数的唯一目的是以迭代方式控制执行，并确保堆栈在任何给定时间都只有一个堆栈帧。

使用蹦床显然不如简单递归的性能，因为您“阻塞”了正常的递归流程，但它更安全。

http://en.wikipedia.org/wiki/Tail_call

http://en.wikipedia.org/wiki/Trampoline_%28computing%29

于 2014-12-30T11:19:34.100 回答
7

循环将while继续运行，直到条件不成立。

fn && typeof fn === 'function'如果fn它本身是假的，或者如果fn不是一个函数，那么它将是假的。

前半部分实际上是多余的，因为虚假值也不是函数。

于 2014-08-10T13:08:44.877 回答
7

其他回复描述了蹦床的工作原理。但是，给定的实现有两个缺点，其中一个甚至是有害的：

  • 蹦床协议只依赖于函数。如果递归操作的结果也是一个函数怎么办？
  • 您必须在整个调用代码中应用递归函数和蹦床函数。这是一个应该隐藏的实现细节。

从本质上讲，蹦床技术以一种热切评估的语言处理惰性评估。这是一种避免上述缺点的方法：

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

惰性求值发生在本地内部repeat。因此，您的调用代码无需担心。

于 2017-05-29T14:22:53.970 回答