What is a continuation?

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.

Transcript

Eric Normand: 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.

You just thread that k through there, and you have this style of programming is called continuation passing style. Now, this is not a pleasant style to write code in, but your compiler can turn your straight-line, imperative, "Do this, do this, do this, call that," nested function calls, you can do all that.

Turn that into continuation passing style, and then it has this really nice property, that you don't need a stack. It has other properties. For instance, because it's a function, and functions are first-class, you can save it somewhere. Just know about that. We'll talk about it in a second.

I don't know if this rings a bell to you, but if you're a JavaScript programmer, you're often calling a function that has a callback. That callback is going to get called with the result of that asynchronous function.

If you do Ajax, the response to your Ajax request is going to get passed to a function sometime in the future. What typically happens is you have, "This Ajax needs this callback, and then that callback makes another Ajax request, and so it has another callback. That one makes another one, and it has another callback..."

You have this deeply-nested callback chain. That is just continuation passing style. It's one of the reasons why I say that JavaScript is one of the best things to happen to functional programming in a long time.

People are doing continuation passing style without even knowing it. They just picked it up, because they had to. This thing that was this arcane, functional programming style idea from compiler theory is now a thing [laughs] that people are writing their code in.

They know it's not very ergonomic. It forces you to break up your program to the right, so you're deeply nested. It's hard to coordinate things. It'd be much better to write it straight up and down, but they're learning it.

They understand its limitations. They understand how to sequence things by calling the next continuation, the next continuation. Just as an aside, the new stuff in JavaScript called async/await. I say new, relatively new.

It lets you write straight-line code, but you put await in there in front of something that would be asynchronous, and it just waits. It looks like it waits. Really, internally, the compiler is turning that into a continuation passing style, or in the JavaScript world, called a callback chain style. I don't know what they call it. It's callbacks in JavaScript.

It looks straight up and down, straight line, like, "I can do this. Then I do this step, then I do this step, and I wait for this step. Then I do this step. I wait for this step." Putting those awaits in there, it'll get turned into continuation passing style. It's an ergonomics issue. It doesn't really add any functionality, but it's a really nice bit of ergonomics.

All right, back to the main thing. What are these useful for? Oh, that's what I said in the beginning, like why you might be using them already. If you're doing JavaScript, you're already doing continuations. What are these useful for?

Notice, we've gotten rid of the stack. That's nice. We don't have this problem of stack overflow anymore. The Scheme folks, the people who invented Scheme, published a lot of papers about how the function call, before Scheme, was actually a very heavyweight thing.

You wouldn't want little, bitty functions, because it would eat into your performance. You'd make big functions, with 20, 30 lines of code in them. You do a whole bunch of stuff in them. Then, just for convenience, for programmer convenience, you'd have another function you would call that would do this common routine.

You wouldn't treat them like, they were too heavyweight to say, "I'm just naming this one operation with a new name, and I'll wrap it in a new function." It was too heavyweight for that. What they showed was that function calls are very lightweight.

That, especially if you do this continuation passing style, you can make it just like go-to. You don't even need to return anymore. You're just passing a few arguments on the stack, the same stack frame you had before, and you're doing a jump.

You don't even have to remember where you were, although you do. It's part of the Clojure of the continuation, if you're curious. Because it's a function, that was function was built in a certain environment. It has certain state.

Anyway, it just showed that function calls could be super, super efficient, just about as efficient as a go-to. You could use them wherever you wanted, and they were a good compiler technique. What can you do with them, besides make nice compilers?

One thing is, just like in the JavaScript world when you have callbacks, is you can add asynchrony in there. I could, instead of calling k, my function could put k on a queue to be called later. That's what JavaScript does.

It's not done directly. There's some other, like the networking engine, if you're doing Ajax. The Ajax happens, and it gets put on a queue when it's done as an event. There's an event loop. There's a lot of machinery there.

In essence, what you're doing is you're putting the continuation onto the queue. Because things are round robin, and they're taking turns, you're able to share a processor between multiple timelines, even though there's only really one thread.

These are often called co-routines. Another thing that you can do with continuations is the same kind of stuff you might do with stack manipulation in function calls. For instance, you could implement exceptions.

You could have exception handling, where the continuation is wrapped in something that will do a finally or do a catch on an exception being thrown. Then it's going to continue after the try-catch block was finished.

Anything that you would do, typically think would require a language-level implementation, if you've got access to those continuations, you can do a lot of stuff. That's how Scheme manages to do so much language-level stuff, but in the language itself.

All right, so, let's recap. Continuations are a way of representing the rest of the calculation. After I return from this function, what else do I need to do? They are wrapped up in a function, and the argument is the return value of the thing that you're calling.

There's a style called continuation passing style, where you replace all return values with calls to the continuation, to the next continuation. If you do this, you don't need a stack. The stack is implicit in those function calls.

You can also use continuations as a means of inserting some indirection. Instead of actually calling the continuation, you could put the continuation onto a queue. You could hand it to something that monitors it or something, makes sure it succeeds, it completes correctly. Maybe it'll retry it, something like that.

Anything you can do with a function, boom, now, you've got that continuation as a function. You can implement exception handling, things like that.

All right, so, if you found this episode useful, you can find all the past episodes at lispcast.com/podcast. There, you'll find audio, video, and text versions of all of the past episodes. You'll also find links to subscribe to the podcast, and also find me on social media.

Social being the keyword. I've got email, Twitter, LinkedIn. I love to get into discussions with people, so please reach out. This has been my thought on functional programming. My name is Eric Normand. Thank you for listening, and rock on.