callCC in Haskell

Intro

Continuation passing style is a very interesting programming concept. In Haskell we have the continuation monad ContT, implemented in the transformers package. An introduction to the topic can be found in the open Haskell wiki book and Gabriel Gonzalez wrote a very nice article about why continuation passing style matters.

The wiki book article also mentions the callCC function. I think in general the explanation and motivation for this function is conveyed well in this article and the article is also not short on examples. The only thing I’m missing in it is an example of a full evaluation involving callCC. I think once you see how the function actually works things become much clearer. That will be the goal of this article. I won’t give any extra explanations, instead I will take one of the examples from the article and do a full evaluation of it.

callCC in action

Note: I will use the definitions from the transformers package, not from the wiki book article.

Here is the full example we will evaluate:

We will transform the bar computation. Desugaring the outer do-notation yields

Using the definition of the ContT monad’s bind (>>=) function and giving the anonymous function to callCC a name yields

Now we use the definition of callCC

Now we can also desugar the inner do computation, which yields

Now we can fill in the definition of check, unpack the delayed continuation with runContT and then apply the continuation to it

Now we can substitute f by its definition and write the lengthy line in several lines

Once again using the definition ContT monad’s bind (>>=) function we end up with

Unwrapping the inner runContT ContT ... layer and substituting for when_f yields

Now we are able to discuss the possible outcomes of the computation.

Calling bar with ‘hello’

Let’s assume we call bar with the string ‘hello’. In this case the predicate function of when returns True and when will simply evaluate to its second argument and we end up with

Which we can simplify to

If we cheat a bit we can rewrite it a bit further. The following won’t compile, because we are using variables out of scope, but it helps to see things a bit better

Now we can run the main function (again in a sort of pseudo code)

They key point to note here is that f ignored its argument, thus it was completely irrelevant what the actual value of k was. That is exactly the “early return” behavior that callCC aims to provide. If you look way to the beginning of the code transformation process you’ll notice that the definition of f came from the application of callCC.

Calling bar with ‘other’

Let’s now assume we call bar with the string ‘other’. In this case the predicate function of when returns False and when will simply evaluate to pure (), which in the case of the continuation monad equals ContT ($ ()).

Which we can simplify to

And now the main function can be evaluated

As can be seen we evaluated the inner compuatation of callCC’s argument to the end and did not make any use of the early return.

Key concept

It was probably not so easy to see the most key point in the above series of transformations, so I want to take the chance to show it once more. The argument to the argument of callCC (k in our case) has the following signature

So it takes a value of type a and returns a continuation monad transformer. In our case k had the following definition

where c1 was the actual continuation passed to callCC and captured as a closure. Let’s now assume a is the type Int and that we have the following computation:

Then we can also write this like that

Using what we know about k we get

Again using the definition of (>>=) we get

I marked for which part in the code c1 and c2 pose the continuation. When we focus at the lengthy term in the middle we can see that it is equal to

This shows that no matter what follows after a call to k will be ignored. No matter how many compX terms there are (they could be arbitrarily many) and however complex c2 actually is, we will use c1 as the continuation. And we’ve been given c1 by callCC. The nice thing is that laziness helps us to end up with efficient code, since we only evaluate terms once we need their result. Thus c2 in our example (i.e. do compB; compC) will never be evaluated because we never actually need it!