C minus minus? No, C monad monad.

[John Meacham]

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⑈