Functional JavaScript – Tail Call Optimization and Babel

Introduction

It’s been two years since I wrote the post Functional JavaScript—Tail Call Optimization and Trampolines where I describe how to implement and use a trampoline to overcome JavaScript’s lack of tail call optimization (TCO) and nothing much has changed during the intervening time. None of the modern JavaScript engines implement tail call optimization. None!

Testing for TCO

The SUCC function is the simplest function to use for testing whether a JavaScript engine implements TCO:

function SUCC(n) {

   var tco = function(n, acc) {
      if (n == 0) {
         return acc;
      } else {
         return tco(n-1, acc+1);
      }
   }

   return tco(n, 1);

Run it with a value of n=250000 and it’s a sure bet you’ll generate a stack overflow if your JavaScript engine doesn’t implement TCO. In fact kangax has setup an ECMAScript 6 compatibility table showing, amongst other things, that TCO is hardly implemented anywhere; with one notable exception.

Babel

Babel is a transpiler transforming JavaScript 6 code to JavaScript 5 code so that the new features of JavaScript 6 may be utilized in legacy environments not supporting these features.

Using Babel the above SUCC function is transformed to the following:

function SUCC(n) {

   var tco = (function (_tco) {
      function tco(_x, _x2) {
         return _tco.apply(this, arguments);
      }

      tco.toString = function () {
         return _tco.toString();
      };

      return tco;
   })(function (n, acc) {
      if (n == 0) {
         return acc;
      } else {
         return tco(n - 1, acc + 1);
      }
   });

   return tco(n, 1);

Sigh. This code is useless—it’s the same code we had before rewritten in a more confusing way. It does not implement TCO as no loop has been introduced. Without the loop we suffer the same stack overflow we experienced using the original code without TCO. I thought Babel was supposed to implement TCO?

Digging a Little Deeper

Turns out we can get Babel to generate the code we want if we tweak our code a little.

function SUCC(n, acc=1) {
    if (n == 0) {
	return acc;
    } else {
	return SUCC(n-1, acc+1);
    }
}

See the difference? I’m using another new JavaScript 6 feature, default function parameters. A call of the form SUCC(n) is equivalent to calling SUCC(n, 1). The initial caller isn’t inconvenienced with having to specify an initial accumulator value, which is a leaky abstraction. What difference does this make? Let’s take a look at what Babel does with this code:

function SUCC(_x7) {
   var _arguments = arguments;
   var _again = true;

   _function: while (_again) {
      acc = undefined;
      _again = false;
      var n = _x7;
      var acc = _arguments[1] === undefined ? 1 : _arguments[1];

      if (n == 0) {
         return acc;
      } else {
         _arguments = [_x7 = n - 1, acc + 1];
         _again = true;
         continue _function;
      }
   }
}

Notice we have our loop – a while loop:

_function: while(_again) {

The _again loop control variable is superfluous in this context, I’m supposing it’s an artifact of Babel’s code generation which may be useful in other contexts. Other than that the code is very straightforward to read. Better yet, it produces a true TCO implementation that runs much faster than using a trampoline!

Other Limitations

Babel is unable to optimize mutual recursions. This means the classic even/odd implementation won’t be optimized:

function even(n) {
   if (n == 0) {
      return true;
   } else {
      return odd(n - 1);
   }
}

function odd(n) {
   if (n == 0) {
      return false;
   } else {
      return even(n - 1);
   }
}

This code is identical before and after Babel transpilation.

Conclusion

With Babel we can get TCO for direct recursion without having to resort to the complications of using trampolines. We do have to complicate our development workflow a little bit to accommodate Babel but Babel makes that easy by integrating in with the most commonly used web development workflow tools, one of which you’re likely to be using already for your project.

Happy hacking!

More to Explore

Functional JavaScript — Memoization, Part I
Functional JavaScript — Memoization, Part II
Functional JavaScript — Tail Call Optimization and Trampolines
Functional JavaScript — Currying

Advertisements

About taylodl

I'm an enterprise architect/developer who enjoys programming, math, music, physics, martial arts and beer
This entry was posted in HTML5, JavaScript. Bookmark the permalink.

5 Responses to Functional JavaScript – Tail Call Optimization and Babel

  1. James Emanon says:

    Dude — I’m reading over your posts about tail optimization/trampoline and its a brain twister, and I’ve been doing JS for a while. Do you have any resources that starts from the very beginning on all this stuff?

  2. taylodl says:

    Three resources come to mind:

    1. Secrets of the JavaScript Ninja, by John Resig
    2. JavaScript: The Good Parts, by Douglas Crockford
    3. JavaScript Patterns, by Stoyan Stefanov

    I wish I could find it, the JavaScript Ninja used to be online and featured live coding to implement a new concept. Now all I can find is the book. Then again the last time I used that site was while the book was a work in progress, maybe it got taken down after the book was published? You can also find a Douglas Crockford’s talk on JavaScript: The Good Parts on YouTube. Finally I’ll leave you with one of my favorite brain twisters – it’s a Ruby talk on Programming with Nothing: http://rubymanor.org/3/videos/programming_with_nothing/

  3. James. I agree. I’ve been doing JavaScript for a long time as well, but with things like Node JavaScript is going further then I ever expected my development skills to go… WHICH IS AWESOME!

    To understand what’s going take a look at the following link, because it will give you more context at TOCs and Trampolines: http://www.integralist.co.uk/posts/js-recursion.html

  4. Jonas Weidler says:

    TCO has been removed from Babel in version 6 due to its “buggyness”. It’s currently pending to be re-implemented, priority is low (https://phabricator.babeljs.io/T2614). So, as of April 2016, since no environment nor transpiler does the job for you, you’ll have to loopify your recursive function calls yourself or use a helper like https://www.npmjs.com/package/tco .

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s