Double Dispatch

A typical runtime polymorphism works on method invocations where the call is on supertype but the actual method comes from the runtime subtype. However, the method selection is not polymorphic in itself, meaning only the method whose signature exactly matches the signature of the call can be invoked.

Double dispatch is a way to achieve runtime polymorphism where method implementation is selected based on both the callee object and actual argument object.

e.g. Consider this class hierarchy:

class A { method(E){} method(F){} }<--class B<--class C 
class E<-- class F

A, B, C have overloaded methods. Note that overloading is early-binding (compile-time polymorphism).

So, a call like

A a = new B();
E e = new F();
a.method(e);

would result in B.method(E) invocation. Which is a classic runtime polymorphism case. A double dispatch would however would result in B.method(F) invocation.

Implementation of Double Dispatch
The idea is to use reference-types for callee and the argument before the method call is dispatched to its implementation, as every invocation on the reference-type would show a runtime polymrphism.

In order to do this, we introduce a new method in E/F as follows:

method(A a) {
  a.method(this);
}

and change the calling program to

A a = new B();
E e = new F();
e.method(a);

This would first dispatch the call to F's implementation of method(A) and from there B's implementation of the method where the argument type is F i.e. B.method(F) .

thats all we set out to do!

Visitor Pattern and Double Dispatch
A visitor pattern is applicabe where we want to add a method to elements of a object hierarchy without changing the classes of the constituents.

We add methods to the visitor not to the classes it visits. The visited objects call back the visitor passing themselves. The visitor would have implementations for all the classes it can visit.

In the example given above A,B,C act as visitors to E,F.
If you have added a new type (e.g. G) in the structure, all you need is to add a method that accepts that type as argument in one of the visitors or a new visitor (e.g. method(G){}) and this method will be invoked whenever an object of G is visited.

Typically, the methods take the following form

visitable.accept(visitor);
...
accept(Visitor vistitor) {
  visitor.visit(this); 
}

Which is analogous to

e.method(a);
...
method(A a) {
  a.method(this);
}