Haskell/Continuation passing style

Template:Haskell minitoc

Continuation passing style, or CPS, is a style of programming where functions never return values, but instead take an extra parameter which they give their result to — this extra parameter represents what to do next, and is called a continuation.

Starting simple

To begin with, we're going to explore two simple examples which illustrate what CPS and continuations are.

square

Let's start with a very simple module which squares a number, then outputs it:

We're clearly doing two things here. First, we square four, then we print the result. If we were to make the square function take a continuation, we'd end up with something like the following:

That is, square takes an extra parameter which is the function that represents what to do next — the continuation of the computation.

quadRoots

Consider the quadratic equation. Recall that for the equation $a{x}^2+bx+c=0$, the quadratic equation states that:

$x=\frac{-b}{2a}\pm \frac{\sqrt{b^2-4ac}}{2a}$

When considering only real numbers, we may have zero, one, or two roots. The quantity under the radical, $d\equiv b^2-4ac$ is known as the discriminant. When $d<0$, there are no (real) roots; when $d=0$ we have one real root; and finally, with $d>0$, we have two real roots. We then write a Haskell function to compute the roots of a quadratic as follows:

To use this function, we need to pattern match on the result, for instance:

To write this in continuation passing style, we will begin by modifying the quadRoots function. It will now take three additional parameters: functions that will be called with the resulting number of roots.

One may notice that the body of quadRoots' is identical to quadRoots, except that we've substituted arbitrary functions for the constructors of Roots. Indeed, quadRoots may be rewritten to use quadRoots', by passing the constructors for Roots. Now we no longer need to pattern match on the result, we just pass in the expressions from the case matches.

Using the Cont monad

By now, you should be used to the pattern that whenever we find a pattern we like (here the pattern is using continuations), but it makes our code a little ugly, we use a monad to encapsulate the 'plumbing'. Indeed, there is a monad for modelling computations which use CPS.

Removing the newtype and record cruft, we obtain that Cont r a expands to (a -> r) -> r. So how does this fit with our idea of continuations we presented above? Well, remember that a function in CPS basically took an extra parameter which represented 'what to do next'. So, here, the type of Cont r a expands to be an extra function (the continuation), which is a function from things of type a (what the result of the function would have been, if we were returning it normally instead of throwing it into the continuation), to things of type r, which becomes the final result type of our function.

All of that was a little vague and abstract so let's crack out an example.

If we expand the type of square, we obtain that square :: Int -> (Int -> r) -> r, which is precisely what we had before we introduced Cont into the picture. So we can see that type Cont r a expands into a type which fits our notion of a continuation, as defined above. Every function that returns a Cont-value actually takes an extra parameter, which is the continuation. Using return simply throws its argument into the continuation.

How does the Cont implementation of (>>=) work, then? It's easiest to see it at work:

The Monad instance for (Cont r) is given below:

instance Monad (Cont r) where
  return n = Cont (\k -> k n)
  m >>= f  = Cont (\k -> runCont m (\a -> runCont (f a) k))

So return n is Cont-value that throws n straight away into whatever continuation it is applied to. m >>= f is a Cont-value that runs m with the continuation \a -> f a k, which receives the result of m, then applies it to f to get another Cont-value. This is then called with the continuation we got at the top level; in essence m >>= f is a Cont-value that takes the result from m, applies it to f, then throws that into the continuation.

callCC

By now you should be fairly confident using the basic notions of continuations and Cont, so we're going to skip ahead to the next big concept in continuation-land. This is a function called callCC, which is short for 'call with current continuation'. We'll start with an easy example.

We pass a function to callCC that accepts one parameter that is in turn a function. This function (k in our example) is our tangible continuation: we can see here we're throwing a value (in this case, n ^ 2) into our continuation. We can see that the callCC version is equivalent to the return version stated above because we stated that return n is just a Cont-value that throws n into whatever continuation that it is given. Here, we use callCC to bring the continuation 'into scope', and immediately throw a value into it, just like using return.

However, these versions look remarkably similar, so why should we bother using callCC at all? The power lies in that we now have precise control of exactly when we call our continuation, and with what values. Let's explore some of the surprising power that gives us.

Deciding when to use k

We mentioned above that the point of using callCC in the first place was that it gave us extra power over what we threw into our continuation, and when. The following example shows how we might want to use this extra flexibility.

foo is a slightly pathological function that computes the square of its input and adds three; if the result of this computation is greater than 20, then we return from the function immediately, throwing the String value "over twenty" into the continuation that is passed to foo. If not, then we subtract four from our previous computation, show it, and throw it into the computation. If you're used to imperative languages, you can think of k like the 'return' statement that immediately exits the function. Of course, the advantages of an expressive language like Haskell are that k is just an ordinary first-class function, so you can pass it to other functions like when, or store it in a Reader, etc.

Naturally, you can embed calls to callCC within do-blocks:

When you call k with a value, the entire callCC call takes that value. In other words, k is a bit like a 'goto' statement in other languages: when we call k in our example, it pops the execution out to where you first called callCC, the msg <- callCC $ ... line. No more of the argument to callCC (the inner do-block) is executed. Hence the following example contains a useless line:

bar will always return 5, and never 25, because we pop out of bar before getting to the return 25 line.

A note on typing

Why do we exit using return rather than k the second time within the foo example? It's to do with types. Firstly, we need to think about the type of k. We mentioned that we can throw something into k, and nothing after that call will get run (unless k is run conditionally, like when wrapped in a when). So the return type of k doesn't matter; we can never do anything with the result of running k. We say, therefore, that the type of k is:

k :: a -> Cont r b

We universally quantify the return type of k. This is possible for the aforementioned reasons, and the reason it's advantageous is that we can do whatever we want with the result of k. In our above code, we use it as part of a when construct:

when :: Monad m => Bool -> m () -> m ()

As soon as the compiler sees k being used in this when, it infers that we want a () result type for k . So the final expression in that inner do-block has type Cont r () too. This is the crux of our problem. There are two possible execution routes: either the condition for the when succeeds, in which case the do-block returns something of type Cont r String. (The call to k makes the entire do-block have a type of Cont r t, where t is the type of the argument given to k. Note that this is different from the return type of k itself, which is just the return type of the expression involving the call to k, not the entire do-block.) If the condition fails, execution pases on and the do-block returns something of type Cont r (). This is a type mismatch.

If you didn't follow any of that, just make sure you use return at the end of a do-block inside a call to callCC, not k.

The type of callCC

We've deliberately broken a trend here: normally when we've introduced a function, we've given its type straight away, but in this case we haven't. The reason is simple: the type is rather horrendously complex, and it doesn't immediately give insight into what the function does, or how it works. Nevertheless, you should be familiar with it, so now you've hopefully understood the function itself, here's it's type:

callCC :: ((a -> Cont r b) -> Cont r a) -> Cont r a

This seems like a really weird type to begin with, so let's use a contrived example.

callCC $ \k -> k 5

You pass a function to callCC. This in turn takes a parameter, k, which is another function. k, as we remarked above, has the type:

k :: a -> Cont r b

The entire argument to callCC, then, is a function that takes something of the above type and returns Cont r t, where t is whatever the type of the argument to k was. So, callCC's argument has type:

(a -> Cont r b) -> Cont r a

Finally, callCC is therefore a function which takes that argument and returns its result. So the type of callCC is:

callCC :: ((a -> Cont r b) -> Cont r a) -> Cont r a

The implementation of callCC

So far we have looked at the use of callCC and its type. This just leaves its implementation, which is:

 callCC f = Cont $ \k -> runCont (f (\a -> Cont $ \_ -> k a)) k

This code is far from obvious. However, the amazing fact is that the implementations for callCC f, return n and m >>= f can all be produced automatically from their type signatures - Lennart Augustsson's Djinn [1] is a program that will do this for you. See Phil Gossart's Google tech talk: [2] for background on the theory behind Djinn; and Dan Piponi's article: [3] which uses Djinn in deriving Continuation Passing Style.

Example: a complicated control structure

This example was originally taken from the 'The Continuation monad' section of the All about monads tutorial, used with permission.

Because it isn't initially clear what's going on, especially regarding the usage of callCC, we will explore this somewhat.

Analysis of the example

Firstly, we can see that fun is a function that takes an integer n. We basically implement a control structure using Cont and callCC that does different things based on the range that n falls in, as explained with the comment at the top of the function. Let's dive into the analysis of how it works.

1. Firstly, the (`runCont` id) at the top just means that we run the Cont block that follows with a final continuation of id. This is necessary as the result type of fun doesn't mention Cont.
2. We bind str to the result of the following callCC do-block:
   1. If n is less than 10, we exit straight away, just showing n.
   2. If not, we proceed. We construct a list, ns, of digits of n `div` 2.
   3. n' (an Int) gets bound to the result of the following inner callCC do-block.
      1. If length ns < 3, i.e., if n `div` 2 has less than 3 digits, we pop out of this inner do-block with the number of digits as the result.
      2. If n `div` 2 has less than 5 digits, we pop out of the inner do-block returning the original n.
      3. If n `div` 2 has less than 7 digits, we pop out of both the inner and outer do-blocks, with the result of the digits of n `div` 2 in reverse order (a String).
      4. Otherwise, we end the inner do-block, returning the sum of the digits of n `div` 2.
   4. We end this do-block, returning the String "(ns = X) Y", where X is ns, the digits of n `div` 2, and Y is the result from the inner do-block, n'.
3. Finally, we return out of the entire function, with our result being the string "Answer: Z", where Z is the string we got from the callCC do-block.

Example: exceptions

One use of continuations is to model exceptions. To do this, we hold on to two continuations: one that takes us out to the handler in case of an exception, and one that takes us to the post-handler code in case of a success. Here's a simple function that takes two numbers and does integer division on them, failing when the denominator is zero.

How does it work? We use two nested calls to callCC. The first labels a continuation that will be used when there's no problem. The second labels a continuation that will be used when we wish to throw an exception. If the denominator isn't 0, x `div` y is thrown into the ok continuation, so the execution pops right back out to the top level of divExcpt. If, however, we were passed a zero denominator, we throw an error message into the notOk continuation, which pops us out to the inner do-block, and that string gets assigned to err and given to handler.

A more general approach to handling exceptions can be seen with the following function. Pass a computation as the first parameter (which should be a function taking a continuation to the error handler) and an error handler as the second parameter. This example takes advantage of the generic MonadCont class which covers both Cont and ContT by default, plus any other continuation classes the user has defined.

For an example using try, see the following program.