Tail Call Optimizations, Stack Frames, and ES6

One of the most interesting changes that ES6 brought with it is the ability to make use of tail call optimization. This post will explain what a tail call optimization is, how tail call optimization works within a theoretical JavaScript engine, and discuss the rules and conditions of their implementation. In order to better understand what’s happening, we’ll also need to reason about such things as stack frames and memory.

What is it?

Put shortly, a tail call optimization is done when some function is called as the last statement in another function. In ES5, tail calls are handled just like any other function call. A new stack frame is created, which then gets pushed onto the call stack. In such a system, every previous stack frame is kept in memory, which is a problem when the call stack gets too large (resulting in a stack overflow) or for performance concerns when a program makes repeated function calls (typically recursion).

Consider the following:

``````
function second(z) {
return z
}
function first(x) {
let y = x * 2
return second(y)
}
console.log(first(2))
``````

On the surface, nothing particularly interesting is happening here. A value of two is passed to the function `first`, it becomes multiplied by 2, and so 4 is logged to the console. This probably isn’t the best way to do such an operation. But for demonstration, it’s helpful to have nested function calls that are simple in nature.

No Tail Call Optimization

Now here’s an outline of what’s occurring in the JavaScript engine without tail call optimization (ES5):

The `first` and `second` functions are added to the global stack frame. In other words, some memory from the stack is allocated to the execution of these two functions.

Global Stack Frame first = function(x) {…} second = function(z) {…}

When our program starts executing, the `first` function is called. That means that `first`‘s arguments and local variables get their own stack frame or allocation of memory in the stack.

first() stack frame x = 2 y = 4 first = function(x) {…} second = function(z) {…}

Now there are two frames on the stack. A third will be added when `first` makes a call to `second`:

second() stack frame z = 4 x = 2 y = 4 first = function(x) {…} second = function(z) {…}

At any given time during execution of the program, the function at the top of the stack is executing, and the rest are waiting for the function above to return something. Once the function at the top of the stack returns, it is cleared from the stack and the function below it can then begin its own execution.

In our example, the `second` function returns its value of 4 and so it gets cleared from the stack:

first() stack frame x = 2 y = 4 first = function(x) {…} second = function(z) {…}

The very same happens with the `first` function and so its stack frame is removed such that execution jumps to the global stack frame:

Global Stack Frame first = function(x) {…} second = function(z) {…}

With everything resolved, the value of 4 is logged to the console.

With Tail Call Optimization

In ES6, the JavaScript interpreter can make use of tail call optimization. It’s able to recognize when a function is called as the last statement by another function, keeping the local variables of the previous function in memory is unnecessary. In our example shown above, the local variables allocated to memory in the `first()` stack frame are not needed after the call to `second`. Let’s walk through the same steps above but assume that the theoretical JavaScript engine can recognize and optimize tail calls.

The `first` and `second` are added to the global stack frame:

Global stack frame first = function(x) {…} second = function(z) {…}

Next, the `first` function is called and its local variables are allocated to memory in its own stack frame:

first() stack frame x = 2 y = 4 first = function(x) {…} second = function(z) {…}

So far, everything has been the same as our previous example. But here is where things change. The JavaScript engine sees that it doesn’t need to keep the values of `x = 2` and `y = 4` in memory, because the `first` function passes the value of `y` along to the `second` function as the last line in its execution. Thus, the stack now looks like this:

second() stack frame z = 4 first = function(x) {…} second = function(z) {…}

And now `second()` can just return the value of 4.

Global stack frame first = function(x) {…} second = function(z) {…}

And then it’s logged to the console.

Rules, conditions and examples

The following conditions are needed for tail call’s to be optimized properly in ES6:

1. The tail call cannot be a closure
2. The function making the tail call has nothing further to execute
3. The result of the tail call is return as the function value
4. Must be done in ‘strict mode’

Now for some examples. This call to `bar()` is the most trivial base case example of a tail call optimization:

``````
function foo() {
return bar(); // Optimized!
}
``````

One small change to it, however, such as not returning the result violates rule #3:

``````
function foo() {
return bar(); // Not Optimized!
}
``````

If we have a tail call that requires further execution beyond simply returning, rule #2 is in violation:

``````
function foo() {
return 1 + bar(); // Not Optimized!
``````

The trickiest situation is rule #1 involving closures. It can help by understanding the first section where consider what’s happening in the JavaScript engine’s memory and stack frames. If the tail call depends on some value that’s closed over (in a closure), then the interpreter can’t clear the stack frame from memory:

``````
function foo() {
let num = 1,
bar = () => num;
return bar(); // Not Optimized!
}
``````

Last to consider is that tail call optimization can only be done in strict mode. This is because of a conflict between the implementation of tail call optimization and non-strict mode implementation of the `func.arguments` and `func.caller` properties which involve the call stack.

Conclusion

Tail call optimization is a must for any recursive function that needs to be performant. It is an interesting and welcome feature in ES6 which brings it closer in parallel with other functional programming languages. Using tail call optimizations lead to a smaller call stack, less memory consumption, and a lesser likelihood of stack overflow errors.