Tail-Call Optimization in the Wild
As software engineers, we are constantly thinking about how we can improve our code. In the past few months, I’ve been reading Javascript Allongé to learn more about functional programming. Because optimization is frequently on my mind, one topic caught my attention: tail-call optimization. You may have also seen this concept referred to as proper tail calls, tail-call recursion, or tail-call elimination. The first part of this post will focus on discussing what it is as a general programming concept. Then, I’d like to bring it all back to JavaScript and how this impacts anyone who writes web applications.
The Stack Overflow Problem
Let’s dissect this error message first. When a function is invoked, it’s pushed into the call stack, where the function and its execution context is stored. This stack frame does not get popped out of the stack until the function is returned. In a recursive function, the function calls itself many times until it reaches a condition. Every time this function is called, another layer is pushed to the stack.
Recursive functions can be memory intensive and the call stack doesn’t have infinite space. You will eventually run out of available stacks. That’s what the stack overflow error is telling you: You’ve invoked this function, but the call stack has run out of resources to finish computing your result.
So what is tail-call optimization and how does it help?
In short, a recursive function can utilize tail-call optimization when it returns a function at its tail-position. This function gets pushed to the call stack, and the previous stack frame gets thrown out. This is because a returning function has no more work left to do. Thus, a tail-recursive function does not create additional stack frames, allowing you to run that function as many times as you need, without flooding the stack.
It is important to note that this would be done implicitly, where all the developer needs to do is have a tail-call. The engine will execute the code in a manner that optimizes stack usage.
For a more comprehensive discussion of how to tell if a function call is in tail-position, check out this article.
Let’s look at an example! The following is a JavaScript function to return the factorial value of the number passed as an argument. It is not tail-recursive.
const factorial = (n) => { if (n === 0) { return 1; } return n * factorial(n - 1);}
This definition of factorial returns an expression (n * factorial(n — 1)) and not a function.
Here is the tail-recursive version of the same function:
const factorial = (n, acc = 1) => { if (n === 0) { return acc; } return factorial(n — 1, n * acc);}
This pattern of using an accumulator to keep track of the current value will look familiar if you’ve used functions like JavaScript’s reduce method!
Now that you know about tail-call optimization, you can use it in all your recursive functions… right? The fact that I’m even asking this should clue you in on the answer: Nope. Not all languages are tail-call optimized. What about JavaScript? A quick Google search will tell you that JavaScript is among those languages. We can finally get rid of all those pesky stack overflow errors!
It’s actually a little more complicated than that. Let’s open up the developer console in a new Chrome window and run that factorial function from earlier.
The function is tail-recursive, so what’s going on here? Why am I still getting this error?
You can certainly start writing your recursive functions to have tail calls. However, the JavaScript engine that is running your code may not actually have tail-call optimization implemented! It’s probably one of the last things a front-end developer wants to hear: Not all browsers support it. From the screenshot above, you can see that it’s not supported in JavaScript’s V8 engine (Google Chrome, Node.js). It’s not supported in SpiderMonkey (Mozilla Firefox) either. But guess which browser supports it? Safari does! In fact, Safari is the ONLY browser that supports tail-call optimization.
Here’s the same factorial code run in Safari:
Yeah, that’s right. It works in Safari! What a twist! When I first saw this, I was confused, because that was definitely not what I expected.
How did this come to be?
According to Andreas Rossberg in this Stack Overflow thread, around 2011, TC39 decided to include tail-call optimization for ES6. When ES6 was officially adopted in 2015, none of the browsers implemented it. There were a lot of new features with higher priority to implement.
By 2016, Safari and Chrome implemented tail-call optimization, though Chrome hid it behind an experimental feature flag. Firefox and Internet Explorer / Edge started to look into it but had doubts about whether it was a viable feature. Edge reportedly had issues implementing it efficiently.
At one point, tail call optimization was available in Node’s strict mode but was eventually removed. As a result, if you do a Google search on whether JavaScript is tail-call optimized, you’ll see varying results!
Though Safari was able to implement tail-call optimization, it is clear that it’s not a straight-forward decision to do so, and opinions about it are also not universal.
At first glance, tail-call optimization sounds wonderful. Who wouldn’t want to optimize their recursive code like this? As with any solution, there are pros and cons. Up till now, we’ve only talked about the positive parts. What are the cons that have some developers so against implicit tail-call optimization?
It boils down to two very important things: Performance and debugging. Theoretically by optimizing the call stack, the engine will run code faster. According to this TC39 proposal, the JavaScriptCore engine (Safari) was able to gain some performance wins. However, other engine teams question whether there will be positive gains. Another concern is if they will be able to implement it in a manner that doesn’t regress performance. Some developers believe it will make debugging code more difficult.
While some developers deem these two issues as deal-breakers, others believe they are not warranted since many of the issues brought up are not backed up by actual data or implementation experience.
The Current State of Tail-Call Optimization in JavaScript
This topic is by no means dead. Some developers feel strongly about having tail-call optimization supported in JavaScript. If you were paying attention, you may have noticed I linked a TC39 proposal in the previous section. There is currently an active proposal for tail calls that are explicitly opt-in by using a keyword, also called Syntactic Tail Calls. In the proposal, they refer to tail-call optimization as Proper Tail Calls (PTC). Here are the code examples that they’ve included to illustrate how it would work:
function factorial(n, acc = 1) { if (n === 1) { return acc; } return continue factorial(n — 1, acc * n)}
let factorial = (n, acc = 1) => n == 1 ? acc : continue factorial(n — 1, acc * n);
By having a statement like return continue to signify a tail call, developers can choose whether they want to utilize this call stack optimization. I think this could be a good solution since it allows developers on both sides of the argument to get what they want. Since utilizing tail calls will be explicit, the developer is being intentional. It can be assumed that he or she knows what they are doing and what the potential pitfalls of this path are.
Some developers may still complain that they want it done implicitly, but that seems unlikely. Unfortunately, no matter what solution we end up with, it won’t appease everyone. In spite of that, I think this is a pretty good compromise. Since syntactic tail calls are still in a proposed state, and with many differing opinions weighing in, it may still be years before we see this actually implemented in browsers.
