/bbenvie.com

JavaScript (ES6) Has Proper Tail Calls

January 6, 2013

Update: Proper Tail Calls vs. Tail Call Optimization

As Dave Herman, champion of proper tails calls for the ES6 specification, pointed out, the correct term to use for what's coming in ES6 is "proper tail calls" instead of "tail call optimization". In short, the distinction is that proper tail calls make a guarantee, where optimizations are something that can't be counted on.

What is a Tail Call and Why Should I Care About Optimizing It?

A tail call is a function call who's return value is used as the caller's return value. Example:

function factorial(remaining, accumulator){
  if (remaining === 0) {
    return accumulator;
  }
  return factorial(remaining - 1, remaining * accumulator); // <--- tail call
}

Without tail call optimization, every recursive call will add another frame to the call stack, eventually leading to memory exhaustion. JavaScript engines typically will fail at 10,000 - 30,000 levels of recursion with a RangeError.

With tail call optimization, the same frame is reused since the calling function has no need of it anymore (its only remaining task is to return the resulting value). Proper tails calls are important to functional programming since they allow iteration to be written as recursive function calls, and are generally useful for any type of extreme recursion. A recursive ForLoop:

function FOR(init, test, update, body){
  if (test(init)) {
    body(init);
    return FOR(update(init), test, update, body);
  }
}

// example using ES6 arrow functions
function map(array, callback){
  var result = [];
  FOR(0,
    i => i < array.length,
    i => ++i,
    i => result[i] = callback(array[i], i, array)
  );
  return result;
}

Without TCO it would be extremely inefficient to use this structure because every recursive call would add another frame to the call stack, and it would fail eventually if you tried to loop 20k+ times. While it's still less efficient to do this in JS versus using iteration, recursion is a more elegant way to do many tasks, such as walking through tree structures.

Introducing Proper Tail Calls to JavaScript

As part of ES6, proper tail calls are coming to JavaScript. This is a feature long desired for JavaScript, but is just now finding its way into the language. I recently implemented this feature in my ES6 virtual machine Continuum, allowing the above example to work (hint: it takes a few seconds to run, but it will complete without error):

function factorial(n, accum){
  return n > 0 ? factorial(n - 1, n * accum) : accum;
}

factorial(50000, 1);

In Firefox (using Firebug), it will cause the browser to crash. Chrome will throw "RangeError: Maximum call stack size exceeded".

Try it in Continuum.