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
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.
Here,
Cont r a
represents a function that can compute some value of typea
, since given a function of typea->r
it can compute a value of typer
.It is clearly a monad:
(a trivial "computation" of a value of type
a
)(here
ma :: Cont r a
, andh :: a -> Cont r b
)(a computation of value of type
a
, ma, can turn into a computation of a value of typeb
-runCont ma
is givenh
, which, given a value of typea
, "knows" how to produce a computation of a value of typeb
- which can be supplied with functionf :: b -> r
to compute a value of typer
)In essence,
h
is the continuation ofma
, and>>=
bindsma
and its continuation to produce the continuation of the function composition (the function "hidden" insidema
to producea
and the function "hidden" insideh
to produceb
). This is the "stack" you were looking for.Let's start with the simplified type (not using
ContT
):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 aftercallCC
- i.e. there is a continuation to pass. Let's consider it is the last line of ado
-block, which is the same as to say it must have something bound to it with>>=
: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 thath
incallCC f = cont $ \h -> runCont (f (\a -> cont $ \_ -> h a)) h
is in fact built using current continuation - it is built using theh
appearing on the right of>>=
- the entiredo
-block from the line following callCC to the end:You can see here how
\_ -> runCont (h a) g
in essence will ignore the continuation following the invocation of the function passed tof
- and "switch the stack", switch to the current continuationh
of the place wherecallCC
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 torunCont
)The last point is that
runCont (f...) h
does not really use this lasth
, if the actual invocation ofh
occurs from inside the continuation computed byf
, if that ever happens.