This course has been updated! We now recommend you take the Functional-Light JavaScript, v3 course.
Transcript from the "Continuation Passing Style" Lesson
[00:00:00]
>> Kyle Simpson: We talked about PTC as a form to modify an existing recursive algorithm and take advantage of the PTC optimization, or whatever you wanna call it, that behavior that would be built into the browser. And we said, well, it's kind of an unfortunate reality that not all the browsers have it yet.
[00:00:23] So, there's a different way of approaching our algorithm when it's difficult to arrange it in the PTC form directly, the way we were talking about. And this form is called CPS, which stands for continuation-passing style. So, sometimes your algorithm will be such that, like for example, if you need to make two recursive calls, like a binary descent, well, two recursive calls that need to happen in the same function, there's no way to have both of them be at the end.
[00:00:57] So, it kind of leaves you in this difficult position where you can't refactor to the PTC form. And in those cases, sometimes CPS, continuation-passing style, can be an approach to that. We're not gonna dig a lot into this, but I just wanna briefly show you how CPS could work for our example.
[00:01:19] What I'm doing here with the sumRecur function, I'm still returning that function on line 4. And this is, because this is definitely going to have a signature that's inconvenient now. So, we need to go back to hiding it. But my inner recursive function, you'll notice that my first position is an array, and that array is gonna get shortened down.
[00:01:42] So, what I immediately do is say, I'm gonna put all of my numbers onto my memory stack, but you'll notice that the second argument is labeled cont, which stands for continuation. That's always gonna be a function, and I started out there on line 5 as, there's a special term for a function that returns whatever value is passed to it.
[00:02:05] That's just I was saving space on the slides to do it in the arrow form, but that's the identity function, that's a special term for a function that just returns whatever you give to it. So, that's the initial value for this continuation that I pass in. Now, when I call my base condition on line 10, if I am in the base condition you'll notice I don't just return the sum I return the result of calling the continuation function with that sum.
[00:02:34] So, if I was in the very first call, that is I passed in only one number, then that would be calling the identity function with whatever I passed in, and just passing back the value directly. But if I was deeper into my stack of recursion, then I would just be passing sum into some function that had been passed to me, that had been passed to me, that had been passed.
[00:02:57] So, what does that non-base case look like? You notice again, instead of calling sum plus recur, I call recur with my list of nums, that's my running array list if you will, but my last position there is a function. It's another continuation, a continuation that takes a v and calls whatever the current continuation is with that plus the sum.
[00:03:26] So, I know it can be really hard to like unwind with all that's happening. But just to give you sort of a visual instinct of what's occurring, we're essentially wrapping up the stuff that would happen after the recursive call in a function and passing that along. So, in the previous one when we did PTC, we calculated the partial sum and passed it along.
[00:03:48] Here we're actually like calculating the next set of steps to do and passing that along. We're wrapping it up in a function and passing it along. So, we pass that function along, and then we pass another function along and another function along. And at the very end, whenever we're done with the base condition and we call line 10, we're gonna fire off that function, and it's gonna call all the functions in that super nested call step.
[00:04:15] And all of them are in PTC form, cuz as you see they're on line 11, they've all been positioned as PTC. So, as long as PTC is in effect, even if that ends up resulting in a million function calls all happening all at once. There won't be any stack growth there.
[00:04:33] We'll just make all of those calls in fixed memory, and then be done. So, the purpose again of the CPS is if I have some stuff that I need to do after my recursive call, like, for example, make another recursive call, or whatever. I can take that code and instead of doing it later wrap it up in a closure, wrap it up in a continuation, and pass it along and do that work later.
[00:04:58] Defer that work until later and later, and later. And then, at the very end, do all of those partial sets of work. So, that's a strategy for doing more complex things, and by the way, in the case where we talked about. You obviously don't need to do it when you're summing up a list of numbers, this would be a much harder way.
[00:05:16] But, if we were talking, for example, about that traversing a binary list thing, you could actually have a continuation of a continuation. You end up doing inside on line 12 you would be creating another continuation for the second part in passing it along. It gets kind of hairy, but you can diagram all this out and say, well, that's a function that calls that, that calls that, and then just at the very end you know the base case just sort of fires off all those calls and does all that work.
[00:05:44] So, CPS is a form, it's definitely more advanced technique. It takes a lot of practice, but it's a form that you can express even more advanced versions of recursion still in PTC form. By the way, some, not in JavaScript, but in some systems, there are either pre-processors, or the compiler itself is able to take a piece of code that is written in this, that is written in a way that is minimal to this.
[00:06:13] And automatically rewrite that code for you. I'm optimistic that maybe eventually we get a tool where somebody can take your recursive function and rewrite it into this PTC form much like what Bable does to transform your code, I'm optimistic that at some point it might require you to be using something like typescript, or I don't know.
[00:06:31] But it'd be really nice if somebody could make one of those tools for JavaScript the way they exist in some other languages, that way we don't have to write all this ugliness. We could just give it our recursive function, and it would figure out how to wrap it all up in those continuations.
[00:06:48] Any questions about CPS?
>> Kyle Simpson: Now, what about this case where we're stuck in the future where [LAUGH] we don't get PTC, or we don't have PTC, or we need to run it in browser that doesn't yet support PTC. Are we just lost? Is there no way to deal with some kind of recurs of algorithms.