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.
This program only outputs 1 and 4.
escape, we’ve effectively returned early.
It’s hard to believe we can (seemingly) change the semantics of the language
callCC and continuations in general are not magic.
And we can understand how they work.
callCC, we must understand continuation passing style.
Continuation passing style isn’t obvious here because we’re working in the
The definition of
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.
So a sequence of steps in the continuation monad is equivalent to a series of nested callbacks.
That brings us to the first key insight.
At every step, there is a function wrapping all of the following steps.
bind conceals that function,
callCC exposes it.
The escape function is a continuation, hence the name
But where does the escape function continue from? “Current continuation” sounds like the continuation of the current step.
But when we call the escape function, some of the following steps are skipped.
That’s because the escape function is a continuation from the point where we
We’ve clarified what is happening but not how it’s happening.
The implementation of
callCC is both suprisingly small and unsurprisingly
Most of what’s happening here is building up and breaking down intermediate
The essence of the function is so subtle it’s easy to miss.
Notice we have two continuations,
k1 is the continuation of the
k2 is the continuation of a step created by calling the escape function.
The essence of
callCC lies in the fact that
k2 is never called.
The step created by calling the escape function invokes
The rest of the function is plumbing required to make this switch.
That brings us to the second key insight: the current step controls the next
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.