www.digitalmars.com         C & C++   DMDScript  

D - Double Sided Virtual...or something like that

reply Russ Lewis <spamhole-2001-07-16 deming-os.org> writes:
Here's a question for all of you programming gurus to figure out:

I have a class, called Shape, which is the base for lots of other
classes.  For some combinations of those types, I have defined
interactions:

void Foo(ShapeChild1,ShapeChild2);
void Foo(ShapeChild1,ShapeChild3);
void Foo(ShapeChild1,ShapeChild4);
void Foo(ShapeChild3,ShapeChild4);

I have an interface function that takes two Shape objects as its
parameters:

void Foo(Shape,Shape);

Q: What is an easy, readable, and runtime-efficient way to have
Foo(Shape,Shape) figure out which of the implementations to call based
on the types of the arguments?  That is, if the first Shape happens to
actually be a ShapeChild1 and the second is a ShapeChild4, then I want
Foo(Shape,Shape) to call Foo(ShapeChild1,ShapeChild4).

Restrictions:
1) I need to support the ability to extend this library to include new
Shape* classes...without changing the interface function
Foo(Shape,Shape).  So hard coding nested switches is NOT going to work.
2) I need to automatically detect (and throw an exception) if
Foo(Shape,Shape) is called and there is no implementation for a given
pair.  It would be even better if I could determine at init time that
there were some implementations missing.
3) I need to be able to support multiple add-ons to the library which
might not know about each other.  So making a requirement that "all
addons must know about all previous shapes" won't be workable.

Thoughts, guys?  I have come up with any number of inelegant
solutions...I figure that somebody here has a better one.

Russ

--
The Villagers are Online! http://villagersonline.com

.[ (the fox.(quick,brown)) jumped.over(the dog.lazy) ]
.[ (a version.of(English).(precise.more)) is(possible) ]
?[ you want.to(help(develop(it))) ]
Mar 10 2003
next sibling parent reply Bill Cox <bill viasic.com> writes:
Russ Lewis wrote:

 Here's a question for all of you programming gurus to figure out:
 
 I have a class, called Shape, which is the base for lots of other
 classes.  For some combinations of those types, I have defined
 interactions:
 
 void Foo(ShapeChild1,ShapeChild2);
 void Foo(ShapeChild1,ShapeChild3);
 void Foo(ShapeChild1,ShapeChild4);
 void Foo(ShapeChild3,ShapeChild4);
 
 I have an interface function that takes two Shape objects as its
 parameters:
 
 void Foo(Shape,Shape);


[snip]


 Thoughts, guys?  I have come up with any number of inelegant
 solutions...I figure that somebody here has a better one.
 
 Russ


Isn't this just a multi-method?  I doubt that there is any nice 
implementation in D, or C++.  We're stuck with emulating them.

I'm basically against adding them to D.  I've looked around a bit on the 
web, and haven't been convinced that D needs multimethods.  If you're 
intersted, I've commented on what I found in a couple hours of browsing.

-----------------------------------------

Multi-methods have been added to several statically compiled languages, 
including C++, Java, and Perl.  IMO, advocates seem to have polymorphism 
fevor.  Here's a web page that seems to exemplify this:

http://www.yetanother.org/damian/seminars/Multimethods.html

However, in a couple hours of searching, I couldn't find any major 
problems where multimethods are the only solution, or IMO the best solution.

I checked a few intro pages to the language mentioned extensions above. 
  I found two examples used.

The first one problems mentioned was shape merging, where we want custom 
merge routines for merging squares and polygons, triangles and squares, 
etc.  Given N shape types, you can write N*N merge routines, and call 
them as a multimethod.  A better solution would be to convert all shapes 
to a generic type (for example, a polygon), write one merge routine, and 
then write routines to convert them back.  That takes 2N+1 functions. 
If speed is the reason we're writing custom functions, then we probably 
need custom dispatch code as well.  For example, if 99% of our shapes 
are rectangles (as is the case in EDA), you want to check for merging 
two rectangles first.

The second problem mentioned was reading many types of documents (PDF, 
postscript, MS Word, etc), and rendering on multiple kinds of devices 
(printer, screen, ...).  Writing custom routines for each of these 
combinations is a terrible idea.  Anyone remember when each company 
writing DOS applications had to write custom printer drivers for each 
printer, as well as a custom screen driver?  What a nightmare.  Again, 
the solution is converting to a generic format (a bitmap, for example), 
and then writing the single format to each device.

Digging a bit deeper, I found nice papers on efficient multimethod 
implementations.  I looked for a "motivation" section in them, and found 
one for extending Java:

"Java allows a new subclass to be added to an existing class in a 
modular way without requiring any modifications to existing code. 
However, Java (along with all other single-dispatch languages of which 
we are aware) does not allow a new method to be added to an existing 
class in a modular way."

That's valid concern, but it's also solvable in other ways.  For one, we 
can have "compile-time reflection classes" (as the OpenC++ guyes call 
it).  Alternatively, we could add an extension capability that allows us 
to add methods to classes in separate source files.  This capability has 
other uses as well.

Another problem mentioned in several places is the "visitor" problem.
It seems to be a problem that comes up in visiting complex class 
hierarchies in Java and C++.  I read a short presentation on this 
problem, and at the end they suggested that another aproach to solving 
it is to write iterators that take call-back functions as parameters. 
If this seems ugly, then add enhanced iterator support so we can 
eliminate the call-backs.

Another problem with multi-methods is they seem very complex to 
implement and support in statically compiled languages.  I found 
multiple papers on the web describing novel ways to overcome obscure 
problems that come up.  It looks really hairy.

In short, the little bit of poking around I've done hasn't led me to 
believe multimethods belong in D.

Bill
Mar 11 2003
parent reply Russell Lewis <spamhole-2001-07-16 deming-os.org> writes:
The problem I'm trying to solve is to determine the time of first/next 
intersection between 2 4D Shapes.  The shapes will all have mathematical 
formulas to represent them, but could be a wide variety of types (moving 
spheres, toroids, boxes, etc.)

It is computationally impractical to convert complex 4D shapes into 
polygons.  The two shapes might never intersect; they might intersect 
but far in the future.  Whereever they intersect, I want to be able to 
determine their intersection with great precision, not an approximation 
as polygons would give me.

The solution, as I see it, is to work out mathematical formulas for each 
pair of types.  I can do that, though it will be hard.

Now, I have to figure out how to use the right formula for each pair of 
types.



One (ugly) solution is a 2D associative array of function pointers, 
taking ShapeID (an enum, probably) as indexes for both.  But that seems 
hackish to me and requires that all of my Shape* classes get assigned 
their own ID...a problematic design.
Mar 11 2003
next sibling parent reply "Sean L. Palmer" <seanpalmer directvinternet.com> writes:
That's funny;  this is exactly what Geometric Algebra is good for.  Just add
another dimension that squares to -1 to represent the time axis.  For shapes
such as spheres and planes you need 4 dimensions.  So at minimum you're
working on a 5D problem.

But GA has these nifty meet and join operations that make the intersection
almost trivial to compute once you have the shapes represented as
multivectors of some sufficiently high dimension.

http://www.iancgbell.clara.net/maths/geoalg1.htm#A33

If it were possible to represent any of your shapes as an array of
multivectors, and were ok with getting arbitrary multivectors back, it could
potentially be done with a single routine.

Sean

"Russell Lewis" <spamhole-2001-07-16 deming-os.org> wrote in message
news:3E6E16FD.2000600 deming-os.org...

 The problem I'm trying to solve is to determine the time of first/next
 intersection between 2 4D Shapes.  The shapes will all have mathematical
 formulas to represent them, but could be a wide variety of types (moving
 spheres, toroids, boxes, etc.)

 It is computationally impractical to convert complex 4D shapes into
 polygons.  The two shapes might never intersect; they might intersect
 but far in the future.  Whereever they intersect, I want to be able to
 determine their intersection with great precision, not an approximation
 as polygons would give me.

 The solution, as I see it, is to work out mathematical formulas for each
 pair of types.  I can do that, though it will be hard.

 Now, I have to figure out how to use the right formula for each pair of
 types.



 One (ugly) solution is a 2D associative array of function pointers,
 taking ShapeID (an enum, probably) as indexes for both.  But that seems
 hackish to me and requires that all of my Shape* classes get assigned
 their own ID...a problematic design.
Mar 11 2003
parent reply Russ Lewis <spamhole-2001-07-16 deming-os.org> writes:
"Sean L. Palmer" wrote:


 That's funny;  this is exactly what Geometric Algebra is good for.  Just add
 another dimension that squares to -1 to represent the time axis.  For shapes
 such as spheres and planes you need 4 dimensions.  So at minimum you're
 working on a 5D problem.

 But GA has these nifty meet and join operations that make the intersection
 almost trivial to compute once you have the shapes represented as
 multivectors of some sufficiently high dimension.



 http://www.iancgbell.clara.net/maths/geoalg1.htm#A33

 If it were possible to represent any of your shapes as an array of
 multivectors, and were ok with getting arbitrary multivectors back, it could
 potentially be done with a single routine.


The page is incredibly dense.  The background doesn't make things too easy to
read, either.  Do you know of another, slower paced, intro to the subject?

I saw, in my Computer Graphics course, how you could use 4x4 matrices to
represent spheres and ellipsoids of all types.  I certainly plan to use that in
the Shape* class that handes ellipsoids.  This multivector thing sounds like the
same general idea, but generalized to N dimensions.  Is that a fair analysis?

In what way are multivectors different from transform matrices?  Those, too,
were sets of orthogonal vectors in a space.

--
The Villagers are Online! http://villagersonline.com

.[ (the fox.(quick,brown)) jumped.over(the dog.lazy) ]
.[ (a version.of(English).(precise.more)) is(possible) ]
?[ you want.to(help(develop(it))) ]
Mar 12 2003
parent reply Russ Lewis <spamhole-2001-07-16 deming-os.org> writes:
Russ Lewis wrote:


 I saw, in my Computer Graphics course, how you could use 4x4 matrices to
 represent spheres and ellipsoids of all types.


(I've also already done some research into using 5x5 matrices to model spheres &
ellipsoids that move or change size over time...)

--
The Villagers are Online! http://villagersonline.com

.[ (the fox.(quick,brown)) jumped.over(the dog.lazy) ]
.[ (a version.of(English).(precise.more)) is(possible) ]
?[ you want.to(help(develop(it))) ]
Mar 12 2003
parent reply "Sean L. Palmer" <seanpalmer directvinternet.com> writes:
From what I understand, a 5x5 matrix would be quite overspecified.

Here's a very gentle intro to some basic GA concepts:

http://sinai.mech.fukui-u.ac.jp/gcj/software/GAcindy/GAcindy.htm

And here's something about your speed:

http://carol.wins.uva.nl/~leo/clifford/sommer.pdf

There is plenty of material on the web about GA.

I haven't tackled your problem but what I've read suggests this is what GA
is good at.

Check out Gaigen or boost::clifford if you want to do your own experiments.

Sean


"Russ Lewis" <spamhole-2001-07-16 deming-os.org> wrote in message
news:3E6F53E6.993E07A4 deming-os.org...

 Russ Lewis wrote:


 I saw, in my Computer Graphics course, how you could use 4x4 matrices to
 represent spheres and ellipsoids of all types.


 (I've also already done some research into using 5x5 matrices to model


spheres &

 ellipsoids that move or change size over time...)
Mar 12 2003
next sibling parent reply Juarez Rudsatz <juarezNOSPAM correio.com> writes:
"Sean L. Palmer" <seanpalmer directvinternet.com> wrote in
news:b4nu31$22vc$1 digitaldaemon.com: 


 ip address is just 4 bytes ( or 4 ints for a v6 (3 ints and 4 bytes
 for compatibly with v4)) // don't quote me on that its the idea I'm
 trying to get across.
 


Ok. I agree.
The idea is a new representation for version numbers. The storage is not so 
important at first.


     assert(int.size == 4, "This code will only run in 32 bits cpus");
 that or having the assert put the condition as a string in the
 message, so; assert( int.size == 4); would give "assert failed
 'int.size==4' is not true at line xxxx in File yyyy"


Both. Sometimes the check have few information.


 3 - Module version

 Each module could have a .version property and a .vendor property.
 They will be assigned within the module:


 
 as much as I like the idea, alas it still fails to catch the usual
 problem .... you forget to increment your version number.
 
 the only automated solution I can see is allowing modules to be
 sectioned each section has its "signature" hashed and that is stored
 both in the module and any places it is imported.



I have sugested only a simple manual versioning.


 classes and structures could also use this (may be with an included 
 length field as the first member)


Yes. It also apply.
Mar 12 2003
parent "Mike Wynn" <mike.wynn l8night.co.uk> writes:
 3 - Module version

 Each module could have a .version property and a .vendor property.
 They will be assigned within the module:


 as much as I like the idea, alas it still fails to catch the usual
 problem .... you forget to increment your version number.

 the only automated solution I can see is allowing modules to be
 sectioned each section has its "signature" hashed and that is stored
 both in the module and any places it is imported.



 I have sugested only a simple manual versioning.
Mar 12 2003
prev sibling parent Russ Lewis <spamhole-2001-07-16 deming-os.org> writes:
"Sean L. Palmer" wrote:


 From what I understand, a 5x5 matrix would be quite overspecified.

 Here's a very gentle intro to some basic GA concepts:

 http://sinai.mech.fukui-u.ac.jp/gcj/software/GAcindy/GAcindy.htm

 And here's something about your speed:

 http://carol.wins.uva.nl/~leo/clifford/sommer.pdf

 There is plenty of material on the web about GA.

 I haven't tackled your problem but what I've read suggests this is what GA
 is good at.

 Check out Gaigen or boost::clifford if you want to do your own experiments.


Thanks for the links.  sommer is still to fast for me, but I found
http://www.mrao.cam.ac.uk/~clifford/introduction/intro/intro.html, which builds
up to the concept of multivectors slowly.  It allows somebody like me, who
starts understanding only linear algebra, to build up to an understanding of a
multivector is.

I haven't yet fininshed the intro at that link, and I'm not even close to
understanding how I could use multivectors to model shapes.  But the experts
think that GA is good for everything, including defining the kitchen sink.

FWIW, my definition, as I understand so far: A multivector is the linear
combination of spaces of different dimensions.  Read the link, if anybody's
interested.

--
The Villagers are Online! http://villagersonline.com

.[ (the fox.(quick,brown)) jumped.over(the dog.lazy) ]
.[ (a version.of(English).(precise.more)) is(possible) ]
?[ you want.to(help(develop(it))) ]
Mar 15 2003
prev sibling next sibling parent Bill Cox <bill viasic.com> writes:
Russell Lewis wrote:

 The problem I'm trying to solve is to determine the time of first/next 
 intersection between 2 4D Shapes.  The shapes will all have mathematical 
 formulas to represent them, but could be a wide variety of types (moving 
 spheres, toroids, boxes, etc.)
 
 It is computationally impractical to convert complex 4D shapes into 
 polygons.  The two shapes might never intersect; they might intersect 
 but far in the future.  Whereever they intersect, I want to be able to 
 determine their intersection with great precision, not an approximation 
 as polygons would give me.
 
 The solution, as I see it, is to work out mathematical formulas for each 
 pair of types.  I can do that, though it will be hard.
 
 Now, I have to figure out how to use the right formula for each pair of 
 types.
 
 
 
 One (ugly) solution is a 2D associative array of function pointers, 
 taking ShapeID (an enum, probably) as indexes for both.  But that seems 
 hackish to me and requires that all of my Shape* classes get assigned 
 their own ID...a problematic design.
 


Ok, sounds like a real application for multimethods.  Frankly, I'd just 
write a big if-then-else statement by hand to do the dispatch.  Any 
programmer reading it will understand it right away, and maintaining it 
is not hard compared to writing all the functions.  To get better speed, 
you could do a switch on a combination of the enumerated types, although 
that's pretty ugly.  It C++, it would look something like:

switch((typeA << SHAPE_TYPE_BITS) | typeB) {
case SHAPE_A | SHAPE_A: return findIntersections((ShapeA *) a, (ShapeB 
*) b);
...
}

Bill
Mar 11 2003
prev sibling next sibling parent Burton Radons <loth users.sourceforge.net> writes:
Russell Lewis wrote:

 One (ugly) solution is a 2D associative array of function pointers, 
 taking ShapeID (an enum, probably) as indexes for both.  But that seems 
 hackish to me and requires that all of my Shape* classes get assigned 
 their own ID...a problematic design.


But common - the rigid-body physics library ODE does this.  You can just 
use ClassInfo:

    typedef Intersection delegate(Shape a, Shape b) Intersector;
    static Intersector[ClassInfo][ClassInfo] intersectList;

    static void registerIntersector(ClassInfo a, ClassInfo b, Intersector i)
    {
       intersectList[b][a] = i;
    }

    Intersection intersect(Shape other)
    {
       assert(other.classinfo in intersectList);
       assert(this.classinfo in intersectList[other.classinfo]);
       return intersectList[other.classinfo][this.classinfo];
    }

I'm on the fence.  This is a helluva painful problem when it comes up, 
but it's also hard to think of any solution that would envelope a broad 
selection of its problem scope - my criteria would be incompatible to 
your own, in fact.  When that happens, it indicates to me that the 
problem is trying to be solved at too high a level.  Bringing it down a 
level lands me at associative arrays of delegates with ClassInfo, with a 
set of functions for best-match searching - which can be implemented 
with my templating syntax:

    /* Breadth-first multimethod search for two arguments. */
    $Type multimethodSearch($Type[ClassInfo][ClassInfo] list, Object a, 
Object b)
    {
        ClassInfo ca;
        ClassInfo cb = b.classinfo;
        int bestDistance = -1;
        $Type best;
        int distance;

        for ( ; cb !== null; cb = cb.superclass, distance ++)
        {
           if (!(cb in list))
              continue;

           $Type[ClassInfo] sublist = list[cb];
           int adding;

           for (ca = a.classinfo; ca !== null; ca = ca.superclass, 
adding ++)
              if (ca in sublist && (bestDistance == -1 || distance + 
adding < bestDistance))
              {
                  bestDistance = distance + adding;
                  best = sublist[ca];
                  break;
              }
        }

        if (bestDistance == -1)
           throw new Error(a.classinfo.name ~ " and " ~ b.classinfo.name 
~ " have no matching method.");
        return best;
    }

    $RType multimethodSearchCall($RType delegate($AType a, $BType 
b)[ClassInfo][ClassInfo] list, $AType a, $BType b)
    {
        return multimethodSearch(list, a, b)(a, b);
    }

    ...
    return multimethodSearchCall(intersectList, this, other);
Mar 11 2003
prev sibling parent "Walter" <walter digitalmars.com> writes:
"Russell Lewis" <spamhole-2001-07-16 deming-os.org> wrote in message
news:3E6E16FD.2000600 deming-os.org...

 One (ugly) solution is a 2D associative array of function pointers,
 taking ShapeID (an enum, probably) as indexes for both.  But that seems
 hackish to me and requires that all of my Shape* classes get assigned
 their own ID...a problematic design.


That's what I'd do. Not the most elegant design, but if you put in a few
contracts to ensure that the IDs are set up correctly, it'll do the job
efficiently.
Apr 18 2003
prev sibling parent "Jeroen van Bemmel" <anonymous somewhere.com> writes:
Scott Meyers gives a nice overview of this issue in "More effective C++"
Item 31: "Making functions virtual w.r.t. more than one object"
See e.g. http://www.paulgrenyer.co.uk/accu/mdevelopers/effectivecpp/, but
for actual contents you need to buy the book. I have it, it's quite nice
Mar 11 2003