[Haskell-cafe] Cont, ContT and IO()

[wren ng thornton]

Günther Schmidt wrote:
> 
> Hi,
> 
> I've got an IO action, some file system IO, traversing one level only 
> and iterating over files found. I wish to build in an "early" exit, ie. 
> if an IO action in the loop encounters a particular value I want it to 
> abort the loop.
> 
> Now so far, pls don't shoot, I have done this by throwing IO Exceptions 
> and catching them. I'm trying to rewrite this using Continuatios / 
> callCC but can't figure out where to place what.
> 
> I certainly don't have the intuition yet and funny enough not even in 
> RWH I could find some Cont/ContT examples.
> 
> Would someone please draw me an example?


The quick and dirty explanation is, given an expression like:

     f . g . h $ callCC (\k -> body)

we might wonder what the meaning of "callCC (\k -> body)" is. If k is 
unused in body, then it means the same thing as "body" which is to say 
that body returns with some value x::A. The alternative is that we use k 
in the body (e.g. by passing it some y::A), in which case the value of 
"callCC (\k -> body)" is whatever value is passed to k (namely y::A). 
Note that the input type of k and the output type of body must be the 
same, and the output type of k is irrelevant because it never returns.

Once we get a value for "callCC (\k -> body)", whatever value that is 
gets passed on to h, then g, then f, in the usual manner. For imperative 
code, this is just like calling return before the end of the function, e.g:

     if_PA_then_return5_else_DoSomethingAndReturnB =
     \ p a b -> callCC $ \exit -> do
             isP <- if p a
                    then exit (return 5)
                         -- return 5 *immediately* to our caller
                    else return True
             -- if we ever get here, isP must equal True because
             -- exit never returns.

             doSomething
             -- if we wanted doSomething to be able to override our
             -- "return b" result, we could pass it exit and then
             -- doSomething will either return control to us (and we
             -- return b) or it will return directly to our caller with
             -- some other answer.

             return b

That isn't the whole story, but it's enough to figure out how to do 
early exits.


In the more compleat explanation, the k which callCC causes to be passed 
to its functional argument is the "f . g . h" which will be invoked 
after callCC returns. That is, it's not the composition of functions, 
but rather it's that exact application of those functions. I.e. the 
fabricated k is a goto statement accepting a value and returning control 
to just outside of the invocation of callCC. Because of this behavior 
you can do interesting things like returning k from the body, or passing 
k to itself, which allows someone else to jump back into the expression 
and rerun it by passing a new value through the "f . g . h"

Another paper to check out if you're a fan of theory is:

     Andrzej Filinski
     Declarative continuations: An investigation of duality in
         programming language semantics
     http://www.springerlink.com/content/m2105282ru426654/

which does quite a good job of investigating how to reason about 
continuations. (Though you need to be somewhat familiar with some 
Category Theory, and intimately familiar with lambda calculus, to enjoy it.)

-- 
Live well,
~wren