Re: [boost] [geometry] view_as concept casting

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_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