Proto for Boost mailing list page: Re: [proto] So I heard proto make AST ...

Subject: Re: [proto] So I heard proto make AST ...
From: Thomas Heller (thom.heller_at_[hidden])
Date: 2010-08-11 03:53:28

On Wednesday 11 August 2010 00:45:44 Eric Niebler wrote:
> On 8/10/2010 3:52
PM, Thomas Heller wrote:
> > On Tue, Aug 10, 2010 at 8:56 PM, Eric Niebler
wrote:
> >> Good. Now if you are saying that Proto's existing transforms
are
> >> too low-level and that things like pre- and post-order traversals
>
>> should be first class Proto citizens ... no argument. Patch? :-)
> > 
> >
I think i am a little bit responsible for that whole discussion as i
> > 
>
>  mentiones on IRC that proto transforms are hard for me.
> 
> The #boost
IRC channel? Perhaps I should spend time there.

You definitely should :)

>
> So, why are they so hard. I am currently learning the principles of
> >
compiler construction (lecture at university). We learn all those
> > fancy
algorithms to optimize the hell out of our codes. But these
> > algorithm
all rely on bottom-up, top-down and what-not traversals of
> > your AST.
proto transforms work a little bit different from these
> > tree traversals.
BUT they are very similiar, and probably as you
> > said, a little more low
level. Just my 2 cents ;)
> 
> And a good 2 cents. I never actually took a
compiler construction class.
> Oops! But as I showed earlier in this thread,
pre-order traversal can be
> expressed in terms of fold. Post-order is much
the same. But if I'm
> going to go around claiming Proto is a
compiler-construction toolkit, it
> should have the algorithms that people
would expect, not the ones I just
> made up. :-P

Yeah, i already did some
traversals. But you have to think everytime: Did I make it right? Did I miss
some rule in my DSEL grammar?
IMHO, the important difference between a proto
transform and a proto expression traversal is that the transform has to
replicate your grammar, every time. And a traversal simply does not care if
your grammar is right or not. You just want to go over all elements of your
tree. The validity of your DSEL should have been checked one step before
(think of multi-pass compiler).
Joel Falcou showed a technique which, to
some extend is able to deal with the no-repetition part.

Let me give you an
example of a traversal which simply doesn't care if the expression given is
in the language or not (I will present you some transforms I have written
for phoenix3).

First, in pheonix, we want to know: What is the arity of our
expression, or sometimes a little weaker, do we have a nullary, or a n-ary
expression?

This is easily done with a proto transform, I agree.
For arity
calculation we have this transform (notice something? We have a transform
where a simple traversal would be sufficient):
        
        struct
arity
          : proto::or_<
               
proto::when<proto::terminal<proto::_>, mpl::int_<0>()>
              ,
proto::when<
                    proto::function<
                       
proto::terminal<funcwrap<argument> >
                      ,
proto::terminal<env>
                      , proto::_
                    >

                 , mpl::next<proto::_value(proto::_child2)>()
              
 >
              , proto::otherwise<
                    proto::fold<
      
                 proto::_
                      , mpl::int_<0>()
           
          , mpl::max<arity, proto::_state>()
                    >
         
      >
            >
        {};

Yet, very elegant (imho), it is quite
complex and not easily spotted what this code is doing.

With some kind of
post-order traversal and the appropriate visitor this might look simpler. I
have to admit though, i have no idea how such a traversal could look
like.

Eric, in one of your posts you mentioned the potential of phoenix3. I
think, this potential can be highly increased by having some kind of
traversal helper functions, just because I think people are more familiar
with the concepts of traversals and visitors (or, FWIW, iterators) than with
proto transforms. On the other hand, proto transform already are a powerful
tool, perhaps a little too powerful for some simple tasks. Perhaps we have
to educate people for a mind-shift to the direction of proto transforms.

>
And if you think Proto's transforms are hard now, be glad you weren't
>
using Proto v2 in 2006. <shudder>