I'm trying to find how call/cc is implemented. The best I've found is this Haskell snippet:
callCC f = Cont $ \k -> runCont (f (\a -> Cont $ \_ -> k a)) k
Although this is not as simple as I want due to the Cont
and runCont
. I've also found descriptions of what it does, although never as clear as actual code.
So how is it implemented in its simplest form? I am tagging this with Scheme and Haskell as those are two languages I prefer.
"Implementing
call/cc
" doesn't really make sense at the layer you're working in; if you can implementcall/cc
in a language, that just means it has a built-in construct at least as powerful ascall/cc
. At the level of the language itself,call/cc
is basically a primitive control flow operator, just like some form of branching must be.Of course, you can implement a language with
call/cc
in a language without it; this is because it's at a lower level. You're translating the language's constructs in a specific manner, and you arrange this translation so that you can implementcall/cc
; i.e., generally, continuation-passing style (although for non-portable implementation in C, you can also just copy the stack directly; I'll cover continuation-passing style in more depth later). This does not really give any great insight intocall/cc
itself — the insight is into the model with which you make it possible. On top of that,call/cc
is just a wrapper.Now, Haskell does not expose a notion of a continuation; it would break referential transparency, and limit possible implementation strategies.
Cont
is implemented in Haskell, just like every other monad, and you can think of it as a model of a language with continuations using continuation-passing style, just like the list monad models nondeterminism.Technically, that definition of
callCC
does type if you just remove the applications ofCont
andrunCont
. But that won't help you understand how it works in the context of theCont
monad, so let's look at its definition instead. (This definition isn't the one used in the current Monad Transformer Library, because all of the monads in it are built on top of their transformer versions, but it matches the snippet's use ofCont
(which only works with the older version), and simplifies things dramatically.)OK, so
Cont r a
is just(a -> r) -> r
, andrunCont
lets us get this function out of aCont r a
value. Simple enough. But what does it mean?Cont r a
is a continuation-passing computation with final resultr
, and resulta
. What does final result mean? Well, let's write the type ofrunCont
out more explicitly:So, as we can see, the "final result" is the value we get out of
runCont
at the end. Now, how can we build up computations withCont
? The monad instance is enlightening:Well, okay, it's enlightening if you already know what it means. The key thing is that when you write
Cont (\k -> ...)
,k
is the rest of the computation — it's expecting you to give it a valuea
, and will then give you the final result of the computation (of typer
, remember) back, which you can then use as your own return value because your return type isr
too. Whew! And when we run aCont
computation withrunCont
, we're simply specifying the finalk
— the "top level" of the computation that produces the final result.What's this "rest of the computation" called? A continuation, because it's the continuation of the computation!
(>>=)
is actually quite simple: we run the computation on the left, giving it our own rest-of-computation. This rest-of-computation just feeds the value intof
, which produces its own computation. We run that computation, feeding it into the rest-of-computation that our combined action has been given. In this way, we can thread together computations inCont
:or, in the more familiar
do
notation:We can then run these computations with
runCont
— most of the time, something likerunCont foo id
will work just fine, turning afoo
with the same result and final result type into its result.So far, so good. Now let's make things confusing.
What's going on here?!
wtf
is aCont
computation with final resultString
and resultInt
, but there's noInt
in sight.What happens when we run
aargh
, say withrunCont aargh show
— i.e., run the computation, andshow
itsInt
result as aString
to produce the final result?We get
"eek!"
back.Remember how
k
is the "rest of the computation"? What we've done inwtf
is cunningly not call it, and instead supply our own final result — which then becomes, well, final!This is just the first thing continuations can do. Something like
Cont (\k -> k 1 + k 2)
runs the rest of the computation as if it returned 1, and again as if it returned 2, and adds the two final results together! Continuations basically allow expressing arbitrarily complex non-local control flow, making them as powerful as they are confusing. Indeed, continuations are so general that, in a sense, every monad is a special case ofCont
. Indeed, you can think of(>>=)
in general as using a kind of continuation-passing style:The second argument is a continuation taking the result of the first computation and returning the rest of the computation to be run.
But I still haven't answered the question: what's going on with that
callCC
? Well, it calls the function you give with the current continuation. But hang on a second, isn't that what we were doing withCont
already? Yes, but compare the types:Huh. You see, the problem with
Cont
is that we can't sequence actions from inside of the function we pass — we're just producing anr
result in a pure manner.callCC
lets the continuation be accessed, passed around, and just generally be messed around with from insideCont
computations. When we haveYou can imagine
cc
being a function we can call with any value inside the function to make that the return value ofcallCC (\cc -> ...)
computation itself. Or, of course, we could just return a value normally, but then callingcallCC
in the first place would be a little pointless :)As for the mysterious
b
there, it's just because you can usecc foo
to stand in for a computation of any type you want, since it escapes the normal control flow and, like I said, immediately uses that as the result of the entirecallCC (\cc -> ...)
. So since it never has to actually produce a value, it can get away with returning a value of any type it wants. Sneaky!Which brings us to the actual implementation:
First, we get the entire rest of the computation, and call it
k
. But what's thisf (\a -> Cont (\_ -> k a))
part about? Well, we know thatf
takes a value of type(a -> Cont r b)
, and that's what the lambda is — a function that takes a value to use as the result of thecallCC f
, and returns aCont
computation that ignores its continuation and just returns that value throughk
— the "rest of the computation" from the perspective ofcallCC f
. OK, so the result of thatf
call is anotherCont
computation, which we'll need to supply a continuation to in order to run. We just pass the same continuation again since, if everything goes normally, we want whatever the computation returns to be our return value and continue on normally. (Indeed, passing another value wouldn't make sense — it's "call with current continuation", not "call with a continuation other than the one you're actually running me with".)All in all, I hope you found this as enlightening as it is long. Continuations are very powerful, but it can take a lot of time to get an intuition for how they work. I suggest playing around with
Cont
(which you'll have to callcont
to get things working with the current mtl) and working out how you get the results you do to get a feel for the control flow.Recommended further reading on continuations: