mpl::inherit_linearly reuse to produce loki's tuple?
Could inherit_linearly be used to create something like loki's tuple? The name, inherit_linearly, and a very brief look at the code suggests it does something like loki's GenScatterHeirarchy, which was used to create the loki tuples as shown in: http://cvs.sourceforge.net/viewcvs.py/loki-lib/loki/Reference/HierarchyGenerators.h?rev=1.5&view=auto If so, then I was wondering if it would be worth it to reuse inherit_linearly to implement boost's tuple?
Larry Evans wrote:
Could inherit_linearly be used to create something like loki's tuple? The name, inherit_linearly, and a very brief look at the code suggests it does something like loki's GenScatterHeirarchy, which was used to create the loki tuples as shown in:
Yes it can be used that way.
If so, then I was wondering if it would be worth it to reuse inherit_linearly to implement boost's tuple?
I don't think so. What would we gain by it? The successor to Boost.Tuple is described in http://www.boost.org/libs/spirit/fusion/readme.txt. Since fusion tuples are "flat" structures, there's no win in building them by repeated folding of an input sequence. -- Dave Abrahams Boost Consulting http://www.boost-consulting.com
On 12/12/2004 08:44 AM, David Abrahams wrote:
I don't think so. What would we gain by it?
Code reuse and hence easier understanding, especially if very similar code can be used for variant.
The successor to Boost.Tuple is described in http://www.boost.org/libs/spirit/fusion/readme.txt. Since fusion tuples are "flat" structures, there's no win in building them by repeated folding of an input sequence.
I've just looked today briefly at: boost/spirit/fusion/sequence/tuple.hpp and the code in: boost-sandbox/boost/indexed_types/product.hpp I believe is much simpler to understand and doesn't use any preprocessor macros. It uses enumerations instead of unsigned constants to access the tuple elements; however, the 1st version did use constants. There might as well be two versions, which could easily be done. In addition, the same can be said for sum.hpp which uses essentially the same code. I'm guessing that the "flatness" of fusion tuples is done by simply creating different field names with corresponding types by means of preprocessing macros. If so, then deciding on either indexed_types/product.hpp or fusion/tuple.hpp amounts to deciding between proprocessing marcros (-) and flatness(?) vs n-level inheritance heirarchy (-) and easier understanding (+). However, in addition, if variant (i.e. sum) is thrown onto the scales, then I believe easier undestanding wins. In addition, I think sum can be modified by adding: term<...Index>::accept(visitor&a_viz) { if(index() == Index) { a_viz(mpl::int_c<Index>(), project<Index>());} else { term<...,Index-1>::accept(a_viz);} } which is essentially the visitor pattern. What I'm also searching for is something that satisfies: list<T> == sum<null_type, product<T,list<T>*> which, I think, could be used as a replacement for the recursive variants; yet, use sum and product just like or similar to the way the disjoint sum and cartesion product are used in textbooks to define a linked list. Any ideas on how this could be done?
Larry Evans wrote:
On 12/12/2004 08:44 AM, David Abrahams wrote:
I don't think so. What would we gain by it?
Code reuse and hence easier understanding, especially if very similar code can be used for variant.
The successor to Boost.Tuple is described in http://www.boost.org/libs/spirit/fusion/readme.txt. Since fusion tuples are "flat" structures, there's no win in building them by repeated folding of an input sequence.
I've just looked today briefly at:
boost/spirit/fusion/sequence/tuple.hpp
and the code in:
boost-sandbox/boost/indexed_types/product.hpp
I believe is much simpler to understand and doesn't use any preprocessor macros.
Yes, but it is much less efficient for some applications. The fusion design was carefully refined for both runtime and compile-time speed. It is a complete hybrid compile-time/runtime framework just like the MPL is a complete compile-time framework, and it integrates well with MPL (every fusion sequence is also an MPL sequence). This wasn't just done lightly; it's the result of a careful and comprehensive design process.
I'm guessing that the "flatness" of fusion tuples is done by simply creating different field names with corresponding types by means of preprocessing macros. If so, then deciding on either indexed_types/product.hpp or fusion/tuple.hpp amounts to deciding between proprocessing marcros (-) and flatness(?) vs n-level inheritance heirarchy (-) and easier understanding (+).
Understanding the implementation of fusion isn't important, except to its maintainer.
However, in addition, if variant (i.e. sum) is thrown onto the scales, then I believe easier undestanding wins.
Maybe you're not the best judge of easy understanding. What does variant have to do with sum? It's completely non-obvious to me.
In addition, I think sum can be modified by adding:
term<...Index>::accept(visitor&a_viz) { if(index() == Index) { a_viz(mpl::int_c<Index>(), project<Index>());} else { term<...,Index-1>::accept(a_viz);} }
which is essentially the visitor pattern.
You've lost me completely.
What I'm also searching for is something that satisfies:
list<T> == sum<null_type, product<T,list<T>*>
which, I think, could be used as a replacement for the recursive variants; yet, use sum and product just like or similar to the way the disjoint sum and cartesion product are used in textbooks to define a linked list. Any ideas on how this could be done?
still lost. -- Dave Abrahams Boost Consulting http://www.boost-consulting.com
Thanks for your responses, David. On 12/12/2004 08:16 PM, David Abrahams wrote:
Larry Evans wrote: [snip]
I believe is much simpler to understand and doesn't use any preprocessor macros.
Yes, but it is much less efficient for some applications.
OK. I was under the (probably mistaken) assumption that speed of access to the elements was essentially the only speed createria, and I couldn't imagine anything faster than: factor<...,Index>::my_field; where Index the enumeration index (an element of Indices in template < Indices, TypeMap<Indices> product; ) and factor<...,Index> is the Index-th superclass of the product. When I tried to see how fusion tuples did it, I couldn't easily because of the boost/preprocessor macro use. However, since your earlier post said it was a "flat" structure, I assumed the fusion tuple has instance variables: T0 my_0; T1 my_1; ... Tn my_n; generated by macros, and that access methods were generated similarly, i.e. a get<I,tuple> general template and a preprocessor generator of specializations. OOPS, that means the tuple size would have to be available for the preprocessor. So, I looked at tuple.hpp then at tuple_builder.hpp, then at get_tuple_n<n> ... then I gave up :(
The fusion design was carefully refined for both runtime and compile-time speed. It is a complete hybrid compile-time/runtime framework just like the MPL is a complete compile-time framework, and it integrates well with MPL (every fusion sequence is also an MPL sequence).
This is probably one place where indexed_types break down wrt MPL because I didn't consider making each product an MPL sequence.
This wasn't just done lightly; it's the result of a careful and comprehensive design process.
As I and everyone else expected. Could you remember or have a record of the reason's why the non-flat structure and use of indexed supertypes was less than optimal?
I'm guessing that the "flatness" of fusion tuples is done by simply creating different field names with corresponding types by means of preprocessing macros.
Understanding the implementation of fusion isn't important, except to its maintainer.
It might more easily reveal the reasons why the flat implementation is more optimal than ae non-flat one.
However, in addition, if variant (i.e. sum) is thrown onto the scales, then I believe easier undestanding wins.
Maybe you're not the best judge of easy understanding.
I completely agree. I believe it's pretty typical that the coder initially believes his code is easier to understand than reviewers would say. However, I'd guess that one attempting to understand product would simply look at the project<Index> code, then at the factor<,, Index> superclass to find my_field of type TypeMap<Index>::type and understand product. OTOH, as reflected in my previous response terminated with :( , understanding how tuple accessed the selected fields seemed much harder, at least to me. Maybe you could give a brief description of the thought process you went through in understanding product.
What does variant have to do with sum? It's completely non-obvious to me.
Well, maybe that's part of the problem. Are you assuming sum has something to do with numbers. I'd meant it to mean disjoint sum applied to types, and of course variant does model disjoint sum. Is that the reason for the disconnect (of our mutual understanding) ?
In addition, I think sum can be modified by adding:
term<...Index>::accept(visitor&a_viz) { if(index() == Index) { a_viz(mpl::int_c<Index>(), project<Index>());} else { term<...,Index-1>::accept(a_viz);} }
which is essentially the visitor pattern.
You've lost me completely.
Well, I had assumed you'd looked at sum.hpp and could see that term<...Index> was one of the sum superclass's representing the Index-th possible type of the disjoint sum. The accept corresponds to the concrete version of the virtual accept in the Element participant in the visitor pattern. However, there is a typo above which contributed to the confusion, I'm sure. The line: { a_viz(mpl::int_c<Index>(), project<Index>());} should really be: { a_viz.visit(mpl::int_c<Index>(), project<Index>());} i.e. the Visitor participant visits the concrete element by using it's visit member function tailored to the concrete Element type argument, which is supplied by the concrete Elements accept method. IOW, The abstract Element participant corresponds to the sum in sum.hpp. The ConcreateElement participants correspond to the various "terms" in the disjoint sum and I got a working version now. I'll upload to sand-box if you'd think that might help.
What I'm also searching for is something that satisfies:
list<T> == sum<null_type, product<T,list<T>*>
[snip]
like or similar to the way the disjoint sum and cartesion product are used in textbooks to define a linked list. [snip] still lost.
I was trying to convey something similar to the line: rec(X.Unit+(A*X)) in: http://www.cs.cornell.edu/Info/People/sfa/Nuprl/NuprlPrimitives/Xrec_type_do... where Unit corresponds null_type (i.e. void* AFAICT ) and + is disjoint sum operator and * is the cartesian product operator. HTH. Regards, Larry
Larry Evans wrote:
Thanks for your responses, David.
[snips] Well, right now, I only have time to reply to one issue, this issue: flat vs. linear tuples: Whenever I have some more free time (too much to chew), I am writing some docs for fusion. A part of it will be dedicated to a rationale which shall attempt to explain why a flat structure is generally optimal. I did have some tests. The tests were driven 2 years ago when Volodya (I'm CCing him) complained that the mere construction of a cons list based tuples (the original) generated > 10 times code than a flat struct. Ditto to accessing the members. Anyway... that said... I believe the right way to go is to do as STL or MPL did: allow the user to choose the right structure for the job. Quite recently, I've been needing a cons based tuple structure which has certain characteristics that I require. I couldn't reuse fusion's flat structures for that. I am of the opinion now that fusion's tuple should really be called fusion::vector. In addition, other types of fusion sequences should be created. Each with its own properties/tradeoffs. I know this is deviating from the TR1 tuples too much, but I think it's the right way to go. A TR1 tuples interface can simply be added on top of the library, not as a basis of it. Regards, -- Joel de Guzman http://www.boost-consulting.com http://spirit.sf.net
On 12/13/2004 06:20 PM, Joel wrote: [snip]
Whenever I have some more free time (too much to chew), I am writing some docs for fusion. A part of it will be dedicated to a rationale which shall attempt to explain why a flat structure is generally optimal. I did have some tests.
Searching past posts containing tuple showed: http://lists.boost.org/MailArchives/boost/msg23983.php which claims inheritance causes extra padding; hence, this is one advantage of flat vs. inherited structure.
Larry Evans wrote:
On 12/13/2004 06:20 PM, Joel wrote: [snip]
Whenever I have some more free time (too much to chew), I am writing some docs for fusion. A part of it will be dedicated to a rationale which shall attempt to explain why a flat structure is generally optimal. I did have some tests.
Searching past posts containing tuple showed:
http://lists.boost.org/MailArchives/boost/msg23983.php
which claims inheritance causes extra padding; hence, this is one advantage of flat vs. inherited structure.
Another is that (unless you use nonstandard language extensions) only flat structures allow O(1) random access. -- Dave Abrahams Boost Consulting http://www.boost-consulting.com
On 12/23/2004 11:16 AM, David Abrahams wrote: [snip]
Another is that (unless you use nonstandard language extensions) only flat structures allow O(1) random access.
I'm afraid I don't understand. By "access" do you mean access to the elements in the structure? If so, then I don't understand why: r.factor<TypeMap,Index>::my_field where r is the tuple and Index is the field number (or the superclass number), is not O(1) access. Could you explain why? BTW, if the method used in sum is slightly changed (replace max with + when calculating max_size), then the storage can all be moved to the most derived class and all superclasses just contain functions; hence, the padding problem (I guess) is not longer there. This, of course, is at the cost of a little more complicated product::project method.
Larry Evans wrote:
On 12/23/2004 11:16 AM, David Abrahams wrote: [snip]
Another is that (unless you use nonstandard language extensions) only flat structures allow O(1) random access.
I'm afraid I don't understand. By "access" do you mean access to the elements in the structure?
Yes, at compile-time.
If so, then I don't understand why:
r.factor<TypeMap,Index>::my_field
where r is the tuple and Index is the field number (or the superclass number), is not O(1) access. Could you explain why?
I have never seen a tuple type with a nested factor template, so no, I guess I can't.
BTW, if the method used in sum is slightly changed (replace max with + when calculating max_size), then the storage can all be moved to the most derived class and all superclasses just contain functions; hence, the padding problem (I guess) is not longer there. This, of course, is at the cost of a little more complicated product::project method.
I guess you're assuming I've looked at your code again ;-) -- Dave Abrahams Boost Consulting http://www.boost-consulting.com
Larry Evans wrote:
Thanks for your responses, David.
Sure thing.
However, in addition, if variant (i.e. sum) is thrown onto the scales, then I believe easier undestanding wins.
Maybe you're not the best judge of easy understanding.
I completely agree.
You snipped the context. My point was that you managed to confuse me by talking about stuff like sum and product without any introduction to what they were.
I believe it's pretty typical that the coder initially believes his code is easier to understand than reviewers would say.
However, I'd guess that one attempting to understand product would simply look at the project<Index> code, then at the factor<,, Index> superclass to find my_field of type TypeMap<Index>::type and understand product.
???? You're off in some other dimension again. Did I miss all this from an earlier post ???? What is product, project, factor, my_field, and what language is factor<,, Index> ??
OTOH, as reflected in my previous response terminated with :( , understanding how tuple accessed the selected fields seemed much harder, at least to me. Maybe you could give a brief description of the thought process you went through in understanding product.
I didn't. I have no clue what you're talking about.
What does variant have to do with sum? It's completely non-obvious to me.
Well, maybe that's part of the problem. Are you assuming sum has something to do with numbers. I'd meant it to mean disjoint sum applied to types, and of course variant does model disjoint sum. Is that the reason for the disconnect (of our mutual understanding) ?
Maybe. You do seem to be assuming all kinds of background vocabulary I don't have.
In addition, I think sum can be modified by adding:
term<...Index>::accept(visitor&a_viz) { if(index() == Index) { a_viz(mpl::int_c<Index>(), project<Index>());} else { term<...,Index-1>::accept(a_viz);} }
which is essentially the visitor pattern.
You've lost me completely.
Well, I had assumed you'd looked at sum.hpp
What sum.hpp?? -- Dave Abrahams Boost Consulting http://www.boost-consulting.com
On 12/14/2004 02:05 PM, David Abrahams wrote: [snip]
You snipped the context. My point was that you managed to confuse me by talking about stuff like sum and product without any introduction to what they were.
OOPS. Sorry. See below for clarification. [snip]
However, I'd guess that one attempting to understand product would simply look at the project<Index> code, then at the factor<,, Index> superclass to find my_field of type TypeMap<Index>::type and understand product.
???? You're off in some other dimension again. Did I miss all this from an earlier post ????
Yep. http://lists.boost.org/MailArchives/boost/msg76404.php mentions product in boost-sandbox. sum.hpp is in same directory.
What is product, project, factor, my_field, and what language is
factor<,, Index>
??
I'd meant to ,, to signify the 1st two template parameters which weren't important at that point. [snip] HTH, and sorry for the miscommunication. I should learn to repeat important parts of earlier posts :( Regards, Larry
Larry Evans wrote:
However, I'd guess that one attempting to understand product would simply look at the project<Index> code, then at the factor<,, Index> superclass to find my_field of type TypeMap<Index>::type and understand product.
???? You're off in some other dimension again. Did I miss all this from an earlier post ????
Yep. http://lists.boost.org/MailArchives/boost/msg76404.php mentions product in boost-sandbox.
Right. In a different message from where you started to talk about sum. Can you see why I might not have made the connection?
sum.hpp is in same directory.
The fact that you dropped a reference into your message doesn't mean I went and looked at all the files.
What is product, project, factor, my_field, and what language is
factor<,, Index>
??
I'd meant to ,, to signify the 1st two template parameters which weren't important at that point.
[snip]
HTH, and sorry for the miscommunication. I should learn to repeat important parts of earlier posts :(
No sweat. -- Dave Abrahams Boost Consulting http://www.boost-consulting.com
On 12/14/2004 03:50 PM, David Abrahams wrote:
???? You're off in some other dimension again. Did I miss all this from an earlier post ????
Yep. http://lists.boost.org/MailArchives/boost/msg76404.php mentions product in boost-sandbox.
Right. In a different message from where you started to talk about sum. Can you see why I might not have made the connection?
Sure. I'll be more careful next time.
participants (3)
-
David Abrahams -
Joel -
Larry Evans