"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.
callCC :: ((a -> Cont r b) -> Cont r a) -> Cont r a
callCC f = -- todoPerhaps 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.
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 ReturnTypeThis 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 functionContinuations 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.
callCC :: ((a -> Cont r b) -> Cont r a) -> Cont r a
callCC f = -- todoSo, 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 codeAnd 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 codeThat's strange. The callback b2r goes unused. And what does any of this mean, anyway?