Koz Ross Koz Ross - 2 months ago 21
Javascript Question

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

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

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 (as of 26/09/2016) If you're using Node v6.6.0, you have TCO (both direct and mutual) if you use strict mode and you use the --harmony flag.

Details:

There's good info about Node's ES2015 support on their ECMAScript 2015 (ES6) and beyond page.

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 v6.6.0, Node enables V8's TCO support but it's behind the --harmony flag and you must be using strict mode. The flag is because for the version of V8 in Node v6.6.0, the V8 team consider TCO "stable" but not yet "shipping," and Node only enables "shipping" (e.g., completed) features without a flag. (See details on the NodeJS ES2015 support page I mentioned earlier.)

The node.green site shows "Yes ⚐" for TCO for v6.6.0. Their tests do work in v6.6.0 if you use --harmony (and in v6.2.0 and up if you use --harmony_tailcalls) to enable it:

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());
$ node --harmony tailcalls.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 v6.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.

Comments