ES6 Tail Call Optimization Explained(benignbemine.github.io)
benignbemine.github.io
ES6 Tail Call Optimization Explained
http://benignbemine.github.io/2015/07/19/es6-tail-calls
5 comments
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.
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.
> 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).
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).
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.
Hm, the question now becomes what kind of `goto` you're talking about. C's goto is definitively not enough either, since you can't use labels in other functions as target (and have other restrictions). Perl's goto qualifies, because it can jump to functions; also, Perl allows to set the @_ array variable which is used to pass arguments to functions; also, Perl has closures, which is also necessary in this case, to maintain the context. You can now simply argue that this is Perl's way to manually declare a subroutine call as tail optimized (i.e. Perl has manual TCO). Java has goto in the JVM, but AFAIK it does not qualify. Assembly language has various kinds of jump instructions, these do qualify, assuming that the rest of your code is able to deal with the jumps (i.e. you're also implementing closures manually).
I'm pretty sure Guy Steele's paper title was tonge-in-cheek, as around a decade before the well-known letter "Go To Statement Considered Harmful" by Edsger Dijkstra was published. How would one want to propagate something as awful as goto? Well, the new goto allowed to pass arguments with it, and would reinstate the context. This would make it safe from a memory corruption stand point, and also be cleaner for it's now all calling of mathematical functions. So you could do all that goto could, but in a clean way.
I don't know if Steele hat C in mind (which appeared just 5 years before the paper) or which other language(s). Also, perhaps "the ultimate goto" was a play on that it's even actually more powerful than goto in most languages? (I think I still haven't finished reading it, actually, and should, perhaps the answer is in the paper.)
If you want to use goto in C to have the full power of TCO, then you need to write your C program as a single C function, with all actual "functions" of your program represented by labels, and allocate a stack and pass arguments on that stack or in globals yourself. And can forget about any type checking and programmer sanity. (A saner way to archieve TCO in C will be to use trampolines. Or use a code generator instead of writing goto'ified C manually; the Gambit-C system uses this approach to compile Scheme to C.)
I'm pretty sure Guy Steele's paper title was tonge-in-cheek, as around a decade before the well-known letter "Go To Statement Considered Harmful" by Edsger Dijkstra was published. How would one want to propagate something as awful as goto? Well, the new goto allowed to pass arguments with it, and would reinstate the context. This would make it safe from a memory corruption stand point, and also be cleaner for it's now all calling of mathematical functions. So you could do all that goto could, but in a clean way.
I don't know if Steele hat C in mind (which appeared just 5 years before the paper) or which other language(s). Also, perhaps "the ultimate goto" was a play on that it's even actually more powerful than goto in most languages? (I think I still haven't finished reading it, actually, and should, perhaps the answer is in the paper.)
If you want to use goto in C to have the full power of TCO, then you need to write your C program as a single C function, with all actual "functions" of your program represented by labels, and allocate a stack and pass arguments on that stack or in globals yourself. And can forget about any type checking and programmer sanity. (A saner way to archieve TCO in C will be to use trampolines. Or use a code generator instead of writing goto'ified C manually; the Gambit-C system uses this approach to compile Scheme to C.)
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
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
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.
What does this do to debugging and stack traces in ES6?
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...
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.
So close yet so far. This is JavaScript's curse.
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.
This example of TCO adds to that.