Continuation-Passing Style

[00:00:00]
>> Kyle Simpson: Because we know that proper tail calls aren't a thing that we can rely upon yet. We have to consider potentially other strategies for writing what are essentially recursive algorithms without having to rely upon that optimization of tail calls, at least in the interim. And I'm gonna present to you two of these and I'll just go ahead and tell you, the first of them, you're probably never gonna write.

[00:00:24]
But it's important for you to at least understand that this technique exists. The second one is the one that I'm gonna end up suggesting that you start doing today. Because it works now even without tail calls. And it will gracefully degrade, or I mean, it will gracefully, progressively enhance to nicer recursion if we ever get tail calls.

[00:00:44]
So the first of these is called CPS. It stands for continuation-passing style, okay? And just so you understand what a continuation is, that's essentially a call back. So if we say continuation passing, that means we're passing some sort of a callback. This is the CPS style. You'll notice that lines 4 and 5 of our function look basically the same.

[00:01:04]
On line 3, we see something a little bit different, which is we see a variable there called continue, cont for continuation. And it's defaulted to this special function which returns whatever it gets back. That special function, by the way, which I've only used the arrow function so that I can save space on the slides, okay?

[00:01:24]
I don't actually endorse the arrow function, but here, it's a nice, clean way to save space in the slides. That's called the identity function. In functional programming speak, a function that simply returns whatever is passed to it is called the identity function. And it turns out to be a really, really useful base condition for a bunch of things in functional programming.

[00:01:45]
So we're using the identity function here. And what I would usually do, rather than writing an inline function expression is I'd refer to the identity function that was provided to me by whatever functional library I was using, okay? So I'd say r.identity or whatever, and that's what I would use as my default, okay?

[00:02:02]
But you'll notice that it starts out as that function. But then when we make the next recursive call, we're gonna pass in a different inline function, the f that you see there on line 6. Look at lines 4 and 5 for a moment. Lines 4 and 5 look almost exactly the same as they did in the previous implementation.

[00:02:21]
In fact, the only difference is that on line 5, instead of returning first, I'm returning the call to the continuation callback with first passed in. That's the only difference between those two lines. So it's not very intrusive on your way of thinking about things that you need to do that.

[00:02:38]
Where it gets intrusive is line 6, because instead of calling count, I mean we are calling countVowels directly, which is nice. But instead of calling it with just a simple value or a simple number, we have to make a new function to pass in for the continuation. And that new function continuation, f there at the end of line 6, you'll notice what it does inside of it is the same thing as line 5.

[00:03:03]
It's gonna return a call to whatever continuation currently is. Cuz we're crossed over whatever cont was passed in and then we're gonna compute the work first plus b. Now, all of this is tremendously complex to like really wrap your brain around. This took me weeks to get to the point where I could even remotely talk about that coherently so if it looks confusing to you, that is entirely natural.

[00:03:29]
Almost nobody ever writes CPS. Continuation-passing style is actually what is usually converted code. Meaning you write your code in some other way in some language, and it literally converts your code to be continuation-passing style. So the fact that it looks confusing is because it's actually normally written by a machine not actually by you.

[00:03:51]
But I'm showing it to you, because I want you to understand we're gonna actually use something kind of like this in the next technique, okay? That's the only reason I'm showing you. So if it's confusing, that's entirely natural. It's not usually something that people read and write themselves anyway.

[00:04:05]
But the key to understanding what CPS is doing, it's a cheat, okay? We are definitely on line 6, making a tail call call. But we're not gonna experience the range error here, because the function call is wrapped up in another function. So we are deferring and that's not obvious yet.

[00:04:33]
But we're not actually gonna have a whole bunch of functions that have all called each other until the very, very end, okay? So we're actually deferring the real recursive call, the one that's on line 7. We're deferring that at each step by creating a bigger and bigger function.

[00:04:46]
And that's sort of cheating the range error issue. But it's not actually fixing the memory problem. Because every time we create a new function, we have to reserve a new area of memory not off the stack, but off of the heap. That's a different area of memory that is the dynamic generation of stuff that gets allocated off the heap instead of off the stack.

[00:05:08]
So we're not actually growing the stack here. But we are growing usage of the heap. Which means, if you were to run a CPS-style program, theoretically, you'd eventually exhaust the entire system of all its memory, and it would crash. And JavaScript does not have any error in check for you exhausting the heap.

[00:05:27]
It only has an error check in place for you exhausting the stack. So the bottom line here is that CPS is not really the solution that we want in JavaScript. Because it cheats to get around one error and creates another probably worse situation, okay? But it's an interesting trick.

[00:05:47]
This is something that computer scientists have studied, and have figured these things out. And I'm sure there's a mathematical principle that allowed them to figure out if we'd defer it with a wrapped function, and that gets around this problem, or whatever.