[geometry] view_as concept casting
There is a clear need for concept casting in a generic geometry type system. Certain geometry concepts imply that an invariant in enforced by a type that models the concept. For some types that invariant is not enforced, but may be true some of the time, and can be checked. Rather than copying the data over to a type that enforces the invariant in order to use a generic API that requires it, it is more convenient to be able to be able view the object as enforcing the invariant. For this purpose, I implemented the view_as function for conceptual casting. //view_of can be specialized or partially specialized as needed template <typename ConceptT, typename T> struct view_of { const T& t_; view_of(const T& t) : t_(t) {} //implements an API that models ConceptT //in terms of T's interface }; template <typename ConceptT, typename T> view_of<ConceptT, T> view_as(const T& obj) { return view_of<ConceptT, T>(obj); } One example of how this could be used is a polygon can be a rectangle, and if so, can be viewed as a rectangle. if(is_rectangle(poly) && equivalent(view_as<rectangle_concept>(poly), rect)) { do_something_with(poly); } else { do_something_else_with(poly); } In the above example, the equivalence check is executed only if the polygon is known to be a rectangle at run time. This is helpful, because while overloads of equivalent that accepts polygon and rectangle as well as rectangle and polygon could be implemented, as the number of types in the system grows, the number of such overloads would grow quadraticly. However, one overload that takes any object that is not a rectangle, checks at runtime if it is a rectangle and views it as a rectangle would suffice for all combinations: template <not_rectangle_type, rectangle_type> //concept checking boilerplate around bool return type goes here equivalent(const not_rectangle_type& obj1, const rectangle_type& obj2) { return is_rectangle(obj1) && equivalent(view_as<rectangle_concept(obj1), obj2); } Another example is that many legacy type systems will have one polygon class that doesn't enforce many invariants and is used everywhere. It depends upon the developer to know (or check) that some invariant (such as rectilinearity) is true when they use it. This polygon type cannot model rectilinear polygon concept, but needs to be conditionally viewed as rectilinear to be used with a generic API that requires type safety wrt. rectilinearity. Is this an issue that the other geometry authors have addressed? Regards, Luke
Hi Luke, I don't think we have addressed exactly the same thing, but something similar. We check geometry types at compile time, indeed using a generic geometry type system. Area calculation, for example, is implemented differently for box (rectangle) than for polygon. So we have two overloads: template <typename B> double area(const B& box) {...} template <typename P> double area(const P& polyon) {...} This alone leads to ambiguities of course. Therefore we use enable_if: template <typename B> double area(const B& box, typename boost::enable_if_c<geometry_type<B>::type == TYPE_BOX>::type* = 0) template <typename P> double area(const P& polyon, typename boost::enable_if_c<geometry_type<P>::type == TYPE_POLYGON>::type* = 0) This works perfectly and distinguishes all geometry types at compile time, as long as the library or the developer provides the meta function geometry_type<T>::type which is currently implemented as an enumeration of TYPE_POINT, etc. Furthermore, you mention: "concept checking boilerplate around bool return type goes here". We've encountered problems with the concept checking on return types. The combination of BCCL and overloads based on SFINAE gives compiler problems here. We therefore use BOOST_CONCEPT_REQUIRES instead of _ASSERT in such cases. (We introduced the geometry type meta function since our preview3, it is planned to be published this month). Regards, Barend Simonson, Lucanus J wrote:
There is a clear need for concept casting in a generic geometry type system <... snipped>
on Thu Jan 08 2009, Barend Gehrels <barend-AT-geodan.nl> wrote:
Hi Luke,
I don't think we have addressed exactly the same thing, but something similar. We check geometry types at compile time, indeed using a generic geometry type system. Area calculation, for example, is implemented differently for box (rectangle) than for polygon. So we have two overloads:
template <typename B> double area(const B& box) {...} template <typename P> double area(const P& polyon) {...}
This alone leads to ambiguities of course. Therefore we use enable_if: template <typename B> double area(const B& box, typename boost::enable_if_c<geometry_type<B>::type == TYPE_BOX>::type* = 0) template <typename P> double area(const P& polyon, typename boost::enable_if_c<geometry_type<P>::type == TYPE_POLYGON>::type* = 0)
This works perfectly and distinguishes all geometry types at compile time, as long as the library or the developer provides the meta function geometry_type<T>::type which is currently implemented as an enumeration of TYPE_POINT, etc.
Seems like you might be better off using tag dispatching... or something like http://article.gmane.org/gmane.comp.lib.boost.devel/120718 http://article.gmane.org/gmane.comp.lib.boost.devel/120728
Furthermore, you mention: "concept checking boilerplate around bool return type goes here". We've encountered problems with the concept checking on return types. The combination of BCCL and overloads based on SFINAE gives compiler problems here. We therefore use BOOST_CONCEPT_REQUIRES instead of _ASSERT in such cases.
I think you mean the opposite, right? -- Dave Abrahams BoostPro Computing http://www.boostpro.com
Hi David, Thanks for your suggestions. David Abrahams wrote:
template <typename P> double area(const P& polyon, typename boost::enable_if_c<geometry_type<P>::type == TYPE_POLYGON>::type* = 0)
This works perfectly and distinguishes all geometry types at compile time, as long as the library or the developer provides the meta function geometry_type<T>::type which is currently implemented as an enumeration of TYPE_POINT, etc.
Seems like you might be better off using tag dispatching... or something like
http://article.gmane.org/gmane.comp.lib.boost.devel/120718 http://article.gmane.org/gmane.comp.lib.boost.devel/120728
You are right. The system using enable_if_c works and is recommended by the boost doc of enable_if :-). (quote: The enable_if family of templates is a set of tools to allow a function template or a class template specialization to include or exclude itself from a set of matching functions or specializations based on properties of its template arguments) But tag dispatching works perfectly as well and I see that there are more advantages.
We therefore use BOOST_CONCEPT_REQUIRES instead of _ASSERT in such cases.
I think you mean the opposite, right?
Sure, the opposite, sorry for the mistake. Regards, Barend
-----Original Message----- From: boost-bounces@lists.boost.org [mailto:boost-bounces@lists.boost.org] On Behalf Of Barend Gehrels Sent: Thursday, January 08, 2009 6:31 AM To: boost@lists.boost.org Subject: Re: [boost] [geometry] view_as concept casting Hi Luke, I don't think we have addressed exactly the same thing, but something similar. We check geometry types at compile time, indeed using a generic geometry type system. Area calculation, for example, is implemented differently for box (rectangle) than for polygon. So we have two overloads: template <typename B> double area(const B& box) {...} template <typename P> double area(const P& polyon) {...} This alone leads to ambiguities of course. Therefore we use enable_if: template <typename B> double area(const B& box, typename boost::enable_if_c<geometry_type<B>::type == TYPE_BOX>::type* = 0) template <typename P> double area(const P& polyon, typename boost::enable_if_c<geometry_type<P>::type == TYPE_POLYGON>::type* = 0) This works perfectly and distinguishes all geometry types at compile time, as long as the library or the developer provides the meta function geometry_type<T>::type which is currently implemented as an enumeration of TYPE_POINT, etc. Furthermore, you mention: "concept checking boilerplate around bool return type goes here". We've encountered problems with the concept checking on return types. The combination of BCCL and overloads based on SFINAE gives compiler problems here. We therefore use BOOST_CONCEPT_REQUIRES instead of _ASSERT in such cases. (We introduced the geometry type meta function since our preview3, it is planned to be published this month). Regards, Barend Simonson, Lucanus J wrote:
There is a clear need for concept casting in a generic geometry type system <... snipped>
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Barend wrote:
Furthermore, you mention: "concept checking boilerplate around bool return type goes here". We've encountered problems with the concept checking on return types. The combination of BCCL and overloads based on SFINAE gives compiler problems here. We therefore use BOOST_CONCEPT_REQUIRES instead of _ASSERT in such cases.
What compiler problems specifically? I don't use BCCL for concept checking, and should have said SFINAE meta-programming boilerplate instead. By the way, I wrote my own true false types: struct gtl_yes{}; struct gtl_no{}; that I use for meta-programming logic, but I didn't quite feel right about it. Library authors often create their own such types, and this becomes a source of incompatibility. A user of two libraries that each define their own true/false types that wants to meta-program on top of both will find the task awkward. Having a boost header file that everyone is supposed to include that defines universal boost::true_type and boost::false_type seems like a good idea, and I've seen people push in that direction on this list for a while, but I don't think it is the best solution. It would be better to instead have a convention that void is false type and all other types are true. Similar to how zero is false and all non-zero integers are true. All meta-programming libraries that follow such a convention are compatible with each other without the need for shared dependency. I would then define my true false types thusly: struct gtl_yes{}; typedef void gtl_no; What do others who have defined their own true/false types or used those defined in boost think about such a convention? Is it backward compatible to change false_type definitions to typedef void to make such a convention feasible? Regard, Luke
AMDG Simonson, Lucanus J wrote:
What compiler problems specifically? I don't use BCCL for concept checking, and should have said SFINAE meta-programming boilerplate instead.
By the way, I wrote my own true false types:
struct gtl_yes{}; struct gtl_no{};
that I use for meta-programming logic, but I didn't quite feel right about it. Library authors often create their own such types, and this becomes a source of incompatibility. A user of two libraries that each define their own true/false types that wants to meta-program on top of both will find the task awkward. Having a boost header file that everyone is supposed to include that defines universal boost::true_type and boost::false_type seems like a good idea, and I've seen people push in that direction on this list for a while, but I don't think it is the best solution.
These have existed for a long time. http://www.boost.org/libs/type_traits/doc/html/boost_typetraits/reference/in... http://www.boost.org/libs/mpl/doc/refmanual/bool.html
It would be better to instead have a convention that void is false type and all other types are true. Similar to how zero is false and all non-zero integers are true. All meta-programming libraries that follow such a convention are compatible with each other without the need for shared dependency. I would then define my true false types thusly:
struct gtl_yes{}; typedef void gtl_no;
What do others who have defined their own true/false types or used those defined in boost think about such a convention?
Please, no. The MPL/TypeTraits solution works fine and is easier to work with.
Is it backward compatible to change false_type definitions to typedef void to make such a convention feasible?
No. In Christ, Steven Watanabe
on Thu Jan 08 2009, "Simonson, Lucanus J" <lucanus.j.simonson-AT-intel.com> wrote:
Barend wrote:
Furthermore, you mention: "concept checking boilerplate around bool return type goes here". We've encountered problems with the concept checking on return types. The combination of BCCL and overloads based on SFINAE gives compiler problems here. We therefore use BOOST_CONCEPT_REQUIRES instead of _ASSERT in such cases.
What compiler problems specifically? I don't use BCCL for concept checking, and should have said SFINAE meta-programming boilerplate instead.
By the way, I wrote my own true false types:
struct gtl_yes{}; struct gtl_no{};
that I use for meta-programming logic, but I didn't quite feel right about it. Library authors often create their own such types, and this becomes a source of incompatibility. A user of two libraries that each define their own true/false types that wants to meta-program on top of both will find the task awkward. Having a boost header file that everyone is supposed to include that defines universal boost::true_type and boost::false_type seems like a good idea,
#include <boost/mpl/bool.hpp>
and I've seen people push in that direction on this list for a while, but I don't think it is the best solution. It would be better to instead have a convention that void is false type and all other types are true.
There are lots of things one often wants to do with a "false_type" that void doesn't allow (e.g. making a function parameter type). -- Dave Abrahams BoostPro Computing http://www.boostpro.com
Hi Luke, Simonson, Lucanus J wrote:
Barend wrote:
Furthermore, you mention: "concept checking boilerplate around bool return type goes here". We've encountered problems with the concept checking on return types. The combination of BCCL and overloads based on SFINAE gives compiler problems here. We therefore use BOOST_CONCEPT_REQUIRES instead of _ASSERT in such cases.
What compiler problems specifically? I don't use BCCL for concept checking, and should have said SFINAE meta-programming boilerplate instead.
Compiler problems: that it fails to specializes the function as soon as the BCCL check is there. That is related to the SFINAE overloads. Cannot reproduce it literally and it was also compiler dependant. But if the BOOST*ASSERT was removed they were gone. It might also be solved by using tag dispatchment suggested by Dave, I'll look to that. Regards, Barend
Barend wrote:
Furthermore, you mention: "concept checking boilerplate around bool return type goes here". We've encountered problems with the concept checking on return types. The combination of BCCL and overloads based on SFINAE gives compiler problems here. We therefore use BOOST_CONCEPT_REQUIRES instead of _ASSERT in such cases.
Simonson, Lucanus J wrote: What compiler problems specifically? I don't use BCCL for concept checking, and should have said SFINAE meta->>programming boilerplate instead.
Barend wrote:
Compiler problems: that it fails to specializes the function as soon as the BCCL check is there. That is related to the SFINAE overloads. Cannot reproduce it literally and it was also compiler dependant. But if the BOOST*ASSERT was removed they were gone. It might also be solved by using tag dispatchment suggested by Dave, I'll look to that.
I had my basic generic geometry API fully implemented using tag dispatching and was very happy with it, until I eliminated the broken semantics of geometry concept inheritance and lost all of the polymorphism of geometry concept type that provided. It became very obvious that tag dispatching had its shortcomings when I was implementing the assign() function. //assigns any B type object to an object of type A template <typename A, typename B> A& assign(A& a, const B& b) { assign_dispatch(a, lookup_tag<A>::type(), b, lookup_tag<B>::type()); } You can assign a rectangle to a polygon but not the other way around. You can assign a polygon to a polygon with holes, but not the other way around. It turns out that roughly half the possible combinations of types that could be arguments to assign were legal, meaning I had O(n^2) assign_dispatch functions to write. This is intolerable because the number of types can be expected to increase over time, and increasing effort to add each type into the system would stunt the growth of the library over time. Instead I wrote O(n) assign functions that were based on SFINAE and used static polymorphism between different concepts to achieve my aim. A rectangle can model the read only polygon concept, for instance. //assigns any type B that can model a read only polygon to A template <typename A, typename B> typename boost::enable_if< typename boost::mpl::and< typename is_mutable_polygon<A>::type, typename is_viewable_as_polygon<B>::type>::type, A>::type & assign(A& a, const B& b) { ... } //further overloads of assign are possible with SFINAE We need more than just overloading of generic functions based on conceptual type to implement a generic geometry library, we need static polymorphism. I'm just completed a release of my library that uses SFINAE overloading for the API. I wouldn't want to try to go back to tag dispatching. Regards, Luke
on Thu Jan 08 2009, "Simonson, Lucanus J" <lucanus.j.simonson-AT-intel.com> wrote:
Barend wrote:
Furthermore, you mention: "concept checking boilerplate around bool return type goes here". We've encountered problems with the concept checking on return types. The combination of BCCL and overloads based on SFINAE gives compiler problems here. We therefore use BOOST_CONCEPT_REQUIRES instead of _ASSERT in such cases.
Simonson, Lucanus J wrote: What compiler problems specifically? I don't use BCCL for concept checking, and should have said SFINAE meta->>programming boilerplate instead.
Barend wrote:
Compiler problems: that it fails to specializes the function as soon as the BCCL check is there. That is related to the SFINAE overloads. Cannot reproduce it literally and it was also compiler dependant. But if the BOOST*ASSERT was removed they were gone. It might also be solved by using tag dispatchment suggested by Dave, I'll look to that.
I had my basic generic geometry API fully implemented using tag dispatching and was very happy with it, until I eliminated the broken semantics of geometry concept inheritance
Umm, yes, inheritance doesn't work. However, concept refinement *does* work.
and lost all of the polymorphism of geometry concept type that provided. It became very obvious that tag dispatching had its shortcomings when I was implementing the assign() function.
//assigns any B type object to an object of type A template <typename A, typename B> A& assign(A& a, const B& b) { assign_dispatch(a, lookup_tag<A>::type(), b, lookup_tag<B>::type()); }
You can assign a rectangle to a polygon but not the other way around.
That's the classic OOP geometry modeling pitfall (i.e. the binary method problem), but I don't see why it should be a problem with GP.
You can assign a polygon to a polygon with holes, but not the other way around. It turns out that roughly half the possible combinations of types
Concepts?
that could be arguments to assign were legal, meaning I had O(n^2) assign_dispatch functions to write.
I don't see it.
This is intolerable because the number of types can be expected to increase over time, and increasing effort to add each type into the system would stunt the growth of the library over time. Instead I wrote O(n) assign functions that were based on SFINAE and used static polymorphism between different concepts to achieve my aim. A rectangle can model the read only polygon concept
Oh, but once you introduce immutable shapes you can no longer claim that concept refinement isn't appropriate for modeling geometry. It's just that you had the wrong hierarchy before. +--- Rectangle <- Square / +-- Polygon <--+ / \ Regular <-- HoleyPolygon <--+ +--- MutablePolygon \ +--- MutableHoleyPolygon Wow, Polygons are even Assignable! In fact, that B refines A *almost never* means that you can assign a B into an A. Consider Field and Vector Space. I don't see any problems; just tag dispatch based on the concept modeled by the LHS. Assign for Polygons can forego asking about the number of RHS holes, assign for Rectangles can forego asking how many points there are, and assign for Squares can forego asking for one of the side lengths. What am I missing here?
//assigns any type B that can model a read only polygon to A template <typename A, typename B> typename boost::enable_if< typename boost::mpl::and< typename is_mutable_polygon<A>::type, typename is_viewable_as_polygon<B>::type>::type, A>::type & assign(A& a, const B& b) { ... }
//further overloads of assign are possible with SFINAE
We need more than just overloading of generic functions based on conceptual type to implement a generic geometry library, we need static polymorphism.
I'm sorry, but that doesn't make any sense to me. One of the big selling points of GP is that you *don't* lose static polymorphism. You certainly don't lose any type information by tag dispatching.
I'm just completed a release of my library that uses SFINAE overloading for the API. I wouldn't want to try to go back to tag dispatching.
Not gettin' it. -- Dave Abrahams BoostPro Computing http://www.boostpro.com
You can assign a polygon to a polygon with holes, but not the other way around. It turns out that roughly half the possible combinations of types that could be arguments to assign were legal, meaning I had O(n^2) assign_dispatch functions to write.
Dave A wrote:
I don't see it.
Ok, I have six different polygon tags. polygon_90 (rectilinear polygon) polygon_90_with_holes polygon_45 (extends rectilinear to allow for 45 degree edges) polygon_45_with_holes polygon polygon_with_holes The API is 100% type safe wrt these six polygon types. Because I have rectilinear, 45 and arbitrary angle geometry algorithms implemented I need all of these types. I'll abbreviate them p90, p90wh, p45, p45wh, p and pwh. Legal combinations of assignment are as follows: pwh can be assigned to pwh only p can be assigned to p and pwh p45wh assigns to p45wh and pwh p45 assigns to p45, p45wh, p and pwh p90wh assigns to p90wh, p45wh and pwh p_90 can assign to all six. That's 18 out of 36 possible combinations are legal. I could just be dense, but I couldn't figure out how to do that with tag dispatching without writing 18 dispatch functions if each type gets its own unique tag. There was no inheritance tree that gave me those 18 and only those 18, and multiple inheritance DAGs didn't improve matters either.
Oh, but once you introduce immutable shapes you can no longer claim that concept refinement isn't appropriate for modeling geometry. It's just that you had the wrong hierarchy before. +--- Rectangle <- Square / +-- Polygon <--+ / \ Regular <-- HoleyPolygon <--+ +--- MutablePolygon \ +--- MutableHoleyPolygon Wow, Polygons are even Assignable! In fact, that B refines A *almost never* means that you can assign a B into an A. Consider Field and Vector Space. I don't see any problems; just tag dispatch based on the concept modeled by the LHS. Assign for Polygons can forego asking about the number of RHS holes, assign for Rectangles can forego asking how many points there are, and assign for Squares can forego asking for one of the side lengths. What am I missing here?
That helps for reading, but not for writing. You can't assign to a non-mutable object. Because your mutable objects are leaves they can only assign from themselves. All of my objects would be mutable, leaves in your hierarchy, and not inter-compatible. You are also missing Polygon <-- Polygon45 <-- Polygon90. You don't want to use multiple inheritance (I crashed the compiler trying.)
We need more than just overloading of generic functions based on conceptual type to implement a generic geometry library, we need static polymorphism.
I'm sorry, but that doesn't make any sense to me. One of the big selling points of GP is that you *don't* lose static polymorphism. You certainly don't lose any type information by tag dispatching.
Ok, I guess I phrased that poorly. Metaprogramming around the return type allows us to specify exactly the logic of types we want to allow without any of the restrictions of hierarchical organization imposed by inheritance. For the above example of six flavors of polygon I wrote six overloads of assign() and metaprogramming around the return types that allowed me to efficiently implement the type restrictions for what is and isn't legal arguments for each overload. I do this of course by inspecting the tags, but I can't do it by tag dispatching, as far as I know. Generic programming inside the implementation of each overload made it easy to write one function body that worked on all types. The hard part wasn't writing code that works in all cases it is supposed to work, it was restricting it from working in the cases that are not supposed to work to provide appropriate type safety. Now, obviously, no sane application developer wants to use six or even three different polygon types. They want to use one and have it work everywhere. That is why I introduced view_as. The application developer can say "OK, I know this polygon is rectilinear, so I'll concept cast it and pass it into the rectilinear algorithm. The code documents the fact that the polygon is supposed to be rectilinear. Respectfully, Luke
on Fri Jan 09 2009, "Simonson, Lucanus J" <lucanus.j.simonson-AT-intel.com> wrote:
You can assign a polygon to a polygon with holes, but not the other way around. It turns out that roughly half the possible combinations of types that could be arguments to assign were legal, meaning I had O(n^2) assign_dispatch functions to write.
Dave A wrote:
I don't see it.
Ok, I have six different polygon tags. polygon_90 (rectilinear polygon) polygon_90_with_holes polygon_45 (extends rectilinear to allow for 45 degree edges) polygon_45_with_holes polygon polygon_with_holes
The API is 100% type safe wrt these six polygon types. Because I have rectilinear, 45 and arbitrary angle geometry algorithms implemented I need all of these types.
I'll abbreviate them p90, p90wh, p45, p45wh, p and pwh.
refinement: +-- p <------+ / \ pwh <--+ +-- p45 <---+ \ / \ +-- p45wh <--+ +-- p90 \ / +-- p90wh <--+ Ja?
Legal combinations of assignment are as follows: pwh can be assigned to pwh only p can be assigned to p and pwh p45wh assigns to p45wh and pwh p45 assigns to p45, p45wh, p and pwh p90wh assigns to p90wh, p45wh and pwh p_90 can assign to all six.
That's 18 out of 36 possible combinations are legal. I could just be dense, but I couldn't figure out how to do that with tag dispatching without writing 18 dispatch functions if each type gets its own unique tag.
You gotta straighten out your terminology, man; it muddles the thinking. Tags correspond to concepts.
From the what you wrote above and the diagram it looks like the RHS simply has to be a possibly-indirect refinement of the LHS.
I'm pretty sure you only need a single dispatch function // dispatch function template <class LhsPoly, class RhsPoly> void assign(LhsPoly& l, RhsPoly const& r) { BOOST_MPL_ASSERT(( is_convertible< typename polygon_category<RhsPoly>::type , typename polygon_category<LhsPoly>::type >)); assign_impl(l, r, typename polygon_category<LhsPoly>::type()); } with at most 6 implementations // for example template <class LhsPoly45, class RhsPoly45> void assign_impl(LhsPoly45& l, RhsPoly45 const& r, p45_tag) { ... } Am I missing something?
There was no inheritance tree that gave me those 18 and only those 18, and multiple inheritance DAGs didn't improve matters either.
You don't need inheritance other than tag inheritance.
I don't see any problems; just tag dispatch based on the concept modeled by the LHS. Assign for Polygons can forego asking about the number of RHS holes, assign for Rectangles can forego asking how many points there are, and assign for Squares can forego asking for one of the side lengths. What am I missing here?
That helps for reading, but not for writing. You can't assign to a non-mutable object.
Yeah, you can ;-) Whole object mutations are okay; it's the partial mutations that may destroy the invariants of a refined concept that get you in trouble. In other words, Rectangle can support assignment but not set_height, because Square's invariants depend on not changing the height without the width.
Because your mutable objects are leaves they can only assign from themselves.
You have to remember that's a refinement (not an inheritance) hierarchy. boost::function<void()> does not have a direct refinement relationship with void(*)() and yet you can still assign from the latter into the former.
All of my objects would be mutable, leaves in your hierarchy, and not inter-compatible.
You are also missing Polygon <-- Polygon45 <-- Polygon90.
You didn't tell me about those, so of course I missed them.
You don't want to use multiple inheritance (I crashed the compiler trying.)
If your compiler can't handle MI, just give up programming now ;-P
We need more than just overloading of generic functions based on conceptual type to implement a generic geometry library, we need static polymorphism.
I'm sorry, but that doesn't make any sense to me. One of the big selling points of GP is that you *don't* lose static polymorphism. You certainly don't lose any type information by tag dispatching.
Ok, I guess I phrased that poorly. Metaprogramming around the return type allows us to specify exactly the logic of types we want to allow without any of the restrictions of hierarchical organization imposed by inheritance. For the above example of six flavors of polygon I wrote six overloads of assign() and metaprogramming around the return types that allowed me to efficiently implement the type restrictions for what is and isn't legal arguments for each overload.
Efficiently? Well, ask yourself this: * how much code did you save over the technique I demonstrated? * how much simpler is your code than mine? * most of all, what happens to your code when you have to integrate a new concept into the system? -- Dave Abrahams BoostPro Computing http://www.boostpro.com
refinement:
+-- p <------+ / \ pwh <--+ +-- p45 <---+ \ / \ +-- p45wh <--+ +-- p90 \ / +-- p90wh <--+
Ja? Ja, that's the one that crashed the compiler when I tried to take out the virtual keyword. I inherited the tags (not the data types) from each other multiply in exactly that manner. I found that more recent version of the compiler were able to handle it, of course ;)
This allows any algorithm that would accept a pwh to accept a p90, which doesn't work for the lhs of an assign, obviously.
You gotta straighten out your terminology, man; it muddles the thinking. Tags correspond to concepts.
Ah, I see, I was calling the dispatched to function a dispatch function because it is usually named foo_dispatch, whereas you call the dispatcher function the dispatch function because it does the dispatching. I implemented the above hierarchy as struct pwh{}; struct p : pwh{}; struct p45wh : pwh{}; struct p45 : virtual p, p45wh {}; struct p90wh : p45wh; struct p90 : virtual p45, p90wh {}; But wasn't keen on a virtual pointer in a tag, so took out virtual keyword.
From the what you wrote above and the diagram it looks like the RHS simply has to be a possibly-indirect refinement of the LHS. I'm pretty sure you only need a single dispatch function // dispatch function template <class LhsPoly, class RhsPoly> void assign(LhsPoly& l, RhsPoly const& r) { BOOST_MPL_ASSERT(( is_convertible< typename polygon_category<RhsPoly>::type , typename polygon_category<LhsPoly>::type >));
assign_impl(l, r, typename polygon_category<LhsPoly>::type()); } with at most 6 implementations // for example template <class LhsPoly45, class RhsPoly45> void assign_impl(LhsPoly45& l, RhsPoly45 const& r, p45_tag) { ... } Am I missing something?
I guess not. Like I said, it is easy to write the six functions to work in all cases they are supposed to work, but hard to exclude them from working in all the other cases they are not type safe. By implementing the in_convertable metafunction and using it in the assert you exclude those. You could have as easily done that around the return type as in the body. Assuming you want to overload assign, or allow it to be safely overloaded later you would want to guard it with SFINAE anyway. Because my function names are very generic I like to avoid collisions. The distance() function between two geometry objects collided with std::distance between two iterators in gcc 3.2.2 or 3.4.2, for instance (despite being in different namespaces) so I had to rename it to euclidean_distance. However, you didn't implement it with tag dispatching alone, you used MPL assert, which is equivalent to SFINAE. If you consider mpl assert to be tag dispatching then you can do it with tag dispatching. I considered them to be two different techniques. I chose SFINAE instead of tag dispatching for my generic overloading. It is equivalent, but is it inferior somehow?
That helps for reading, but not for writing. You can't assign to a non-mutable object.
Yeah, you can ;-)
Whole object mutations are okay; it's the partial mutations that may destroy the invariants of a refined concept that get you in trouble. In other words, Rectangle can support assignment but not set_height, because Square's invariants depend on not changing the height without the width.
Ah, terminology again. I don't support partial mutations of polygons anyway, though I do for points and rectangles.
Because your mutable objects are leaves they can only assign from themselves.
Efficiently? Well, ask yourself this:
* how much code did you save over the technique I demonstrated?
None, in fact I have a great deal of code duplication in the SFINAE metaprogramming around the return types of my overloads that could be factored together into the dispatcher function.
* how much simpler is your code than mine?
No simpler.
* most of all, what happens to your code when you have to integrate a new concept into the system?
In some cases it might take me more code, but in others not. If I add triangle to the mix I can specialize is_polygonal and give the triangle polygon-read-only traits to work with the existing overloads of assign. Tag dispatching could help cut down on the number of SFINAE protected overloads of functions, which would save some typing, but the number of functions in the library would be about the same. Right now I have 314 SFINAE overloads of various function names. Having to modify all of them to deal with a limitation in the way the MS compiler parses SFINAE really is a chore. I'd have only 200 or so to do if I implemented things the way you propose, but that is a difference in degree, not order of work. I readily admit I'd be happy to type less, not least because I typed my fingers so sore switching to SFINAE overloading that I could barely sign my name. Respectfully, Luke
on Fri Jan 09 2009, "Simonson, Lucanus J" <lucanus.j.simonson-AT-intel.com> wrote:
refinement:
+-- p <------+ / \ pwh <--+ +-- p45 <---+ \ / \ +-- p45wh <--+ +-- p90 \ / +-- p90wh <--+
Ja?
Ja, that's the one that crashed the compiler when I tried to take out the virtual keyword.
Which 'piler is this?
I inherited the tags (not the data types) from each other multiply in exactly that manner. I found that more recent version of the compiler were able to handle it, of course ;)
This allows any algorithm that would accept a pwh to accept a p90, which doesn't work for the lhs of an assign, obviously.
You gotta straighten out your terminology, man; it muddles the thinking. Tags correspond to concepts.
Ah, I see, I was calling the dispatched to function a dispatch function because it is usually named foo_dispatch, whereas you call the dispatcher function the dispatch function because it does the dispatching.
I implemented the above hierarchy as struct pwh{}; struct p : pwh{}; struct p45wh : pwh{}; struct p45 : virtual p, p45wh {}; struct p90wh : p45wh; struct p90 : virtual p45, p90wh {}; But wasn't keen on a virtual pointer in a tag, so took out virtual keyword.
Yeah, you shouldn't need it.
From the what you wrote above and the diagram it looks like the RHS simply has to be a possibly-indirect refinement of the LHS. I'm pretty sure you only need a single dispatch function // dispatch function template <class LhsPoly, class RhsPoly> void assign(LhsPoly& l, RhsPoly const& r) { BOOST_MPL_ASSERT(( is_convertible< typename polygon_category<RhsPoly>::type , typename polygon_category<LhsPoly>::type >));
assign_impl(l, r, typename polygon_category<LhsPoly>::type()); } with at most 6 implementations // for example template <class LhsPoly45, class RhsPoly45> void assign_impl(LhsPoly45& l, RhsPoly45 const& r, p45_tag) { ... } Am I missing something?
I guess not. Like I said, it is easy to write the six functions to work in all cases they are supposed to work, but hard to exclude them from working in all the other cases they are not type safe. By implementing the in_convertable metafunction
That's in boost/type_traits/is_convertible.hpp; I didn't have to implement it!
and using it in the assert you exclude those. You could have as easily done that around the return type as in the body. Assuming you want to overload assign, or allow it to be safely overloaded later you would want to guard it with SFINAE anyway. Because my function names are very generic I like to avoid collisions. The distance() function between two geometry objects collided with std::distance between two iterators in gcc 3.2.2 or 3.4.2, for instance (despite being in different namespaces) so I had to rename it to euclidean_distance.
Sure, makes sense.
However, you didn't implement it with tag dispatching alone, you used MPL assert, which is equivalent to SFINAE.
If you use SFINAE in the traditional way, you can't take advantage of any refinement relationships and you need to explicitly exclude all the other cases. Of course, you could use SFINAE with an is_convertible test on the tags, which would get around that problem. But I would still do that on the dispatch function and use tags to select the implementation.
If you consider mpl assert to be tag dispatching then you can do it with tag dispatching. I considered them to be two different techniques.
They are completely different. The dispatching problem, which is what you said you struggled with, is handled completely by tag dispatching. The other problem is how to generate errors for the cases you don't want to allow, and yeah, there are several different possible approaches there.
I chose SFINAE instead of tag dispatching for my generic overloading. It is equivalent, but is it inferior somehow?
That helps for reading, but not for writing. You can't assign to a non-mutable object.
Yeah, you can ;-)
Whole object mutations are okay; it's the partial mutations that may destroy the invariants of a refined concept that get you in trouble. In other words, Rectangle can support assignment but not set_height, because Square's invariants depend on not changing the height without the width.
Ah, terminology again. I don't support partial mutations of polygons anyway, though I do for points and rectangles.
Then Rectangles aren't immutable but Polygons are. Odd asymmetry.
Because your mutable objects are leaves they can only assign from themselves.
Efficiently? Well, ask yourself this:
* how much code did you save over the technique I demonstrated?
None, in fact I have a great deal of code duplication in the SFINAE metaprogramming around the return types of my overloads that could be factored together into the dispatcher function.
Exactly.
* how much simpler is your code than mine?
No simpler.
* most of all, what happens to your code when you have to integrate a new concept into the system?
In some cases it might take me more code, but in others not. If I add triangle to the mix I can specialize is_polygonal and give the triangle polygon-read-only traits to work with the existing overloads of assign.
You lost me.
Tag dispatching could help cut down on the number of SFINAE protected overloads of functions, which would save some typing, but the number of functions in the library would be about the same.
It's not about the number of functions; it's about having to hit a whole bunch of unrelated implementations when a new concept is introduced, to make sure they don't match it.
Right now I have 314 SFINAE overloads of various function names. Having to modify all of them to deal with a limitation in the way the MS compiler parses SFINAE really is a chore. I'd have only 200 or so to do if I implemented things the way you propose, but that is a difference in degree, not order of work.
are you arguing that a 35% reduction in the size of your job is insignificant? It's your funeral I guess ;-). -- Dave Abrahams BoostPro Computing http://www.boostpro.com
refinement:
+-- p <------+ / \ pwh <--+ +-- p45 <---+ \ / \ +-- p45wh <--+ +-- p90 \ / +-- p90wh <--+
Ja?
Ja, that's the one that crashed the compiler when I tried to take out the virtual keyword.
Which 'piler is this?
I think it was gcc 3.4.2, but it might have been gcc 3.2.2. I don't clearly remember. I pretty much stopped worrying about it when I found that it isn't a problem with current compilers and I was no longer planning to do it anyhow. No need for bug report.
That's in boost/type_traits/is_convertible.hpp; I didn't have to implement it!
Nice. Good to know. How does it work?
If you use SFINAE in the traditional way, you can't take advantage of any refinement relationships and you need to explicitly exclude all the other cases. Of course, you could use SFINAE with an is_convertible test on the tags, which would get around that problem. But I would still do that on the dispatch function and use tags to select the implementation.
Yes, saves some typing of SFINAE meta-logic.
Then Rectangles aren't immutable but Polygons are. Odd asymmetry.
Well, if the number of points in the polygon is changed by the modification you will pay O(n) wrt. points to modify it one way or another, might as well just set it. If I were going to fix the asymmetry I'd probably make all types immutable. It is really a bad idea to modify one coordinate of a polar point through a Cartesian view and then modify the other coordinate in the very next line. If I know the data type at compile time I can use its non-generic interface to partially modify it, of course.
In some cases it might take me more code, but in others not. If I add triangle to the mix I can specialize is_polygonal and give the triangle polygon-read-only traits to work with the existing overloads of assign.
You lost me.
I can view a triangle as a polygon. My polygon_traits is for read only access. I have another polygon_mutable_traits for writing to a polygon. I can specialize polygon_traits for any object that models triangle and it will become a legal RHS of the polygon assign functions. I still need to write the assign for triangle as LHS, however, which would require SFINAE guard that your tag dispatch function would not.
Tag dispatching could help cut down on the number of SFINAE protected overloads of functions, which would save some typing, but the number of functions in the library would be about the same.
It's not about the number of functions; it's about having to hit a whole bunch of unrelated implementations when a new concept is introduced, to make sure they don't match it.
That would be bad if it were the case. By splitting the traits into read-only and mutable and looking up by meta-function whether an object models the read-only or over writable concept I've done essentially the same thing as tag-inheritance concept refinement accomplishes, but through meta-functions. Updating those metafunctions is about the same work as adding a new tag into the hierarchy, and much less than adding the interfaces required by the traits, which would be necessary in either case.
Right now I have 314 SFINAE overloads of various function names. Having to modify all of them to deal with a limitation in the way the MS compiler parses SFINAE really is a chore. I'd have only 200 or so to do if I implemented things the way you propose, but that is a difference in degree, not order of work.
are you arguing that a 35% reduction in the size of your job is insignificant?
No, just that I'm not going to change the design for that reason alone. I expect I'll rewrite it again in the future for other reasons, and I can incorporate this change at that time. Respectfully, Luke
on Fri Jan 09 2009, "Simonson, Lucanus J" <lucanus.j.simonson-AT-intel.com> wrote:
I think it was gcc 3.4.2, but it might have been gcc 3.2.2. I don't clearly remember. I pretty much stopped worrying about it when I found that it isn't a problem with current compilers and I was no longer planning to do it anyhow. No need for bug report.
That's in boost/type_traits/is_convertible.hpp; I didn't have to implement it!
Nice. Good to know. How does it work?
Use the source, Luke.
If you use SFINAE in the traditional way, you can't take advantage of any refinement relationships and you need to explicitly exclude all the other cases. Of course, you could use SFINAE with an is_convertible test on the tags, which would get around that problem. But I would still do that on the dispatch function and use tags to select the implementation.
Yes, saves some typing of SFINAE meta-logic.
Not just typing; also coupling and maintenance nightmares. Cheers, -- Dave Abrahams BoostPro Computing http://www.boostpro.com
On Jan 9, 2009, at 4:21 PM, David Abrahams wrote:
on Fri Jan 09 2009, "Simonson, Lucanus J" <lucanus.j.simonson-AT- intel.com> wrote:
I implemented the above hierarchy as struct pwh{}; struct p : pwh{}; struct p45wh : pwh{}; struct p45 : virtual p, p45wh {}; struct p90wh : p45wh; struct p90 : virtual p45, p90wh {}; But wasn't keen on a virtual pointer in a tag, so took out virtual keyword.
Yeah, you shouldn't need it.
Interestingly, virtual inheritance of tags shouldn't have any runtime cost. There's an interesting example in the Templates Complete Guide which uses virtual inheritance for a default policy scheme. For the same reason (never instantiated) not necessary here.
participants (5)
-
Barend Gehrels -
David Abrahams -
Gordon Woodhull -
Simonson, Lucanus J -
Steven Watanabe