call/cc implementation?

Question

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.

Answer 1

"Implementing call/cc" doesn't really make sense at the layer you're working in; if you can implement call/cc in a language, that just means it has a built-in construct at least as powerful as call/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 implement call/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 into call/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 of Cont and runCont. But that won't help you understand how it works in the context of the Cont 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 of Cont (which only works with the older version), and simplifies things dramatically.)

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

OK, so Cont r a is just (a -> r) -> r, and runCont lets us get this function out of a Cont r a value. Simple enough. But what does it mean?

Cont r a is a continuation-passing computation with final result r, and result a. What does final result mean? Well, let's write the type of runCont out more explicitly:

runCont :: Cont r a -> (a -> r) -> r 

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 with Cont? The monad instance is enlightening:

instance Monad (Cont r) where   return a = Cont (\k -> k a)   m >>= f = Cont (\k -> runCont m (\result -> runCont (f result) k)) 

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 value a, and will then give you the final result of the computation (of type r, remember) back, which you can then use as your own return value because your return type is r too. Whew! And when we run a Cont computation with runCont, we're simply specifying the final k — 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 into f, 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 in Cont:

computeFirst >>= \a -> computeSecond >>= \b -> return (a + b) 

or, in the more familiar do notation:

do a <- computeFirst    b <- computeSecond    return (a + b) 

We can then run these computations with runCont — most of the time, something like runCont foo id will work just fine, turning a foo with the same result and final result type into its result.

So far, so good. Now let's make things confusing.

wtf :: Cont String Int wtf = Cont (\k -> "eek!")  aargh :: Cont String Int aargh = do   a <- return 1   b <- wtf   c <- return 2   return (a + b + c) 

What's going on here?! wtf is a Cont computation with final result String and result Int, but there's no Int in sight.

What happens when we run aargh, say with runCont aargh show — i.e., run the computation, and show its Int result as a String to produce the final result?

We get "eek!" back.

Remember how k is the "rest of the computation"? What we've done in wtf 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 of Cont. Indeed, you can think of (>>=) in general as using a kind of continuation-passing style:

(>>=) :: (Monad m) => m a -> (a -> m b) -> m b 

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 with Cont already? Yes, but compare the types:

Cont   :: ((a -> r)        -> r)        -> Cont r a callCC :: ((a -> Cont r b) -> Cont r a) -> Cont r a 

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 an r result in a pure manner. callCC lets the continuation be accessed, passed around, and just generally be messed around with from inside Cont computations. When we have

do a <- callCC (\cc -> ...)    foo ... 

You can imagine cc being a function we can call with any value inside the function to make that the return value of callCC (\cc -> ...) computation itself. Or, of course, we could just return a value normally, but then calling callCC in the first place would be a little pointless :)

As for the mysterious b there, it's just because you can use cc 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 entire callCC (\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:

callCC f = Cont (\k -> runCont (f (\a -> Cont (\_ -> k a))) k) 

First, we get the entire rest of the computation, and call it k. But what's this f (\a -> Cont (\_ -> k a)) part about? Well, we know that f 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 the callCC f, and returns a Cont computation that ignores its continuation and just returns that value through k — the "rest of the computation" from the perspective of callCC f. OK, so the result of that f call is another Cont 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 call cont 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:

• The Mother of all Monads (linked previously)
• The continuation passing style chapter of the Haskell Wikibook
• Quick and dirty reinversion of control (showing a "real-world" use of continuations)
• The continuations and delimited control section of Oleg Kiselyov's site

Answer 2

call/cc is trivial to implement. The hard part is setting up the environment where it is possible to implement.

We must first define a continuation-passing style (CPS) execution environment. In this environment, your functions (or function-like things) don't directly return values; instead, they are passed a function that represents the 'next step' in the computation - the 'continuation' - and they pass their result there. In Haskell, this looks like this:

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

As you can see, a Cont monad action is really a function that takes a continuation (a -> r), passes a result a to the continuation, and gets back a final result of r, which it simply passes through to its caller (ie, a Cont monad action should tail call into the continuation). runCont just takes it out of the newtype wrapper - you could also think of it as invoking an action with some particular continuation, as in runCont someAction someContinuation.

We can then turn this into a monad:

instance Monad (Cont r) where     return x = Cont $ \cc -> cc x     (Cont f) (>>=) g = Cont $ \cc -> f (\r -> runCont (g r) cc) 

As you can see, return just gets a continuation cc, and passes its value to the continuation. (>>=) is a bit trickier, it has to invoke f with a continuation that then invokes g, gets the action back, and then passes the outer continuation to this new action.

So given this framework, getting at the continuation is simple. We just want to invoke a function with its continuation twice. The tricky part is we need to rewrap this continuation in a new monadic action that throws out the existing continuation. So let's break it down a bit:

-- Invoke a raw continuation with a given argument, throwing away our normal  -- continuation gotoContinuation :: (a -> r) -> a -> Cont r x gotoContinuation continuation argument = Cont $ \_ -> continuation argument  -- Duplicate the current continuation; wrap one up in an easy-to-use action, and -- the other stays the normal continuation for f callCC f = Cont $ \cc -> runCont (f (gotoContinuation cc)) cc 

Simple, no?

In other languages like Scheme, the principle is the same, although it may be implemented as a compiler primitive; the reason we can do it in Haskell is because the continuation-passing was something we defined in Haskell, not at a lower level of the runtime. But the principle is the same - you need to have CPS first, and then call/cc is a trivial application of this execution model.