How to interpret callCC in Haskell?

Question

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 ```

Accepted Answer

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.

How to interpret callCC in Haskell?

Solution

Problem