How to interpret callCC in Haskell?

问题:

In Scheme executing a continuation obtained from a call/cc effectively jumps back to that initial call/cc and reinstates the saved call stack.

I just started learning Haskell and I am trying to figure out how to comprehend callCC. That is try to comprehend callCC in terms of understanding of Scheme's call/cc. The implementation of callCC is

callCC f = cont $ \h -> runCont (f (\a -> cont $ \_ -> h a)) h

As far as I can tell there is nothing mentioned relating to call stacks saved or reinstated. How does one interpret callCC in Haskell coming from familiarity with Scheme's call/cc.

Edit: Maybe if someone could translate the following to Haskell that would help me understand.

(define (f return)
  (return 2)
  3)

(display (f (lambda (x) x))) ; displays 3

(display (call-with-current-continuation f)) ; displays 2

回答1:

It does work very much like Scheme's call/cc. You need to take into account that it is in Cont monad.

The actual function is defined using ContT. ContT is a monad transformer that allows to add continuations into other monads, but let's see how this works with Identity monad first, and limit ourselves to Cont.

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

Here, Cont r a represents a function that can compute some value of type a, since given a function of type a->r it can compute a value of type r.

It is clearly a monad:

return x = Cont $ \f -> f x

(a trivial "computation" of a value of type a)

ma >>= h = Cont $ \f -> runCont ma $ \a -> runCont (h a) f

(here ma :: Cont r a, and h :: a -> Cont r b)

(a computation of value of type a, ma, can turn into a computation of a value of type b - runCont ma is given h, which, given a value of type a, "knows" how to produce a computation of a value of type b - which can be supplied with function f :: b -> r to compute a value of type r)

In essence, h is the continuation of ma, and >>= binds ma and its continuation to produce the continuation of the function composition (the function "hidden" inside ma to produce a and the function "hidden" inside h to produce b). This is the "stack" you were looking for.

Let's start with the simplified type (not using ContT):

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

Here, callCC uses a function that constructs a continuation given a continuation.

There is a important point that you seem to be missing, too. callCC only makes sense if there is a continuation after callCC - i.e. there is a continuation to pass. Let's consider it is the last line of a do-block, which is the same as to say it must have something bound to it with >>=:

callCC f >>= return "blah"

will do. The important bit here is that the operation of callCC can be understood easier when you see this context, when you see it is on the left hand side of >>=.

Knowing how >>= works, and taking into account right-associativity of >>=, you can see that h in callCC f = cont $ \h -> runCont (f (\a -> cont $ \_ -> h a)) h is in fact built using current continuation - it is built using the h appearing on the right of >>= - the entire do-block from the line following callCC to the end:

(callCC f) >>= h =
Cont $ \g -> runCont
               (cont $ \h -> runCont (f (\a -> cont $ \_ -> h a)) h) $ 
               \a -> runCont (h a) g =

[reduction step: runCont (Cont x) => x]

Cont $ \g -> (\h -> runCont (f (\a -> Cont $ \_ -> h a)) h) $
               \a -> runCont (h a) g =

[(\h -> f) (\a -> ...) => f [h/(\a -> ...)] -- replace
occurrences of h with (\a -> ...)]

Cont $ \g -> runCont (f (\a -> Cont $ \_ -> (\b -> runCont (h b) g) a)) $
               \a -> runCont (h a) g =

[(\b -> runCont (h b) g) a => runCont (h a) g]

Cont $ \g -> runCont (f (\a -> Cont $ \_ -> runCont (h a) g)) $
               \a -> runCont (h a) g

You can see here how \_ -> runCont (h a) g in essence will ignore the continuation following the invocation of the function passed to f - and "switch the stack", switch to the current continuation h of the place where callCC is invoked.

(Similar reasoning can be applied if callCC is the last in the chain, albeit it is less clear that the "current continuation" in that case is the function passed to runCont)

The last point is that runCont (f...) h does not really use this last h, if the actual invocation of h occurs from inside the continuation computed by f, if that ever happens.

回答2:

To understand what callCC means in Haskell, you might want to rather look at its type, not at its implementation:

callCC :: MonadCont m => ((a -> m b) -> m a) -> m a

The first and most important thing here is MonadCont m. This means that callCC only works in monads that implement MonadCont -- and this might be a disappointment for you, but IO is not an instance of MonadCont. In this respect, callCC doesn't work the way it does in scheme.

Anyway, the parameter to callCC is ((a -> m b) -> m a): this is a computation that takes (a -> m b) as its parameter, which is the continuation that callCC is capturing. So let's try to write something that makes use of callCC:

import Control.Monad.Cont
fun _ = return "hi"
main = print $ runCont (callCC fun) id

Now this is pretty boring, as we don't use the continuation in any way. Let's try with different fun:

fun' escape = do escape "ahoy"
                 return "die die die"

When you run the code you will see that the "call" to escape never "returns" -- it has invoked the continuation just like it would in scheme. You probably know that "return" doesn't work this way in Haskell: it's not a short-circuiting operation. You could think of callCC as giving you a way to terminate a computation early.

On the implementation level, cont and runCont are functions that convert to/from continuation-passing-style. You will want to study the continuation monad in more detail to find out how it actually works. Try eg. http://www.haskellforall.com/2012/12/the-continuation-monad.html

(In many scheme implementations, call/cc doesn't really work by "saving the call stacks" either. If you convert a program into CPS, call/cc sort of falls out of the thing "for free". I think you might want to read eg. this http://www.pipeline.com/~hbaker1/CheneyMTA.html, which discusses one way CPS can be implemented at a low level.)