Paul Barry Shows How to Accomplish Tail Call Optimization in JavaScript

Local Polyglot Extraordinare, Paul Barry has been on a JavaScript spree of late, especially in showing how JavaScript compares to other full functional programming languages like Clojure, Haskell, and Erlang. In his most recent article, he goes about showing how to use the accumulator pattern, from the SICP book if I am not mistaken, to accomplish Tail Call Optimization in JavaScript. One of the things he doesn't mention and is a known issue with JavaScript in most interpreters is that after around 1,000 recursive calls the interpreter will exception out the execution regardless. This is done based purely on the call stack and not on memory usage in an (vain) attempt to be protective in nature due to the "constrained" client environment and operating sandbox of JavaScript. It more often then not becomes a pain in the tail (recursion) in the modern era where people have more than 64kb of memory. That said, Paul's technique is a great one that is widely applicable in many formats, not just JavaScript.

Here's hoping he continues to love the JS and what he is doing that has transpired these recent posts.

Aug 31, 2009

pjb3 said...

Oh I do love me some JavaScript, but I must not have made my point clear in the article. You can't "do" Tail Call Optimization in JavaScript. In fact, you can't "do" Tail Call Optimization in any language. If it's supported in the language than the interpreter does the tail call optimization for you, transparently. You can write a function that is in the tail recursive position, as I did with the odds1 function, but if the language doesn't do Tail Call Optimization for you, your function will eventually blow the stack if it performs enough recursive calls. AFAIK, no JavaScript interpreters do that and probably rightfully so, since it's not in the language spec. It is in the language spec for Scheme, for example, that the interpreter must perform tail call optimizations to be a Scheme compliant interpreter. I believe it was Douglas Crockford who said JavaScript is just Scheme in C's clothing, so hopefully we will see tail call optimization in the language spec some day.

Chris Williams said...

Hey Paul,

Ironically your code examples show how to circumvent the recursion limits within JavaScript and actually shows the way of doing "tail call optimization". Not in the full functional sense as describe by the aforementioned languages, but in the sense of how TraceMonkey accomplishes Trace recursion using Trace Trees. Brendan Eich presents this in the Language Roadmap (albeit in the comments), with
"Tail recursion is just a loop, which Trace Trees eat for breakfast. Non-tail is more challenging but we're doing it. - Posted by: Brendan Eich at September 3, 2008 9:51 PM" http://weblogs.mozillazine.org/roadmap/archives/2008/09/tracemonkey_update.html and John Resig mentions in his performance evaluation of V8 versus an early TraceMonkey at http://ejohn.org/blog/javascript-performance-rundown/

Optimizing JavaScript tail recursion with NanoJIT Trace Trees will essentially accomplish the same process as the insight you provided. Albeit, TraceMonkey does this by detecting repetition and compiling to native optimized code, but your example provides this insight of unravelling the code.

Voodoo Tiki God

I am Zero Cool