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:
yield
thing work in Node.js?There are two fairly-distinct questions here:
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:
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).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.it.next()
advances the state inside counter
to the next yield
.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.