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

in the Printer hierarchy.

An elaboration of the above example in Java is at Double Dispatch Example.

Isn't this what the Gang Of Four Visitor Pattern does? And Common Lisp has built into the language via its Generic Functions?

Dan Ingalls 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 Ivan Sutherland's PhD thesis.

-- Ralph Johnson

Boy This Stuff Makes Me Feel Stupid ... 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 Double Dispatch Example

See forum.java.sun.com (Broken Link) for a "simple" example of a case where Multiple Dispatch is the "expected" behaviour in Java, and why it is puzzling that such behaviour doesn't actually occur in Java.

Item 31 in More Effective Cee Plus Plus is "Making functions virtual with respect to more than one object", i.e., Multiple Dispatch. 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 More Effective Cee Plus Plus.

Andrei Alexandrescu's book on Modern Cee Plus Plus Design contains a chapter titled "Multimethods" that discusses several schemes to implement Double Dispatch in standard Cee Plus Plus.

Double Dispatch is a way of working around a lack of Multi Methods, and as such, could be considered a Language Smell.

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.

Double Dispatch 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 Bridge Pattern?). I have a big err with this situation, where does the actual 'doing' code go? Or is this incorrect usage of Double Dispatch and should something else be used (like the Visitor Pattern)? Any thoughts?

---

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

etc

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

-- Bill Weston

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 Double Dispatch enough times here that I needed to understand what it meant. I read most of this page, sure that Double Dispatch meant something truly interesting, but completely baffled what that could be - so I checked the Double Dispatch Example page. Upon seeing the six lines of code in the client class, it is completely obvious how to implement Double Dispatch.

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

-- Anonymous Donor

Well, you've at least misunderstood Multi Methods. 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.

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

Multi Methods 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?

-- Dan Muller

An approach to Double Dispatch using the Visitor Pattern has been patented in the United States. See Ibm Double Dispatch Patent.

See also Multiple Dispatch, Message Oriented Programming

Category Polymorphism Category Conditionals And Dispatching

See original on c2.com