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

问题描述

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

function foo(x) {如果 (x == 1) {返回 1；}别的 {返回 foo(x-1);}}富(100000)；

现在，我做了一些挖掘，我发现了这个.这里，好像说应该这样写:

function* foo(x) {如果 (x == 1) {返回 1；}别的 {产量 foo(x-1);}}富(100000)；

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

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

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

解决方案

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

• 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() {严格使用"；返回(函数 f(n){如果(n <= 0){返回富"；}返回 f(n - 1);}(1e6)) === "foo";}函数相互(){严格使用"；函数 f(n){如果(n <= 0){返回富"；}返回 g(n - 1);}函数 g(n){如果(n <= 0){返回酒吧"；}返回 f(n - 1);}返回 f(1e6) === "foo" &&f(1e6+1) === "bar";}控制台日志(直接())；控制台日志(相互())；

<前>$ # 只​​有某些版本的 Node，特别是 8.x 或(目前)9.x 不是；看上面$ node --harmony tco.js真的真的

<块引用>

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

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

生成器函数(使用 function* 编写并使用 yield 的函数)通过​​能够停止并返回一个迭代器来工作，该迭代器捕获它们的状态并可用于继续它们的在随后的场合陈述.Alex Rauschmeyer 有一篇关于它们的深入文章这里.

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

"使用严格";函数*计数器(从，到){让 n = 从；做 {产量 n;}while (++n 

有这个输出:

<前>01234

这是它的工作原理:

• 当我们调用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 设置为 true 和 value 设置为 counter 的返回值.

具有迭代器和状态对象的变量并调用 it.next() 并访问 done 和 value 属性是所有(通常)阻碍我们尝试做的事情的样板，所以 ES2015 提供了新的 for-of 语句，它为我们隐藏了一切，只为我们提供了每个值.这是上面用 for-of 编写的相同代码:

"使用严格";函数*计数器(从，到){让 n = 从；做 {产量 n;}while (++n 

v 对应于前面例子中的 state.value，for-of 做了所有的 it.next() 调用和 done 为我们检查.

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

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. 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:

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

Does or doesn't Node.js do 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.

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.

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.

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.

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

How does this magical yield thing work in 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.

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

That has this output:

0
1
2
3
4

Here's how that works:

• 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.

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 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屋！