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

Subject: Re: [proto] So I heard proto make AST ...
From: Eric Niebler (eric_at_[hidden])
Date: 2010-08-11 11:52:30

On 8/11/2010 3:53 AM, Thomas Heller wrote:
> 
> 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. 

That hasn't been my experience. And it's not true for the arity
transform you show below, which doesn't duplicate Phoenix's grammar, so
maybe you mean "every time, except that once". ;-)

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

I don't exactly recall the details of Joel's technique. My experiments
to separate transforms from grammars were largely unsuccessful because
control flow often need pattern matching. I'd like to see alternate designs.

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

Ah, but the control flow of this transform depends on pattern matching
(i.e., the grammar) to dispatch to the correct handler. I'm interested
to see what this arity calculation would look like with a tree traversal.

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

Yah, we're just speculating at this point.

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

No argument.

> Perhaps we have to educate people for a
> mind-shift to the direction of proto transforms.

That shouldn't be necessary. I'm not trying to innovate for the sake of
innovation. If there are well-known idioms for this kind of thing, we
should be using them.

-- 
Eric Niebler
BoostPro Computing
http://www.boostpro.com