callCC

callCC has a rather daunting type, and an even more daunting implementation. As Arthur C. Clarke said, "any sufficiently advanced technology is indistinguishable from magic." callCC together with the implementation of (>>=) in the Cont monad gives us the ability to abort deeply nested function calls without those functions ever returning, just as in Scheme. The magic is that this is possible even though, in contrast to Scheme, this ability is not bolted directly into the runtime system of Haskell.¹ To achieve this, the interaction between callCC and (>>=) is carefully orchestrated.

The Type

So let's look at the type of callCC first:²

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

The type makes more sense if we look at an example:

prog :: Cont r c
prog = do
    a <- callCC helper
    restOfProg1 a

helper :: (a -> Cont r ()) -> Cont r a
helper yield = do
    yield a
    restOfHelper

In this case, helper is a function that takes as argument a function yield. Calling yield has the effect of making callCC helper in prog return immediately. When it does, it returns the result passed to yield as argument.

So let's assume that the value we give to yield as an argument has type a. Then callCC helper must also return a value of type a; its type must be Cont r a. So that's where the result type of callCC comes from.

If we have a different implementation of helper,

helper :: (a -> Cont r ()) -> Cont r a
helper yield = do
    when cond (yield a)
    return a'

then helper may invoke yield, if cond is true, or it may return normally, with the result of return a' as its return value. When helper returns normally, the result of callCC helper is whatever value helper returns. Thus, since we already figured out that callCC has the return type a, helper must have the same return type. In general, the return types of callCC and of the function we pass to callCC as an argument (helper here) must be the same type as the argument type of yield.

Next let's look at the type of yield. helper is a function in the Cont monad. Each of its steps must have the type Cont r b, for some type b. One of the steps it calls is yield a. So we need yield to map its argument of type a to a result of type Cont r b, for an appropriate type b. In this example, b = () is fine, because we don't use the return value of yield anywhere. This gives the type a -> Cont r () for yield. It looks like an ordinary function that takes an argument of type a and returns void.

The statement that "we don't use yield's return value anywhere" is odd. We know that yield never returns. It aborts what helper is doing and makes callCC return immediately. So we know that we never use yield's return value anywhere; the implemention of callCC will make this clearer. Can't we always give yield the type a -> Cont r () then? Let's look at a different implementation of helper:

helper :: (a -> Cont r Int) -> Cont r a
helper yield = do
    b <- if cond
             then yield  a
             else return 5
    restOfHelper b

If cond is false, then we produce the value 5 of type Int and assign it to b. We then invoke restOfHelper with b as its argument. If cond is true, then we invoke yield a. This function never returns and instead transfers control back to callCC. From the type checker's point of view, however, both branches of the if-statement need to have the same type. Thus, we want yield a to have the the same type as return 5, which is Cont r Int. Thus, yield has the type a -> Cont r Int in this example.

And that gives us the whole type of callCC. Let's recap. callCC needs to return a value of some type a:

callCC :: ??? -> Cont r a

The argument of callCC is a function that takes an exit function, which we called yield above, as argument. This function may not invoke yield, in which case the result of callCC is whatever this function returns. So the function must have the same return type as callCC:

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

When we do call yield, then the result of callCC is whatever argument we pass to yield. So we better call yield with an argument of type a:

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

And finally, we observed that yield a is a normal step in the Cont monad, so it must produce a value of an appropriate type b, or at least look like it does:

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

Let's look at one more example of helper to highlight a limitation of callCC:

helper :: (a -> Cont r ???) -> Cont r a
helper yield = do
    b <- if cond1
             then yield  a1
             else return 5

    c <- if cond2
             then yield  a2
             else return "Hello world!"

    restOfHelper b c

What should the return type of yield be in this case? In the first if-statement, we expect it to produce an Int, just as return 5 does. In the second if-statement, we expect it to produce a String, just as return "Hello world!" does. There is just no way to give yield a type that makes this code typecheck.

We can work around this as follows:

helper :: (a -> Cont r ()) -> Cont r a
helper yield = do
    b <- if cond1
             then yield  a1 >> undefined
             else return 5

    c <- if cond2
             then yield  a2 >> undefined
             else return "Hello world!"

    restOfHelper b c

In this case, we are fine with yield having the return type () because that's not what the then-branch in either if-statement returns. The result of the then-branch is produced using undefined. In the first if-statement, we choose the type Cont r Int for undefined. In the second if-statement, we choose the type Cont r String. Or rather the type checker does this for us.

Using undefined anywhere in our code is usually dangerous because if we every try to evaluate it, our program panics. Here, this is safe—even though it's still a hack—because we know that yield never returns, so we never ask for the value of undefined.³

The Implementation

I hope the type of callCC makes sense to you now. Now let's look at the implementation:

callCC f = Cont $ \cont -> runCont (f (\x -> Cont $ \_ -> cont x)) cont

What an incomprehensible symbol salad. If we know how to look at it though, it all makes sense. First, recall the definition of Cont:

newtype Cont r a = Cont { runCont :: (a -> r) -> r }

It's a simple wrapper around a function of type (a -> r) -> r. The data constructor Cont takes such a function and converts it into a Cont r a. runCont takes a Cont r a and reveals the wrapped function of type (a -> r) -> r. So all that these uses of Cont and runCont in the implementation of callCC do is to wrap and unwrap functions of type (a -> r) -> r, for appropriate choices of a. To understand callCC better, it helps to pretend that Cont r is defined as

type Cont r a = (a -> r) -> r

This makes all the wrapping and unwrapping using Cont and runCont go away:

callCC f = \cont -> f (\x -> \_ -> cont x) cont

To make this even clearer, let's give the anonymous function passed to f a name:

callCC f cont = f yield cont
  where
    yield x _ = cont x

callCC f has the type Cont r a, for some type a. That's the type (a -> r) -> r. cont is the continuation to which callCC passes its result. Its type is thus

cont :: a -> r

and the expression f yield cont must produce a value of type r.

A point that will be important soon: In the Cont monad, "callCC f returns x" means that callCC f calls the continuation cont given to it as its second argument with x as argument. Thus, if f calls cont in tail position, then this has the same effect as callCC f returning. Let this sink in. It's really important.

f is the argument of callCC. This is what helper was in our discussion of the type of callCC. Its type is (a -> Cont r b) -> Cont r a, for an appropriate choice of b. Substituting the definition of Cont r a, we obtain the type

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

callCC calls f with arguments yield and cont. So yield is exactly the function we called yield in our different versions of helper. It's the function that f can call to abort its computation and make callCC return.

In particular, yield's type must be

yield :: a -> Cont r b

Now nobody forces f to invoke yield. In that case, f yield returns normally, producing some value x. In the Cont monad, this means that f yield calls the continuation given to it as an argument with x as the argument. Our implementation of callCC calls f yield with argument cont. So f yield calls cont x. Remember what we said a few paragraphs earlier: Calling cont x is the same as having callCC f return x. So, if f does not call yield, then f's return value simply becomes callCC f's return value.

Now let's look at what happens when f does call yield. This should somehow abort the remainder of f and make callCC f return whatever value we pass to yield as an argument. In general, we can describe the structure of f in this case as

f yield = do
    x <- computationBeforeYield
    yield x
    computationAfterYield

computationBeforeYield is the part that produces the value x that yield passes back to callCC, and computationAfterYield should never run.

Desugared, this becomes

f yield = computationBeforeYield >>= \x -> (yield x >>= \_ -> computationAfterYield)

Let's focus on the yield x >>= \_ -> compuationAfterYield part first.

The (>>=) operator for the Cont monad was

x >>= f = Cont $ \cont' -> runCont x $ \a -> runCont (f a) cont'

which after switching to our definition of Cont as a simple type alias becomes

x >>= f = \cont' -> x (\a -> f a cont')

Thus,

yield x >>= \_ -> computationAfterYield = \cont' -> yield x (\b -> (\_ -> computationAfterYield) b cont')

And now the magic happens. yield is defined as yield x _ = cont x, where cont is the continuation that expects callCC's return value. Thus, yield x (\b -> (\_ -> computationAfterYield) b cont') completely ignores its second argument (\b -> (\_ -> computationAfterYield) b cont') and simply calls cont x. Thus,

yield x >>= \_ -> computationAfterYield = \cont' -> cont x

Plugging this into the definition of f, we obtain

f yield = compuationBeforeYield >>= \x -> \cont' -> cont x

Let's expand the (>>=) operator again:

f yield = \cont'' -> computationBeforeYield (\y -> (\x -> \cont' -> cont x) y cont'')

Applying (\x -> \cont' -> cont x) to y and cont'' gives

f yield = \cont'' -> computationBeforeYield (\y -> cont y)

which is the same as

f yield = \cont'' -> computationBeforeYield cont

Calling computationBeforeYield cont means that we pass the result of computationBeforeYield—that is, the argument of yield—to the continuation cont, which we said is the same as making callCC return with the argument of yield as the return value. The continuation cont'' that expects f yield's "normal" return value is never called. In that sense, f never returns.

I'm sure you'll have to work through this a few times before it all starts to make sense, but this is all there is to using the fact that the Cont r monad captures values encoded in CPS to construct a non-local control flow construct that behave exactly like Scheme's call/cc.

It's bolted into Haskell's runtime system a little. If Haskell did not have tail call optimization, then the way we program in CPS in Haskell would be horribly inefficient. Every time we call a continuation, this would create another function call that pushes another stack frame onto the stack. Do this for a while, and your program runs out of stack space. The (>>=) operator in the Cont monad calls continuations all the time. In the Cont monad, every single step is a continuation. So programming in the Cont monad would let us run out of stack space very quickly. Tail call optimization makes this problem go away. Every time we call a function in tail position, this tail call replaces the current function call, exactly what a continuation should do. Its stack frame replaces the current function call's stack frame. ↩
Actually, its type is more general:
```
callCC :: ((a -> ContT r m b) -> ContT r m a) -> ContT r m a
```
The Control.Monad.Cont module even has a MonadCont type class analogous to MonadReader, MonadWriter, MonadState, and MonadIO. callCC is the only method this class provides:
```
class Monad m => MonadCont m where
    callCC :: ((a -> m b) -> m a) -> m a
```
Having this class combined with appropriate instance definitions allows us to use callCC, without the need to lift it, in any monad obtained by wrapping a continuation monad in any number of layers of ReaderT, WriterT, StateT, and a number of other monad transformers.

I'm sticking with the simpler definition
```
callCC :: ((a -> Cont r b) -> Cont r a) -> Cont r a
```
since wrapping our head around it is hard enough without having to worry about how to deal with more general continuation monads. ↩
It would be possible to avoid this hack by convincing the implementers of the Haskell standard library to give callCC the type
```
callCC :: ((forall b. a -> Cont r b) -> Cont r a) -> Cont r a
```
This works without changing the implementation of callCC. However, it would have the consequence that every function passed to callCC as an argument must also have the type
```
(forall b. a -> Cont r b) -> Cont r a
```
for an appropriate choice of a. Thus, this innocent change in callCC's type would break a lot of existing code. Moreover, the type
```
(forall b. a -> Cont r b) -> Cont r a
```
is not standard Haskell. If we want to write a type signature like this, we need to enable the RankNTypes language extension. Choosing to use some language extension is fine—that's why they exist—but forcing programmers to use a language extension in order to use a standard library feature probably isn't. ↩