Java method dispatch and visitor pattern

This page explains the concept of method dispatch and different types of dispatch. And also explain issues related with method dispatch in implementing Visitor Pattern. Full implementation of Visitor Pattern is not covered.

Programming language determines which method to call via method dispatch.
In Java, overloaded method calling is determined by static dispatch, what happens in compile phase.

class CarElement { }
class Engine extends CarElement { }
class Wheel extends CarElement { }
class CarElementVisitor {
    public void visit(CarElement element){
        System.out.println("CarElement visited");
    }

    public void visit(Engine element){
        System.out.println("Engine visited");
    }

    public void visit(Wheel element){
        System.out.println("Wheel visited");
    }
}
public class Test {
    public static void main(String[] args) {
        CarElement carElement = new Engine();
        //The dispatch based on static/apparent type, even it is Engine,
        //but "CarElement" is printed in the console
        new CarElementVisitor().visit(carElement);

        Engine engine = new Engine();
        new CarElementVisitor().visit(engine);
    }

}

output is:

CarElement visited
Engine visited

Overridden Method calling is determined by dynamic dispatch, what happens in run time. This is the traditional polymorphism.

public class Test {
    public static void main(String[] args) {
        CarElement wheel = new Wheel();
        //The dispatch based on actual type
        System.out.println(wheel.getClass());

        CarElement engine = new Engine();
        //The dispatch based on actual type
        System.out.println(engine.getClass());
    }
}

output is:

class Wheel
class Engine

In the above example of static dispatch, the dispatch cares the receiver only, don’t care the actual argument type. This sort of dispatch is single dispatch. Programing languages like C++, Java, Smalltalk Objective-C, JavasScript and Python are single dispatch.

There is another type of dispatch, that is double/multiple dispatch, double multiple dispatch is a special form of multiple dispatch.
Language like C# use double dispatch. In C#, variables declared as dynamic, type will not be checked at compile time, its type is determined at run time as well. Take above static dispatch example in Java, if it is in C#, the correct method will executed based on argument actual type.

Single and Double dispatch is a key issue in implementing the Visitor Pattern. Define Element(Node) and Visitor(NodeVisitor) interface,

interface CarElement {
    void accept(CarElementVisitor visitor);
}

interface CarElementVisitor {
    void visit(Body body);
    void visit(Car car);
    void visit(Engine engine);
    void visit(Wheel wheel);
}

There are 2 issues here,

  • Which concrete CarElement accept() will be dispatched?
  • Which concrete CarElementVisitor visit() will be dispatched?

The first dispatch is easy, because it is via method overridden, thus once the correct concrete CarElement is chosen, the correspond accept() will be executed.
The second issue is a little bit confused in Java, because it is overload. However, it is not a problem, see reason in inline comment,

class Engine implements CarElement {
    public void accept(final CarElementVisitor visitor) {
        //type of argument "this" is Engine,
        //so visit() will be dispatched to visit(Engine engine)
        //in the concrete CarElementVisitor
        visitor.visit(this);
    }
}

Basically, the double dispatched is implemented above.
This same issue not exist in C#, because the language itself support double dispatch.
Wikipedia gives a very helpful description of this topic at below articles,
Visitor Pattern, Double Dispatch.
And, Using Type dynamic in C# programming guide give helpful explanation of dynamic type.