Polymorphism Deep Dive: 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 process in which a call to an overridden method is resolved at runtime rather than compile-time. In this process, an overridden method is called through the reference variable of a superclass. The determination of the method to be called is based on the object being referred to by the reference variable. Whenever an object is bound with the functionality at run time, this is known as runtime polymorphism. The runtime polymorphism can be achieved by method overriding.

polymorphism
polymorphism

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.

double dispatch
double dispatch