Double Dispatch

Say you have three kinds of figures that you want to print on four kinds of printers. The message

circleFigure printOn: laserPrinter

must dispatch on both the Figure and Printer hierarchies. One does this by defining methods like

printOn: aPrinter
aPrinter printCircle: self

in the Figure hierarchy and methods like

printCircle: aCircle
... circle printing stuff ...

in the Printer hierarchy.

An elaboration of the above example in Java is at DoubleDispatchExample.

Isn't this what the GangOfFour VisitorPattern does? And CommonLisp has built into the language via its GenericFunctions?

DanIngalls wrote this technique up for one of the early OOPSLAs. The program committee almost rejected the paper because the idea was considered obvious, or insufficiently scientific, or something like that.

It was one of my favorite OOPSLA papers, and it was because OOPSLA doesn't publish papers like that any more that I wanted to start a conference on patterns, where an idea will not be rejected just because it was in IvanSutherland's PhD thesis.

-- RalphJohnson

BoyThisStuffMakesMeFeelStupid ... Would someone be willing to create a more verbose example? (hopefully in Java or C++) Perhaps it would make more sense (to me at least) if there were more code that a person could step through.

See DoubleDispatchExample

See http://forum.java.sun.com/read/16789542/q_tzLgu-LxJkAAagM (BrokenLink) for a "simple" example of a case where MultipleDispatch is the "expected" behaviour in Java, and why it is puzzling that such behaviour doesn't actually occur in Java.

Item 31 in MoreEffectiveCeePlusPlus is "Making functions virtual with respect to more than one object", i.e., MultipleDispatch. Actually, he concentrates on double dispatch, and only waves his hands at dispatching on n > 2 objects. At 24 pages, it is one of the longest items in the book. Meyers discusses several alternative approaches to implementation, and the advantages and (mostly) disadvantages of each. He comes up with a workable way of doing it, while making you appreciate what the compiler does for you in single dispatch and making you wish you were using a language that did all this for you.

Meyers' stimulating article is rather old now, and one can do much better in several respects... As you point out, he sticks to double dispatch. Also he uses typeid(T).name() as his type identifier key, which is not actually guaranteed to be unique, and he requires all user functions to down cast their arguments, and does not consider different base types for the same argument slots, etc. etc.

Most importantly, Meyers does not tackle the problem of how to find the correct polymorphic match when the calling signature does not exactly match one of the candidate functions. But then I don't think the template trickery that enables us to do this nowadays was around when he wrote MoreEffectiveCeePlusPlus.

AndreiAlexandrescu's book on ModernCeePlusPlusDesign contains a chapter titled "Multimethods" that discusses several schemes to implement DoubleDispatch in standard CeePlusPlus.

DoubleDispatch is a way of working around a lack of MultiMethods, and as such, could be considered a LanguageSmell.

I personally prefer some sort of table lookup. It is easier to manage and view a bunch of these in tables than in linear code IMO. Plus, with tables you can have/add X-way dispatching if need be without significant structure alteration for each new dimension.

DoubleDispatch may work well with different basic types of objects, but what about objects of the same basic type and essentially functionality?

Take for example a simple primitive collision system; you may have spheres, bounding boxes, lines, points etc. and you would like to be able to test every primitive type against every other primitive type, with the possibility of adding in new primitives in the future without modifying existing code (maybe in conjunction with the BridgePattern?). I have a big err with this situation, where does the actual 'doing' code go? Or is this incorrect usage of DoubleDispatch and should something else be used (like the VisitorPattern)? Any thoughts?

---

The doing code is all you have to write!!! (in an ideal world)... and it goes in the obvious place....

    collide(Sphere& sphere, Box& box) { /* do sphere box collision here */  }
    collide(Sphere& sphere, Line& line) { /* do sphere line collision here */  }

etc

then the calling code just collides two shapes, and the right 'doing' is automatically done!

    Shape shape1 = *new Sphere, shape2 = *new Box;
    collide(shape1, shape2);

-- BillWeston

Can you say something more about what you mean by "a simple primitive collision system"? Suppose you have classes Sphere, Box, Line and Point. Do you want to define operations on these, and then be able to add new geometric classes that participate in these operations?

There is a concept - a pattern I "have" - that I'm struggling to name. After encountering DoubleDispatch enough times here that I needed to understand what it meant. I read most of this page, sure that DoubleDispatch meant something truly interesting, but completely baffled what that could be - so I checked the DoubleDispatchExample page. Upon seeing the six lines of code in the client class, it is completely obvious how to implement DoubleDispatch.

I have a sort of block where I can't understand certain patterns by description because they are so obvious and I'm expecting some sort of deeper meaning. Then when I realized what they are, I realize it's something I've done dozens of times.

I wonder if this dooms me to cowboy programmer status for eternity. I guess I'd make a crappy academic, too.

I haven't learned the language of language architects. I have found educational texts to be condescending, irrelevant, or possessing too much noise for the signal. I've learned everything I know about programming from language reference texts and working examples while working out my immediate problems.

I do have this to ask: Why would you want MultiMethods for solving this sort of problem? It seems terribly disorganized compared to the alternative. I don't understand how the multimethods version is easier/better/faster/intuitive/maintainable.

Taking the printer example, you define a set of drawing primitives (the least likely to change axis), and you define a printer interface so that each printer implementation can draw each primitive.

Each time you add a different type of printer, the new drawing code goes there in the new printer class. Organized.

With multimethods, you would have one class that had the cartesian product (printers x shapes) of methods for rendering on different printers. Is this fear of adding classes?

I suspect I'm somehow missing the point.

-- AnonymousDonor

Well, you've at least misunderstood MultiMethods. You've touched on three ways of approaching a task that varies according to the types of two objects (a printer, and a shape). (You talked about drawing primitives, but it's actually about shape objects of some sort -- this is critical, and may be at the heart of your misunderstanding.) Each one of these approaches involves a function or method for each valid combination of printer and shape. The differences are in how the code is arranged, and how much code the programmer has to write to get control dispatched to the correct function.

We'll assume that the printers all have a common base class (APrinter), and the shapes also have a common base class (AShape).

In the simplest case, as you say, you extend the printer interface with a separate function per shape that it can render. Now, given some code where you have a printer object, and a shape object. But the code only knows the printer object to be of type APrinter (assuming a statically typed language), and the shape object to be of type AShape. How do you, or the compiler, know which printer method to call? That's the crux of the problem. You need to select the method based on the run-time types, not the static types, of two objects.

DoubleDispatch is a pattern for solving this problem in a typical OO language that can dispatch only on one object's type. It requires a bit of extra work by the programmer.

MultiMethods are inherently polymorphic on multiple objects, so you simply write a method for each specific combination of derived types that you want to support, and call them in a straightforward way. In the code, it looks like you're passing an APrinter and an AShape to a function. The language system does the hard work for you, and selects the specific multimethod that's a closest match, according to whatever rules the particular language uses.

Does that explanation help?

-- DanMuller

An approach to DoubleDispatch using the VisitorPattern has been patented in the UnitedStates. See IbmDoubleDispatchPatent.

CategoryPolymorphism CategoryConditionalsAndDispatching