Boost logo

Boost :

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


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


> At first, this lead to the development of segmented fusion
> iterators. Eric actually implemented this:
> 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:
> 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:
> 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.


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


Eric Niebler
Boost Consulting

Boost list run by bdawes at, gregod at, cpdaniel at, john at