Node.Js Tail-Call Optimization: Possible or Not

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

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: Are there optimizations for tail calls in async functions?

async function processBatch(nthBatch) {
    // do a bunch of async work and build up variables
    await processBatch(nthBatch + 1);
}

This snippet results in a memory leak because the variables declared at the comment cannot be garbage collected, because the interpreter doesn't know that they won't be needed again. e.g. the interpreter doesn't know at that point that there isn't a line after the await that might need all those declared variables.

async function processBatch(nthBatch) {
    // do a bunch of async work and build up variables
    return processBatch(nthBatch + 1);
}

In this example, the function is returned, so the garbage collector can safely clean up the variables declared in the method. Note that the stack sticks around, and if this recursive function has too many iterations there will be a Maximum call stack size exceeded error thrown, but the variables declared live in the heap and so can be garbage collected while keeping the stack information intact.

Tail recursion in NodeJS

First off, if your actual case you're concerned about is when a function calls itself from an async callback, then you likely don't have any stack buildup there anyway.

That's because the original function has already returned and the whole stack unwound before the async callback gets called, so though it visually looks like recursion, there is no stack build up.

Here's a simple code example of making multiple sequenced network requests where a function calls itself from an async callback and there is no stack buildup.

function getPages(baseURL, startParam, endParam, progressCallback) {

    function run(param) {
         request(baseURL + param, function(err, response, body) {
             if (err) return progressCallback(err);
             ++param;
             if (param < endParam) {
                 progressCallback(null, body);
                 // run another iteration
                 // there is no stack buildup with this call
                 run(param);
             } else {
                 // indicate completion of all calls
                 progressCallback(null, null);
             }
         });
    }
    run(startParam);
}

The prior invocation of run() has already returned and the stack has completely unwound before the async callback is called so while this visually looks like recursion, there is no stack buildup.

In the specific code you show, you can avoid the recursion entirely by rewriting using a while loop which would work efficiently in any version of Javascript:

function fac(n){    var total = 1;    while (n > 1) {        total *= n--;    }    return total;}
// run demo in snippetfor (var i = 1; i <= 10; i++) {    console.log(i, fac(i))}

Are any JavaScript engines tail call (TCO) optimized?

The ECMAScript 4 specification was originally going to add support for TCO, but it was dropped:

No more tail calls in JavaScript?

As far as I know, no widely-available implementations of JavaScript currently do automatic TCO. This may be of use to you, though:

Tail Call Optimization

Essentially, using the accumulator pattern accomplish the same effect.

Tail Call Optimization implementation in Javascript Engines

TCO, or rather, Tail Call Elimination in JavaScript -- also often referred to as Proper Tail Calls (PTC) in discussions -- is a long and sad story.

Around 2011, TC39 (the JavaScript standards committee) decided to adopt mandatory TCE for the forthcoming ES6 standard, with consensus from all major browser vendors.

In 2015, the new standard was officially adopted, under the name EcmaScript 2015. At this point, no browser had actually implemented TCE, mostly because there were too many new features in ES2015 that were deemed more important to get out. (Today's process for JS feature proposals and their adoption, which includes the requirement of two implementations in production engines, did not yet exist for ES6.)

In early 2016, both Safari and Chrome implemented TCE. Safari announced shipping it, while Chrome kept it behind an Experimental Feature flag. Other browsers (Firefox and Internet Explorer / Edge) started looking into it as well and had second thoughts. Discussion evolved whether this is a viable feature after all. Edge had problems implementing it efficiently for the Windows ABI, Firefox was concerned about the developer experience of calls "missing" from stack traces (an issue that was already discussed at length in 2011).

In an attempt to address some of these concerns while rescuing the tail call feature, several members, including the Chrome and Edge teams, proposed to make tail calls explicit, i.e., require return statements to be annotated with an additional keyword to opt into tail call semantics. These so-called "syntactic tail calls" (STC) were implemented in Chrome as a proof of concept.

At the May 2016 TC39 meeting the issue of tail calls was discussed extensively for almost an entire day with no resolution. Firefox and Edge made clear that they would not implement TCE as specified in the standard. Firefox members proposed to take it out. Safari and Chrome did not agree with that, and the Safari team made clear that they have no intention of unshipping TCE. The proposal for syntactic tail calls was rejected as well, especially by Safari. The committee was in an impasse. You can read the meeting notes of this discussion.

Technically, this impasse still exists today, as far as I am aware. Practically speaking, though, tail calls for JavaScript are pretty much dead, and it's unclear whether they will ever come back. At least that was the conclusion of the Chrome team after the disastrous meeting, which led to the decision to remove the implementation of tail calls from Chrome, in order to simplify the engine and prevent bit rot. They are still available in Safari.

Disclosure: I was a member of TC39 and of the Chrome/V8 team until 2017, so my views may be biased.

Simple tail-call optimization for recursive, while-loop style functions

You got it right, the while-loop in procedural programming can be replaced by recursion in functional programming paradigm. Hence, a technique called "tail-call optimization" is invented in some functional programming languages (Haskell for example) to deal with long call stacks in these scenarios.

The maximum call stack in javascript also depends on the runtime environment: for example, it's 30000 in my browser but could this could vary. So your code works fine in my browser and not throw an error. But the idea is that there is an upper limit and tail-call optimization could eliminate that.

However, tail-call optimization is a feature supported on language engine level and works in the background rather than a feature that we can use. And unfortunately, javascript is not truly an FP language so it does not support this feature yet. Hopefully, when ES6 is finalized we can have this cool feature and use functional programming to its full extent.

Edit: You can check whether your runtime environment support TCO here (look like Safari already supported it)

https://kangax.github.io/compat-table/es6/

ES6 Tail Recursion Optimisation Stack Overflow

V8, the JavaScript engine in Chrome, had TCO support for a while, but as of this updated answer (November 2017) it no longer does and as of this writing, there is no active development on TCO in V8, and none is planned. You can read the details in the V8 tracking bug for it.

TCO support seems to have reached a decent level in V8 at one point, but remained behind a flag for several reasons (debugging issues, bugs). But then several things happened, not least that the V8 team raised significant issues with TCO and strongly supported a spec change called syntactic tail calls (STCs) that would require that tail calls be flagged in source code intentionally (e.g., return continue doThat();). That proposal became inactive in July 2017, though. Also in July, with no TCO work being done, the V8 team removed the code for supporting TCO from the source for TurboFan* as it would otherwise be subject to bitrot. (E.g., become a maintenance pain and source of bugs.)

So at present (Nov 2017) it's not clear that "invisible" TCO will ever be in V8, whether some kind of STCs will come in, or what. The Chrome Platform Status page for this indicates "mixed" public signals from Mozilla (Firefox/SpiderMonkey) and Microsoft (Edge/Chakra) on supporting TCO, that Safari is shipping with TCO, and that web developers are "positive" about the feature. We'll see where we go from here. If anywhere.

* (TurboFan = the current cutting-edge JIT compiler in V8, now they've switched from Full-Codegen [JIT] + Crankshaft [aggressive optimizing JIT] to Ignition [interpreter+] and TurboFan [aggressive optimizing JIT])

Can't enable tail call optimization in node v6.4.0

Using node v6.5.0, the following works :

function countTo(n, acc) {
  'use strict';
  if(n === 0) {
    return acc;
  }
  return countTo(n - 1, acc + n);
}
console.log(countTo(100000 , 0));

Running with --harmony-tailcalls flag :

node --harmony-tailcalls tco.js

Node.Js Tail-Call Optimization: Possible or Not