Node.js tail-call optimization: possible or not?

Question

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?

Answer 1

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.

Answer 2

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

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

Answer 3

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

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

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

flag works seamlessly and rapidly even with 99999999999999 calls.

Answer 4

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

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

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

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