开发者问题收集

ES6 尾部递归优化 Stack Overflow

2017-03-14
18866

在阅读了 Rauschmayer 博士对 es6 中递归尾调用优化的描述 后,我一直试图重新创建他详述的递归阶乘函数的“零堆栈”执行。

使用 Chrome 调试器在堆栈帧之间移动,我发现尾部优化没有发生,并且为每个递归创建了一个堆栈帧。

我还尝试通过在不使用调试器的情况下调用该函数来测试优化,而是将 100000 传递给阶乘函数。这会引发“最大堆栈”错误,这意味着它实际上并未经过优化。

这是我的代码:

const factorial = (n, acc = 1) => n <= 1 ? acc : factorial(n - 1, n * acc)
console.log( factorial(100000) )

结果:

Uncaught RangeError: Maximum call stack size exceeded
2个回答

Chrome 中的 JavaScript 引擎 V8 曾一度支持 TCO,但自此更新答案(2017 年 11 月)起,它不再支持 TCO,V8 中没有 TCO 的积极开发,也没有计划。您可以在 V8 跟踪错误 中阅读详细信息。

TCO 支持似乎在 V8 中一度达到了不错的水平,但由于多种原因(调试问题、错误),仍处于标记状态。但随后发生了几件事,其中最主要的是 V8 团队提出了 TCO 的重大问题 ,并强烈支持一项名为 语法尾调用 (STC) 的规范变更,该变更要求在源代码中故意标记尾调用(例如 return continue doThat(); )。不过,该提案于 2017 年 7 月变为 无效 。同样在 7 月,由于没有进行任何 TCO 工作,V8 团队从 TurboFan* 的源代码中删除了支持 TCO 的代码,否则它可能会受到 bitrot 的影响。(例如,成为维护的麻烦和错误的来源。)

因此,目前(2017 年 11 月),尚不清楚“隐形”TCO 是否会出现在 V8 中,是否会引入某种 STC,或者其他什么。 Chrome 平台状态页面 对此表示,Mozilla(Firefox/SpiderMonkey)和 Microsoft(Edge/Chakra)在支持 TCO 方面公开发出了“混合”信号,Safari 随附 TCO,并且 Web 开发人员对该功能持“积极”态度。我们将拭目以待下一步。如果有的话。

*(TurboFan = V8 中当前最先进的 JIT 编译器,现在他们已经 切换 从 Full-Codegen [JIT] + Crankshaft [积极优化 JIT] 到 Ignition [interpreter+] 和 TurboFan [积极优化 JIT])

T.J. Crowder
2017-03-14

V8(Chrome 的 JS 引擎)团队暂时不会实施 TCO。该功能已从最新版本中删除( 请参阅此主题 )。

在主流浏览器中, 只有 Safari 真正实现了该功能 (在 这篇 2016 Webkit 博客文章 中进行了描述)。

在 Node.JS 版本 8 及更高版本中, TCO 不可用

可能有一些希望正在实施的 TCO:在 2017 年 WebAssembly 会议 上,Google 和所有其他与会团体对进一步探索 TCO 实施持中立或积极态度。

Freewalker
2017-11-09