ES6 尾递归优化堆栈溢出 [英] ES6 Tail Recursion Optimisation Stack Overflow

问题描述

已阅读Rauschmayer 博士对递归尾调用优化的描述在 es6 中，我一直在尝试重新创建他详细介绍的递归阶乘函数的零堆栈"执行.

使用 Chrome 调试器在堆栈帧之间步进，我看到尾部优化没有发生，并且正在为每次递归创建一个堆栈帧.

我还尝试通过在没有调试器的情况下调用函数来测试优化，而是将 100000 传递给阶乘函数.这会引发最大堆栈"错误，这意味着它实际上并未优化.

Having read Dr Rauschmayer's description of recursive tail call optimisation in es6, I've since been trying to recreate the 'zero-stack' execution of the recursive factorial function he details.

Using the Chrome debugger to step between stack frames, I'm seeing that the tail optimisation is not occurring and a stack frame is being created for each recursion.

I've also tried to test the optimisation by calling the function without the debugger, but instead passing 100000 to the factorial function. This throws a 'maximum stack' error, which implies that it is, in fact, not optimised.

这是我的代码:

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

结果:

Uncaught RangeError: Maximum call stack size exceeded

推荐答案

V8，Chrome 中的 JavaScript 引擎，支持 TCO 有一段时间了，但从这个更新的答案(2017 年 11 月)开始，它不再支持写作，在 V8 中没有关于 TCO 的积极开发，也没有计划.您可以在针对它的 V8 跟踪错误中阅读详细信息.

V8, the JavaScript engine in Chrome, had TCO support for a while, but as of this updated answer (November 2017) it no longer does and as of this writing, there is no active development on TCO in V8, and none is planned. You can read the details in the V8 tracking bug for it.

在 V8 中，TCO 支持似乎一度达到了不错的水平，但由于多种原因(调试问题、错误)仍然落后于标志.但随后发生了几件事，尤其是 V8 团队提出TCO 的重大问题，并强烈支持称为句法尾调用 (STC) 要求在源代码中有意标记尾调用(例如，return continue doThat();).不过，该提案在 2017 年 7 月成为无效.同样在 7 月，由于没有完成 TCO 工作，V8 团队从 TurboFan* 的源代码中删除了支持 TCO 的代码，否则它会受到 bitrot 的影响.(例如，成为维护的痛苦和错误的来源.)

TCO support seems to have reached a decent level in V8 at one point, but remained behind a flag for several reasons (debugging issues, bugs). But then several things happened, not least that the V8 team raised significant issues with TCO and strongly supported a spec change called syntactic tail calls (STCs) that would require that tail calls be flagged in source code intentionally (e.g., return continue doThat();). That proposal became inactive in July 2017, though. Also in July, with no TCO work being done, the V8 team removed the code for supporting TCO from the source for TurboFan* as it would otherwise be subject to bitrot. (E.g., become a maintenance pain and source of bugs.)

因此，目前(2017 年 11 月)尚不清楚隐形"TCO 是否会出现在 V8 中，是否会出现某种 STC，或者什么.Chrome 平台状态页面表示来自 Mozilla (Firefox/SpiderMonkey) 和Microsoft (Edge/Chakra) 支持 TCO，Safari 附带 TCO，Web 开发人员对该功能持积极态度".我们会看看我们从这里往哪里去.如果在任何地方.

So at present (Nov 2017) it's not clear that "invisible" TCO will ever be in V8, whether some kind of STCs will come in, or what. The Chrome Platform Status page for this indicates "mixed" public signals from Mozilla (Firefox/SpiderMonkey) and Microsoft (Edge/Chakra) on supporting TCO, that Safari is shipping with TCO, and that web developers are "positive" about the feature. We'll see where we go from here. If anywhere.

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

* (TurboFan = the current cutting-edge JIT compiler in V8, now they've switched from Full-Codegen [JIT] + Crankshaft [aggressive optimizing JIT] to Ignition [interpreter+] and TurboFan [aggressive optimizing JIT])

这篇关于ES6 尾递归优化堆栈溢出的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！