35

到目前为止,我喜欢 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 还是不做 TCO?
  2. 这个神奇yield的东西在 Node.js 中是如何工作的?
4

4 回答 4

50

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

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

Node.js 做 TCO 还是不做 TCO?

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

细节:

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

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

节点 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;往上看
$节点--harmony tco.js
真的
真的

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

这是另一个 ES2015 的东西(“生成器函数”),所以这也是 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()运行代码。此时,暂停并存储其内部状态。返回带有标志和 的状态对象。如果标志是,则是语句产生的值。counteryieldcounterit.next()donevaluedonefalsevalueyield
  • 每次调用都会将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.value于我们前面的例子,为我们for-of做所有的it.next()调用和done检查。

于 2015-05-21T09:26:44.383 回答
4

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

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

于 2016-03-01T20:34:18.317 回答
1

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

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

7.2.0 带有 'use strict' 和 '--harmony'

即使拨打 99999999999999,flag 也能无缝快速地工作。

于 2017-05-14T21:06:12.420 回答
-1

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

总拥有成本有效。它不是防弹的,但它非常体面。这是阶乘(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。

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

于 2016-09-26T10:49:49.510 回答