Node.js尾调用优化:可行吗?

37

目前我很喜欢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 中是如何工作的?

2
运行带有“--harmony”标志的节点,以查看您的第二个版本如何工作。例如:node --harmony mytest.js。但首先重新查看您引用的示例,您只适应了其中的一部分到您的情况。关于TCO,真正的问题是V8是否已经实现了它 - 我在v8 changelog中没有看到任何提及。 - barry-johnson
@barry-johnson:我尝试着复制第二个链接中使用“yield”的示例函数,但是Node.js对于“function*”会出现异常。这就是我困惑的原因之一。 - Koz Ross
这就是为什么我说你需要使用--harmony选项运行节点。生成器是ES6/Harmony的一部分,而这不是节点的默认设置。 - barry-johnson
4个回答

54

这里有两个比较明显的问题:

  • Node.js是否支持TCO?
  • 在Node.js中,这个神奇的yield是如何工作的?

Node.js是否支持TCO?

TL;DR: 自 Node 8.x 起不再支持。在某些标志位后面,Node.js 曾经支持 TC0。但截至本文(2017年11月),因为底层的 V8 JavaScript 引擎不再支持 TCO,Node.js 不再支持它。请参见此答案了解更多信息。

详情:

尾调用优化(TCO)是 ES2015(“ES6”)规范的必要部分。因此,支持它并不是一个 Node.js 的特性,而是需要 Node.js 使用的 V8 JavaScript 引擎支持它。

从 Node 8.x 开始,V8 不再支持 TCO,即使是在标志位后面也不行。以后可能会再次支持它;请参见此答案了解更多信息。

Node 7.10 到至少 6.5.0(我的笔记说是 6.2,但node.green的数据不同)只在严格模式下支持 TCO(在早期使用 --harmony_tailcalls,在 6.6.0 及更高版本中使用 --harmony 标志位)。

如果您想检查您的安装情况,请参见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 
true
true

Node.js中这个神奇的yield怎么起作用?

这又是一个ES2015的东西("generator functions"),所以它是V8必须实现的。在Node 6.6.0中的V8版本中完全实现了它(并已经实现了几个版本),而且没有任何标志。

生成器函数(使用function*编写并使用yield)能够通过停止和返回捕获其状态的迭代器来工作,并可用于在随后的场合继续其状态。Alex 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函数中的任何代码。
  • 调用it.next()函数会运行counter函数中的代码,直到第一个yield语句。此时,counter函数暂停并存储其内部状态。it.next()函数返回一个状态对象,其中包含一个done标志和一个value值。如果done标志为false,则value是由yield语句生成的值。
  • 每次调用it.next()函数都会将counter函数内部的状态向前推进到下一个yield语句。
  • 当调用it.next()函数使counter函数完成并返回时,我们得到的状态对象里的done属性被设置为truevalue属性被设置为counter函数的返回值。

由于在使用迭代器时需要定义变量来保存迭代器和状态对象,并且需要不断调用it.next()函数并访问其返回值中的donevalue属性,这些内容通常会干扰我们所需完成的实际操作。因此,ES2015提供了新的for-of语句,将这些内容都封装起来,只提供每个值给我们使用。下面是使用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.valuefor-of会执行所有it.next()调用和done检查。


1
请问}和while是否可以在同一行上 - 这对我来说看起来更清晰 - 我不能编辑这个 - 因为更改两个字符不足以进行编辑... - AndyS
4
@AndyS:在任何情况下,纯样式编辑都不合适。 - T.J. Crowder

4
自2016年5月17日起,6.2.0版本的node.js终于支持TCO了。要使TCO生效,需要使用--use-strict --harmony-tailcalls这两个标志来执行代码。

1
链接页面上没有任何关于“tail”或“TCO”的内容,你能否提供一个宣布尾调用支持的链接?(支持确实存在,我已经检查过了。)另外请注意,启用尾调用不需要--use-strict,只需要--harmony-tailcalls即可。 - T.J. Crowder
1
还要注意的是,它被放在自己的标志后面的原因是V8团队认为它不稳定,更不用说完成了。他们仍然(截至Node v6.2.2中的V8)认为它是正在进行中的。 - T.J. Crowder
@T.J.Crowder:尽管它还不被认为是稳定的,但迄今为止它对我来说运行得非常好。 - yairchu
@T.J.Crowder:这是第一个拥有此标志的版本。它的变更日志项是V8的升级。 - yairchu

2

6.2.0 -使用'use strict'和'--harmony_tailcalls'

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

7.2.0与'use strict'和'--harmony'

标志无缝快速地处理99999999999999次调用。


1
99999999999999?这么多调用...它是否会优化计算? - yairchu

-1

更简洁的答案...截至实施日期,如上所述...

TCO有效。它不是万无一失的,但非常不错。这里是Factorial(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

这是没有尾递归优化的代码。

>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。

至于yield,请参见其他答案。应该单独提出一个问题。


没错。我额外增加了几个数量级,只是为了让CPU运行更多时间。 - TylerY86

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接