Could current Javascript engines optimize "tail" recursive calls?

Question

In functional programming, it is very common to use functions recursive. Certain languages, such as Scheme, do not even have control structures for loops, depending on recursion to iterate over lists.

Javascript has functional features, such as first-class functions, but has restrictions on the use of recursion. For example:

function fatorial(num) {
    if (num === 0) { 
        return 1; 
    }
    return num * fatorial(num - 1);
}
fatorial(5);      // 120
fatorial(100000); // RangeError: Maximum call stack size exceeded

^{Please ignore the fact that fatorial(100000) is a number that Javascript is not even able to represent.}

If the number of recursions exceeds a certain limit, the engine is not able to process the result by launching an error or locking the program. This is because the size of the call stack (which stores the execution context of each function invocation - which includes local variables and the reference to the "parent" scope of the function, basis of the mechanism of the closures) has a fixed size. And this limit exists to ensure that the call stack does not consume excess memory.

However, there is a technique to avoid this limitation, depending on how the function code is structured. If the recursive call is in position "tail", that is, it is the last instruction of the function, its execution context is dispensable, as it is guaranteed that the function will not need it anymore when recursive calls are popped. Thus, it is possible to clean or "recycle" the frame (frame) of the stack used by the execution context of the running function, and use it for the recursive call, so that a tail recursive function ends up using a single stack frame for the entire operation. This technique is known as tail call optimization (Tail call Optimization).

Question

Although this technique is widely known, no Javascript engine seems to use it, either in the interpreter itself or as part of the operations performed by the JIT compilers that all modern Engines use. The question is, why? Is there any restriction in language that makes this optimization impossible? Or maybe it’s possible, but too costly?

The grammar of the next version of the language (Ecmascript 6, still in draft) includes checks for the tail position, predicting this type of optimization. However, I do not think that the lack of this in the current version would prevent the technique from being used today.

Answer 1

Firstly, I would like to highlight an important difference in terms:

• Tail Call Optimization: When an implementation optimizes a tail call so that a new stack frame is not allocated and the Caller be used, creating a zero memory accrescimo. Note that this is an optimization, ie it is optional and should not be assumed to happen. It alters the behavior of the program by making it consume less memory and potentially creating endless loops.
• "Proper Tail Call": A feature of language that guarantor that "optimization" will happen. In this case an implementation that consumes memory linearly or causes a RangeError is invalid. This requires language specification to define the exact format the function should be written to.

Recursive call optimization has always been possible, but has never been properly implemented by any known engine (except the Rhino, as utluiz mentioned). There is nothing in the language that prohibits this optimization. <function>.caller can be passed as if it were an argument to every call and <function>.arguments may be part of the stack. I am very impressed that no one supports this optimization, but there are no arguments against it. Maybe just the engineering effort involved that isn’t worth the small amount of uses. Or collecting the stack frame in case an Exception occurs.

"Proper Tail Call" is in plans for Ecmascript 6 and, if not removed by release (which is expected to occur later this year), should be supported by all major browsers and Engines by mid-2015.

The Continuum, an ES6 implementation written in ES3, already has support for this:

<html>
  <script src="https://rawgithub.com/Benvie/continuum/gh-pages/continuum.js"></script>
  <script>
    var realm = continuum.createRealm();
    realm.evaluate("function fac(n, accum){return n > 0 ? fac(n - 1, n * accum) : accum;}");
    // pode demorar um pouco
    console.log("fac(100000) = " + realm.evaluate("fac(100000, 1)"));
    // mas eventualmente chegará na resposta: Infinity :)
  </script>
</html>

Answer 2

Well, I don’t really understand compilers or interpreters, so I’ll stick to the facts I found in the documentation and references.

In thesis, Javascript could have "tail" call optimization. In fact, there is a special implementation that already has this feature: Rhynowithcontinuations. This is a version of Rhyno, a Javascript implementation made 100% in Java.

Regarding the Ecmascript pattern, reading some details here and here, what I could understand was that Proper Tail calls, as they call Tail call Optimization, not just a mere optimization, but an important semantic aspect of language. So a pattern that imposes certain restrictions is necessary, because if each language implementation applied its own rules, codes that used this resource would not be portable.

In addition, as quoted in the penultimate link, there seems to be a difficulty with some language features, such as the ability to access the arguments (<function>.arguments), who called the function (<function>.caller) and others. In short, implementing optimization and tail recursion would affect the function call stack. This is one of the reasons for the most current documentation state that optimization will be applied only in Strict mode, because this way prohibits the use of these resources.

Finally, there is a very interesting discussion (here), article-based "Javascript (ES6) Has Tail Call Optimization", where the author states that the reason for not yet having this feature in the language is the same of several others: a matter of priorities.