The example executes in the ContT () IO
monad, the Monad allowing continuations that result in ()
and some lifted IO
.
type ExM a = ContT () IO a
ContT
can be an incredibly confusing monad to work in, but I've found that Haskell's equational reasoning is a powerful tool for disentangling it. The remainder of this answer examines the original example in several steps, each powered by syntactic transforms and pure renamings.
So, let's first examine the type of the callCC
part—it's ultimately the heart of this entire piece of code. That chunk is responsible for generating a strange kind of tuple as its monadic value.
type ContAndPrev = (Int -> ExM (), Int)
getContAndPrev :: ExM ContAndPrev
getContAndPrev = callCC $ \k -> let f x = k (f, x)
in return (f, 0)
This can be made a little bit more familiar by sectioning it with (>>=)
, which is exactly how it would be used in a real context—any do
-block desugaring will create the (>>=)
for us eventually.
withContAndPrev :: (ContAndPrev -> ExM ()) -> ExM ()
withContAndPrev go = getContAndPrev >>= go
and finally we can examine that it actually looks like in the call site. To be more clear, I'll desugar the original example a little bit
flip runContT return $ do
lift (putStrLn "alpha")
withContAndPrev $ \(k, num) -> do
lift $ putStrLn "beta"
lift $ putStrLn "gamma"
if num < 5
then k (num + 1) >> return ()
else lift $ print num
Notice that this is a purely syntactic transformation. The code is identical to the original example, but it highlights the existence of this indented block under withContAndPrev
. This is the secret to understanding Haskell callCC
---withContAndPrev
is given access to the entire "rest of the do
block" which it gets to choose how to use.
Let's ignore the actual implementation of withContAndPrev
and just see if we can create the behavior we saw in running the example. It's fairly tricky, but what we want to do is pass into the block the ability to call itself. Haskell being as lazy and recursive as it is, we can write that directly.
withContAndPrev' :: (ContAndPrev -> ExM ()) -> ExM ()
withContAndPrev' = go 0 where
go n next = next (\i -> go i next, n)
This is still something of a recursive headache, but it might be easier to see how it works. We're taking the remainder of the do block and creating a looping construct called go
. We pass into the block a function that calls our looper, go
, with a new integer argument and returns the prior one.
We can begin to unroll this code a bit by making a few more syntactic changes to the original code.
maybeCont :: ContAndPrev -> ExM ()
maybeCont k n | n < 5 = k (num + 1)
| otherwise = lift (print n)
bg :: ExM ()
bg = lift $ putStrLn "beta" >> putStrLn "gamma"
flip runContT return $ do
lift (putStrLn "alpha")
withContAndPrev' $ \(k, num) -> bg >> maybeCont k num
And now we can examine what this looks like when betaGam >> maybeCont k num
gets passed into withContAndPrev
.
let go n next = next (\i -> go i next, n)
next = \(k, num) -> bg >> maybeCont k num
in
go 0 next
(\(k, num) -> betaGam >> maybeCont k num) (\i -> go i next, 0)
bg >> maybeCont (\i -> go i next) 0
bg >> (\(k, num) -> betaGam >> maybeCont k num) (\i -> go i next, 1)
bg >> bg >> maybeCont (\i -> go i next) 1
bg >> bg >> (\(k, num) -> betaGam >> maybeCont k num) (\i -> go i next, 2)
bg >> bg >> bg >> maybeCont (\i -> go i next) 2
bg >> bg >> bg >> bg >> maybeCont (\i -> go i next) 3
bg >> bg >> bg >> bg >> bg >> maybeCont (\i -> go i next) 4
bg >> bg >> bg >> bg >> bg >> bg >> maybeCont (\i -> go i next) 5
bg >> bg >> bg >> bg >> bg >> bg >> lift (print 5)
So clearly our fake implementation recreates the behavior of the original loop. It might be slightly more clear how our fake behavior achieves that by tying a recursive knot using the "rest of the do block" which it receives as an argument.
Armed with this knowledge, we can take a closer look at callCC
. We'll again profit by initially examining it in its pre-bound form. It's extremely simple, if weird, in this form.
withCC gen block = callCC gen >>= block
withCC gen block = block (gen block)
In other words, we use the argument to callCC
, gen
, to generate the return value of callCC
, but we pass into gen
the very continuation block
that we end up applying the value to. It's recursively trippy, but denotationally clear—callCC
is truly "call this block with the current continuation".
withCC (\k -> let f x = k (f, x)
in return (f, 0)) next
next (let f x = next (f, x) in return (f, 0))
The actual implementation details of callCC
are a bit more challenging since they require that we find a way to define callCC
from the semantics of (callCC >>=)
but that's mostly ignorable. At the end of the day, we profit from the fact that do
blocks are written so that each line gets the remainder of the block bound to it with (>>=)
which provides a natural notion of continuation immediately.