C minus minus? No, C monad monad.

John Meacham john at repetae.net
Thu Nov 10 20:41:18 EST 2005


On Thu, Nov 03, 2005 at 12:57:54PM +0100, Christof Douma wrote:
> 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.

I am glad to see other people using it too :) I have read some of your
stuff and am looking forward to seeing the results.

> 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


The problem is that this is the exact opposite transformation that I am
trying to carry out :) The above is what is generated by my
front-middle-end (hmm. need new terminology) and my goal is to transform
it into explicit loops with updatable variables. These things cannot be
expressed directly in traditional Grin which is why I introduced
continuations and a series of transformations to turn the above into
efficient looping updating c-- code. 

> >yay! Grin has gained a whole lot of power from stealing this idea from c--.
> yay! Grin already has a whole lot of power. ;-)

Indeed, but the goal of jhc is to produce code that is faster than C
code. any compromises in expressing algorithms that can be expressed in
C are not ones I am willing to make :) so powerful here doesn't mean
being able to do more. it means being able to express the optimizations
I need to in order to produce code that runs as efficiently as I want
without sacrificing Grin's nice theoretical properties.

> 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?

Although jhc does not have global variables, it does have global names,
this is how CAFs are implemented. theoretically, you can think of them
as parameters that are implicitly passed to every function and they have
the same semantics, but practically, I don't implement them that way of
course. They are not special in any way and are just like any other grin
name so none of the machinery needs to change to take them into account.

in any case, one of these global names can easily hold the value of some
heap location or register to store the exception stack. This is exactly
what needs to be done to implement updatable CAFs properly so I am not
adding any new concepts to support exceptions.


> 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.

Indeed, I was looking at using this model too, but I decided against it
for a couple reasons, the main one is that continuations give me a whole
lot of other advantages I can make good use of. but other than that, it
means that the IO monad will have to be special since it has these
primitives that are part of the monad. in jhc, the IO monad is exactly

 
data World__

data IOResult a = FailIO World__ IOError | JustIO World__ a
newtype IO a = IO (World__ -> IOResult a)

with continuations as a primitive, I could get rid of FailIO and have
the continuation actually be the World__ value that is passed around,
this also incidentally obviates the need for a global variable as
mentioned above. It also opens up the use of the continuation primitive
to other uses, like a more efficient Control.Monad.Cont. 

though, imprecise exceptions most likely would need a global exception
stack though I am still undecided as to whether those are a good idea.


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

Yeah, I think boquist would have benefited from a lot of these ideas
since he went directly from grin -> assembly. going through c or c--
affords us a lot more freedom. but using this algorithm to decide what
goes in C local variables is quite useful too.

        John

-- 
John Meacham - ⑆repetae.net⑆john⑈ 


More information about the Glasgow-haskell-users mailing list