This post is about the mechanics of callCC. Practical uses of callCC are not discussed. Understanding the Monad instance for ContT is helpful. You can read more about that here. The examples are written in PureScript.

There is mercifully little magic in functional programming. Everything desugars to functions and data. And even the data can be encoded as functions.

I take comfort in the idea that everything is a function, however over-simplified that might be. A function is something I can understand. And what I understand, I can control.

Like everything else, continuations are just functions. But continuations used to implement control flow often seem magical. For example, we can use callCC to simulate returning early from a function in a language (PureScript) that does not have early returns.

main :: Effect Unit
main = flip runContT pure do
  lift $ log "1"
  callCC \escape -> do
    void $ escape unit
    lift $ log "2"
    lift $ log "3"
  lift $ log "4"

This program only outputs 1 and 4. By calling escape, we’ve effectively returned early.

> main
1
4
unit

It’s hard to believe we can (seemingly) change the semantics of the language without magic. But callCC and continuations in general are not magic. And we can understand how they work.

To understand callCC, we must understand continuation passing style. Continuation passing style isn’t obvious here because we’re working in the continuation monad. The definition of bind for ContT conceals it.

Continuation passing style means that each step is a function that receives a callback. The callback is the continuation of that step. Instead of returning a value directly, the current step passes control to the next step by invoking the continuation.

main = flip runContT pure do
  lift $ log "1"
  lift $ log "2"
  lift $ log "3"
  lift $ log "4"

So a sequence of steps in the continuation monad is equivalent to a series of nested callbacks.

step1 k = log "1" >>= k

step2 k = log "2" >>= k

step3 k = log "3" >>= k

step4 k = log "4" >>= k

main =
  step1 \_ ->
    step2 \_ ->
      step3 \_ ->
        step4 pure

That brings us to the first key insight. At every step, there is a function wrapping all of the following steps. Where bind conceals that function, callCC exposes it. The escape function is a continuation, hence the name call-with-current-continuation or callCC.

But where does the escape function continue from? “Current continuation” sounds like the continuation of the current step.

main = flip runContT pure do
  lift $ log "1"
  callCC \escape -> do
    void $ escape unit
    lift $ log "2"
    lift $ log "3"
  lift $ log "4"

But when we call the escape function, some of the following steps are skipped.

main = flip runContT pure do
  lift $ log "1"
  callCC \escape -> do
    void $ escape unit
    lift $ log "2"
    lift $ log "3"
  lift $ log "4"

That’s because the escape function is a continuation from the point where we invoke callCC.

main = flip runContT pure do
  lift $ log "1"
  callCC \escape -> do
    void $ escape unit
    lift $ log "2"
    lift $ log "3"
  lift $ log "4"

We’ve clarified what is happening but not how it’s happening. The implementation of callCC is both suprisingly small and unsurprisingly inscrutable.

callCC 
  :: forall r m a
   . Monad m
  => ((forall b. a -> ContT r m b) -> ContT r m a)
  -> ContT r m a
callCC f =
  ContT \k1 -> runContT (f \a -> ContT \k2 -> k1 a) k1

Most of what’s happening here is building up and breaking down intermediate ContT structure. The essence of the function is so subtle it’s easy to miss.

Notice we have two continuations, k1 and k2.

callCC f =
  ContT \k1 -> runContT (f \a -> ContT \k2 -> k1 a) k1

k1 is the continuation of the callCC expression.

main = flip runContT pure do
  lift $ log "1"
  callCC \escape -> do
    void $ escape unit
    lift $ log "2"
    lift $ log "3"
  lift $ log "4"

k2 is the continuation of a step created by calling the escape function.

main = flip runContT pure do
  lift $ log "1"
  callCC \escape -> do
    void $ escape unit
    lift $ log "2"
    lift $ log "3"
  lift $ log "4"

The essence of callCC lies in the fact that k2 is never called. The step created by calling the escape function invokes k1 instead. The rest of the function is plumbing required to make this switch.

callCC f =
  ContT \k1 -> runContT (f \a -> ContT \k2 -> k1 a) k1

That brings us to the second key insight: the current step controls the next step. Because the next step only happens when the current step calls the continuation, the current step can choose when the next step happens or if it happens at all. callCC enables you, the programmer, to make this choice.

So the escape function is not magic. No semantics have been changed. There is no early return. It is all an effect of calling one function, one continuation, instead of another. The essence of control flow is what happens next. When “next” is a function, no magic is needed to control it.