Node.js 尾调用优化:可能与否?

IT技术 javascript node.js tail-call-optimization
2021-02-08 20:45:56

我像JavaScript到目前为止,并决定使用Node.js的为我的发动机的部分原因是因为这个,它声称的Node.js提供TCO。但是,当我尝试使用 Node.js 运行此(显然是尾调用)代码时,它会导致堆栈溢出:

function foo(x) {
    if (x == 1) {
        return 1;
    }
    else {
        return foo(x-1);
    }
}

foo(100000);

现在,我做了一些挖掘,我找到了这个这里,好像说我应该这样写:

function* foo(x) {
    if (x == 1) {
        return 1;
    }
    else {
        yield foo(x-1);
    }
}

foo(100000);

但是,这给了我语法错误。我尝试了它的各种排列,但在所有情况下,Node.js 似乎对某些东西不满意

基本上,我想知道以下内容:

  1. Node.js 是否有 TCO?
  2. 这个神奇的yield东西在 Node.js 中是如何工作的?
4个回答

这里有两个相当不同的问题:

  • Node.js 是否有 TCO?
  • 这个神奇的 yield 东西在 Node.js 中是如何工作的?

Node.js 是否有 TCO?

TL;DR不再是,从 Node 8.x 开始它有一段时间,在一个或另一个标志背后,但在撰写本文时(2017 年 11 月),它不再支持,因为它使用的底层 V8 JavaScript 引擎不再支持 TCO。有关更多信息,请参阅此答案

细节:

尾调用优化 (TCO) 是ES2015(“ES6”)规范的必需部分因此,直接支持它并不是 NodeJS 的事情,而是 NodeJS 使用的 V8 JavaScript 引擎需要支持的东西。

从 Node 8.x 开始,V8 不支持 TCO,甚至不支持。它可能会(再次)在未来的某个时候这样做;有关更多信息,请参阅此答案

Node 7.10 至少降到 6.5.0(我的笔记说 6.2,但node.green不同意)仅在严格模式下支持标记后面的 TCO(--harmony在 6.6.0 及更高--harmony_tailcalls版本中更早版本)。

如果你想检查你的安装,这里是node.green使用的测试(如果你使用的是相关版本,请务必使用该标志):

function direct() {
    "use strict";
    return (function f(n){
      if (n <= 0) {
        return  "foo";
      }
      return f(n - 1);
    }(1e6)) === "foo";
}

function mutual() {
    "use strict";
    function f(n){
      if (n <= 0) {
        return  "foo";
      }
      return g(n - 1);
    }
    function g(n){
      if (n <= 0) {
        return  "bar";
      }
      return f(n - 1);
    }
    return f(1e6) === "foo" && f(1e6+1) === "bar";
}

console.log(direct());
console.log(mutual());
$ # 只​​有某些版本的 Node,特别是 8.x 或(目前)9.x 不是;往上看
$ node --harmony tco.js
真的
真的

这个神奇的yield东西在 Node.js 中是如何工作的?

这是 ES2015 的另一个东西(“生成器函数”),所以这也是 V8 必须实现的东西。它在 Node 6.6.0 的 V8 版本中完全实现(并且已经用于多个版本)并且没有任何标志。

生成器函数(用function*和 using编写的yield)通过能够停止并返回一个迭代器来工作,该迭代器捕获它们的状态,并可用于在随后的情况下继续它们的状态。亚历克斯Rauschmeyer对他们进行了深入的文章在这里

这是一个显式使用生成器函数返回的迭代器的示例,但您通常不会这样做,我们稍后会看到原因:

"use strict";
function* counter(from, to) {
    let n = from;
    do {
        yield n;
    }
    while (++n < to);
}

let it = counter(0, 5);
for (let state = it.next(); !state.done; state = it.next()) {
    console.log(state.value);
}

有这个输出:

0
1
2
3
4

这是它的工作原理:

  • 当我们调用counter( let it = counter(0, 5);) 时,调用的初始内部状态counter被初始化,我们立即得到一个迭代器;没有counter运行中的实际代码(还)。
  • Callingit.next()将代码counter向上运行到第一个yield语句。此时,counter暂停并存储其内部状态。it.next()返回一个带有done标志和value. 如果done标志为falsevalue则为yield语句产生的值
  • 每次调用都会将it.next()内部状态推进counter到下一个yield.
  • 当调用it.next()使counter完成并返回时,我们返回的状态对象已done设置为truevalue设置为 的返回值counter

拥有迭代器和状态对象的变量以及调用it.next()和访问donevalue属性都是样板文件,(通常)会妨碍我们尝试做的事情,因此 ES2015 提供了新的for-of语句,将其全部隐藏起来我们,只是给我们每一个value。这是上面写的相同代码for-of

"use strict";
function* counter(from, to) {
    let n = from;
    do {
        yield n;
    }
    while (++n < to);
}

for (let v of counter(0, 5)) {
    console.log(v);
}

v对应state.value于我们之前的示例,为我们for-of执行所有it.next()调用和done检查。

请把 } 和 while 放在同一行上-对我来说似乎更清楚-无法编辑它-因为更改 2 个字符不足以进行编辑...
2021-03-20 20:45:56
@AndyS:纯风格的编辑在任何情况下都不合适。
2021-03-24 20:45:56

node.js 终于从 2016.05.17版本 6.2.0 开始支持 TCO

它需要使用--use-strict --harmony-tailcalls标志来执行,TCO 才能工作。

另请注意,它背后原因是 V8 团队不认为它稳定,更不用说完成了。他们仍然(从 Node v6.2.2 中的 V8 开始)认为它正在进行中
2021-03-13 20:45:56
链接页面的任何地方都没有“tail”或“TCO”,您能链接到宣布支持tail call的内容吗?(支持在那里,我已经检查过。)另外请注意,--use-strict启用它不是必需的,只需--harmony-tailcalls.
2021-03-25 20:45:56
@TJCrowder:这是第一个拥有此标志的版本。它的变更日志项是V8的升级
2021-03-30 20:45:56
@TJCrowder:虽然不被认为是稳定的,但到目前为止它对我来说很好用。
2021-04-06 20:45:56

6.2.0 - 使用“严格使用”和“--harmony_tailcalls”

仅适用于 10000 的小尾优化递归(如问题中所示),但函数调用自身 99999999999999 次失败。

7.2.0 带有“严格使用”和“--和谐”

即使使用 99999999999999 呼叫,flag 也能无缝快速地工作。

99999999999999?这是很多电话......它是否以某种方式优化了计算?
2021-03-13 20:45:56

更简洁的答案......正如所提到的,截至实施日期......

TCO 有效。它不是防弹的,但它非常体面。这是因子(7000000,1)。

>node --harmony-tailcalls -e "'use strict';function f(n,t){return n===1?t:f(n-1,n*t);}; console.log(f(7000000,1))"
Infinity

它没有 TCO。

>node -e "'use strict';function f(n,t){return n===1?t:f(n-1,n*t);}; console.log(f(15669,1))"
[eval]:1
function f(n,t){return n===1?t:f(n-1,n*t);}; console.log(f(15669,1))
      ^

RangeError: Maximum call stack size exceeded
at f ([eval]:1:11)
at f ([eval]:1:32)
at f ([eval]:1:32)
at ...

尽管如此,它确实一直到 15668。

至于产量,请参阅其他答案。应该是一个单独的问题。

是的。为了让 CPU 燃烧,将它增加了几个数量级。
2021-03-27 20:45:56