Proper Tail Calls

[00:00:00]
>> Kyle Simpson: So we have traditionally allowed a wide berth of choice in terms of implementation. And if the JavaScript specification steps in and says, you absolutely must throw away stack frames and allow 0(1) memory usage, all of the sudden that now starts to really encroach upon the space of these JavaScript engines.

[00:00:21]
Because there's almost nothing that JavaScript engines do that is more intensive, from a resource perspective, than function calls. So we're really mucking at the very lowest levels of the stuff that they're doing in their memory and their optimizations and stuff. We're really reaching far into their normal realm and saying, no, no, you have to do it in some specific kind of a way.

[00:00:42]
So there has been significant pushback from JavaScript engines over the years to say we don't want tail calls, we don't even think people care about it that much. I've had conversations with developers at Microsoft, for example, that told me, well, nobody uses recursion so why would we implement that feature?

[00:00:59]
And my response was, nobody uses the feature cuz you haven't implemented it, and they say well nobody uses it so we're not gonna implement it. You can see the problem here, right, the catch 22. They don't want to implement something that's hard to implement unless people wanna use it and nobody wants to use it cuz it's not even possible to use.

[00:01:16]
How are we supposed to resolve this problems? So I've been fighting actually this battle for a long time trying to convince them please do this sort of thing. Well, there's a proposal that came in ES6, this was back in 2014, 2015, when ES6 landed. There's a proposal that said, let's finally standardize that JavaScript engines have to do tail calls, specifically we called them proper tail calls, PTC as it's referred to.

[00:01:41]
Now, just a quick note, there is a related term that if you do some Googling you gonna see TCO, which stands for tail call optimization. This is different and for a long time I actually thought they were basically the same thing, they are different. So let's make sure we're clear, proper tail calls are the idea that a tail call gets memory optimized, that we only use 0(1) memory space essentially.

[00:02:07]
PTO, I'm sorry TCO tail call optimization, too many acronyms, TCO tail call optimization is a family of potential optimizations on top of PTC which are optional that an engine may decide that it wants to do. For example, it may decide to throw away old memory, it may decide to garbage collect old stack frames, or it may decide to reuse a stack frame and grow its memory usage, or whatever.

[00:02:35]
Those are this whole other family of low level optimizations that essentially have absolutely no bearing on the JavaScript world. They matter to JavaScript engine developers but they don't matter to us, okay. The only thing that matters to us is, is PTC in the language or not? Do we either get that members of optimization and eliminate the range error or not?

[00:02:57]
So the proposal was let's standardize proper tail calls and the language in the spec was deliberately a bit more open to essentially say we're not gonna require specific TCOs we're just gonna generally say that it should be possible for a function in a tail call position to be able to not take up extra memory.

[00:03:21]
The language is more formal than that but it's essentially a bit gray area-ish, it's not very fine grained like you have to do the memory in this particular way. So the proposal was discussed at TC39 at length over a period of months, and sometime in 2014, or 2015, they voted, that is TC39 and that was present all members of all the JavaScript engines, they voted to say yes, let's go ahead and include proper tail calls in the ES6 standard.

[00:03:57]
So here's what PTC was standardized on in ES6. Number one, you have to have strict mode on. It's not going to work if you're in the non-strict mode, sometimes referred to as sloppy mode, you have to opt in to strict mode to be able to do this. By the way, you should already be using strict mode in all of your programs, if you're not, it's time to adopt that cuz that's been around and out for literally 10 years.

[00:04:21]
So what are you waiting for? [LAUGH] Let's get on the boat with strict mode. But you have to be in strict mode to be able to take advantage of tail calls. Then you have to have your function call in what is called a proper tail position, it has to be a proper tail call.

[00:04:39]
Now, the function call that you see here is in a proper tail position because even though there's an x and 1, and we could even do stuff in the arguments, what you'll note is that nothing has to happen after that function call finishes except for its value to be returned, that's a tail call position.

[00:04:59]
It is notable that without the return keyword it is not a proper tail call, even if it's at the end of the function, it's not a proper tail call unless there's a return keyword, okay. Proper tail calls require a return keyword and a single function call, and nothing else in that expression that needs to be computed afterwards.

[00:05:20]
There's a slight little grammatical nuance there which is, if you have a ternary expression on your return statement, and the function call is in one of the branches that's a tail call, because nothing else is gonna happen, the ternary precomputes and then picks one of the function calls.

[00:05:37]
So that even though it didn't look like a tail call that technically is. But otherwise, generally speaking, the pattern is you're gonna see return and then a function call and that's it and that's gonna mean that it qualifies as a tail call. This has nothing to do with recursion.

[00:05:50]
This is just it's a proper tail call and the spec then says that the JavaScript engine has to make sure that no matter how deep that chain of function calls gets you won't get a range error, it won't run the system out of memory. Of course we're normally gonna see this in the context of things like recursion, like this function here which keeps dividing a number and calling it for several times and those calls to diminish are proper tail calls.

[00:06:19]
Even though there's math that's happening inside of there the Math.trunc and the x divided by two 2, those are proper tail calls. Notably, Math.trunc is not a proper tail call cuz there isn't a return before it, but it's okay, because Math.trunc doesn't call any further functions, so it's not contributing to the growth of the call stack.

[00:06:39]
The thing that would contribute to the growth of the call stack is the call to diminish and that one is in a proper tail call position. So theoretically we should never have a growth of that stack and therefore we should not ever have a range error memory no matter how many times that had to run, okay.

[00:06:56]
>> Speaker 2: What would happen if instead of Math.trunc we had another function that calls another function? Like something else-
>> Kyle Simpson: That would not, yeah, that's a great question. So if that was a call that would contribute to the growth of the call stack, like if we're calling another function that called another function and created its own call stack growth, then that would definitely potentially grow the stock eventually to create a range error.

[00:07:18]
So you only get the benefits of removal of stack frame from a conceptual perspective, if the function calls are all in tail call position. So if you have some that are not and some that are, you're getting the benefit of the ones that are and not the benefit from the ones that aren't, so basic bottom line.

[00:07:34]
So you do want to try to arrange everything to be in tail all position if you're expecting for that to happen. If you're in that fortunate position where you're writing only for Safari then you can take advantage of this today. And hopefully some day you're gonna be able to take advantage of this across all of the JavaScript.