Node.js尾调用优化：可能与否？ [英] Node.js tail-call optimization: possible or not?

问题描述

到目前为止我喜欢JavaScript，并决定使用Node.js作为我的引擎，部分原因是 this ，声称Node.js提供TCO。但是，当我尝试使用Node.js运行此代码（显然是尾调用）时，会导致堆栈溢出：

I like JavaScript so far, and decided to use Node.js as my engine partly because of this, which claims that Node.js offers TCO. However, when I try to run this (obviously tail-calling) code with Node.js, it causes a stack overflow:

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

foo(100000);

现在，我做了一些挖掘工作，我找到了这个。在这里，似乎我应该这样写：

Now, I did some digging, and I found this. Here, it seems to say I should write it like this:

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

foo(100000);

然而，这给了我语法错误。我尝试了各种各样的排列，但在所有情况下，Node.js似乎对某事不满意。

However, this gives me syntax errors. I've tried various permutations of it, but in all cases, Node.js seems unhappy with something.

基本上，我想知道以下内容：

Essentially, I'd like to know the following:

1. 是或Node.js不执行TCO吗？


2. 这个神奇的收益如何在Node.js中运行？

1. Does or doesn't Node.js do TCO?
2. How does this magical yield thing work in Node.js?

推荐答案

这里有两个截然不同的问题：

There are two fairly-distinct questions here:

• Node.js是否执行TCO？


• 这个神奇的产量在Node.js中是如何工作的？

Node.js是否执行TCO？

TL; DR ：不再是，从Node 8.x 开始。它有一段时间，在一面或另一面旗帜后面，但截至本文（2017年11月），它已不复存在，因为它使用的基础V8 JavaScript引擎不再支持TCO。有关详细信息，请参阅此答案。

TL;DR: Not anymore, as of Node 8.x. It did for a while, behind one flag or another, but as of this writing (November 2017) it doesn't anymore because the underlying V8 JavaScript engine it uses doesn't support TCO anymore. See this answer for more on that.

详细信息：

尾部呼叫优化（TCO）是必需的 ES2015（ES6）规范的一部分。所以支持它不是直接的NodeJS，它是NodeJS使用的V8 JavaScript引擎需要支持的东西。

Tail-call optimization (TCO) is a required part of the ES2015 ("ES6") specification. So supporting it isn't, directly, a NodeJS thing, it's something the V8 JavaScript engine that NodeJS uses needs to support.

从Node 8.x开始，V8没有不支持TCO，甚至不支持旗帜。它可能（再次）在未来的某个时刻;有关详细信息，请参阅此答案。

As of Node 8.x, V8 doesn't support TCO, not even behind a flag. It may do (again) at some point in the future; see this answer for more on that.

节点7.10向下至少6.5.0（我的笔记说6.2，但 node.green 不同意）支持标志背后的TCO（ - 和谐在6.6.0及以上， - harmony_tailcalls 之前）仅在严格模式下。

Node 7.10 down to 6.5.0 at least (my notes say 6.2, but node.green disagrees) supported TCO behind a flag (--harmony in 6.6.0 and up, --harmony_tailcalls earlier) in strict mode only.

如果您想检查安装，请参阅 node.green 使用的测试（确保如果您使用相关版本，请使用该标志）：

If you want to check your installation, here are the tests node.green uses (be sure to use the flag if you're using a relevant version):

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());

$ # Only certain versions of Node, notably not 8.x or (currently) 9.x; see above
$ node --harmony tco.js
true
true

这个神奇的收益如何在Node.js中运作？

How does this magical yield thing work in Node.js?

这是ES2015的另一个东西（生成器功能），所以V8必须实现这一点。它完全在节点6.6.0中的V8版本中实现（并且已经有多个版本）并且不在任何标志之后。

This is another ES2015 thing ("generator functions"), so again it's something that V8 has to implement. It's completely implemented in the version of V8 in Node 6.6.0 (and has been for several versions) and isn't behind any flags.

生成器函数（用 function * 并使用 yield ）通过能够停止并返回捕获其状态并可以使用的迭代器来工作在随后的场合继续他们的国家。 Alex Rauschmeyer在此处上有一篇深入的文章。

Generator functions (ones written with function* and using yield) work by being able to stop and return an iterator that captures their state and can be used to continue their state on a subsequent occasion. Alex Rauschmeyer has an in-depth article on them here.

这是一个使用生成器函数返回的迭代器的示例，但是你通常不会这样做，我们马上就会看到原因：

Here's an example of using the iterator returned by the generator function explicitly, but you usually won't do that and we'll see why in a moment:

"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

以下是它的工作原理：

• 当我们调用计数器（ let it = counter（0,5）; ），初始化对计数器的调用的初始内部状态立即回到迭代器; 计数器中没有任何实际代码运行（尚未）。


• 调用 it.next（）通过第一个 yield 语句在计数器中运行代码。此时，计数器暂停并存储其内部状态。 it.next（）返回一个状态对象，其中包含已完成标志和值。如果已完成标志为 false ，则值为 yield 语句产生的值。


• 每次调用 it.next（）将计数器内的状态提升到下一个 yield 。


• 当调用 it.next（）使计数器完成并返回，我们得到的状态对象已完成设置为 true 和值设置为<$的返回值c $ c> counter 。

• When we call counter (let it = counter(0, 5);), the initial internal state of the call to counter is initialized and we immediately get back an iterator; none of the actual code in counter runs (yet).
• Calling it.next() runs the code in counter up through the first yield statement. At that point, counter pauses and stores its internal state. it.next() returns a state object with a done flag and a value. If the done flag is false, the value is the value yielded by the yield statement.
• Each call to it.next() advances the state inside counter to the next yield.
• When a call to it.next() makes counter finish and return, the state object we get back has done set to true and value set to the return value of counter.

拥有迭代器和状态对象的变量并调用 it.next（）并访问已完成和值属性是（通常）妨碍我们尝试做的所有样板，因此ES2015提供了新的 for-of 语句，它将所有内容都包含在我们手中只给我们每个价值。这是上面用写的的相同代码：

Having variables for the iterator and the state object and making calls to it.next() and accessing the done and value properties is all boilerplate that (usually) gets in the way of what we're trying to do, so ES2015 provides the new for-of statement that tucks it all away for us and just gives us each value. Here's that same code above written with 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 （）来电和已完成检查我们。

v corresponds to state.value in our previous example, with for-of doing all the it.next() calls and done checks for us.

这篇关于Node.js尾调用优化：可能与否？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！