Visitor and Double Dispatch
Let's take a look at following class hierarchy of geometric shapes (beware the pseudocode):
interface Graphic is method draw() class Shape implements Graphic is field id method draw() // ... class Dot extends Shape is field x, y method draw() // ... class Circle extends Dot is field radius method draw() // ... class Rectangle extends Shape is field width, height method draw() // ... class CompoundGraphic implements Graphic is field children: array of Graphic method draw() // ...
The code works fine and the app is in production. But one day you decided to make an export feature. The export code would look alien if placed in these classes. So instead of adding export to all classes of this hierarchy you decided to create a new class, external to the hierarchy, and put all the export logic inside. The class would get methods for exporting public state of ech objects into XML strings:
class Exporter is method export(s: Shape) is print("Exporting shape") method export(d: Dot) print("Exporting dot") method export(c: Circle) print("Exporting circle") method export(r: Rectangle) print("Exporting rectangle") method export(cs: CompoundGraphic) print("Exporting compound")
The code look good, but let's try it out:
class App() is method export(shape: Shape) is Exporter exporter = new Exporter() exporter.export(shape); app.export(new Circle()); // Unfortunatelly, this will output "Exporting shape".
Thinking as a compiler
Note: the following information is true for the most modern object oriented programming languages (Java, C#, PHP and others).
Pretend that you are compiler. You have to decide how to compile following code:
method drawShape(shape: Shape) is shape.draw();
Let's see... the
draw() method defined in
Shape class. Wait a sec, but there are also four subclasses that override this method. Can we safely decide which of the implementations to call here? Doesn't look so. The only way to know for sure is to launch the program and check the class of an object passed to the method. The only thing we know for sure is that object will have implementation of the
So the resulting machine code will be checking class of the
s parameter and picking the
draw() implementation from the appropriate class.
Such dynamic type check is called late (or dynamic) binding:
- Late, because we link object and its implementation after compilation,at runtime.
- Dynamic, because every new object might need to be linked to different implementation.
Now, let's "compile" following code:
method exportShape(shape: Shape) is Exporter exporter = new Exporter() exporter.export(shape);
Everything is clear with the second line: the
Exporter class doesn't have a constructor, so we just instantiate an object. What's about the
export() call? The
Exporter has five method with the same name that differ with parameter types. Which one to call? Looks like we're going to need a dynamic binding here as well.
But there's another problem. What if there is a shape class that does not have appropriate
export() method in
Exporter class? For instance, an
Ellipse object. Compiler can't guarantee that appropriate overloaded method exists in contrast with overridden methods. The ambiguous situation arise which a compiler can't allow.
Therefore, compiler developers use a safe path and use the early (or static) binding for overloaded methods:
- Early because it happens at compile time, before program is launched.
- Static because it can't be altered at runtime.
Let's return to our example. We are sure that incoming argument will be of
Shape hierarchy: either the
Shape class or one of its subclasses. We also know that
Exporter class has basic implementation of the export that supports
That's the only implementation which can be safely linked to a given code without making things ambiguous. That's why even if we pass a
Rectangle object into
exportShape, the exporter will still call a
export(s: Shape) method.
Double dispatch is a trick that allows using dynamic binding alongside with overloaded methods. Here how it's done:
class Visitor is method visit(s: Shape) is print("Visited shape") method visit(d: Dot) print("Visited dot") interface Graphic is v.visit(this) class Shape implements Graphic is method accept(v: Visitor) // Compiler knows for sure that `this` is a `Shape`. // Which means that the `visit(s: Shape)` can be safely called. v.visit(this) class Dot extends Shape is method accept(v: Visitor) // Compiler knows that `this` is a `Dot`. // Which means that the `visit(s: Dot)` can be safely called. v.visit(this) Visitor v = new Visitor(); Graphic g = new Dot(); // The `accept()` method is overriden, not overloaded. Compiler binds it // dynamically. Therefore the `accept()` will be executed on a class that // corresponds to an object calling a method (in our case, the `Dot` class). g.accept(v); // Output: "Visited dot"
Even though the Visitor pattern is built on the double dispatch principle, that's not its primary purpose. Visitor allows adding "external" operations to a whole class hierarchy without changing existing code of these classes.