CPS & Trampolines Q&A

[00:00:00]
>> Speaker 1: So CPS is some sort of memorization where we're trying to call Const V?
>> Kyle Simpson: If I go back to CPS for just a moment, I'll go back a couple of slides. In CPS the trick is that what we're doing is, instead of actually making the recursive call, doing the work now.

[00:00:21]
We're deferring the work by wrapping it up in a function and passing that function forward. So none of that work is actually happening. You know how earlier we talked about do the work now and pass it along in a variable as an argument? Here, we're saying, don't do work now but pass along the function which will do the work later.

[00:00:42]
And then that one passes along another function which we do their work later. So that cont variable becomes a bigger and bigger and bigger wrapped function. None of the inner functions have ever been called yet, but it's a bigger and bigger and bigger wrap function all of which are actually in tail call form.

[00:00:57]
It's all a bunch of return return return return return. None of the work has been done, but we have made a bigger and bigger function with all that stuff closed over. And then at the very last thing, which is what happens on line five, there's our base condition.

[00:01:10]
We say, hey big giant wrapped huge function, collapse yourself down into one value. That's what line five does, it calls that giant function which [SOUND] computes all those values.
>> Speaker 1: Why have tools to translate code to CPS if we still have the memory issues?
>> Kyle Simpson: Well we get around the stack issue and they have other ways of dealing with the heap allocation issue.

[00:01:37]
This is specifically, my comments were specifically about JavaScript, which is that JavaScript is getting around a stack problem but creating a heap problem. CPS is actually how languages like compilers in C deal with recursion in an optimized form. They don't necessarily rewrite it in to a tail call form, they will rewrite it in to a CPS form.

[00:01:58]
And that's what the C compiler does automatically for them. So they have other techniques for dealing with the memory allocation problem there. But for us the problem is, because they're not dealing with closure there, like we are. They're doing in a different way. We're dealing with closure, which is allocation off of the heap.

[00:02:13]
So we have a memory problem that we have to deal with.
>> Speaker 1: What are good trampoline libraries?
>> Kyle Simpson: You don't need a Trampoline library. Trampoline is a utility that will be provided to you by your favorite functional programming library. Aramda has one, Low Dash has one. Almost all the functional libraries will have that utility that you just pass it in.

[00:02:32]
Then they have slightly different quirks for how they work, so read the documentation. But, they basically all provide this because it is generally one of the accepted or preferred forms for doing recursion when you can't take advantage of tail call.
>> Speaker 1: And can you summarize the difference between trampoline and regular recursion?

[00:02:55]
>> Kyle Simpson: Yes. The difference between a trampoline call like what we see here and regular recursion is that in regular recursion we stack up the work. We literally stack up the work. We say you do some work, and then you do some work, and you do some work, and you do some work, and you do some work, and that's growing our memory size.

[00:03:11]
In a trampoline we never stack up the work. We do some work here. And then we return work back to this helper, this utility called trampoline, by way of returning the function. That's what we're doing on line 5, we return a function. And then the trampoline says you returned me a function, I need to do that work.

[00:03:29]
And then we return some more work, and then we do it. And so we're bouncing up and down between a stack depth of zero and a stack depth of one, over, and over, and over again. We're not stacking up. And that's the difference, that's how we avoid that range error.

[00:03:44]
So just as by way of one final comparison let's put the two implementations of countVowels next to each other. I just want you to see that it's not actually all that scary. Writing a trampolinable recursive function versus a non trampolinable version. In the first version up on top, we have a function countVowels, which is tail call form.

[00:04:07]
And then in the version on the bottom we have a trampolined version of it. And if you notice, line 4 on top and line 2 on the bottom, they are the same line. Line 5 on top and line 3 on the bottom they are the same line. Line 6 on top and line 5 on the bottom they are the same line.

[00:04:26]
>> Kyle Simpson: So those are exactly the same pattern you can write a tail call form function and then all you have to do is insert that wrapper function line 4 and line 6 there at the bottom. Insert the wrapper function to return that work and pass it to a trampoline.