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