Continuations are a cool feature you often find in functional languages. In this episode, we look at what they are, why you're probably already using them, and the cool things you can do with them.

►► Audio, Video, and Transcript available: [ Ссылка ]
►► Subscribe on iTunes: [ Ссылка ]

Transcript

What is a continuation? By the end of this episode, we will have gone over this concept. You will understand it. You will see why you're likely already using continuations, even if you don't know it yet, and what you can do with continuations.

Hello, my name is Eric Normand, and I help people thrive with Functional Programming.

Continuations became important in scheme. They were used as part of the compiler as a...continuations were used as a compiler implementation technique. We will go over a little bit how that's done.

What is a continuation? That is the main part of this episode. Continuations have to do with how functions are called and then returned.

Imagine a typical scenario -- you have Function A which does some work, calls Function B, and then does some more work with the return value from B. When Function A calls B, what actually has to happen?

You're passing control to another function, you're going to push onto the stack a new stack frame and record in that stack frame where to return to. After you do a jump, a go-to, to run that function, where does the return statement take you back?

You have to write that down as a pointer, just write it down. You also have to write down all the arguments into the stack. Then, when you jump to the Function B, it knows where to look up the arguments and then it also knows where to return when it's done.

That's how the function calls work and the stack works. Notice we pushed this pointer onto the stack along with the arguments, but what if we made it an argument? What if we made that pointer an argument, instead of something to check when you are about to return?

Instead of a pointer, what if we made it into a function that you could call? Basically, you do x equals b, and then you have some more code. You're saving the return value of b. I said b, and I did parentheses with my fingers. It's x equals call b, so b().

You have the return value of b stored in x. After b returns, it's going to get saved to x, and then you're going to do some more stuff. What if you made a function that was just that, some more stuff? Also, assigns that stuff to x, the return value to x.

This is a function you've packaged up. Instead of a pointer to jump there, you just make it into a function. You pass that to b. Now, b, instead of calling return, could just call the function that's an argument.

In Scheme, it's called k. It's the continuation. Just imagine you add an argument to your function b. It's called k. Then at the end of the function, when it's done, it calls k. That does the continuation of what a was doing.

Now, typically, when you return, you're returning a value. That value is useful. To get that value that's returned from b, you make it an argument to k. k is a function of one argument, and b will just call that with whatever value it would have returned.

Now, imagine you did this with every function. Every function, you added an argument called k -- that was the continuation -- and it was one argument. Instead of having a return statement, you just called k. Of course, because it's a return statement, it's the last thing your function will ever do before it's over.

That means that it's always in tail position. We talked about that in a previous episode. There's a tail call removal, where, if you're in tail position, meaning it's the last call, the last call of a function call of the function -- a function that's made out of other function calls -- The last function call before you return, that's called the tail position.

Because you've threaded this k through every function call -- this is a different k each time -- you've turned your program inside-out and nested it to the right, instead of going straight down, every function call is in tail position.

Which means that every function call can be optimized into a go-to, and you never have to return. You don't have to return, because there's no return statements used anymore. They're just always calling k, the next thing, the next thing, and the next thing.

You don't need a stack anymore, because the stack's main job is to keep track of where to go back, how to return. You're not returning, so you don't need a stack. You need one frame to store the current arguments.

свернуть