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 16:55:03

On Mon, Oct 4, 2010 at 12:43 PM, Thomas Heller
<thom.heller_at_[hidden]>wrote:

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

OK, but let's be clear: Proto strictly enforces the separation of data and
algorithm. The grammar is not part of the data. We have:

Expression: data
Grammar: schema
Transforms: algorithm

The idea of being able to specify the transforms separately from the grammar
is conceptually very appealing. The grammar is the control flow, the
transform the action. Passing in the transforms to a grammar would be like
passing a function object to a standard algorithm: a very reasonable thing
to do. I don't think we've yet found the right formulation for it, though.
Visitors and tag dispatching are too ugly/hard to use.

I have some ideas. Let me think some.

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

I said "rarely unchanged". That is, you would *have* to write it again in
most cases.

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

Yes, that's very important.

>
> >
> > 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
>
>
Neat! You're getting very good at Proto. :-)

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

We abandoned those early prototypes. Now I can't remember why. Can you?