Proto for Boost mailing list page: Re: [proto] Thoughts on traversing proto expressions and reusing grammar

Subject: Re: [proto] Thoughts on traversing proto expressions and reusing grammar
From: Eric Niebler (eric_at_[hidden])
Date: 2010-10-04 14:45:52

On 10/4/2010 6:49 AM, Thomas Heller wrote:
> Hi,
> 
> I spent some time on thinking how one could make the traversal of a proto 
> expression tree easier. I know want to share my findings with you all, and 
> propose a new addition to proto.
> 
> My first idea was to decouple grammars from transforms, to follow the idea of 
> separation of data and algorithm. 

Data and algorithm are already separate in Proto. "Data" is the
expression to traverse. "Algorithm" is the transform, driven by
pattern-matching in the grammar.

> Currently, a transform is only applyable 
> when a certain expression is matched, this is good and wanted, though 
> sometimes you get yourself into a situation that requires you to reformulate 
> your grammar, and just exchange the transform part.

True. But in my experience, the grammar part is rarely unchanged.

> Let me give you an example of a comma separated list of proto expression you 
> want to treat like an associative sequence:
> 
>     opt1 = 1, opt2 = 2, opt3 = 3
> 
> A proto grammar matching this expression would look something like this:
> 

<snip>

> 
> This code works and everybody is happy, right?
> Ok, what will happen if we want to calculate the number of options we 
> provided in our expression?
> The answer is that we most likely need to repeat almost everything from 
> pack. except the transform part:
> 
>    struct size :
>        or_<
>            when<
>                 comma<pack, spec>
>               , mpl::plus<size(_left), size(_right)>()
>            >
>          , when<
>                spec
>              , mpl::int_<1>()
>            >
>        >
>     {};

This trivial example doesn't make your point, because the "grammar" that
gets repeated ("comma<pack, spec>" and "spec") is such a tiny fraction
of the algorithm.

> Now think of it if you are having a very complicated grammar, c&p the whole 
> grammar, or even just parts of it no fun.

This is true, but it can be alleviated in most (all?) cases by building
grammars in stages, giving names to parts for reusability. For instance,
if "comma<pack, spec>" were actually some very complicated grammar, you
would do this:

   struct packpart:
     : comma<pack, spec>
   {};

And then reuse packpart in both algorithms.

> My solution to this problem is proto::visitor (see attached):
> 
> the signature looks like the following:
> 
>     template <
>         template <typename> class Visitor
>       , template <typename> class Grammar
>     >
>     struct visitor;
> 
> So, visitor is implemented in terms of proto::switch_, What it does is the 
> following: Every tag that is encountered gets dispatched to the Grammar 
> template specified by the user, is that grammar matched the expression, the 
> transform Visitor<Tag> is called.
> 
> Let me demonstrate this with our little example above:
> 
>    template <typename Tag>
>    struct option_grammar // provide a default, don't match anything
>       : proto::not_
>    {};
> 
>    template <template <typename> Visitor>
>    struct option_visitor
>       : proto::visitor<Visitor, option_grammar>
>    {};
> 
>    template <>
>    struct option_grammar<proto::tag::terminal>
>       : proto::terminal<proto::_>
>    {};
> 
>    template <>
>    struct option_grammar<proto::tag::assign>
>       : proto::assign<term, proto::terminal<proto::_> >
>    {};
> 
>    template <>
>    struct option_grammar<proto::tag::comma>
>       : proto::comma<option_grammar, spec >
>    {};
> 
> With the defintions of spec and term from the above, this is the grammar  
> which matches our expressions. the defintion of our two proto transforms now 
> becomes the following:
> 
>    template <typename Tag> struct option_eval : proto::_ {};
>    
>    typedef option_visitor<option_eval> pack;
> 
>    template <>
>    struct option_eval<proto::tag::terminal>
>       : proto::_value
>    {};
> 
>    template <>
>    struct option_eval<proto::tag::assign>
>        : if_<
>            matches<_left, _state>()
>          , pack(_right)
>          , not_found()
>        >
>    {};
> 
>    template <>
>    struct option_eval<proto::tag::comma>
>       : if_<
>           matches<_left(_right), _state>()
>         , pack(_right(_right))
>         , pack(_left)
>       >
>    {};
> 
> How the size calculation would look like is left as an exercise ;)
> 
> I hope the motivation and the need for what i called proto::visitor gets 
> clear :)

I'm not opposed to such a thing being in Proto, but I (personally) don't
feel a strong need. I'd be more willing if I saw a more strongly
motivating example. I believe Joel Falcou invented something similar.
Joel, what was your use scenario?

I've also never been wild for proto::switch_, which I think is very
syntax-heavy. It's needed as an alternative to proto::or_ to bring down
the instantiation count, but it would be nice if visitor has a usage
mode that didn't require creating a bunch of (partial) template
specializations.

I'll also point out that this solution is FAR more verbose that the
original which duplicated part of the grammar. I also played with such
visitors, but every solution I came up with suffered from this same
verbosity problem.

> I hear you people scream: what about compile times, when i define my DSL and 
> different transforms to the proto trees, i most of the time only need a tiny 
> subset of my actual grammar, 

Right, that's my experience. For instance, in Phoenix, the algorithm to
calculate the arity of a lambda expression is only concerned with
placeholders, other terminals, and then everything else. That shares
nothing with the algorithm to evaluate the lambda. This seems more the
rule than the exception.

> won't compile times be even higher with this 
> approach?
> The short answer is no. It seems compile time of proto transforms is not 
> really dependent on the grammar's complexity but on the complexity of the 
> expressions (I did some basic tests for this, if you don't believe me, i can 
> deliver it ;)).

Interesting! Makes sense, actually. I'd like to see your results.

> The next thing i wanted to share is about traversals. While working with 
> this visitor idea i searched for a good and easy way to specify traversals 
> of proto trees. My search was soon over, because, calling transforms 
> recursively is what makes proto traverse the tree. I will try to formulate 
> some traversal orders in one of my next mails.

I think I have some pre- and post-order traversal transforms lying
around somewhere. In fact, I think I posted one to this very list some
time ago.

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