javascript Node.js 尾调用优化：可能与否？

Question

提问by Koz Ross

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:

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

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

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

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

Essentially, I'd like to know the following:

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

Does or doesn't Node.js do TCO?
How does this magical yieldthing work in Node.js?

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

Answer 1

回答by T.J. Crowder

There are two fairly-distinct questions here:

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

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

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

Does or doesn't Node.js do TCO?

Node.js 是否有 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 answerfor more on that.

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

Details:

细节：

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.

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

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 answerfor more on that.

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

Node 7.10 down to 6.5.0 at least (my notes say 6.2, but node.greendisagrees) supported TCO behind a flag (--harmonyin 6.6.0 and up, --harmony_tailcallsearlier) in strict mode only.

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

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

如果你想检查你的安装，这里是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());

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

How does this magical yieldthing work in Node.js?

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

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.

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

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.

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

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

That has this output:

有这个输出：

Here's how that works:

这是它的工作原理：

When we call counter(let it = counter(0, 5);), the initial internal state of the call to counteris initialized and we immediately get back an iterator; none of the actual code in counterruns (yet).
Calling it.next()runs the code in counterup through the first yieldstatement. At that point, counterpauses and stores its internal state. it.next()returns a state object with a doneflag and a value. If the doneflag is false, the valueis the value yielded by the yieldstatement.
Each call to it.next()advances the state inside counterto the next yield.
When a call to it.next()makes counterfinish and return, the state object we get back has doneset to trueand valueset to the return value of counter.

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

Having variables for the iterator and the state object and making calls to it.next()and accessing the doneand valueproperties is all boilerplate that (usually) gets in the way of what we're trying to do, so ES2015 provides the new for-ofstatement that tucks it all away for us and just gives us each value. Here's that same code above written with for-of:

拥有迭代器和状态对象的变量以及调用it.next()和访问done和value属性都是样板文件，（通常）会妨碍我们尝试做的事情，因此 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);
}

vcorresponds to state.valuein our previous example, with for-ofdoing all the it.next()calls and donechecks for us.

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

Answer 2

回答by yairchu

node.js finally supports TCO since 2016.05.17, version 6.2.0.

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

It needs to be executed with the --use-strict --harmony-tailcallsflags for TCO to work.

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

Answer 3

回答by Mihey Mik

6.2.0 - with 'use strict' and '--harmony_tailcalls'

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

works only with small tail-optimized recursions of 10000 (like in the question), but fails the function calls itself 99999999999999 times.

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

7.2.0 with 'use strict' and '--harmony'

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

flag works seamlessly and rapidly even with 99999999999999 calls.

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

Answer 4

回答by TylerY86

More concise answer... as of it's date of implementation, as mentioned...

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

TCO works. It's not bulletproof, but it is very decent. Here's Factorial(7000000,1).

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

And here it is without TCO.

它没有 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 ...

It does make it all the way to 15668 though.

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

As for yield, see other answers. Should probably be a separated question.

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

javascript Node.js 尾调用优化：可能与否？

提问by Koz Ross

回答by T.J. Crowder

回答by yairchu

回答by Mihey Mik

回答by TylerY86

相关推荐

最近更新

标签

javascript Node.js 尾调用优化：可能与否？

提问by Koz Ross

回答by T.J. Crowder

回答by yairchu

回答by Mihey Mik

回答by TylerY86

相关推荐

javascript 检查对象是否在 localStorage 中的 AngularJS 数组中

javascript window.close() 在 android webview 中不起作用？

javascript 通过javascript将查询字符串从一个页面传递到另一个页面

javascript Kendo UI - 网格中的工具提示

相关推荐

最近更新

标签