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:

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

Run node with the --harmony flag to see how your second version works. e.g. node --harmony mytest.js. But first re-look at the example you cite, you have only adapted part of it to your case. Regarding TCO the real question is whether V8 has implemented it - and there is no mention of that being done yet in the v8 changelog that I can see. — barry-johnson
@barry-johnson: I tried just copying the sample functions using yield in the second link, and Node.js takes exception to function*. This is one of the reasons why I'm confused. — Koz Ross
That is why I said you need to run node with the --harmony option. Generators are part of ES6/Harmony, which is not the node default. — barry-johnson

T.J. Crowder T.J. Crowder · Accepted Answer · 2015-05-21T09:26:44

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:

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 tail-call optimization: possible or not?

4 Answers