ES6 Tail Call Optimization Explained

http://benignbemine.github.io/2015/07/19/es6-tail-calls

by rkho • 11 years ago

29 11 11 years ago

benignbemine.github.io

taylodl• 11 years ago

Not one browser implements TCO, and Babel only implements direct recursion, not mutual recursion. Sigh. Trampolines are your only option aside from Babel. I've written about trampolines here: https://taylodl.wordpress.com/2013/06/07/functional-javascri...

strmpnk• 11 years ago

This. It's sad to have this in the standard but with no vendors communicating their intention to implement it and no way to polyfill that doesn't involve significant overhead.

So close yet so far. This is JavaScript's curse.

balls187• 11 years ago

Tangeant: while very simple to memorize the solution to, I find that Fibonacci is a very fun problem to discuss with CS candidates.

This example of TCO adds to that.

_jal• 11 years ago

Completely aside from the content, the article reminds me indirectly of how amazing second, third, etc. order effects can be. Some manager at Netscape decided that two weeks was all the time an engineer would get to implement a client-side language almost 25 years ago, and we're still discussing how to hack in tail recursion today.

StefanKarpinski3• 11 years ago

This blog post hints at but doesn't outright state a crucial fact about TCO: it is only possible when the code could be expressed with a loop instead of recursion. People make a big deal about TCO, but it was only necessary in Scheme because they didn't want to include loops in the language, opting instead to provide recursion and implement loops in terms of recursion. Without guaranteed TCO, that would sometimes blow your stack out. Hence, guaranteed TCO in Scheme. In a language with loops, however, TCO is not essential since you can always just use a loop.

pflanze2• 11 years ago

In a language with loops, however, TCO is not essential since you can always just use a loop.

That's not correct. Loops are just one kind (the simplest) of iteration. In a language with TCO, you can also implement state machines with function calls, or do continuation passing style (pass one or multiple functions to a function to be called with a result when done). There's a reason Guy Steele called the function the ultimate goto (assuming TCO): you can then build all control structures with them.

Missing TCO, you need to fall back on handling state yourself (like you can still implement recursive algorithms in a language that doesn't offer recursion, like old Basics or whatever, you just need to build your own stack).

StefanKarpinski3• 11 years ago

Right, that's a fair point. If you have goto, however, you don't need TCO, but then you're programming with gotos. This is not the argument most people make when arguing for TCO – they often talk about recursive algorithms for walking data structures – which usually are not actually eligible for TCO at all.

srean• 11 years ago

I think this is the first time I am disagreeing with a comment of yours. Sadly, this factually incorrect position about TCO is held by many and repeated often.

On the larger scheme (pun intended) of things, of course TCO is not essential, very few things are. However, the assertion "you can just always use a loop" is incorrect. To pull out just one example, with TCO I can have the producer-consumer coroutine for free without stack overflow. Loops are not the only use case for TCO.

Furthermore, there is nothing 'O' about it, doing extra work (maintaining call frames) not required by the semantics is not an optimization but an act of pessimization, unless there are compelling reasons to do that extra work. Guido feels lack of stacktraces is one such a compelling reason. I don't find that to be particularly compelling because that 'stack trace' is quite absent in the alternative he suggests: loops

StefanKarpinski3• 11 years ago

Good point about it not being an optimization – calling it "tail call elision" would be more correct. And it's true, as @pflanze's comment correctly points out and I think you're getting at, that loops aren't sufficient – but gotos are. Of course, then you're programming with gotos, which may not be awesome. But point taken.

millstone• 11 years ago

What does this do to debugging and stack traces in ES6?

ES6 Tail Call Optimization Explained

Related Stories