如何在JavaScript中理解蹦床？

Question

这是代码:

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以及它是如何实现其目标的？

感谢您的任何帮助 :)

Answer 1

蹦床只是一种优化递归并防止不支持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)
    }
}

返回的函数是递归执行的下一步,而trampoline是一种在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

Answer 2

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

• 蹦床协议仅取决于功能。如果递归操作的结果也是一个函数呢？
• 您必须在整个调用代码中使用带有trampoline 函数的递归函数。这是一个应该隐藏的实现细节。

本质上，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)); // 1000000

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

Answer 3

该while循环将继续运行,直到条件为falsy.

fn && typeof fn === 'function'如果fn它本身是假的,或者fn除了函数之外的任何东西,它将是假的.

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