Re: [boost] My Proto Review

From: Eric Niebler (eric_at_[hidden])
Date: 2008-03-25 18:33:58

Joel de Guzman wrote:
> Hi,
> 
> I'm sorry if this is very late. This month has been a whirlwind
> for me. So many things happening.
> 
> ***I vote to accept Proto.***

Thanks.

> - What is your evaluation of the design?
> 
> Proto is very well designed. I've seen it progress through the
> years. It's very mature and stable now. I've been using it as
> early as 2005 as a Spirit-2 core library. Spirit-2's design
> and evolution somehow influenced Proto's design. I'm very happy
> with Eric's design decisions.
> 
> Some history...
> 
> Eric and I had our share of squabbles in the past ;-) related
> to how I expected Proto to be. I knew from the start that I
> needed something like it. Joao Abecasis, a Spirit developer,
> started one like it, from my urging. Fusion was developed,
> in part, due to the need for manipulation of heterogeneous
> data structures, specifically for spirit: syntax trees.

But there still isn't a Fusion tree data structure, is there?

> I recall that our biggest disagreement, and one that we
> resolved soon enough, was my need for flattened sequences.
> Eric insisted on presenting the results with no flattening,
> I wanted flattening. For example, I wanted:
> 
>      a >> b >> c >> d
> 
> to be a flattened fusion sequence, not a tree. I was reluctant
> to have Spirit go through a 2-step process that necessitated
> a conversion from a tree to a fusion-sequence:
> 
>      proto-tree-->fusion-sequence

All things come around again. With proto domains and generators, there 
is now a way to get the incremental flattening you originally wanted -- 
within a domain, where it belongs. But as I was able to show, the 
current solution in Spirit-2 -- letting proto build the tree and 
flattening it all at once -- actually performs better.

<snip>

> At first, this lead to the development of segmented fusion
> iterators. Eric actually implemented this:
> http://lafstern.org/matt/segmented.pdf into Fusion!
> It was OK and efficient at runtime. Unfortunately, compile
> time suffered considerably.

To be clear, the compile time of a segmented Fusion algorithm with a 
segmented Fusion data structure is very good. It's when you use a 
non-segmented algorithm with a segmented data structure that the compile 
times get bad -- because you need to flatten the sequence first. Any 
attempt to use an ordinary Fusion algorithm with a hierarchical data 
structure will have this problem.

The biggest problem with segmented fusion is the need to implement 
segmented variants of all the algorithms. That's a non-trivial undertaking.

> Our endless discussions culminated with:
> 
>      http://article.gmane.org/gmane.comp.parsers.spirit.devel/2765
> 
> Seems some folks were tuning in to our discussions.
> The C++ version of "Scrap Your Boiler Plate", a very
> powerful, well studied and widely used design pattern
> for generic traversal from the Haskell world:
> http://portal.acm.org/citation.cfm?id=1159861.1159871
> references Eric's post above.
> 
> So far so good, yet, SYB ("Scrap Your Boiler Plate")
> was not available in a mature form in C++ yet. This then,
> again, lead to Dan Marsden's proposed traversal library.
> 
> What Eric ended up doing was to provide a zero-overhead
> tree structure that's converted very efficiently to a
> flattened fusion sequence. It was as fast as my non-proto
> Spirit2 implementation and with some compile time performance
> hit.

I would be surprised if the flatten-all-at-once approach causes longer 
compile times than the flatten-incrementally approach. I remember 
showing that, since flattening incrementally amounts to pushing at the 
back of a cons list, it causes more templates to be instantiated than 
just building the cons list all at once back-to-front when all the 
elements are known.

If the proto-ified version of Spirit-2 has longer compile times than the 
non-proto-ified version, I suspect the problem is elsewhere.

> In due time, I'll be using Dan traversal library.

With Proto? Or as a replacement for Proto? How do you intend to use 
Dan's code in Spirit-2?

> At any
> rate, Eric's intuition to not flatten the trees is
> dead-on correct. It's the right approach. I'm glad that
> it influenced interesting solutions to interesting
> generic programming problems.

<snip>

> In the end, Eric
> pulled it all through. I gave him a very tough time :-)

Not *so* rough.

> - What is your evaluation of the implementation?
> 
> A+
> 
> - What is your evaluation of the documentation?
> 
> A+
> 
> - What is your evaluation of the potential usefulness of the library?
> 
> Oh man!
> 
> - Did you try to use the library?  With what compiler?  Did you have any
> problems?
> 
> Yes. With all compilers required by Spirit. No problems.
> 
> - How much effort did you put into your evaluation? A glance? A quick
> reading? In-depth study?
> 
> Many years of study; from its inception.
> 
> - Are you knowledgeable about the problem domain?
> 
> Yes. very.

Thanks,

-- 
Eric Niebler
Boost Consulting
www.boost-consulting.com