This course has been updated! We now recommend you take the Functional-Light JavaScript, v3 course.
Transcript from the "Trampolines" Lesson
[00:00:00]
>> Kyle Simpson: There's one final technique we can look at and that's called trampolines. And trampolines are a mechanism that allows us to do the same kind of work but do not require that growing call stack. And, therefore, end around the whole problem. We don't even need PTC, because they don't ever do it that way.
[00:00:17] There's an adapter that you can put on top of a function. And what is said is that you're trampolining that function. So I don't know where this name comes from. And I wish I had a good, concrete metaphor for this. I could invent some stuff, but I don't really have a good metaphor for it.
[00:00:34] So I'm not really sure why this is the right name or how to give you an instinct of the name. But let me just describe the general algorithm. When I call a function, if I am done calling the function, if I've completed all the work, I'm gonna return the immediate result.
[00:00:52] If I'm not done, I'm gonna return a continuation function just like we talked about. So I'm gonna return the continuation function. And the trampoline utility, it's gonna look at the return value. And if it gets back a function, it's going to assume that was a continuation function, and then call it.
[00:01:11] And it's just gonna keep looping. It's gonna call it and if it gets a function back, call it again, and if it gets one back, call it again. That's not call, call, call, that's call, call, call. So we never have more than one call on the call stack at any given length.
[00:01:28] We return it back, and there's just a while loop that spins forever as long as it gets back a function on the next iteration it calls it. And then on the next iteration, it calls it until it no longer gets a function. And then it says I guess it's time to get off the trampoline.
[00:01:44] So that's a technique for getting around our limitations if we don't have PTC. So it would look like this. So if we had a trampoline utility, we would call trampoline and pass in our PTC form function. You'll notice that on line 2 I don't need that weird signature.
[00:02:07] But I do still return my continuation like on line 5. I don't return the sum, I return a continuation that will compute the next sum. So I just return that, and the trampoline utility, which I'll show in the next slide, when it receives that function, it will just call it again.
[00:02:24] Which of course calls and calls and calls until we get back something that's not a function. What I like about this technique is that it's still pretty close to the recursive representation that we started with 15 slides ago. It's not perfect, there is some boilerplate, but it's nice that we can wrap up the utility of trampolining into a call.
[00:02:51] And the only real downside here is that we had to put a function wrapper lines 5 through 7. We had to put a function wrapper around the recursive bit. But other than that, it's exactly the same expression as what we were doing before. And it completely gets around the whole PTC thing.
[00:03:09] On multiple occasions, I have found that to be an easier and more straightforward way of dealing with this algorithm that I need to run recursively.
>> Kyle Simpson: Because I can just express the second and third steps in continuations as I need. So here's how the trampoline utility is written.
[00:03:31] This is just a sketch of a utility, there are more sophisticated ones in libraries. But this is a sketch of how you could make a trampoline utility. You notice, just like we've done 1,000 times already in this course, it's a machine making machine. It returns us back a function on line 2.
[00:03:47] That one takes in the list of arguments. It calls the function the first time with those arguments, saving that result. And, as long as that result keeps coming back as typeof function, we're just gonna keep repeating that in the while loop. And whenever that fails, then well, if it's anything other than a function, just jump off the trampoline and return the result.
[00:04:10] It's as pretty straightforward in terms of the concept that's going on. Emphasis again, we did not have to be that intrusive to our recursive algorithm to make trampolining work. There was a little bit about adaptation, but it wasn't that difficult. Now with all of PTC, CPS, and trampolining.
[00:04:32] All three of those techniques that we just talked about. You can't possibly be expected at this point to be an expert on those, and be ready to just go do that all on your own code. This is taken me personally, weeks and months of practice. So my recommendation is to take something at work that you're doing iteratively, or take some problem that might lend itself well to recursion.
[00:04:55] And try it first, see if you can get it into the PTC form. If that proves too difficult, try the CPS. And if that proves too difficult, try the trampoline. And just practice those things a few times. And after you've done that five or ten times, you'll start to develop a sense of which one of those tools in my tool box is appropriate for any given spot.
[00:05:16] As with everything that we have taught in this course, but it is especially true here. Always have a step in that process for yourself where you take that step back and you look at the final product, the thing that gives you the right answer. And ask yourself if I'm better off here than what I started with with my for loop or whatever the previous version was.
[00:05:36] Because sometimes you'll end up in a worse position. It's harder to read, it's harder to understand. In those places, don't use these techniques. This is the pragmatism speaking. But sometimes you'll end up with a pretty good result. And that, I think, is a benefit, that's the functional light kicking in.
[00:05:54] Recursion, questions, what can I answer for you?
>> Kyle Simpson: I was tempted to restart my lecture on recursion to just keep going, but that seemed too cheesy of a joke.
>> Speaker 2: Do you have just a simple definition for recursion, or like a simple explanation like one or two sentences?
[00:06:18]
>> Kyle Simpson: Yeah, so recursion is when a function calls itself repeatedly until it reaches a base condition and it stops calling itself.
>> Kyle Simpson: That's also referred to as single recursion, because there's just a single call. There's a term called mutual recursion, when two or more functions are calling each other in a cycle.
[00:06:43] That's called mutual recursion. There's always a base condition that stops the recursion from happening. So your definition always needs to include at the end, until a base condition is met. But either a function calling itself, two or more functions calling each other. A function calling multiple functions recursively until it reaches a base condition.
[00:07:06]
>> Speaker 2: Maybe an off topic question, but in your work when do you use recursions?
>> Kyle Simpson: I try to use recursion, again, this is the pragmatist in me speaking. I try to use recursion if I've developed an instinct that there's a problem that I'm solving that either would be more gracefully expressed, more declaratively expressed with recursion.
[00:07:27] So sometimes something like the summing of a list can be more gracefully done that way, sometimes not. Or I've developed an instinct for this kind of problem that I wanna do would be a lot harder to do with a loop. Depth first descent of a binary tree, for example, is like the classic you should do that with recursion.
[00:07:50] Don't do a loop and manage all your own pointers and stuff. Cuz that's what the stack is good for. So you develop an instinct either for something where it's gonna help the visibility or recursion is just a much better tool. When I'm trying to put a screw in, I don't wanna use a hammer for that.
[00:08:05] I wanna use a screwdriver.
>> Kyle Simpson: Unfortunately the not terribly satisfying answer here is you only get that instinct from practice. There's no way to just give you a decision graph and then you're done. Y ou have to do it a while before you figure it out.