Search code examples
haskellschemecontinuationscallcc

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

Solution

  • 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.