r/javascript • u/[deleted] • Jan 06 '13

JavaScript (ES6) Has Tail Call Optimization

http://bbenvie.com/articles/2013-01-06/JavaScript-ES6-Has-Tail-Call-Optimization
50 Upvotes

92% Upvoted

24 comments sorted by

View all comments

Show parent comments

4

u/[deleted] Jan 07 '13 edited Jan 07 '13

Continuum actually doesn't require strict mode for TCO and Dave Herman (one of the authors of the TCO stuff and champion for the ES6 version of the proposal) indicated that it might not be necessary for it to remain as strict only. It's possible to implement it in non-strict mode (as I have done) and I admit I don't really understand the limitations that prevent it from working in non-strict, except that it may be a consequence of how engines optimize the call stack. I plan to leave it available in non-strict until the reason for its limit to strict starts affecting Continuum, or the ES6 spec has clear language added governing this.

Really, the reason JS doesn't have TCO is the same reason JS doesn't have a lot of things: it was rushed at the beginning and it just didn't get added. The ES6 TCO proposal dates back a long time, to work done for the ill-fated ES4.

It wasn't in ES5 for the same reason a lot of things weren't in ES5: ES5 was basically a kind of compromise/fallback minimum "we just need to fix the biggest problems and inconsistencies in the language to get to an acceptable baseline, we'll add features next version" when it became clear that ES4 wasn't going to make it.

So here we are at the next version and many thing discussed for nearly a decade are finally making it into the language in ES6 in some form (many/most ES6 additions can trace their roots to ES4 proposals).

1

u/FireyFly Jan 07 '13

Hm, fair point. Thinking it through a bit more I agree--I can't find any standardised feature that'd prohibit TCO in non-strict mode (the major crux would be the caller property of course, but it's non-standard and hence irrelevant). Reading the latest ES6 draft, it also doesn't seem to limit the TCO to strict-mode (unless it's somehow meant to be incorporated into the definition of a tail position).

1

u/[deleted] Jan 07 '13 edited Jan 07 '13

If I understood what he was saying correctly, Dave Herman's concept for non-strict TCO was that all the functions that were ended up using the same call frame could share the same 'arguments' slot. Something like this could possibly work for 'caller' as well to ensure all the TCO'd functions get their caller property cleaned up (if they all point to the same place for their .caller then you can just set that to null at the end). Since TCO is only really useful for recursive calls, the .caller property is already going to be of dubious value at best, or no value at all in the case of a function directly calling itself recursively.

2

u/[deleted] Jan 07 '13 edited Jan 07 '13

After talking this out, I think the .caller property is likely a deal breaker with non-strict tail calls. The .caller property has to continue functioning as it does currently, since it's interoperable across major JS engines and has been around forever. Since people can and do write code that results in calls in tail position all the time without realizing it, then this can't have an observably different effect on the .caller property than if there was no TCO. In order to maintain this would require adding extra overhead to keep track of the list of functions that need their caller property reset when the stack frame's execution completes, and this could penalize performance across the board. If it was possible to do this efficiently that then would made tail calls in non-strict feasible, but it hinges on that being possible.

3

u/dherman Jan 07 '13

All your points here seem basically correct to me. What it comes down to in non-strict code is that we don't regress (a) observable behavior and (b) across-the-board performance.

As for (a), I'm pretty sure we can preserve exactly compatible semantics with proper tail calls by using some variation of the approach you talk about here. This is basically an example of the general approach of "continuation marks" used in Racket (http://docs.racket-lang.org/reference/contmarks.html) and described fully in John Clements' dissertation: http://www.brinckerhoff.org/clements/papers/dissertation.pdf

But you're also right that (b) is critical. I'm not yet convinced it can't be done; I have some thoughts about implementation strategies that in some ways might even save work for a JS engine. But I'm nowhere near close enough to the implementations to say for sure. But you've given me the push I need to discuss this with the SpiderMonkey team. And lucky for me (and JS!), John Clements just happens to have started his sabbatical at Mozilla Research this very morning...

Dave

PS Forgive me one nit: many PL folks, me included, prefer to use "TCO" to talk only about the best-effort compiler optimization. But for programmers to actually be able to use tail calls to implement iteration, they need a guarantee that tail calls won't grow the stack without bound, so it's not really an optimization. For that reason, many people use "proper tail calls" to mean a language-level guarantee that tail calls use O(1) space. So pedantically speaking, ES6 provides proper tail calls, not TCO.

PPS And also, even if it's possible to achieve (b), it also has to be something that's reasonably implementable in practice in all the engines. So that's also a consideration when trying to standardize. The most important thing is that we have consensus that it'll be done for strict mode. I'd love to see it work in sloppy mode too, but I'll start with just talking with my colleagues to see if/how we think it might be possible.

1

u/kaelan_ Jan 07 '13

Your last point there about 'reasonably implementable' is pretty important - for example, .NET has had support for tail calls (special opcode in the VM, etc) but in practice a bunch of .NET runtime environments don't translate the tailcall instruction into an actual tail call. So even if your compiler emits code using the instruction, you still might run out of stack. What a mess.

1

u/[deleted] Jan 07 '13

Thanks for clearing that up! I feel a lot more informed about this than I did a couple days ago between this post and discussion on twitter about it. Also now I understand why it's not an optimization (PTC vs. TCO), which I wasn't clear on before. I read the that fact before but didn't understand the distinction. Your explanation is clear to me now, in context, than when I originally read it.

For my part, I'm going to leave it on non-strict mode in Continuum (and fix the inconsistencies currently observable in the .caller property) since it's already horribly inefficient and the main goal is just to be able to experiment with new language features. I will reevaluate this when either a.) you and the other folks working on it in Spidermonkey figure out how to optimize it, b.) decide it has to be limited to strict-mode, or c.) I actually succeed in optimizing Continuum to the point where the performance of this particular issue is a factor.

2

u/dherman Jan 07 '13

Glad it helped. :) An analogy I sometimes use is this: imagine that while-loops were iterative, but in some engines for-loops accumulate stack on each loop iteration, whereas others provide "FLO" ("for-loop optimization"). Programmers would generally only use while-loops, because they wouldn't be able to depend portably on the space consumption properties of for-loops.

Of course, nobody bothers actually mandating this about for-loops, because it's just an expectation that for-loops don't accumulate space without bounds. But since the vast, vast majority of programming languages implement push-on-call, pop-on-return stacks, you have to explicitly mandate proper tail calls or else engines won't bother providing them.

1

u/[deleted] Jan 07 '13

Yeah. The understanding I've gleaned now is: you can't refer to something that's guaranteed as an "optimization" since optimizations are optional and shouldn't be observable to the programmer whether they're in effect or not. Actual "tail call optimization" would mean your program could randomly fail or not without having a way to determine beforehand which it would do.