Polymorphism, Dynamic Dispatch, and Visitor

Let’s revisit a classic example from our early days of object-oriented programming: shapes and transformations. We will design a system that allows applying scaling and rotation to lines, circles, and rectangles. However, this time, we’ll take it a step further and make it extensible. This means future developers should be able to easily add new types of transformations without modifying existing code.

What we need is a polymorphic function that exhibits different behaviour based on the data we provide. Specifically, a function that performs various transformations (rotate, scale, etc.) on the shape/type (Line, Circle, Rectangle) of the object. Basically we want a function

1apply(transformation, shape); 

The challenge is to design a model such that adding new transformation is trivial.

Well, we have to start somewhere!

We could try to simply mimic the above function as a polymorphic method in a Transformer class, but we will soon realise the function will get messy with if-else clauses or switch cases. Also adding new transformations entails modifying the method which goes against Open-closed Principle.

Function Overloading (Static Polymorphism)

Function overloading or method overloading is the ability to create multiple functions of the same name with different implementations. Overloading is resolved statically, that is at compile time, depending only on the static types of the arguments (different argument types, different number of arguments). For any particular call, the compiler determines which overloaded function to use, and resolves this

This seems like the way forward, don’t you think? Multiple implementations with same function name (transform) with different behaviour based on the parameters we passed (transformations and shapes).

 1public class Transformer {
 2  public Shape transform(Scale s, Rectangle r) {
 3     // Scale the given rectangle r by a factor represented by Scale s
 4  }
 5  
 6  public Shape transform(Rotation r, Circle c) {
 7     // Rotating a Circle doesn't make any sense !!
 8  } 
 9  
10  ...
11}

Using overloaded functions to achieve different behaviour for different shapes and transformations would lead to an explosion of classes and methods, making the code cumbersome and difficult to maintain. All we are doing is breaking the switch statement in previous approach into their own functions. Each case is its own function.

Method Overriding (Dynamic Polymorphism)

Method overriding, in object-oriented programming, allows a subclass or child class to provide a specific implementation of a method that is already provided by one of its superclasses or parent classes. The version of a method that is executed will be determined by the object that is used to invoke it. Overriding allows Subtype polymorphism.

To make use of dynamic polymorphism, we have to group our objects into special classes that shares a common interface.

At first, you might be tempted to create an interface like this:

1public interface Shape {
2    Shape scale(double factor); // Scale the shape by a factor
3    Shape rotate(double angle); // Rotate the shape by an angle (in radians)
4
5}

This approach seems straightforward, but it suffers from a crucial flaw: with this interface, adding a new transformation requires modifying all existing shape classes to implement the new method. It violates the Open-Closed Principle (OCP). OCP expects our software to be open for extension.

Behaviour as Objects (Combining both)

Notice that adding a new transformation must be easy, lets model transformations as objects. Supporting a new transformation in future is as simple as creating a new class that implements the Transformation interface.

First the Shapes themselves:

1public interface Shape { }
2
3public class Line implements Shape { }
4public class Circle implements Shape { }
5public class Rectangle implements Shape { }  

Then, we implement transformation for each shape.

 1public interface Transformation {
 2  void apply(Line line);
 3  void apply(Circle circle);
 4  void apply(Rectangle rectangle);
 5  
 6  default void apply(Shape shape) {
 7    System.out.println("Unknown Shape... Cannot apply transformation!");
 8
 9  }
10}
11
12public class Scale implements Transformation {
13  private final double factor;
14
15  public Scale(double factor) {
16    this.factor = factor;
17  }
18  
19  @Override
20  public void apply(Line line) {
21    System.out.println("Applying Scaling transformation to Line");
22  }
23
24  @Override
25  public void apply(Circle circle) {
26    System.out.println("Applying Scaling transformation to Circle");
27  }
28
29  @Override
30  public void apply(Rectangle rectangle) {
31    System.out.println("Applying Scaling transformation to Rectangle");
32  }
33}

Let’s give this a run. But before that we need a simple client :

 1Shape line      = new Line()
 2Shape circle    = new Circle();
 3Shape rectangle = new Rectangle()
 4
 5Transformation transformation = new Scale(0.5);
 6
 7List<shape> shapes = new ArrayList<>();
 8shapes.add(line);
 9shapes.add(circle);
10shapes.add(rectangle);
11
12for (Shape shape : shapes) {
13    transformation.apply(shape);
14}

Here is what you will get-

1Unknown Shape... Cannot apply transformation!
2Unknown Shape... Cannot apply transformation!
3Unknown Shape... Cannot apply transformation!

Oops! This isn’t what we expected! What happened? To understand what happened, we need to take a deeper look first.

Static and Dynamic Dispatch

In static dispatch the polymorphic function/method is fully resolved during compile time (Overloading). In dynamic dispatch, resolution happens at run time. It is considered a prime characteristic of object-oriented programming.

1for (Shape shape : shapes) {
2    transformation.apply(shape);
3}

During compilation, the type of transformation and shape objects are not known. Which of the 3 overloaded apply method is to be called? This is resolved at runtime. Depending on the type of shape object method call is ‘dispatched’ to appropriate function.

This still doesn’t explain the behaviour we observed.

1Unknown Shape... Cannot apply transformation!

Single Dispatch

When the dispatching is done based on receiver alone (or first arg to the function), it is called Single Dispatch system. Java, C, C++, both use single dispatch. When a method is overridden, this is how the correct object’s method are called even when the type of the ref is of parent type (Subtype polymorphism).

Example:

1objRef.method(arg1, arg2);
2method(objRef, arg1, arg2);

In single dispatch system, only the type of objRef is considered while dispatching. Type of arg1 and arg2 are not considered.

1transformation.apply(shape);

For the the above code to work, there needs to be two levels of dispatch -

1. choosing which transformation to call (based on the receiver type)

2. choosing which apply(shape) method to call (based on argument type)

In Java, only the type of receiving object (transformation) is considered. Type of shape is the type of the reference which is Shape. Hence, the call to the apply method is resolved to the default apply method from Shape interface.

Well, that explains the weird behaviour, but what do we do now?

Multiple Dispatch

Multiple dispatch is like overloading but at runtime. Types of all the params are considered to dispatch to correct function. Some languages support this (C#, Clojure, CommonLisp, Julia). Few languages use libraries for the same. If your language doesn’t support this, you have to do another redirection

Additional Redirection for Double Dispatch

The idea is behind redirection is to remove one level of dynamic dispatch by handling it ourself by making use of the this reference. Instead of passing our shapes to apply method, we pass our transformation object to our shapes which will redirect correctly to appropriate apply method.

First we add a method to our Shape interface for redirection. It is usually named accept.

1public interface Shape {
2  public void accept(Transformation t);
3}

All our Shape classes will now implement this method.

1public class Line implements Shape  {
2  
3  @Override
4  public void accept(Transformation t){
5    t.apply(this);
6  }
7}

By passing this, we are essentially handing over the current Line object to t. This ensures that the visitor receives the specificLine instance that needs to be transformed, not just a genericShape object.

Also, because of this redirection, there is no need to overload the apply method. We can safely name them differently according to the shape - applyToLine, applyToCircle, applyToRectangle, etc.

Now we modify the client slightly to use our new accept method.

1for (Shape shape : shapes) {
2  //transformation.apply(shape);
3  shape.accept(transformation);
4}

Lets give this a run -

1Applying Scaling transformation to Line
2Applying Scaling transformation to Circle
3Applying Scaling transformation to Rectangle

This is exactly what Visitor design pattern achieve - Double Dispatch.