Intro
In this article, I will present a more sophisticated type of Polymorphism that you’re probably not familiar with. The reason being it’s not directly supported in many of the modern general-purpose languages like Java, C#, Ruby, etc.
Nevertheless, we still often emulate it via a series of twisted virtual calls. That’s why it’s important to understand the core concept. This will make you more aware of your program design in general.
Namely, I will discuss the idea of Multiple Dispatch (Multimethods).
I wasn’t familiar with those terms and their semantics until receiving some very valuable feedback on the Clash of Styles Series, more specifically the Double Dispatch and the Visitor Pattern parts.
This helped me figure out that the popular notion of Polymorphism (or Virtual Dispatch) is actually quite restrictive. It’s all about a single argument in a function call – the implicit this/self/me reference.
This post is not a theoretical overview of some esoteric language features you’ll never see or hear about again. As I already mentioned, we emulate it quite frequently, although we don’t realize it. What’s more, Multiple Dispatch has an even stronger influence in the C# language after introducing the dynamic keyword.
Whatever your language of choice may be, I believe this article will generally strengthen your understanding of polymorphic/virtual calls and the rules for runtime method resolution.
It’s not About C# and “dynamic”
At the end of this article, you will see that in C#, although you shouldn’t, you can emulate Multiple Dispatch by using the dynamic keyword.
However, this is not the main focus of the post.
The discussion is meant to be language agnostic. It will be specifically applicable to languages with similar type systems like Java.
After this side note, it’s time to get concrete and present the actual example.
The Sample Use Case
For the examples in this article, I will stick to the problem domain from the Clash of Styles Series as it allows me to showcase the problem quite effectively.
However, I will re-introduce and simplify the use case because I’d like the code to be as minimal as possible, allowing me to focus directly on the problem.
Adding Integers and Rationals
Let’s say you have two types of numbers – integers and rational.
You want to implement an addition between them. In particular, the following four operations:
- Add a rational to an int
- Add an int to a rational
- Add an int to an int
- Add a rational to a rational
You want to do this in an OOP style. Thus, you will express all of the operations from the perspective of some objects that represent numbers.
For example, you will define how an int will add a rational to itself, how a rational would add another rational to itself, etc.
If this sounds a little confusing, it will become apparent in the upcoming sections.
The Starter Code
First, let’s declare an INumber interface with an Add(INumber) method signifying that every type of number can add any other type of number to itself:
public interface INumber
{
INumber Add(INumber number);
}
And a couple of classes that implement this interface. MyInt for integers and MyRational for rational numbers:
public class MyInt : INumber
{
// ...
public INumber Add(INumber number) => // Implementation
// ...
}
public class MyRational : INumber
{
// ...
public INumber Add(INumber number) => // Implementation
// ...
}
Now, imagine you have the following Adder method:
INumber Adder(INumber op1, INumber op2) => op1.Add(op2);
I know this method is not super useful. However, it makes it clear that the invocation op1.Add(op2) is polymorphic as we don’t know the concrete types of op1 and op2 at compile time.
Actually, the rules of Polymorphism depend only on the runtime type of op1.
Let me dissect that in the next section.
Polymorphism on the Receiver – The “Standard” Single Dispatch
So, how does the runtime handle the invocation op1.Add(op2)?
That’s easy. We’ve known the answer ever since the first OOP class(or YouTube video). Based on the concrete type of op1 at runtime, we will end up executing either the MyInt or MyRational version of Add(INumber)
This is what we call Polymorphism, right? There are other related terms, though. In C#, Java, and most popular programming languages, this is also an example of Single Dispatch.
Why “Single Dispatch”?
When we call a method on an object, we write something like the following:
myObject.DoSomething(arg1, arg2);
In OOP, we say that a method call represents a message sent to an object. In other words, the object receives a message from the outside world and needs to somehow react to it.
From our example above, myObject is the receiver of the message.
The receiver is very special for a lot of reasons. One of them is that only the runtime type of the receiver is included in the rules of polymorphic(virtual) calls.
In other words:
The method resolution logic depends on the runtime type of the “receiver” and the compile-time types of the method arguments.
Remember that when a method is called, besides the standard method arguments, you also get an additional implicit argument that points to the receiver. You guessed it – that’s the this/self/me reference.
Therefore, we can describe any object method call as a regular function invocation with one more argument – this, pointing to the receiving object itself.
Because the laws of Polymorphism depend on the runtime type of a single argument – “this,” C# and most of the other programming languages are classified as “Single Dispatch” languages.
But what if this was not the case? What if all of the method arguments were part of the Virtual Dispatch logic? Let’s discuss this next.
Polymorphism on the Arguments – Multiple Dispatch
So far, we’ve discussed how the expression op1.Add(op2) will end up executing the Add(INumber) method either in MyInt or MyRational, depending on the runtime type of op1.
Suppose that the concrete type of op1 is MyInt. Therefore the virtual call would be dispatched to the Add(INumber) method in the MyInt class:
public class MyInt : INumber
{
// ...
public INumber Add(INumber number) => // Implementation
}
The question is – how do we implement this method?
One option would be to check for the runtime type of number explicitly and then cast to MyInt or MyRational. This represents a more Functional approach, which may be quite convenient. However, for this example, let’s say we forbid checking for types. We want to implement the method in pure OOP style utilizing the rules for runtime method resolution.
Let’s forget about Single Dispatch for a moment and propose an interesting option:
public class MyInt : INumber
{
// ...
public INumber Add(INumber number) => Add(number);
private INumber Add(MyInt number) => new MyInt(Val + number.Val);
private INumber Add(MyRational number) => new MyRational(Val * number.Den + number.Num, number.Den);
}
Here is the idea. We define two more private methods in MyInt – one for adding another MyInt(line 6) and one for adding a MyRational(line 7).
Now, notice the Add(number) expression on line 5. The goal here is that based on the runtime type of the argument number, the method call would be dispatched to one of the private Add methods – Add(MyInt) or Add(MyRational).
Of course, this wouldn’t work, and you get a compilation error. As I’ve already described, C# is a Single Dispatch language as it supports virtual calls only on the receiver, not on the method arguments.
On the other hand, the approach I just described makes some sense, right? That’s exactly the idea behind Multiple Dispatch/Multimethods.
To state it more formally:
Resolving what method to execute based on the runtime types of all arguments (not only ”this”) is called Multiple Dispatch or Multimethods.
For better or worse, Multiple Dispatch is not baked into C#. This means we need to find another way to solve our addition problem.
Let’s see what this looks like.
Single Dispatch Forces us to Use the Visitor Pattern
It turns out that the lack of Multiple Dispatch forces us to look for a way to emulate it. A specific technique exists and is very well known – the Visitor Pattern. This pattern, in its’ essence, mimics Multiple Dispatch (or more accurately – Double Dispatch) via a chain of virtual Single Dispatch calls.
Writing a couple of articles, one on The Visitor and one on Double Dispatch, speaks for itself that these techniques are not quite intuitive and straightforward.
I encourage you to read those articles as I will not go into too many details in this post. Still, in the next section, I will present a high-level description. You can also find the full implementation here.
Flip the Position of the Argument by Making it a “Receiver”
Back to the problem. I still have to implement the Add method:
public class MyInt : INumber
{
// ...
public INumber Add(INumber number) => // Implementation
}
At this point, we know two things. First, the type of the current object is MyInt. Second, the method argument is of interface type INumber.
Here’s the tricky part. What we do next is to invoke an Add(MyInt) method on number passing the current object(this) as an argument. Like so:
public class MyInt : INumber
{
// ...
public INumber Add(INumber number) => number.Add(this);
}
The important question is – why did we do that, and how did it help?
The invocation number.Add(this) will execute an Add(MyInt) method either in MyInt class or MyRational class, depending on the runtime type of the number argument. Of course, those methods need to be declared in the INumber interface and implemented in both classes.
Again, please check the full implementation to develop a better intuition.
But the key point here is that, because C# supports virtual calls only on the receiver, number needs to become a receiver. So I flip the workflow by calling an Add method on number.
Let’s re-iterate. I started in the Adder method calling op1.Add(op2). This is the first polymorphic (virtual) dispatch based on op1. Next, the method number.Add(this) is invoked, which is the second virtual dispatch based on number (which is essentially op2 from the initial call).
This is how I just emulated Multiple Dispatch (Double Dispatch in our case).
For completeness, I need to mention the Double Dispatch technique described above is also an implementation of the Visitor Pattern. Concretely, INumber is both the “visitor” and the “visitee.”
The ”Fix” with “dynamic”
There is another way to get Multiple Dispatch in C#. The critical ingredient is the dynamic keyword.
Remember the example with the two private methods from a few sections above – Add(MyInt) and Add(MyRational). It turns out that all we need to do for this to work is cast number to dynamic:
public class MyInt : INumber
{
// ...
public INumber Add(INumber number) => Add((dynamic) number);
private INumber Add(MyInt number) => new MyInt(Val + number.Val);
private INumber Add(MyRational number) => new MyRational(Val * number.Den + number.Num, number.Den);
}
This piece of code will now execute one of the private Add methods based on the runtime type of the INumber argument.
This is how you get Multiple Dispatch by using the “dynamic” keyword.
Is this our silver bullet, though? Unfortunately, the answer is no. There are many disadvantages of using dynamic to emulate Multiple Dispatch. Moreover, it can (should) be considered an anti-pattern.
Let’s see why.
Multiple Dispatch via “dynamic” is an Antipattern
There are multiple reasons why you should not use dynamic to emulate Multiple Dispatch in C#.
I will give you my thoughts on some of them, but I would advise you to read more on the topic here from the insightful series by Eric Lippert – a former Principal Developer at Microsoft on the C# compiler team.
First, you are entirely abandoning static typing. As C# developers, we are used to all the goodies we get from the type system and the tools for static analysis. We lose all of this with dynamic.
Second, you are invoking the compiler at runtime (this is just how dynamic works), which takes a lot of time and space even with the various optimizations and advanced caching.
Third, in some circumstances, it can make the code very hard to comprehend. I will discuss this point a little more in the next section.
Why is it not Widespread?
Although Multiple Dispatch can be very useful in some scenarios, I believe with such potential flexibility, you can make your code very hard to reason about.
Imagine a group of five abstract arguments and implementations for every combination of the concrete types of those arguments. It will be nearly impossible to wrap your head around what code gets executed at runtime and why.
I believe this complexity is the main reason Multiple Dispatch is just not supported in most modern languages. Missing this feature may be limiting, but I guess language designers have decided it’s better to implement something more sustainable.
Where Can You Find Multiple Dispatch?
There aren’t plenty of languages that directly support Multiple Dispatch.
One of the most popular ones are R and Julia.
Another one is Clojure borrowing the idea and design from Common Lisp. The exact implementation details are out of scope for this article, but you may find this resource very helpful in case you’re interested.
Multiple Dispatch is not Static Overloading
You are most probably familiar with the concept of Static Overloading in C# and Java. This mechanism lets you define methods with the same name but different types and number of arguments.
This is different from Multiple Dispatch (Multimethods). The semantics of Multimethods is about the ability to resolve the method to execute based on the runtime types of the arguments.
Static overloading depends only on the compile-time types of the arguments. Make sure you don’t confuse the two concepts.
Summary
In this article, I described the idea of Multiple Dispatch; it’s Pros and Cons, and how to emulate it in C#.
I’ve also reviewed some of the patterns and techniques we are forced to use to bypass the lack of direct support for Multiple Dispatch – namely, the Visitor Pattern and the Double Dispatch technique.
If you’ve come this far, I believe you have a fresh perspective on the concept of Polymorphism and all of the flexibility it can bring.
Also, I hope you appreciate how the design of programming languages and type systems, like any other software development activity, can be a matter of tradeoff between flexibility and complexity.
See you next time!
