Understanding Continuations

In this tutorial I would like to talk all about continuations, to attempt to demystify this rather simple concept somewhat. For it's not so much that continuations are difficult, but that the ways in which they're used can get complex pretty fast.

In essence, a continuation is a function which represents the next block of code to be executed. Take this code for example:

main = do
    putStrLn "alpha"
    putStrLn "beta"
    putStrLn "gamma"

It may not look it, but this code uses continuations! In order to see them, let's desugar that do-notation. You can click on the Run button to convince yourself that this code has the same behavior:

main = putStrLn "alpha"
       >>= \_ ->
           putStrLn "beta"
           >>= \_ ->
               putStrLn "gamma"

As you can see, each expression, such as putStrLn "alpha" is bound to a continuation function that "continues" the execution of main in an explicit series. Thus, any language which allows for sequential statements uses implicit continuations. It just happens that the continuation always means "the rest of the code".

Let's give our continuation functions explicit names, just for fun:

main = putStrLn "alpha"            -- main
       >>= \_ ->                   -- k
           putStrLn "beta"
           >>= \_ ->               -- j
               putStrLn "gamma"

We can now read this code as follows: main evaluates the expression putStrLn "alpha", then takes the result of that evaluation and calls the function k, which in turn calls the function j, which implicitly calls a function we might call exit.

So far this isn't very useful. But what if we could truly name our continuation function, and even call them whenever and wherever we wanted?

Named continuations

In order to name continuations, we must operate within a special monad called Cont. We'll actually use the transformer variety, called ContT, so that we can do some IO at the same time. Here is our main function, moved into ContT:

import Control.Monad.Trans.Class
import Control.Monad.Trans.Cont

main = flip runContT return $ do
    lift $ putStrLn "alpha"
    lift $ putStrLn "beta"          -- k
    lift $ putStrLn "gamma"         -- j

The flip runContT return prolog just means that we're entering the ContT monad transformer, demarcating a kind of "scope" within which named continuation functions may be called. Once we exit the ContT block, it is not possible the invoke our named continuations again.

Within ContT, we use the function callCC ("call with current continuation"), to name the "current" continuation: the continuation which now follows immediately after the call to callCC itself:

import Control.Monad.Trans.Class
import Control.Monad.Trans.Cont

main = flip runContT return $ do
    lift $ putStrLn "alpha"
    callCC $ \k -> do
      k ()
    lift $ putStrLn "beta"          -- k
    lift $ putStrLn "gamma"         -- j

Nothing special happening here. We inject a call to callCC, capture the current continuation as a function value, and then immediately call it -- just as the code would have done itself had we not interfered. In fact, all we're doing right now is making something explicit that was always there, hiding behind the mask of do-notation.

Also note that in the code above, not calling k would have had the same effect, since there is an implied call to k after the call to callCC. Our making it explicit really had no effect at all. But things can get progressively interesting from here, so let's cover each possibility in turn.

Early exits

The first useful thing to do with a continuation is to call it from someplace other than where it would get called ordinarily. For example:

import Control.Monad.Trans.Class
import Control.Monad.Trans.Cont

main = flip runContT return $ do
    lift $ putStrLn "alpha"
    callCC $ \k -> do
      k ()
      lift $ putStrLn "uh oh..."
    lift $ putStrLn "beta"          -- k
    lift $ putStrLn "gamma"         -- j

Can you guess what the output of this code will be before running it?

We can get even trickier when there is logic within the callCC block:

import Control.Monad.Trans.Class
import Control.Monad.Trans.Cont

main = flip runContT return $ do
    lift $ putStrLn "alpha"
    num <- callCC $ \k -> do
      if 42 == 7 * 6
          then k 42
          else lift $ putStrLn "uh oh..."
      return 43
    lift $ putStrLn "beta"          -- k
    lift $ putStrLn "gamma"         -- j
    lift $ print num                -- l

Coming back again

But wait, there's more. I never said that the continuation function could only be called once, or that it had to be called within the callCC block! Check this out:

import Control.Monad.Trans.Class
import Control.Monad.Trans.Cont

main = flip runContT return $ do
    lift $ putStrLn "alpha"
    (k, num) <- callCC $ \k -> let f x = k (f, x)
                               in return (f, 0)
    lift $ putStrLn "beta"          -- k
    lift $ putStrLn "gamma"         -- j
    if num < 5
        then k (num + 1) >> return ()
        else lift $ print num       -- l

You may want to spend some time with this example, to get comfortable with what's happening here. The lazily recursive magic inside the callCC block is saying the following: We want to return from callCC a function which, when called with a number, will invoke the current continuation and return that same function along with the given number. So basically, this code packages up the continuation in a nicely callable form.

As an exercise, try finding a way to hand back k directly, without wrapping it up in the helper function f. You'll run into problems with infinitely recursive types. But why is that? Read the definition of f more closely to find your answer. (As a bonus: The trick we're using here is called "tying the knot", and allows us to deal with just these sorts of recursive expressions).

Conclusion

Let's cover what we've learned so far:

Any code which represents sequential "statements" uses implied continuations.
callCC within the Cont (or ContT) monad allows us to name these continuations.
We can call a named continuation at any time to jump to that point in the code.
We can invoke continuations as many times as we like, with different arguments.

Using only what we've learned so far, it should be possible to implement:

pretty much any iterative control construct from your favorite imperative language.
exception handling (hint: the "try" block is just a callCC, with the continuation pointing at the "catch" block following just after it, and "throw" is just calling the continuation function with an exception value. But how do you make the continuation function known to the code that does the throw?).
goto! or setjmp and longjmp.
green threads (hint: when you "sleep" to transfer control to another thread, you are really invoking callCC, calling the continuation with a "not now" argument, returning that continuation function to the scheduler, which then later calls it with an "ok now" argument that allows the thread to resume executing).

Next up, delimited continuations, which let us get even fancier!

Sections

Named continuations

Early exits

Coming back again

Conclusion