Are Functions in JavaScript Tail-Call Optimized

Are functions in JavaScript tail-call optimized?

Update: As of January 1, 2020 Safari is the only browser that supports tail call optimization.

The chromium team explicitly states that Tail Call Optimization is not under active development and can be tracked here.

The implementation for Firefox can be tracked here

Original Post

Yes, ES2015 offers tail call optimization in strict mode. Dr. Axel Rauschmayer lays it out beautifully at the link below so I shall not repeat his words here.

Note: ES 5 does not optimize tail calls.

http://www.2ality.com/2015/06/tail-call-optimization.html

What is tail call optimization?

Tail-call optimization is where you are able to avoid allocating a new stack frame for a function because the calling function will simply return the value that it gets from the called function. The most common use is tail-recursion, where a recursive function written to take advantage of tail-call optimization can use constant stack space.

Scheme is one of the few programming languages that guarantee in the spec that any implementation must provide this optimization, so here are two examples of the factorial function in Scheme:

(define (fact x)
  (if (= x 0) 1
      (* x (fact (- x 1)))))

(define (fact x)
  (define (fact-tail x accum)
    (if (= x 0) accum
        (fact-tail (- x 1) (* x accum))))
  (fact-tail x 1))

The first function is not tail recursive because when the recursive call is made, the function needs to keep track of the multiplication it needs to do with the result after the call returns. As such, the stack looks as follows:

(fact 3)
(* 3 (fact 2))
(* 3 (* 2 (fact 1)))
(* 3 (* 2 (* 1 (fact 0))))
(* 3 (* 2 (* 1 1)))
(* 3 (* 2 1))
(* 3 2)
6

In contrast, the stack trace for the tail recursive factorial looks as follows:

(fact 3)
(fact-tail 3 1)
(fact-tail 2 3)
(fact-tail 1 6)
(fact-tail 0 6)
6

As you can see, we only need to keep track of the same amount of data for every call to fact-tail because we are simply returning the value we get right through to the top. This means that even if I were to call (fact 1000000), I need only the same amount of space as (fact 3). This is not the case with the non-tail-recursive fact, and as such large values may cause a stack overflow.

Tail Call Optimizing recursive function

You can't optimize it when your recursive call is inside forEach, because in order to apply TCO, the compiler need to check that you not saving a "state" of the previous call. In case of forEach you do save a "state" of the current position.

In order to implement it with TCO you can rewrite that foreach to be implemented with the recursive call, it would look something like that:

function deepFlattenTCO(input) {  const helper = (first, rest, result) => {    if (!Array.isArray(first)) {      result.push(first);      if (rest.length > 0) {        return helper(rest, [], result);      } else {        return result;      }    } else {      const [newFirst, ...newRest] = first.concat(rest);
      return helper(newFirst, newRest, result);    }  };
  return helper(input, [], []);}
console.log(deepFlattenTCO([  [1], 2, [3], 4, [5, 6, [7]]]));

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.

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.

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

How can I get TypeScript to perform Tail Recursion Optimization?

TypeScript does not optimize tail-called recursive functions. See microsoft/TypeScript#32743 for an authoritative answer.

Usually the term "tail call optimization" in JavaScript denotes rewriting a tail-recursive function to an iterative version. This differs somewhat from "tail call elimination" which usually means keeping the recursion but rewriting the current stack frame instead of pushing a new one onto the stack. Both behave similarly from the outside if all you care about is stack growth, but tail call optimization generally happens at a level of abstraction higher than tail call elimination.

---

If you are suggesting that TypeScript implement tail call optimization as a performance improvement, that's not something that fits with TypeScript's design goals. Generally speaking if you write some code which is syntactically correct JavaScript for your target runtime environment, the compiler will emit that code as-is. TypeScript isn't supposed to optimize your JavaScript, just emit it. So there's no chance it would do this by itself.

---

On the other hand, you might be talking about proper tail call elimination, as introduced in the ECMAScript 2015 (ES2015/ES6) specification. This feature was intended so that JavaScript runtime engines would detect tail calls and not add to the call stack in such cases.

This feature was never widely adopted; currently only Safari-based browsers seem to consistently do this.

When runtime engine designers looked into implementing this, they ran into issues with possible performance degradation, developer confusion, etc. See this V8 blog post for example. Most runtime engines seem to have opted for a "wait-and-see" approach for some more desirable version of this, such as a syntax to explicitly opt in to such elimination. And the only notable proposal for such syntax has been "inactive" for years. So it looks like the "wait" part of "wait-and-see" might last forever.

While it would be possible for TypeScript to downlevel proper tail call elimination into something like tail call optimization, it would likely run into the same issues, and they have declined to do it.

---

For better or worse, it looks like automatic tail call elimination is a de-facto dead feature, and TypeScript is not going to revive it for us.

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:

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.

Implement javascript function using tail recursion

The basics of a tail recursion is to return the same function with changed parameters. This allows to replace the last stack entry with the new call of the function without increasing the stack size.

The following approach uses a TCO and returns the function call and uses a standard exit condition to return from a recursive function at the top of the function.

The algorithm visits each item only ones and builds a tree which has multiple roots. At the end only the wanted root is returned. This approach works for unsorted data, because for every node, both information of id and parent are used and their relation is preserved.

function getTree(data, root, index = 0, tree = {}) {    var o = data[index];    if (!o) return tree[root];    Object.assign(tree[o.id] = tree[o.id] || {}, o);    tree[o.parent] = tree[o.parent] || {};    tree[o.parent].children = tree[o.parent].children || [];    tree[o.parent].children.push(tree[o.id]);    return getTree(data, root, index + 1, tree);}
const    data = [{ id: 'root' }, { id: 0, parent: 'root' }, { id: 1, parent: 'root' }, { id: 2, parent: 0 }, { id: 3, parent: 1 }, { id: 4, parent: 2 }, { id: 5, parent: 1 }, { id: 6, parent: 4 }, { id: 7, parent: 0 }, { id: 8, parent: 0 }],    tree = getTree(data, 'root');
console.log(tree);

.as-console-wrapper { max-height: 100% !important; top: 0; }

Does Google Apps Script (GAS) support proper tail calls or tail call optimization?

(V8 developer here.)

Does Google Apps Script (GAS) support proper tail calls?

No. V8 does not support PTCs (nor STCs); you've already linked to the background story yourself. Since GAS is built on V8 for JS execution, it can't support them either.

wondering whether investing time into doing tail call optimization for a script is worth it. / Does GAS support tail call optimization to the point where it is worth doing it, for performance, in any way?

I'm not sure what you mean: TCO is something that a compiler potentially does, not something you do.

If you mean "moving calls into tail positions, so the compiler can turn them into iterations": No, V8 doesn't do that, so that's not worth your time. Whether a call occurs in a tail position or not makes no difference for performance. (And I wouldn't bet on that changing any time soon.)

If you mean "manually converting recursion into iteration": that may be worth doing for performance-critical code; whether it's worth doing in your particular case can only be answered by trying it and measuring the effect. (As always, a small artificial test a.k.a. "microbenchmark" is very likely to produce misleading results that don't apply to other situations.)

This doesn't need any "support" from GAS or V8.

---

Related Topics