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 _______________________________________________ proto mailing list proto@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/proto