Polymorphism Unique Deep Dive: Think Single vs Double Dispatch

Polymorphism Basics

Let’s start from polymorphism basics with an example. Let’s have a hierarchy of shapes that are defined with each of the derived types overloading a base virtual Draw() method.  Next, we used a console application to define a list of each of the shapes. And to iterate over each shape in the collection calling the Draw() method of each item in the list:

class Shape
    {
        public virtual void Draw()
        {
            Console.WriteLine("A shape is drawn.");
        }
    }

    class Polygon : Shape
    {
        public override void Draw()
        {
            Console.WriteLine("A polygon is drawn.");
        }
    }

    class Quadrilateral : Polygon
    {
        public override void Draw()
        {
            Console.WriteLine("A quadrilateral is drawn.");
        }
    }

    class Parallelogram : Quadrilateral
    {
        public override void Draw()
        {
            Console.WriteLine("A parallelogram is drawn.");
        }
    }

    class Rectangle : Parallelogram
    {
        public override void Draw()
        {
            Console.WriteLine("A rectangle is drawn.");
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            var shapes = new List<Shape>
                             {
                                 new Shape(),
                                 new Polygon(),
                                 new Quadrilateral(),
                                 new Parallelogram(),
                                 new Rectangle()
                             };

            foreach (Shape shape in shapes)
            {
                shape.Draw();
            }

            Console.ReadLine();
        }
    }

When we run the application; we see the following lines in the console:

A shape is drawn.
A polygon is drawn.
A quadrilateral is drawn.
A parallelogram is drawn.
A rectangle is drawn.

Note that the program calls proper Draw() method for each item in the collection. Most object-oriented languages achieve this polymorphic behavior is through the use of a virtual table consulted at run-time. It derives the proper offset address for an object’s method from the table. We refer to this behavior as “Dynamic Dispatch” or “Single Dispatch”.
So, how does this relate to Double Dispatch?
To answer this question, let’s next review method overloading.

Method Overloading

In the following example, let us redefine our Shape class to have two overloaded Draw methods. One with a parameter of type Surface and one with a parameter of type EtchASketch:

    class Surface
    {
    }

    class EtchASketch : Surface
    {
    }

    class Shape
    {
        public void Draw(Surface surface)
        {
            Console.WriteLine("A shape is drawn on the surface with ink.");
        }

        public void Draw(EtchASketch etchASketch)
        {
            Console.WriteLine("The knobs are moved in attempt to draw the shape.");
        }
    }
  
    class Program
    {
        static void Main(string[] args)
        {
            var shape = new Shape();
            shape.Draw(new Surface());
            shape.Draw(new EtchASketch());

            Console.ReadLine();
        }
    }

When we execute the application; we see the following lines in the console:

A shape is drawn on the surface with ink.
The knobs are moved in attempt to draw the shape.

Note that the parameter type determines which Draw() method to invoke.
But what happens if we change the Main() method to the following?

class Program
    {
        static void Main(string[] args)
        {
            var shape = new Shape();
            Surface surface = new Surface();
            Surface etchASketch = new EtchASketch();

            shape.Draw(surface);
            shape.Draw(etchASketch);

            Console.ReadLine();
        }
    }

Executing this produces the following:

A shape is drawn on the surface with ink.
A shape is drawn on the surface with ink.

Dispatch Types

Single dispatch is when a method is polymorphic on the type of one parameter (including the implicit this). Double dispatch is polymorphism on two parameters.

The typical example for the first one is a standard virtual method, which is polymorphic on the containing object’s type. And we can implement the second one via the Visitor pattern.

• static dispatch -> the dispatch order is defined at compile time. It simply means that any function/method call say foo() or x.foo() will always invoke the very same function — this is established once and then stays that way. This implies that the compiler can determine the type of x at compile time.
• dynamic dispatch -> the dispatch order is resolved at run time. This means the compiler builds a lookup table of all functions/methods and determines which one to actually call at run time. Say there there is class A and B, both of which implement interface X with method X.bar(). At runtime, y is examined and based on its actual class either A.bar() or B.bar() is called.
• multiple dynamic dispatch -> the dispatch order is dependent on function/method name + argument types. And the actual implementation that gets called is determined dynamically at runtime. Say class A implements methods A.fooBar(int) and A.fooBar(char *). There is a call to a.fooBar(x) in our program. At runtime both a and x are examined and the actual method to call is determined based on the type of x.

Runtime Polymorphism

Runtime polymorphism or dynamic method dispatch is a feature of object-oriented programming languages that allows a subclass or derived class to provide a different implementation for a method that is already defined in its superclass or base class. This is achieved by creating a method with the same name and signature in the derived class as in the base class, and then replacing or “overriding” the implementation of the method in the derived class.

At runtime, when an object of the derived class is created and a method is called on it, the object will execute the overridden version of the method rather than the one inherited from the base class. This allows the derived class to customize the behavior of the method to suit its own needs, while still maintaining the same interface as the base class.

For example, consider a base class called “Shape” that has a method called “area” that calculates the area of the shape. A derived class called “Rectangle” might override the “area” method to provide its own implementation that calculates the area of a rectangle using the length and width of the rectangle. When an object of the “Rectangle” class is created and the “area” method is called on it, the object will execute the overridden version of the method, which calculates the area of a rectangle.

In this way, runtime polymorphism allows an object to behave differently based on its type, even if the object is referred to through a base class reference. This can be useful for creating more flexible and reusable code, as it allows different types of objects to be used interchangeably without the need to write separate code for each type.

Bringing All Together: Visitor Pattern

In C/C++, for the paradigm of separating function from data; our tools are functions and structs. Along the way; we have something called virtual function dispatching that allows us to have different function implementations based on the different type of data. This is a little something we like to call ‘polymorphism’ in the Computing world. In fact, polymorphism is a fundamental pillar of Object Oriented programming. It is also a form of what is called ‘single dispatch’, whereby we make a single function call and it’s dispatched to the proper implementation based on the data type. The compiler builds a virtual function table, and ensures that the correct function is called based on the type. So this example will be C++ syntax, to show virtual single dispatch.

// create a virtual base class
class base
{
public:
    virtual ~base() = default;
    virtual void do_something()
    {
        // do something
    }
};

// override the base class
class derived : public base
{
public:
   virtual void do_something() override
   {
       // do something derived
   }
}; 

int main()
{
     base b;
     derived d;
     base &a = b;
     base &c = d;
     
     // call the correct function, from the base, to the derived
     // base do_something
     a.do_something();

     // derived do_somethng
     c.do_something();
}

So Single Dispatch, virtual function table, and data / function segregation.
Now, there’s a second type of Single Dispatch called ‘function overloading’; , but it doesn’t exist in C. In C++,  it’s done at compile time. Basically, the compiler picks the right function based on the type passed in. Something like this….

void foo(int i)
{
    // do foo for int
}

void foo(double d)
{
    // do foo for double
}

int main()
{
   double pi{3.1415};
   int i{0};
   foo(i);
   foo(pi);
}

As I mentioned, this form of dispatching is only at compile time. The compiler has to know the type when selecting the proper overload. So something like below code won’t work –

class ibase
{
public:
    virtual ~ibase() = default;
    virtual void do_something() const = 0;
};

class derived1 : public ibase
{
public:
   virtual void do_something() const override
   {
   };
};

class derived2 : public ibase
{
public:
   virtual void do_something() const override
   {
   }
};

void foo(const derived1 &d)
{
    d.do_something();
}

void foo(const derived2 &d)
{
   d.do_something();
}


int main()
{
   // This won't compile, it's for illustration purpose
   derived1 d1;
   derived2 d2;
   ibase &b1 = d1;
   ibase &b2 = d2;
   foo(b1);
   foo(b2);
}

However, the point is, that if we combine the two examples, we get ‘Double Dispatch’.  Now, if C++ supported this, that would be grand. But it doesn’t and the problem lies with what’s illustrated above. We can’t use a runtime type to do function overloading.

Double Dispatch?

From this point forward, we’re going to use a image system as an example. In our image system, the image can be of different types, and we want to be able to apply some different action to the image; adjust color, crop, scale, black & white, etc. If we sketch our example in our fairytale C++ language that supports runtime type function overloading. It would look like this –

struct rgb
{
public:
  unsigned char red, green, blue;
};

class iimage
{
public:
    virtual ~iimage()  = default;
    virtual int height() = 0;
    virtual int width() = 0;
    virtual rgb get_pixel_color(int x, int y) = 0;
    virtual void set_pixel_color(int x, int y, rgb color) = 0;
};

class bmp_image : iimage
{
  // any none shared functions  & data
  // implement shared functions
};

class jpg_image : iimage
{
  // any none shared functions & data
  // implement shared functions
};

class iaction
{
public:
    virtual ~iaction() = default;
    virtual void apply(bmp_image &image) = 0;
    virtual void apply(jpg_image &image) = 0;
};

class adjust_color_action : iaction
{
    virtual void apply(bmp_image &image) override
    {
       // some specific algorithm for bmp images
    }
    
    virtual void apply(jpg_image &image) override
    {
       // some specific algorithm for jpg images
    }
};

void apply_action(iimage &image, iaction &action)
{
    action.apply(image);
};

int main()
{
    iimage &image = generate_image();
    iaction &action = get_user_action();
    apply_action(image, action);
}

So as you can see, if this was to compile, we’ve done two things, we’ve separated our algorithms from our data; actions & images, and given ourselves the ability to apply different algorithms based on the different types of data. We’re using both types of single dispatch at once, a runtime polymorphic virtual function dispatch, when we call ‘apply’. Then a runtime function overload, with the argument passed in. That right there — is Double Dispatch.

Unfortunate for us that runtime function overload, doesn’t exist in C++. So we need to somehow invert our call, so that the compiler can be sure of the type when it compiles.

Enter Visitor Pattern.

By inverting the dispatch of the action onto the image base, we can cause the dynamic dispatch to the action while knowing at compile time the type getting passed in. It looks like this.

struct rgb
{
public:
 unsigned char red, green, blue;
};

class iaction;

class iimage
{
public:
 virtual ~iimage() = default;
 virtual int height() = 0;
 virtual int width() = 0;
 virtual rgb get_pixel_color(int x, int y) = 0;
 virtual void set_pixel_color(int x, int y, rgb color) = 0;
 virtual void apply(iaction &action) = 0;
};

class bmp_image;
class jpg_image;

class iaction 
{ 
public: 
    virtual ~iaction() = default; 
    virtual void visit(bmp_image &image) = 0; 
    virtual void visit(jpg_image &image) = 0; 
};
class bmp_image : iimage
{
    // any none shared functions & data
    // implement shared functions
    virtual void apply(iaction &action) override
    {
         // the *this, tells the compiler, that when you
         // call apply on the bmp_image, it will call the
         // bmp_image overload of the iaction
         action.visit(*this);
    }
};

class jpg_image : iimage
{
    // any none shared functions & data
    // implement shared functions
    virtual void apply(iaction &action) override
    {
        action.visit(*this);
    }
};

class adjust_color_action : iaction
{
  virtual void visit(bmp_image &image) override
  {
    // some specific algorithm for bmp images
  }
 
  virtual void visit(jpg_image &image) override
  {
   // some specific algorithm for jpg images
  }
};

void apply_action(iimage &image, iaction &action)
{
    image.apply(action);
};

int main()
{
   iimage &image = generate_image();
   iaction &action = get_user_action();
   apply_action(image, action);
}

So as we can see, in this example we’re emulating Double Dispatch, by inverting our calls. Which uses first polymorphism to make the correct call, and then a compile time overloaded function. Voila! Double Dispatch, kind of. This pattern lends itself very nicely when we need to separate your function, from our data. It allows us to easily expand data function, without having to change code in the data. However, additional data becomes a bit of a pain, because we need to change all of your function classes to support the new data class.

The visitor pattern is a software design pattern that allows adding new behaviors to existing classes without modifying their code. It is a way of separating an algorithm from an object structure on which it operates.

In the visitor pattern, we create a separate class called the visitor that contains a set of methods, each one implementing an operation to be performed on the elements of an object structure. The object structure is made up of elements that have an “accept” method that takes a visitor as an argument.

When we call the accept method on an element, it passes itself to the visitor’s corresponding method, allowing the visitor to perform the desired operation on the element. This is known as double dispatch.

Polymorphism is the ability of an object to take on multiple forms. In the context of the visitor pattern, polymorphism allows the elements in the object structure to be of different types, and the visitor’s methods can be written to handle each type differently.

Single dispatch is when the type of an object is determined at runtime based on its class. In the visitor pattern, this would mean that the type of the element is determined when the accept method is called on it.

Double dispatch is when the type of an object is determined based on both its class and the type of the visitor passed to its accept method. This allows the visitor’s methods to be written specifically for each combination of element and visitor types.

Overall, the visitor pattern allows us to add new behaviors to existing classes without modifying their code, by separating the algorithm from the object structure and using polymorphism and double dispatch to handle different element and visitor types. This can be useful in scenarios where we need to perform different operations on the same object structure, or when we want to keep the object structure and algorithm separate for easier maintenance and extensibility.