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

• Russ Lewis (35/35) Mar 10 2003 Here's a question for all of you programming gurus to figure out:
• Bill Cox (61/80) Mar 11 2003 Isn't this just a multi-method? I doubt that there is any nice
• Russell Lewis (17/17) Mar 11 2003 The problem I'm trying to solve is to determine the time of first/next
• Sean L. Palmer (14/31) Mar 11 2003 That's funny; this is exactly what Geometric Algebra is good for. Just...
• Russ Lewis (14/25) Mar 12 2003 The page is incredibly dense. The background doesn't make things too ea...
• Russ Lewis (8/10) Mar 12 2003 (I've also already done some research into using 5x5 matrices to model s...
• Sean L. Palmer (13/18) Mar 12 2003 From what I understand, a 5x5 matrix would be quite overspecified.
• Juarez Rudsatz (9/30) Mar 12 2003 Ok. I agree.
• Russ Lewis (17/26) Mar 15 2003 Thanks for the links. sommer is still to fast for me, but I found
• Bill Cox (13/37) Mar 11 2003 Ok, sounds like a real application for multimethods. Frankly, I'd just
• Burton Radons (60/64) Mar 11 2003 But common - the rigid-body physics library ODE does this. You can just...
• Walter (5/9) Apr 18 2003 That's what I'd do. Not the most elegant design, but if you put in a few
• Jeroen van Bemmel (4/4) Mar 11 2003 Scott Meyers gives a nice overview of this issue in "More effective C++"
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

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

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

Automatic versioning? Like C# ?
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
"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.

Automatic versioning? Like C# ?
I have sugested only a simple manual versioning.

what does C# do ?
```
Mar 12 2003
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

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
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
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
```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];

for (ca = a.classinfo; ca !== null; ca = ca.superclass,
if (ca in sublist && (bestDistance == -1 || distance +
{
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
"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
"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