Refactoring to PTC Form

[00:00:00]
>> Kyle Simpson: Let's go back to our example of count valves, you remember this implementation from earlier in our discussion, and let's analyze that this is not improper tail call position. How do we know it's not improper to call position, because there is an addition operation that has to happen after the countVowels has run.

[00:00:19]
So we know that those stack frames are gonna be kept around, and the question is, that was the way we designed or solved this problem recursively, and it led to a non-tail call representation of the problem solution, so what do we do? Because in theory it sounds great from recursion, but in practice now, we have this problem where it can't ever be optimized, even if they ever implement proper tail calls.

[00:00:43]
And the good news is that many forms of recursion, not all, but many forms of recursion can be reoriented to take advantage of tail calls, but it requires thinking a little bit more carefully about the problem. So this is a technique that you should be aware of, because if you are ever going to use recursion practically anywhere, even in Safari only, you're gonna have to get comfortable with the idea, thinking about proper tail calls.

[00:01:09]
Because it won't always be the case that your recursion nicely, cleanly is already in tail call position, you're gonna have to probably put in that extra work. And sometimes you're gonna be stuck where no matter what you do you're not going to be able to do tail calls.

[00:01:25]
There is a form of recursion called binary recursion, which is that you, and this is what you see when you're traversing binary trees, for example, where you call left and then you call right, and each one of those goes left and right. When you have a forked or a binary, or even more, any sort of recursion, you absolutely can't do tail calls, cuz one of those is not gonna be on the tail position.

[00:01:45]
One of them might, but one of them isn't, and so you're just stuck there is no way to solve that problem, you can't do two forms of recursion in the same function and have both of them be in tail call position. But most recursion that we do, that isn't of that form, at least is possible to consider rewriting it into tail call form.

[00:02:05]
So what we need to do is, analyze how do we get rid of that, essentially how could we get rid of that first variable, cuz that's the reason that it's not in tail call form, that's the reason why we need to preserve it. It's because that pesky thing that's stuck there, it's hanging out there while the other function calls are finishing, and then we're coming back to it.

[00:02:26]
So the key recognition point that is often gonna lead you to being able to refactor something that's non-tail call into a tail call form, that key recognition point is to say, if I am keeping track of this information in the stack frame, that is, my local variables in the stack.

[00:02:45]
Where else could I keep track of that information and not keep track of it in the stack frame? And there's only one other place that even makes sense. The other place that I could keep track of it in, is in the next stack frame, AKA, the arguments that I'm gonna pass to the next function.

[00:03:03]
So instead of preserving a variable here, if I were to compute my response and pass it forward to the next function, then I have a place for that to sit. Instead of keeping my stack frame, finish all of my business, and pass it all on to the next stack frame, and he finishes all of his business, and he passes it on to the next stack frame, and so on.

[00:03:24]
That's how you refactor from non-tail call to tail call form. So what that looks like then is that we are going to want to reserve one of the argument positions for our running count. We could start that argument position out at 0, and then we just, each time we make the recursive call, make sure that that number has been incremented properly to hold that new value.

[00:03:50]
So this is what it might look like, we could call count values with the count argument and started it out at 0. We could precompute count, like we were computing first before, but notice I'm doing a plus equals here, so I am adding two count rather than recomputing only first.

[00:04:07]
I'm basically making count bigger and bigger, and bigger every time it's called, and then we are forward passing. And you see on line 6 we pass in the new count to the next level of recursive. Now, the problem with this is that it makes the signature of our recursive function more awkward.

[00:04:24]
When it's a single number, like starting it out at 0, it's not a huge problem to tell people you have to pass 0, but it is a sort of leaky abstraction, wait, why do I have to pass 0? Shouldn't you be taking care of that? So it's kind of leaking the abstraction that we're doing a recursion, that we're doing a tail call recursion here.

[00:04:42]
So what you often will see, is that someone will create an interface function that has a nice, clean looking signature, and then they'll have the recursive function hidden away, that has the non clean signature. That's kinda the trade off here. So what you might see is something like this.

[00:04:59]
You might see a countVowels that we're gonna store it in some place and here's what I'm gonna do, I'm gonna store it in a Curry. I'm gonna create a countVowels that takes both of those inputs separately, and then I'm gonna prespecify one of those inputs down on line 7.

[00:05:19]
That's a fancy way of showing you, that's a functional way of showing you that I'm gonna store it in a closure somewhere. I'm gonna store that information in a closure so that the call sight that everybody else sees is the one that's only providing the second value. This is yet another example of using Curry to our advantage.

[00:05:36]
When we have some information that we need to store somewhere, Curry takes advantage of, or allows us to store that information in that closure. So this is a common way that you might take a function written, like the one on line 3, you see I've written it in the sort of naive sense, but then I've presented to the outside program one that has a cleaner information signature, where I only need the to pass in the string.

[00:06:02]
So, now this countVowels function would in fact run, we can see the call-site on line 6, that is the recursive call-site, and we can see that it does in fact work as a proper tail code, it is in proper tail call form, we have strict mode. So if we were to take this code and try to run it inside of something like Safari and give it a really, really giant string that was millions of characters long, it would happily run through all of those characters and give us a response.

[00:06:30]
It would probably run a little bit slower than the for loop version, cuz we'd have a million function calls instead of one. And there is some amount of runtime overhead, but we would at least not have a runaway memory situation.