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: Thomas Heller (thom.heller_at_[hidden])
Date: 2010-10-04 15:43:05

On Mon, Oct 4, 2010 at 8:45 PM, Eric Niebler <eric_at_[hidden]> wrote:
> 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.

True, but you can only attach one grammar to one transform. Thus for
every transformation you want to make, you need (in theory) replicate
your grammar, see further down that this is not the case in real life.

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

Yep, unchanged, and therefore you don't want to write it again.

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

Right, this example does not show the full potential.

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

Right, that also works!

<snip>

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

Ok, point taken. The partial specializations is also something i don't
like. I thought about
doing the same as you did with contexts (tag as parameter to operator() calls),
but decided against it, cause you would end up with an enormous set of
operator()
overloads. With this solution you end up with an enormous set of
classes, but this
solution is extendable (even from the outside), both from the grammar
part and the transform part. Meaning you can add new tags without
changing th intrinsics of your other grammars/transforms.

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

Ok, the verbosity is a problem, agreed. I invented this because of
phoenix, actually. As a use case i wrote a small prototype with a
constant folder:
http://github.com/sithhell/boosties/blob/master/proto/libs/proto/test/phoenix_test.cpp

Note that the phoenix grammar could end up growing very complex! But
users should still be able to add their own tags for their own
expressions. I decided to propose the visitor because Joel Falcou
showed interest in it (Because he invented something similiar for NT2,
remember one of the first prototypes for phoenix3? They were actually
based on the same concepts).

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

Sure, give me some time, until tomorrow.