Letters

On reading Nat Goodspeed's interesting article "Double Dispatch Revisited" (DDJ, January 2004), another approach to the described problem came into my mind. It is explained in detail in Jeff Alger's Secrets of the C++ Masters (AP Professional, 1995; ISBN 0-12-049940-1), which is still one of my favorite books on practical C++ programming.

Here, the double dispatch problem is solved by two consecutive virtual function calls (see Listing One). Consider two GameObject pointers p1 and p2; the first actually being an Asteroid and the other a SpaceShip. Calling p1->collideWith(*p2) forces the first vtable lookup, yielding virtual void Asteroid::collideWith(GameObject& g) { g.collideWith(*this); }. At this point, the compiler knows that this is an asteroid. The trick is to swap the parameter, forcing a second vtable lookup that correctly brings us to the desired implementation: virtual void SpaceShip::collideWith(Asteroid&).

In my opinion, this approach is superior to the one Nat describes for the following reasons:

• It is more efficient (two vtable lookups versus a linear function list scan).
• It is more readable, does not contain ugly template code.

• It naturally solves the inheritance problem, as shown for the class CommercialShip, which behaves all the way as a SpaceShip except for the overwritten method collideWith(Asteroid&).

Wolfgang Stephan

[email protected]

Who's On First?

Dear DDJ,

Ed Nisley had a huge oversight in his recapitulation of the history of computing in his "Recovered Memories" article (DDJ, December 2003). It was not ENIAC, but the Atanasoff-Berry Computer that was the world's first electronic digital computer.

Built by John Vincent Atanasoff and Clifford Berry at Iowa State University during 1937-42, the Atanasoff-Berry Computer's memory was a rotating drum that stored 30 numbers of 50 bits each. This drum memory was capacitor based rather than magnetic. It is well documented, for instance, at http://inventors.about.com/library/inventors/blatanasoff_berry.htm that "a 1973, patent infringement case (Sperry Rand vs. Honeywell), voided the ENIAC patent as a derivative of Atanasoff's invention." Indeed, Atanasoff had a chance meeting with Mauchly on a fateful train ride in 1940 and passed on the basic concepts or the so-called von Neumann Machine (I/O, CPU, memory). "The story starts in the mid 1930s with Atanasoff driving 100 mph down a yardstick-straight Iowa road." The rest is the real history.

Ron Wolf

[email protected]

Ed responds: Ron, thanks for your note. Scott McCartney covers the Atanasoff story in the book ENIAC: The Triumphs and Tragedies of the World's First Computer, which I mentioned in the column. Here's the bottom line (page 212-213):

...Eckert said, "The work by Dr. Atanasoff in Iowa was, in my opinion, a joke. He never really got anything to work. He had no programming system. He tried for a patent and was told the work he had done was too incomplete to get a patent. A competitor in a patent suit convinced what in my mind was a very confused judge to believe Atanasoff's story, even though it had no real relation to the case at hand."

"Mauchley and I achieved a complete workable computing system. Others had not," Eckert said. "If Edison is the inventor of the incandescent lamp it would appear that by the same yardstick Mauchley and I are clearly the inventors of the computer."

McCartney notes that the relevant court case was Sperry versus Honeywell, not Atanasoff versus Mauchley and that the decision broke the Sperry/IBM lock on the key patents. By invalidating the ENIAC patent, the judge ensured that everybody had access to the raw materials of the computer age. Blowing away Eckert and Mauchley's claim to inventing the computer was just regrettable collateral damage.

The details of what Atanasoff did and did not accomplish, who he met with, what they knew and when they knew it, are all covered in reasonable detail. Atanasoff had several opportunities over the course of many years to stake his claim and did not, despite running a well-funded Navy computer program into the ground, so his claims came rather late in the day.

DDJ

Listing One

// Demonstrates double dispatch using two consecutive vtable lookups
// based on Jeff Alger, 'Secrets of the C++ Masters' ISBN 0-12-049940-1
// author: Wolfgang Stephan [email protected]
#include <stdio.h>

class Asteroid;
class SpaceStation;
class SpaceShip;
class GameObject
{
public:
	virtual void collideWith(GameObject&)=0;
	virtual void collideWith(Asteroid&)=0;
	virtual void collideWith(SpaceStation&)=0;
	virtual void collideWith(SpaceShip&)=0;
};
class Asteroid : public GameObject
{
public:
	virtual void collideWith(GameObject& g)  { g.collideWith(*this); } 
                                   // double dispatch via 2nd vtable lookup
	virtual void collideWith(Asteroid&)      { printf("Asteroid <-> Asteroid\n"); }
	virtual void collideWith(SpaceStation&)  { printf("Asteroid <-> SpaceStation\n"); }
	virtual void collideWith(SpaceShip&)     { printf("Asteroid <-> SpaceShip\n"); }
};
class SpaceStation : public GameObject
{
public:
	virtual void collideWith(GameObject& g)   { g.collideWith(*this); }
	virtual void collideWith(Asteroid&)     { printf("SpaceStation <-> Asteroid\n"); }
	virtual void collideWith(SpaceStation&) { printf("SpaceStation <-> SpaceStation\n"); }
	virtual void collideWith(SpaceShip&)    { printf("SpaceStation <-> SpaceShip\n"); }
};
class SpaceShip : public GameObject
{
public:
	virtual void collideWith(GameObject& g)  { g.collideWith(*this); }
	virtual void collideWith(Asteroid&)     { printf("SpaceShip <-> Asteroid\n"); }
	virtual void collideWith(SpaceStation&) { printf("SpaceShip <-> SpaceStation\n"); } 
	virtual void collideWith(SpaceShip&)    { printf("SpaceShip <-> SpaceShip\n"); }
};
// behaves same way as SpaceShip, except for special collision with asteroids
class CommercialShip : public SpaceShip
{
public:
	virtual void collideWith(GameObject& g)  { g.collideWith(*this); }
	virtual void collideWith(Asteroid&)     { printf("CommercialShip <-> Asteroid\n"); }
};
int main(int argc, char* argv[])
{
	GameObject* p1 = new Asteroid;
	GameObject* p2 = new SpaceShip;
	p1->collideWith(*p2);
	GameObject* gameObjs[4];
	gameObjs[0]= new Asteroid;
	gameObjs[1]= new SpaceStation;
	gameObjs[2]= new SpaceShip;
	gameObjs[3]= new CommercialShip;
	// start the battle...
	for (unsigned i=0;i<4;++i)
		for (unsigned k=0;k<4;++k)
			gameObjs[i]->collideWith(*gameObjs[k]);
	return 0;
}

Back to Article