Subject: Re: [boost] [geometry] view_as concept casting
From: David Abrahams (dave_at_[hidden])
Date: 2009-01-09 14:51:15
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_45 (extends rectilinear to allow for 45 degree edges)
> 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.
+-- p <------+
pwh <--+ +-- p45 <---+
\ / \
+-- p45wh <--+ +-- p90
+-- p90wh <--+
> 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
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)
, 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
> Because your mutable objects are leaves they can only assign from
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
> All of my objects would be mutable, leaves in your hierarchy, and not
> 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
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
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk