6

I recently learned about tail call optimization in Haskell. I've learned from the following posts that this is not a feature of javascript:

Is there something inherent to javascript's design that makes tail call optimization especially difficult? Why is this a main feature of a language like haskell, but is only now being discussed as a feature of certain javascript engines?

Community
  • 1
  • 1
asloan
  • 123
  • 7
  • 2
    I think ES6 will provide it. – ErikR Jul 07 '15 at 15:44
  • Yep, I believe you're correct. I was more wondering **why** it is the case that it has only **now** been added as a feature? – asloan Jul 07 '15 at 15:45
  • 1
    See [this article](http://duartes.org/gustavo/blog/post/tail-calls-optimization-es6/) explaining the difficulties in tail-call optimization. And yes, it will be implemented for sure in ES6. – Mike Cluck Jul 07 '15 at 15:46
  • 3
    The vast difference is that TCO is *necessary* in haskell, while it is just a *feature* in other languages that adds complexity to the compiler. – Bergi Jul 07 '15 at 15:49
  • In addition, massive recursion will also encounter call stack limitation which is very small by default. I think JS (as of ES5) is not primarily aimed for recursion in the past. – TaoPR Jul 07 '15 at 15:50
  • @Bergi One might argue that because of the ackermann function's existence, all languages need tail recursion. – AJF Jul 07 '15 at 16:39
  • @AJFarmar: How would TCO help with computing the ackermann function? – Bergi Jul 07 '15 at 16:58

1 Answers1

9

Tail call optimisation is supported in JavaScript. No browsers implement it yet but it's coming as the specification (ES2015) is finalized and all environments will have to implement it. Transpilers like BabelJS that translate new JavaScript to old JavaScript already support it and you can use it today.

The translation Babel makes is pretty simple:

function tcoMe(x){
    if(x === 0) return x;
    return tcoMe(x-1)
}

Is converted to:

function tcoMe(_x) {
    var _again = true;

    _function: while (_again) {
        var x = _x;
        _again = false;

        if (x === 0) return x;
        _x = x - 1;
        _again = true;
        continue _function;
    }
}

That is - to a while loop.

As for why it's only newly supported, there wasn't a big need from the community to do so sooner since it's an imperative language with loops so for the vast majority of cases you can write this optimization yourself (unlike in MLs where this is required, as Bergi pointed out).

Benjamin Gruenbaum
  • 270,886
  • 87
  • 504
  • 504
  • You don't mean Machine Languagues, do you? – Bergi Jul 07 '15 at 17:01
  • @Bergi hehe, no, I meant [ML](https://en.wikipedia.org/wiki/ML_(programming_language)s, which is a family of languages like OCaml and F# (direct dialects) and Haskell (ML with non-strict evaluation but same idea), although the statement is equally true for other functional languages like scheme. – Benjamin Gruenbaum Jul 07 '15 at 17:03
  • Yeah that's what I suspected, but the plural confused me. I've never referred to ML as a *family* of language*s* :-) – Bergi Jul 07 '15 at 17:07
  • A Tail call can reuse the stack frame of its enclosing function (same return point). Only the internal vars including arguments have to be initialized. Does that mean, tail calls are similarly well optimizable for JS engines as imperative loops? Usually I don't care about micro optimization, but when it comes to iterations... –  Jan 17 '16 at 19:10
  • @IvenMarquardt yes, potentially tail calls are _as_ fast. – Benjamin Gruenbaum Jan 17 '16 at 19:14
  • 2019 and still practically no support implemented in web browsers - https://kangax.github.io/compat-table/es6/ – arcseldon Jan 28 '19 at 04:02
  • It was removed from the language – Benjamin Gruenbaum Jan 28 '19 at 07:17
  • In other posts some Chrome team dev explained why Chrome "unshipped" TCE/TCO and basically TCE/TCO is really dead because browser vendor disagree on the semantics that it should have etc. It will probably be removed from the standard or in the next one. – Bakuriu Jun 15 '19 at 09:46
  • See my extensive recap of the history in [this reply](https://stackoverflow.com/questions/54719548/tail-call-optimization-implementation-in-javascript-engines/54721813#54721813). – Andreas Rossberg Jun 19 '19 at 18:21