On Mon, Oct 31, 2005 at 05:37:31PM -0000, Simon Peyton-Jones wrote:

Interesting message. http://repetae.net/john/repos/jhc/docs/c-minus-monad.txt

But I'm not completely convinced.

That's okay, I am pretty sure I wasn't trying to convince anyone of anything other than I find this neat :)

Firstly, C-- *continuations* are quasi-first class values: you can pass them as arguments to functions, and store them in data structures. In contrast, your continuations are more akin to C-- *labels*. These are definitely not first class. They just give a textual way of describing a control flow graph. That's much closer to what you mean to do (with join points etc).

Oh, I just didn't mention first class continuations because they wern't very interesting to me. If compiling to c-- then any such continuations would just be directly translated to c-- continuations. I didn't feel it was worth mentioning because it would sort of be like saying adding exceptions gives me exceptions :) (I have a feeling there is a pun here involving turing oracles I should be able to come up with) Though, it does bug me to no end I was not able to come up with a type system to ensure c-- continuations wern't called after the continuee has left scope. at least not without severely restricting their usefulness like not storing them in data structures.

Of course, labels allow you to build a cyclic graph. Your hack for building cycles feels to me like using the monadic story for something it wasn't really meant for. Somehow, a set of labelled blocks seems more more direct.

Yes, but the interesting thing to me wasn't the final result, it was the ability to transform grin to a set of labeled blocks via a set of source->source translations. The benefits of source -> source translations are well known, (especially to you I imagine :) ) and transforming a set of mutual tail-recursive top level functions into efficient loops is a non-trivial transformation. having to come up with a single-pass analysis that would allow direct translation to efficient C/C-- is quite tricky and subtle, especially when dealing with several mutually recursive functions. a simple set of simple pattern matching code improving transformations that eventually converge is a whole lot nicer to deal with. Perhaps it was unclear because I sort of mashed together two independent ideas. One was the (very useful to me) ability to use these transformations to output _efficient_ c--/c directly with nothing more complicated by pretty printing the grin code and without placing the burden on gcc or qc-- to figure out what can be turned into loops and perform the appropriate code hoisting. c-- explicit tail calls help a lot, but in order to take full advantage of them with traditional grin, I would be forced to lift every basic block to its own function and hope that the c-- compiler does cross-function register allocation, if they turned into actual functions then the results would be pretty disasterous. These optimizations are also much easier to do at the grin level, once the transformation to c-- has been done then memory allocation and register assignment (not machine registers, but deciding what should be stored in local variables) has already been done, which signifigantly complicates the job of the c-- compiler. The above I plan to fully use in jhc for both my c-- and c back ends. in fact, it makes using straight C rather than C-- and getting good results quite plausable. The C-- compiler most likely will use the more natural basic blocks representation you mention, but the new bit is how I get to that point from Grin. The next idea was sort of a flight of fancy and is probably more of fun than practical interest. (though, if I were to write a c-- compiler (which I barely resist the urge to do every time I run into an issue with gcc), I would definitly explore the possibility of using Cmf for a lot of the middle-end work). Using the same source->source translation based on simple pattern matching I wanted to see how far I could go. I was honestly surprised by being able to go all the way to fully register allocated assembly code without ever having to leave the mathematical framework. Furthermore, I found it interesting that there was a very clear point at which you were done that was independent of 'finally being assembly', when every (>>=) has turned into a (>>).

I'm also not convinced that you are getting anything much from your monadic presentation that you would not also get, sometimes more directly, from a C-- representation. What, do you think you gain?

Well, aside from the fact that I actually plan to use a C-- representation :) I really like mathematical frameworks. Without one I find myself with too many degrees of freedom, run around randomly flailing about and ultimatly producing not much of interest. Haskell owes a lot of its innovations to adhering strictly to sound theory because it forced us to actually think about the problems in a new manner and that has lead to huge advances in the practical state of the art. I am not sure how to exactly quantify the value that a monadic representation gives me over an ad hoc one, but i feel it is there :)

There is a long and distinguished history to regarding lambda code as an intermediate language that can go all the way to machine code (e.g. the lambda-the-ultimate papers; the T compiler; Appel's book etc). Using a monadic, rather than CPS, framework may be better -- though it's a tricky case to make. But in fact, few compilers do take this idea right through. It's hard to say why, except that it can be a bit clumsy to make one hammer that is truly comfortable on many different nails.

Yeah, I have read a lot of those papers, and I think you hit the nail on the head, none feel very comfortable using all the way through. the assembly you produce is not very idiomatic, or things like register allocation and updatable loops are sort of handwaved around. I use that term somewhat loosly, it is not that they don't give algorithms for those things, it is that the results are not really what an efficient compiler would produce. (I am also just not a very big fan of CPS for reasons I can't really figure out, it never really felt right to me.) But yeah, I certainly need to do some more reading on the subject. I certainly didn't think the idea of going directly from a mathematical form to assembly was new.

At the moment, I'd still incline to translating Grin into C-- (or something like it), and optimising there. But maybe you have good reasons not to do that.

This is what I plan to do :) though, I leave the optimizing to the c-- compiler and am going to be presenting it with much easier to optimize code without having to rely on it carrying out any non-trivial analysises one wouldn't expect from a basic global C compiler. Perhaps if I were to write a C-- compiler I will explore my other ideas.. John -- John Meacham - ⑆repetae.net⑆john⑈