C minus minus? No, C monad monad.
wizztick-ghc at douma.eu.org
Thu Nov 3 07:04:46 EST 2005
In my master thesis I use GRIN and C-- to writing a backend to ehc
(essential haskell compiler - http://www.cs.uu.nl/wiki/Ehc/)
It is nice to see GRIN is used by other people as well. My work has been
to extend the GRIN model to be usefull for exceptions and implement a
grin compiler. I am currently in the process of writing the results down.
For those not familiar to GRIN some lines on its ideas:
- Explicit behaviour (no buildin magic functions)
- Thunks and values are represented by a node (A tag followed with zero
or more fields)
- Do a global analysis to find an approximation of which nodes are
stored in memory and the values that variables hold.
- Use this approximation to remove any unknown function call and remove
unneeded case alternatives
> I have recently been thinking about writing a c-- backend for jhc, printing out
> and reading the various c-- papers in preparation. As I expected, the
> translation would be quite simple and straightforward, but I found the section
> on continuations and cut to particulary inspiring. Adding them to Grin
> (graph-reduction-intermediate-form, the last form of jhc programs before code
> generation) would give me exactly the features I have been missing and having
> to do in an ad-hoc manner in the code generator or do without, exceptions, join
> points, loops.
> I formulated how to add them to Grin, verified it still followed
> the monad laws and think I might have come up with something that is not only
> practically useful to me now, but has implications for c-- optimizers and
> implementations in general which is what this message is about.
> for example, a join point:
> myfunc = \ (a,b) -> do -- ^ note, tupled, no currying
> cont <- mkContinuation $ \ x -> do
> return (x + 4)
> case a - b of
> 3 -> return -1
> 5 -> cutTo (cont 2)
> z -> cutTo (cont z)
Continuations in this example are not needed. The example calls some
function by using continuations. The idea of GRIN is to have nodes which
represent thunks. A partial application to some function foo can be
represented by a node which describes which function to be called when
fully saturated and the already applied arguments. The above example can
be rewritten to standard GRIN as follows:
foo x = return (x + 4)
myfunc = \(a,b) -> do
cont <- return (P1foo) //store a partial application node
case (a - b) of
3 -> return -1
5 -> apply cont 2
z -> apply cont z
apply f a = case f of
P1foo -> foo a
> yay! Grin has gained a whole lot of power from stealing this idea from c--.
yay! Grin already has a whole lot of power. ;-)
Secondly. Modelling exceptions in GRIN does not benefit from the use of
these continuation constructs. GRIN does not have some global variable
in which you can store the exception handler. Of course this can also be
added (as a primitive in the monad). But what is the difference to a
global variable with a node in it?
The extension I created allows exceptions in GRIN with the use of try
catch and throw statements. These two are monad primitives. The try
catch statments defines a continuation and pushes it on the exception
handler stack. The throw statment cuts to that handler. Leaving the
scope of the try statement or entering the handler will restore the
Doing register allocation and instruction selection in GRIN sure looks
nice. It is an intresting thought.
More information about the Glasgow-haskell-users