Why Are Continuations So Darn Cool?
Jun 05, 2014
Meet your programming language's time machine.
Continuations are the least understood of all control-flow constructs. This lack of understanding (or awareness) is unfortunate, given that continuations permit the programmer to implement powerful language features and algorithms.
– Matt Might, in Continuations By Example
The usual way to control the flow of execution of a computer program is via procedure calls and returns; a stack data structure is how high-level programming languages keep track of the point to which each active subroutine should return control when it finishes executing.
Unfortunately, you’ll need more than that if you intend to write useful
programs to solve real-world problems. That’s why most high-level programming
languages also provide other control-flow primitives, like the
statement, loops, and exception handling.
I’m not saying that implementing a programming language is an easy task, but putting that aside for a moment, it’s like programming languages in general fight as hard as they can to make the call stack something as hidden and intangible as possible - something no one but itself are allowed to control.
What would happen if some programming languages, instead of keeping the call stack inside a 2” solid steel safe, actually gave the programmers the ability to “capture” them as functions that can be invoked, stored, and passed around as values?
In this post, I hope to show you what continuations are and how they can be used in practical situations. So grab Racket and let’s go!
Update (Jun 20, 2014): I’ve changed some things in this post in response to some great comments in this Reddit discussion and this blog post by jecxjo.
Note: The following problem is solvable without continuations, but I’d like to start with something simple enough.
Suppose you are writing code that interfaces with some API over HTTP. Also
suppose this API requires a
SessionId header to be sent over with the request
in order to avoid
When the first request is sent - without the
SessionId header - the server
responds with an error, i.e. HTTP 409, in which case the procedure updates
session with the session id given by the server and retries the request.
The code makes sense, but it’s broken.
The recursive call is not made in tail position. So, when it happens, another stack frame is pushed to the call stack and even though the retried request succeeds, what gets returned to the caller is the response to that first unauthorized request.
If only we had the chance to return that second response right to the caller instead of having the stack to unwind itself…
A continuation can be viewed as the evaluation context surrounding an expression or, in other words, a snapshot of the current control state of the program.
Here’s an example:
It turns out that, if we rename
return, this is exactly the thing
we need in order to fix that broken API client example:
Now the function captures the current continuation at the moment the procedure
perform-request! is first called. Then, if the server denies a request, we
re-send the request with the given
SessionId and use that grabbed continuation
to transfer the control back to the caller.
Nice, don’t you think? It’s like we’re freezing time at
let/cc, doing some
stuff, and then resuming from there.
This is a common use case of continuations. Check out this project if you want to read the code that inspired this example.
Generators can be viewed as special routines that behave like iterators. If you are familiar with Python, you’ve probably seen code like this one:
Do you see any resemblance between this example and the previous one? Although
Python doesn’t provide a
call/cc-like facility in the language, one can argue
that its generators are like a poor man’s continuation.
Let’s pretend for a moment that Racket didn’t have a generator library that does exactly this. How could this be implemented Racket using continuations?
What we need is a function that returns another function which, when called, yields one item at a time, until the list is exhausted.
This code follows the same pattern as the previous ones, but it doesn’t seem
to work the way you might expect. The reason should be clear though:
returns a lambda that uses the captured continuation to yield the list’s first
To make this code work, we need to capture the current continuation from the
for-each and store it so it can be used to resume the computation
next is called again.
If you are having trouble understanding how this code works, the following diagram might help.
Moving along to more high level stuff, in this example Matthew Flatt explains how to build a continuation-based web server in Racket. Still in the realm of continuation-based-web-something, if you are into Smalltalk, don’t forget to check Seaside, a web application framework that uses continuations to model multiple independent flows between different components.
If you don’t code Scheme or Smalltalk for a living, don’t worry. The chances are your language does support some flavor of continuations, either natively or via some third-party library.
It seems that continuations can be used to implement a wide variety of advanced control constructs including non-local exits, exception handling, backtracking, and coroutines.
In this post, I hope to have clarified some of the key aspects about continuations. If you have any suggestion on how to improve this text, please let me know.Share