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