Visitor and Double Dispatch
Let’s take a look at following class hierarchy of geometric shapes (beware the pseudocode):
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 each object into XML strings:
The code looks good, but let’s try it out:
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’re a compiler. You have to decide how to compile the following code:
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? It 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 object passed to the
shape parameter and picking the
draw implementation from the appropriate class.
Such a 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 a different implementation.
Now, let’s “compile” following code:
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 methods 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’s a shape class that doesn’t have appropriate
export method in
Exporter class? For instance, an
Ellipse object. The compiler can’t guarantee that the appropriate overloaded method exists in contrast with overridden methods. The ambiguous situation arises 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 the program is launched.
- Static because it can’t be altered at runtime.
Let’s return to our example. We’re sure that the incoming argument will be of
Shape hierarchy: either the
Shape class or one of its subclasses. We also know that
Exporter class has a basic implementation of the export that supports
That’s the only implementation that 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 an
export(s: Shape) method.
Double dispatch is a trick that allows using dynamic binding alongside with overloaded methods. Here how it’s done:
Even though the Visitor pattern is built on the double dispatch principle, that’s not its primary purpose. Visitor lets you add “external” operations to a whole class hierarchy without changing the existing code of these classes.