C minus minus? No, C monad monad.

[Christof Douma]

Hi,

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

[snip]
> 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 
previous handler.

[snip]

Doing register allocation and instruction selection in GRIN sure looks 
nice. It is an intresting thought.

Christof