Could current JavaScript engines optimize recursive "tail" calls?

Navigation
19

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 how to use 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, throwing an error or crashing the program. This is because the call stack size (which stores the execution context of each invocation of the function - which includes local variables and the reference to the "parent" scope of the function, the basis of the closures ) has a fixed size. And this limit exists to ensure that the call stack does not consume excess memory.

There is, however, a technique to avoid this limitation, depending on how the function code is structured. If the recursive call is in

asked by anonymous 27.01.2014 / 17:29

2 answers

7

First of all, I want to point out 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 caller is used, creating an additional zero memory. Notice that this is an optimization, that is, it is optional and one should not assume that it will happen. It changes the behavior of the program making it consume less memory and potentially creating infinite loops.
  • "Proper Tail Call": A language feature that ensures that "optimization" will happen. In this case an implementation that consumes memory linearly or causes a RangeError is invalid. This requires specification by the language 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 Rhino , as the utluiz mentioned). There is nothing in the language that prohibits this optimization. <function>.caller can be passed as an argument to each call and <function>.arguments can be part of the stack. I am very impressed by the fact that nobody supports this optimization, but there are no arguments against it. Maybe it's just the engineering effort involved that is not worth the small amount of uses. Or the collection of the stack frame in case an exception occurs.

The "Proper Tail Call" is in the plans for ECMAScript 6 , and if not is removed until the release (which is expected later this year), should be supported by all major browsers and engines by mid-2015.

The Continuum , an ES6 implementation written in ES3, already #: 

<html>
  <script src="https://rawgithub.com/Benvie/continuum/gh-pages/continuum.js"></script><script>varrealm=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>
    
27.01.2014 / 21:12
4

Well, I do not really understand compilers or interpreters, so I'll stick to the facts I found in documentation and references.

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

Regarding the ECMAScript standard, by reading a few details here and here , what I could understand was that proper tail calls , as they call tail call optimization, is not just a simple optimization, but an important semantic aspect of language. So a pattern that imposes certain constraints is necessary, because if each language implementation applied its own rules, codes using that feature would not be portable.

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

Finally, there is a very interesting discussion ( here ), based on article " (ES6) Has Tail Call Optimization

a> ", where the author states that the reason for not yet having this feature in the language is the same as several others: a matter of priorities.

    
27.01.2014 / 18:18
What is the "Principle of Dependency Inversion" (DIP)? Galton Board - Central boundary theorem