What the Heck is CallCC, Anyway?

callCC.md

What the Heck is CallCC, Anyway?

"Call with current continuation", abbreviated to call/CC or callCC, is an operator popularized by Scheme and often used to implement or emulate nonlocal control transfer in functional languages. However, how call/CC even works is really confusing. It exists at the intersection of higher order functions, continuation passing, and monadic composition; three concepts considered difficult to understand.

Todo: Type signature of callCC, trying to implement callCC, what the b parameter is for.

Part 0: The Type of Call/CC

callCC :: ((a -> Cont r b) -> Cont r a) -> Cont r a
callCC f = -- todo

Perhaps the first hurdle to understanding call/CC is the fact that it is a third order function - it accepts as its argument a function that itself accepts a function. I would say most programmers' exposure to higher order functions ends at second order functions like the map function on iterators, or the esoteric qsort function in the C standard library. Furthermore, the type Cont - a continuation - is itself a higher order function. The next parts will go into detail on the continuation type and how one might implement callCC.

Part 1: Continuations

Continuations, in short, are a reification of passing callbacks. Instead of calling a function and executing some code after the function returns, one passes a continuation to the function which can be executed at the function's leasure. The idea of passing a callback is present clearly in Haskell's definition of the Cont (short for continuation) type.

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

If the type of runCont doesn't make sense yet, consider a function that returns a continuation.

foo :: ArgType -> Cont r ReturnType

This function can be understood as a function ArgType -> ReturnType that takes a callback to run after producing the return value.

foo :: ArgType -> (ReturnType -> r) -> r

--                 v  we take a callback...
foo arg callback = callback (fooImpl arg)
    where fooImpl :: ArgType -> ReturnType
--        ^^^^^^^ ...and pass it the result of this function

Continuations are in fact a very powerful abstraction, but for our purposes here, it is sufficient to think of a function a -> Cont r b as a "callbackified" a -> b function.

Part 2: Implementing Call/CC

callCC :: ((a -> Cont r b) -> Cont r a) -> Cont r a
callCC f = -- todo

So, now that we know how to interpret continuations, we can start demystifying the type signature of callCC. First to note is that callCC is itself a "callbackified" function that returns a. Second is that all the functions in the type signature are similarly continuations. The argument is a function that produces our return type a, and it ostensibly accepts the "current continuation", which is itself a function from the return type a to some mysterious type b.

callCC :: ((a -> Cont r b) -> Cont r a) -> Cont r a
--                      ^     ^^^^^^^^     ^^^^^^^^ callCC returns `a`...
--                      |     \ ...and accepts a function that produces `a`...
--                      \ ...that accepts a mysterious continuation of `b`

Perhaps providing a definition for the function would help. We'll start by calling f to get the return value.

callCC :: ((a -> Cont r b) -> Cont r a) -> Cont r a
callCC f = f $ \a -> ???

This needs to return a continuation, which is fairly straightforward to construct.

callCC :: ((a -> Cont r b) -> Cont r a) -> Cont r a
callCC f = f $ \a -> Cont $ \b2r -> ???
--                   ^^^^^^^^^^^^^^^^^^ new code

And now we're stuck. It's not possible to get a value of type b to feed to the callback. No matter. Perhaps the a -> r callback encapsulated in the return value of callCC will help.

callCC :: ((a -> Cont r b) -> Cont r a) -> Cont r a
callCC f = Cont $ \a2r -> runCont (f $ \a -> Cont $ \b2r -> ???) ar
--         ^^^^^^^^^^^^^^^^^^^^^^ new code                       ^^

Ah, now there's a way to fill in the missing piece.

callCC :: ((a -> Cont r b) -> Cont r a) -> Cont r a
callCC f = Cont $ \a2r -> runCont (f $ \a -> Cont $ \_ -> a2r a) a2r
--                                                        ^^^^^ new code

That's strange. The callback b2r goes unused. And what does any of this mean, anyway?