Trampolines

[00:00:00]
>> Kyle Simpson: That idea that I'm gonna defer the work of first+v until a later function call by wrapping it in a function. That idea we wanna key off of for our last technique, this is the one I want you to actually use, okay? That technique is called trampolines. I want you to use trampolines because you're gonna see that you write it almost as if it's just a regular normal recursive function.

[00:00:26]
And then you have this adapter that helps take care of the whole tail calling problem. So what is a trampoline? It's a funny way of basically indicating that we want something to sort of bounce back and forth. That's why it's called a trampoline. So what's is it bouncing back and forth?

[00:00:43]
Instead of having function call function call function, call function, call function. Our strategy is basically going to be function call function, return another function, then call that one and return another function, then call that one and return another function, then call that one and return another function. And you can sort of visually get the idea of somebody bouncing up and down on a trampoline.

[00:01:01]
So in other words, we never have the case where this thing has called this thing. We never build up a stack at all, the stack depth never goes beyond 1. Because what we do instead of making a recursive call is we return a function that will make the next call.

[00:01:18]
That's how the technique works. So let's look at utility for that, this is real simple, this would be provided to you by your functional programming librarian. They are a little more sophisticated than this. But essentially a trampoline function is just gonna do a while loop here, and as long as you keep returning a function back, it's just gonna repeat the loop again and call the function and then get the result.

[00:01:40]
And if that's the function again, it's just gonna keep. So as long as you keep returning the function it's gonna assume you want me to keep going with the trampoline until the very end when it just returns the result line 9. It didn't give back a function, it got back a number, string, something non function that's how it knows.

[00:01:58]
Now libraries have it little more sophisticated than just the type of check on the function. So there's way to even return back functions from recursion. But the point that I want you to get is that we're just doing a while loop bounce back and forth. Call the function, get a function back, call the function, get a function back, that sort of thing.

[00:02:15]
And it can go forever. Because the stack frame never runs out, the heap never runs out, and it only ever executes one function at a time. It's an interesting and unique sort of trick to the tail call problem. The way we solve the tail call problem is to just never have a stack in the first place.

[00:02:34]
So what does it look like to use this trampoline utility? Notice that I've got a countVowels that from the most prospective, countVowels looks exactly like what we implemented before. I'm wrapping it in a call to trampoline like we did with memoize earlier in the course. But the only difference, line 6 looks exactly like what we expected in the tail call form.

[00:02:57]
The only difference is that line 5 wraps up line 6 in a function and returns it. That's the only intrusion that we have to do. Line 4 still looks normal. Line 3 still looks normal. Line 6 looks normal. The only difference to use trampoline is you have to take any call that would have been recursive and wrap it in a function and return it.

[00:03:20]
And that's how you opt into this whole trampolining thing.
>> Kyle Simpson: And that function that we're creating, the function f on line 5, the way that function works is because it has closure over the stuff that it needed. So temporarily, for a brief microsecond, holds on to those values so that they can be returned back to the trampolining utility, popping the call stack, and then immediately re-invokes that and starts over.

[00:03:49]
So we're taking advantage of the place that we store our information is in the return value of our stack frame which then pops the stack frame off.
>> Kyle Simpson: That's how trampolining works. And the reason I want you to start writing this form of recursion is because this form of recursion will be very easy for you and,, or a tool to automatically convert to real tail-call form at some later time, if we get to the point where tail calls are reliable and cross JavaScript.

[00:04:18]
If you use a trampolining like this, all a tool would have to do is know that you use trampolining everywhere and go find those places like line 5 and 7 and just take them out. And then take out the wrapping around the trampoline thing that's easily automatable by tools.

[00:04:35]
So we can write something that is in tail call form, have a small little intrusion on it and then automatically remove that at some point if we ever get to the point where tail calls are supported by the language. And if not, then our trampolining just keeps working and we get most all of the declarative benefit out of the recursion technique here.

[00:04:55]
Even though this code is a bit more complex than where we started it's still significantly more declarative than what we did with the iterative for loop version.
>> Kyle Simpson: This is my current state of the art, if you will. This is how I do recursion in my programs, is I write a tail call form and wrap it in a trampoline.

[00:05:18]
But just like everything else I've taught you, you're not gonna get to be comfortable with this sort of topic unless you start to try to practice it. So retry the exercises, try the stuff on your own code. Look for places that you're doing things iteratively and ask is there a way I could do that recursively?

[00:05:33]
Could I use a trampoline here and do it recursively?