Re: [boost] [geometry] view_as concept casting

Subject: Re: [boost] [geometry] view_as concept casting
From: Simonson, Lucanus J (lucanus.j.simonson_at_[hidden])
Date: 2009-01-09 13:43:13

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