ES6 is old news by now. It's fully implemented across all modern browsers. Nothing to see here.
The compat-table of ES6 by kangax that we used to check to see progress should be all green by now, right?
Well, it's not.
The proper tails call section, (tail call optimization) is red.
Why? is it a feature that can't be implemented for JS?
Well, no. There is one browser that implemented this feature. Safari.
Then it is possible, and it is out for large audience in Safari. Why does chrome and firefox lagging behind?
The answer is complicated. And as it seems from my browsing in many many bug trackers comments for V8, Firefox JS engine, github issues, TC39 committee discussions and more - also very political and opinionated.
I'll try to give here a bit of background on the subject, that may hopefully leave you knowing more why is this so hard.
PTC? TCO?
PTC - proper tail call
TCO - tail code optimization
These 2 terms are not the same. And it is important to understand the difference between them for the discussion ahead.
Assumptions moving forward
I don't want to make this article a primer on recursions and call stacks.
I will assume you already know about that part. In case you don't, freecodecamp have a great article regarding this.
Proper Tail Call
I'll say before starting, proper tail call is what should have been implemented in ES6, and not tail code optimization (which we will talk about later).
It is in the ES6 Standard document and if you can't read the Formal definitions of it (don't worry, neither can I) you can just look at the introduction:
Goals for ECMAScript 2015 include providing better support for [...].
Some of its major enhancements include modules, class declarations, [..]
and proper tail calls.
Proper tail call is a technique where the program will not create additional stack frames for a recursion that fits the tail call definition.
This, and this only is the proper tail call value proposition.
So, instead of having a recursion with all its stack saved in memory, we will have just one level of stack saved, optimizing the recursion stack.
But how can it be? Tail recursion functions basically keep passing all the necessary data it needs down the recursion, so you don't have to rely on the stack.
The classic example here is the Fibbonaci function.
Consider this in the classic (head) recursion:
function factorial(n) {
if (n === 0) {
return 1
}
return n * factorial(n - 1)
}
It has to rely on the stack on each step, as each step have to be "processed up" to the n * factorial(n - 1).
Now consider this tail recursive version:
function factorial(n, acc = 1) {
if (n === 0) {
return acc
}
return factorial(n - 1, n * acc)
}
In this version, we have an accumulator as an argument. This keeps track of the total so far. Therefore, the stack here have no use, all the data is available all the way down the recursion call.
Great! Recursive programming that is sometimes easier to grasp than the iterative alternative without the call stack problem. They are basically equivalent!
Only, they are not. Not in the PTC case.
The problems with PTC are described beautifully on a recent proposal for TCO in Ecmascript.
Basically, this is what they are:
- Performance issues. This only optimize the call stack, not the calls themselves.
- Debugging. The call stack will be tempered with unnaturally, a thing that might make debugging much harder.
Yicks. No wonder people are so passionate about their positions on this regard.
Some say the debugging issues is a deal breaker, and the performance issues will kill profiling. Others disregard this as FUD, since Safari implemented PTC and hell is still closed.
You can find adults fight passionately for what they believe here:
https://github.com/tc39/proposal-ptc-syntax/issues/23
https://bugs.chromium.org/p/v8/issues/detail?id=4698
Tail Call Optimization
Tail call optimization to the rescue!
Well, not really but I wanted to be dramatic.
Tail code optimization is different by the fact that it does not simply eliminate the additional stack calls, it completely re-compiles the recursive function to be an iterative one.
Behind the scenes, tail code optimization takes a recursive function and generate an iterative function, using goto internally, and then runs it.
It does not limit the stack calls, because there are none once the function is actually not recursive behind the scenes.
This solves the performance issues perfectly.
Lua actually has this implemented long ago and it works perfectly. A recursive function is identical in performance to its equivalent iterative function.
Alright, so why not just implement TCO?
Well... There is much debate about that too.
There are people who want "implicit" TCO - that is, when it recognizes a fit function for tail optimization - just do it in place.
And there are people who want "explicit" TCO - do this only if it is the developer intent by purpose.
This is what the current proposal for Syntactic Tail Calls is all about.
It introduces new syntax and new keyword for tail calls optimizations, namely the continue keyword.
And, again, much controversy here too it seems.
- Will we have to beg third-party library owners to re-write their code?
- The new syntax required will basically kill the feature before anyone will use it.
- etc' etc'.
So, that's the story of tail call optimization in JS as it stands right now.
I didn't go too deep on the details, ofcourse, but I feel like this should give you a basic understanding on why this subject is complicated and hard to get right.
And as always - thank you to all the guys working on this subject and the Ecmascript proposals. Your work and passion-full discussions ends up benefit us all.
Top comments (6)
This article is rather confusing.
TCO is Tail CALL Optimization, not "Tail Code". Obviously, all (non-empty) functions have CODE in the tail position.
"This only optimize the call stack, not the calls themselves" makes no sense, and nobody at the PTC proposal said anything like this.
You say "The problems with PTC are described beautifully" in the linked proposal, but if you read the comments there, the people they're summarizing say it's not accurate. For example, the summary says JSC saw a perf improvement (which would be great, if true), but the JSC devs say they saw no measurable change in performance. I don't know why anyone is still mentioning performance, because I see no JS engine devs saying that's a problem (or a benefit).
You say "Tail code optimization is different [than what?] by the fact that it does not simply eliminate the additional stack calls, it completely re-compiles the recursive function to be an iterative one." I've written compilers before, and I can't tell what you mean by "completely re-compiles". Essentially all it does is replace a CALL with a GOTO so it doesn't add a new stack frame. It doesn't need to "re"-do anything, and it doesn't affect the rest of the function at all.
You say "The classic example here is the Fibbonaci function." That's not a Fibonacci function. That's not even how "Fibonacci" is spelled.
You say "Proper tail call is a technique where the program will not create additional stack frames for a recursion that fits the tail call definition." Recursion is a common use of PTC, but TCO isn't just for recursion. It applies to all calls in the tail position, not just self-calls.
You show "classic (head) recursion", but I've never heard of either of those terms before. The recursive call here clearly isn't in the head position. It's in the middle. I don't know what might be more "classic" about the head or non-tail positions, either.
Anyone who wants to learn about this subject online would do better to read the Wikipedia article for "Tail call", and the TC39 issue comments.
So, what has been the response of the Safari people, how did they implement proper tail calls? Douglas Crockford was saying something like it was Microsoft's fault, that they didn't want to implement the feature, and that now that they have essentially give up in the browser by the adoption for Chromium, that now we might have the change of having these feature implemented
Why not have both? Proper Tail Calls as a standard behaviour with the option to use a keyword to tell the compiler to do Tail Call Optimization.
Or the other way around, I really don't care as long as we have it implemented already. Jeez.
That's not Fibonacci...
He should change that because it can confuse the noobs.
function fibonacci(num, memo) {
memo = memo || {};
if (memo[num]) return memo[num];
if (num <= 1) return 1;
return memo[num] = fibonacci(num - 1, memo) + fibonacci(num - 2, memo);
}
Amazing, I never thought that TCO could bring so many "problems", thanks for clarify.
IMHO at least PTC should be available, as it could remove many of common issues with recursive behavior in JS