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