Re: [boost] [review] Fusion review begins
- What is your evaluation of the design?
Very nice. Joel and Dan have put a lot of thought into the design of Fusion. Lazy heterogeneous sequences are very powerful. As Joel and I have discussed extensively in recent weeks, support for segmented data structures would make traversal of some sorts of sequences much more efficient. Joel seems interested and committed to making these changes, and I'm happy to help. Like Dave, I'd like to see some more thought put into the extensibility mechanism. Defining new Fusion iterators is a bit painful, and something like a Fusion iterator adaptor library might be very useful. That might be possible if the metafunctions were all part of the same struct. I'd be satisfied with an analysis that breaks down the pros and cons of such an approach. Some miscelaneous questions: - Why is there a traits::tag_of<> for extracting the sequence tag, but no corresponding metafunction for extracting the iterator's tag? - Why do I have to declare both my sequence's category *and* my iterator's category? Won't there always be an obvious relation between them? - how is is_view<> used? The Extensibility section says I have to specialize it, but I don't think it says anywhere why. - Where is as_tuple? I need it!
- What is your evaluation of the implementation?
Top notch. Clean and very granular headers. The directory structure could be a bit simpler, but that's a nit.
- What is your evaluation of the documentation?
I confess, I haven't looked in detail. I did notice, however, that on extension.html, there is a reference to the non-existant file <boost/fusion/core/tag_of_fwd.hpp>. This should be <boost/fusion/support/tag_of_fwd.hpp>
- What is your evaluation of the potential usefulness of the library?
I've already found Fusion very useful.
- Did you try to use the library? With what compiler?
Yes, with VC7.1, VC8 and gcc 3.4.
Did you have any problems?
None of significance.
- How much effort did you put into your evaluation? A glance? A quick reading? In-depth study?
I've studied Fusion in-depth, and even contributed to its developement.
- Are you knowledgeable about the problem domain?
Very. I've used Fusion in xpressive and proto, and I've spent a lot of time in the past few weeks noodling about in Fusion's internals. I see room for improvement, but not much. Fusion is essential infrastructure. I vote to accept. -- Eric Niebler Boost Consulting www.boost-consulting.com
Eric Niebler wrote:
- What is your evaluation of the design?
Very nice. Joel and Dan have put a lot of thought into the design of Fusion. Lazy heterogeneous sequences are very powerful. As Joel and I have discussed extensively in recent weeks, support for segmented data structures would make traversal of some sorts of sequences much more efficient. Joel seems interested and committed to making these changes, and I'm happy to help.
I think the segmentation idea is very good. I love the direction that this is leading to. Thank you very much for spear-heading the effort.
Like Dave, I'd like to see some more thought put into the extensibility mechanism. Defining new Fusion iterators is a bit painful, and something like a Fusion iterator adaptor library might be very useful. That might be possible if the metafunctions were all part of the same struct. I'd be satisfied with an analysis that breaks down the pros and cons of such an approach.
As I mentioned in my reply to Eric Friedman, the extensibility mechanism is no more difficult than extending MPL. It just so happens that the extension section gave a not so trivial example (that of a random access and associative sequence). Anyway, I do agree that a better extension mechanism, if one can be found, would be a definite boon to using Fusion.
Some miscelaneous questions:
- Why is there a traits::tag_of<> for extracting the sequence tag, but no corresponding metafunction for extracting the iterator's tag?
traits::tag_of<> should be usable for iterators too. The docs should make that clear.
- Why do I have to declare both my sequence's category *and* my iterator's category? Won't there always be an obvious relation between them?
Iterators do not have the exact same categories as sequences. For example, iterators do not have the associative category.
- how is is_view<> used? The Extensibility section says I have to specialize it, but I don't think it says anywhere why.
I'll discuss this in another post.
- Where is as_tuple? I need it!
It resides in the future :)
- What is your evaluation of the implementation?
Top notch. Clean and very granular headers. The directory structure could be a bit simpler, but that's a nit.
Thanks! What directory structure do you have in mind? [...]
I vote to accept.
Thank you very much! Regards, -- Joel de Guzman http://www.boost-consulting.com http://spirit.sf.net
Joel de Guzman wrote:
Eric Niebler wrote:
- What is your evaluation of the design?
Very nice. Joel and Dan have put a lot of thought into the design of Fusion. Lazy heterogeneous sequences are very powerful. As Joel and I have discussed extensively in recent weeks, support for segmented data structures would make traversal of some sorts of sequences much more efficient. Joel seems interested and committed to making these changes, and I'm happy to help.
I think the segmentation idea is very good. I love the direction that this is leading to. Thank you very much for spear-heading the effort.
My pleasure. FYI - I now have a general implementation of fusion::segmented_iterator<>, so we can proceed with our simplified segmentation interface.
Like Dave, I'd like to see some more thought put into the extensibility mechanism. Defining new Fusion iterators is a bit painful, and something like a Fusion iterator adaptor library might be very useful. That might be possible if the metafunctions were all part of the same struct. I'd be satisfied with an analysis that breaks down the pros and cons of such an approach.
As I mentioned in my reply to Eric Friedman, the extensibility mechanism is no more difficult than extending MPL. It just so happens that the extension section gave a not so trivial example (that of a random access and associative sequence). Anyway, I do agree that a better extension mechanism, if one can be found, would be a definite boon to using Fusion.
I am imagining an interface similar to Boost.Iterator's iterator_facade<>. That would make it possible to easily adapt the implementation from another fusion iterator. The Fusion filter_view and transform_view can be build on top just as Boost.Iterator's filter_iterator and transform_iterator are built on top of iterator_facade<>.
Some miscelaneous questions:
- Why is there a traits::tag_of<> for extracting the sequence tag, but no corresponding metafunction for extracting the iterator's tag?
traits::tag_of<> should be usable for iterators too. The docs should make that clear.
Nope. There's code like this, from fusion/iterator/next.hpp: namespace result_of { template <typename Iterator> struct next { typedef typename extension::next_impl<typename Iterator::ftag>:: template apply<Iterator>::type type; }; } You're accessing the nested Iterator::ftag directly. You should be using the tag_of<> metafunction here, otherwise specializing it will have no effect.
- Why do I have to declare both my sequence's category *and* my iterator's category? Won't there always be an obvious relation between them?
Iterators do not have the exact same categories as sequences. For example, iterators do not have the associative category.
But you have an is_associative<> metafunction. Why do you need an associative sequence category? IMO, sequences shouldn't have catogories. Iterators should have categories, and sequences have iterators. Extra information, like whether the sequence is associative, should be provided by specializing external traits, like is_associative. Otherwise, you have duplication. (Eg., of course a forward sequence has forward iterators!)
- how is is_view<> used? The Extensibility section says I have to specialize it, but I don't think it says anywhere why.
I'll discuss this in another post.
- Where is as_tuple? I need it!
It resides in the future :)
- What is your evaluation of the implementation?
Top notch. Clean and very granular headers. The directory structure could be a bit simpler, but that's a nit.
Thanks! What directory structure do you have in mind?
Less nesting. IMO there is no reason for there to be iteration/, query/, and transformation/ sub-directories under algorithm. Just put all the algorithms in algorithm/. IMO, all the subdirectories under sequence/ are unnecessary, too. I've had to grep through the tree structure to find the header I'm looking for. That's crazy. If you don't want to flatten the tree structure (seems we spend a lot of time talking about flattening trees ;-), I like the approach taken by Boost.PP. There is a tree structure, but also top-level headers that simply #include the correct header from the sub-directory. That way, if I want to use boost::fusion::begin() I can just #include <boost/fusion/begin.hpp> without needing to know that it actually lives at <boost/fusion/sequence/intrinsic/begin.hpp>. -- Eric Niebler Boost Consulting www.boost-consulting.com
On 05/10/2006 12:34 PM, Eric Niebler wrote:
Joel de Guzman wrote:
Eric Niebler wrote:
[snip]
I think the segmentation idea is very good. I love the direction that this is leading to. Thank you very much for spear-heading the effort.
My pleasure. FYI - I now have a general implementation of fusion::segmented_iterator<>, so we can proceed with our simplified segmentation interface.
Hi Eric, Could you give us some idea of what a segmented_iterator is or post your general implementation. I'm sure others are curious too. -regards, Larry
Larry Evans wrote:
On 05/10/2006 12:34 PM, Eric Niebler wrote:
Joel de Guzman wrote:
I think the segmentation idea is very good. I love the direction that this is leading to. Thank you very much for spear-heading the effort.
My pleasure. FYI - I now have a general implementation of fusion::segmented_iterator<>, so we can proceed with our simplified segmentation interface.
Hi Eric,
Could you give us some idea of what a segmented_iterator is or post your general implementation. I'm sure others are curious too.
Joel and I have been having an extensive discussion on spirit-devel about support in Fusion for segmented sequence. See Matt Austern's "Segmented Iterators and Hierarchial Algorithms": http://lafstern.org/matt/segmented.pdf. Feel free to read the last few weeks of http://news.gmane.org/gmane.comp.parsers.spirit.devel to bring yourself up to speed. The short story is that many Fusion sequences are segmented, like fusion::joint_view. Some day we'll have fusion trees, which will be segmented out the wazoo. Making them look non-segmented so that the algorithms can work with them is inefficient, not to mention rather tricky. My proposal is to make Fusion algorithms hierarchical, so they can work efficiently with segmented data structures. Rather that using Matt Austern's formulation, I've come up with a much simpler interface based not on segmented iterators, but rather on segmented sequences. This works great until you need to return an iterator into a segmented sequence, as fusion::find must do. Then you need a segmented iterator. But it's possible to implement fusion::segmented_iterator<> just once so that it works with any segmented sequence, and a segmented_iterator_range<> that reconstitutes a segmented sequence from two segmented iterators. -- Eric Niebler Boost Consulting www.boost-consulting.com
Hi Eric, Eric Niebler wrote:
[...] My proposal is to make Fusion algorithms hierarchical, so they can work efficiently with segmented data structures. Rather that using Matt Austern's formulation, I've come up with a much simpler interface based not on segmented iterators, but rather on segmented sequences.
What's wrong with Austern's interface? I've both implemented and used it and found it both simple and powerful. Then again I didn't deal with anything the complexity of fusion. -- Giovanni P. Deretta
Giovanni P. Deretta wrote:
Hi Eric,
Eric Niebler wrote:
[...]
My proposal is to make Fusion algorithms hierarchical, so they can work efficiently with segmented data structures. Rather that using Matt Austern's formulation, I've come up with a much simpler interface based not on segmented iterators, but rather on segmented sequences.
What's wrong with Austern's interface? I've both implemented and used it and found it both simple and powerful. Then again I didn't deal with anything the complexity of fusion.
It's more complicated than it needs to be for the purposes of Fusion. A strightforward translation of Austern's segmented_iterator_traits<> interface into Fusion would require the following new Fusion primitives (which all operate on Fusion iterator): is_segmented segment local segment_begin segment_end These are necessary because the STL algorithm interface deals with iterators. Fusion's algorithms deal with sequences, however. The proposed segmentation interface for Fusion requires only the following primitives (which operate on Fusion sequences): is_segmented segments where segments(seq) returns seq's segments as a sequence of sequences. This makes it vastly simpler to satisfy the requirements for a segmented Fusion sequence. For example, I implemented segmented Fusion sequence support for a Fusion tree data structure both in Austern's interface and the new one. With Austern's interface, it look ~200 lines of code. With the proposed interface, it took ~50. The implementation of the segmented Fusion algorithms gets dramatically simpler, too. -- Eric Niebler Boost Consulting www.boost-consulting.com
Giovanni P. Deretta wrote:
Hi Eric,
Eric Niebler wrote:
[...] My proposal is to make Fusion algorithms hierarchical, so they can work efficiently with segmented data structures. Rather that using Matt Austern's formulation, I've come up with a much simpler interface based not on segmented iterators, but rather on segmented sequences.
What's wrong with Austern's interface? I've both implemented and used it and found it both simple and powerful. Then again I didn't deal with anything the complexity of fusion.
There's nothing wrong with Austern's interface. It's just that Eric took advantage of 1) the heterogeneous nature of sequences and 2) the way Fusion uses lazy views which are essentially segmented to begin with. Hence, with 1 and 2 to our advantage, the interface and implementation was significantly simplified. I have a hunch that Fusion can simplify non-fusion segmented mechanisms as well (matrices?, arrays?), but I'll leave it at that for now. Regards, -- Joel de Guzman http://www.boost-consulting.com http://spirit.sf.net
Eric Niebler wrote:
Joel de Guzman wrote:
Eric Niebler wrote:
- What is your evaluation of the design?
Very nice. Joel and Dan have put a lot of thought into the design of Fusion. Lazy heterogeneous sequences are very powerful. As Joel and I have discussed extensively in recent weeks, support for segmented data structures would make traversal of some sorts of sequences much more efficient. Joel seems interested and committed to making these changes, and I'm happy to help.
I think the segmentation idea is very good. I love the direction that this is leading to. Thank you very much for spear-heading the effort.
My pleasure. FYI - I now have a general implementation of fusion::segmented_iterator<>, so we can proceed with our simplified segmentation interface.
Awesome!
Like Dave, I'd like to see some more thought put into the extensibility mechanism. Defining new Fusion iterators is a bit painful, and something like a Fusion iterator adaptor library might be very useful. That might be possible if the metafunctions were all part of the same struct. I'd be satisfied with an analysis that breaks down the pros and cons of such an approach.
As I mentioned in my reply to Eric Friedman, the extensibility mechanism is no more difficult than extending MPL. It just so happens that the extension section gave a not so trivial example (that of a random access and associative sequence). Anyway, I do agree that a better extension mechanism, if one can be found, would be a definite boon to using Fusion.
I am imagining an interface similar to Boost.Iterator's iterator_facade<>. That would make it possible to easily adapt the implementation from another fusion iterator. The Fusion filter_view and transform_view can be build on top just as Boost.Iterator's filter_iterator and transform_iterator are built on top of iterator_facade<>.
Same thinking here. I think I just concocted a solution before I went to bed last night.
Some miscelaneous questions:
- Why is there a traits::tag_of<> for extracting the sequence tag, but no corresponding metafunction for extracting the iterator's tag?
traits::tag_of<> should be usable for iterators too. The docs should make that clear.
Nope. There's code like this, from fusion/iterator/next.hpp:
namespace result_of { template <typename Iterator> struct next { typedef typename extension::next_impl<typename Iterator::ftag>:: template apply<Iterator>::type type; }; }
That is clearly wrong. Noted.
You're accessing the nested Iterator::ftag directly. You should be using the tag_of<> metafunction here, otherwise specializing it will have no effect.
Right.
- Why do I have to declare both my sequence's category *and* my iterator's category? Won't there always be an obvious relation between them? Iterators do not have the exact same categories as sequences. For example, iterators do not have the associative category.
But you have an is_associative<> metafunction. Why do you need an associative sequence category? IMO, sequences shouldn't have catogories. Iterators should have categories, and sequences have iterators. Extra information, like whether the sequence is associative, should be provided by specializing external traits, like is_associative. Otherwise, you have duplication. (Eg., of course a forward sequence has forward iterators!)
Hmmm... You have a point.
Thanks! What directory structure do you have in mind?
Less nesting. IMO there is no reason for there to be iteration/, query/, and transformation/ sub-directories under algorithm. Just put all the algorithms in algorithm/. IMO, all the subdirectories under sequence/ are unnecessary, too. I've had to grep through the tree structure to find the header I'm looking for. That's crazy.
If you don't want to flatten the tree structure (seems we spend a lot of time talking about flattening trees ;-), I like the approach taken by Boost.PP. There is a tree structure, but also top-level headers that simply #include the correct header from the sub-directory. That way, if I want to use boost::fusion::begin() I can just #include <boost/fusion/begin.hpp> without needing to know that it actually lives at <boost/fusion/sequence/intrinsic/begin.hpp>.
Yes, that's part of the plan, in fact. There will be a header directory where all the forwarding headers can be found. Cheers! -- Joel de Guzman http://www.boost-consulting.com http://spirit.sf.net
Joel de Guzman wrote:
Eric Niebler wrote:
- how is is_view<> used? The Extensibility section says I have to specialize it, but I don't think it says anywhere why.
I'll discuss this in another post.
I want to discuss this separately because I am re-thinking this. The issue, again, is how a view holds a sequence. Holding it by reference is the sensible answer. However, views are typically quite small and can be passed on as values. That way, we don't have the issue of dangling references. For example, for complex views, you'd want to construct them piecemeal using local variables. For example, here's the "insert" function: typedef result_of::insert< Sequence const, Position, T> result_of; typedef typename result_of::left_type left_type; typedef typename result_of::right_type right_type; typedef typename result_of::single_view single_view; typedef typename result_of::left_insert_type left_insert_type; typedef typename result_of::type result; left_type left( fusion::begin(seq), convert_iterator<Position>::call(pos)); right_type right( convert_iterator<Position>::call(pos), fusion::end(seq)); single_view insert(x); left_insert_type left_insert(left, insert); return result(left_insert, right); This is only possible if left, right, insert and left_insert, holds its views *by value*. Otherwise, we'll have dangling references pointing to stale objects in the stack that are dead after we exit the function. So, as a matter of convenience, views in Fusion-2 are held by value. Yet, again, I am not quite sure if this is a good thing or not. It requires us to differentiate between a view and a container. Containers are always held by reference. Regards, -- Joel de Guzman http://www.boost-consulting.com http://spirit.sf.net
participants (4)
-
Eric Niebler -
Giovanni P. Deretta -
Joel de Guzman -
Larry Evans