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. 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 I had code that didn't use Proto, that produced tight code and fast compile times. The challenge was for Eric to beat that or at least come close to its performance. I wanted to take advantage of fusion algorithms to *efficiently* iterate over the sequence. 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. 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. In due time, I'll be using Dan traversal library. 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. I was happy :-) Proto proved it's worth. Oh, there were more disagreement on things big and small. Development happened in an evolutionary manner spanning years. If you guys are interested in what transpired, it's all archived in the Spirit-devel list. I gave him a very tough time :-) The space here won't do justice to what actually happened, nevertheless, I already did my review a long time ago, spaning years. In the end, Eric pulled it all through. I gave him a very tough time :-) - 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. Regards, -- Joel de Guzman http://www.boost-consulting.com http://spirit.sf.net
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
Eric,
Joel de Guzman wrote:
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?
It will be used to transform the data structures (well, currently not the 'structure' itself, but the contents) as generated by a parser. The transformed data items then could be feed back to a generator to create some transformed output. OTOH, I could see the possibility to use Spirit-2 parsers directly with the traversal library. It should be possible and very powerful to use a Spirit-2 (parser) grammar to describe the node types to transform. Regards Hartmut
Hartmut Kaiser wrote:
Joel de Guzman wrote:
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?
It will be used to transform the data structures (well, currently not the 'structure' itself, but the contents) as generated by a parser. The transformed data items then could be feed back to a generator to create some transformed output.
OK, parsing builds a DOM, and the traversal library manipulates the DOM.
OTOH, I could see the possibility to use Spirit-2 parsers directly with the traversal library. It should be possible and very powerful to use a Spirit-2 (parser) grammar to describe the node types to transform.
Not sure I get this part. If the result of the parse is a DOM, then the Spirit grammar is like the schema. So ... you would be annotating your schema with attribute transforms? That would be like semantic actions, except they would be applied to the DOM after the parse completes? -- Eric Niebler Boost Consulting www.boost-consulting.com
Eric, Changed topic to avoid getting off topic :-P
Joel de Guzman wrote:
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?
It will be used to transform the data structures (well, currently not
Hartmut Kaiser wrote: the
'structure' itself, but the contents) as generated by a parser. The transformed data items then could be feed back to a generator to create some transformed output.
OK, parsing builds a DOM, and the traversal library manipulates the DOM.
Exactly.
OTOH, I could see the possibility to use Spirit-2 parsers directly with the traversal library. It should be possible and very powerful to use a Spirit-2 (parser) grammar to describe the node types to transform.
Not sure I get this part. If the result of the parse is a DOM, then the Spirit grammar is like the schema. So ... you would be annotating your schema with attribute transforms? That would be like semantic actions, except they would be applied to the DOM after the parse completes?
The traversal library exposes an interface requiring to specify the 'type' of the nodes to apply a certain action to. OTOH, the types of the DOM generated by Spirit parsers may get fairly complicated. So the idea is to use a Spirit-2 parser grammar to describe the type of the DOM node to modify. This works, because Spirit-2 parsers are fully attributed and any grammar essentially defines the (set of possible) data structure(s) generated by the corresponding parser. Certainly, you won't be able to describe any DOM, but only those generated by a Spirit-2 parser. So the answer to your question is no. There is no need to attribute the schema since the parser described by the grammar already is (implicitly) attributed. Hope this makes sense now. Regards Hartmut
Eric Niebler wrote:
Joel de Guzman wrote:
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?
Nope. But I see no need. A fusion sequence can represent a hierarchy because the elements are heterogeneous. A sequence element can simply be another sequence.
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.
Cool. Actually, in Spirit-2, not all nodes are flattened. So that makes perfect sense; I'm already doing per node flattening in the transforms. Perhaps I can take advantage of this new feature to further simplify Spirit-2?
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.
Yes. And it's always better to deal with it on the sequence level, (not the iterator level) as we found out. Indeed, that's the fundamental idea behind SYB.
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.
Right. Perhaps I was under an obsolete impression :P It might be a good idea to show some new benchmarks on this? Alas, I no longer have the old non-proto code :(
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?
Proto+Fusion+SYB. It seems Hartmut already outlined one plan. I've some more ideas in addition to Hartmut's: 1 Proto+Spirit creates an ET tree from the Spirit grammar and rules. No need to flatten, Spirit stores the ET nodes as-is plus some node specific info (e.g. sequence, alternate tags). 2 Spirit+Fusion+Traversal traverses the ET tree using per-node specific specialized algorithms (e.g. parse/generate for terminals, sequences, alternates, etc) and generates attributes. Traversal deals with the walking strategy (e.g. I want to have a full stride over all sequence elements as if it was flattened). 3 Attributes are fusion-sequences, stl-sequences and variants essentially representing the AST. This AST can again be traversed/transformed by Traversal (e.g. for subsequent passes over the AST like optimizations and actual backend code generation). If this is a bit unclear at the moment, no worries. The ideas are just forming :-) Regards, -- Joel de Guzman http://www.boost-consulting.com http://spirit.sf.net
participants (3)
-
Eric Niebler -
Hartmut Kaiser -
Joel de Guzman