Double Dispatch and Visitor Pattern [C# implementation]
- siqisundev
- Nov 6, 2022
- 4 min read
Updated: Nov 10, 2022
Dynamic dispatch
Dynamic dispatch (Wikipedia link) is a technique, commonly used in OOP, for dispatching the correct function/method (essentially picking the correct function to call) at run time. The contrast of dynamic dispatching is "STATIC DISPATCHING" where the binding of the function calls happens at the compile time.
Typical application of dynamic dispatching is the polymorphism, where the virtual method/functions are picked based on the runtime type of object.
Single and Multiple Dispatch
In single dispatch, the choice of which version of a method to call is based on a single object.
In multiple dispatch, the choice of which version of a method to call is based on a combination of objects.
fooObj.Func(barObj); In the above code, if *only* the type of fooObj or barObj determine which polymorphic function to call, it is single dispatching.
*If* the function call is determined by *both* the type of fooObj and barObj, it is multiple (double) dispatching.
Common OOP languages (e.g. Java, C#*, Python etc.) is using Single Dispatch, more precisely, it's the type of the object that the method is called upon (i.e. fooObj in the example), is used to determine which polymorphic operations (virtual function) to use.
* Double dispatch is possible in newer versions of C# with dynamic keyword, see below
Challenges for single dispatch and visitor pattern
Problem
The characteristic of OOP's dynamic dispatching described above gives the following behaviour:
Polymorphic functions (virtual functions) are dynamically dispatched, the function overloads are not. (i.e. function overloading calls are bind at the compile time based on the COMPILE TIME TYPE)
e.g.
fooObj.Func()fooObj.Func() can be dynamically dispatched based on the type of fooObj if Func() is a virtual function.
public class Foo{
//omitting other declarations and function body
public void Func(object o){/*...*/}
public void Func(double d){/*...*/}
public void Func(string s){/*...*/}
}
public static void main(){
var fooObj = new Foo();
Object actuallyAString = "A string value";
Object actuallyADouble = 10d;
fooObj.Func(actuallyAString);
fooObj.Func(actuallyADouble);
}
However, in the above example, calling fooObj.Func(actuallyAString) and fooObj.Func(actuallyADouble) will all use the Func(object o) overload because Object is the declared type at compile time and the overloading is binded at the compile time.
Solution (in C#)
Dynamic Keyword
A naive solution is to make use of the dynamic keyword in C#, as the dynamic keyword will tell the compile to bind types at the run time so in this case the actual run-time type of the parameter is also used to determine the function call so essentially it becomes double dispatching when using dynamic keyword.
public class Foo{
//omitting other declarations and function body
public void Func(object o){/*...*/}
public void Func(double d){/*...*/}
public void Func(string s){/*...*/}
}
public static void main(){
var fooObj = new Foo();
dynamic actuallyAString = "A string value";
dynamic actuallyADouble = 10d;
fooObj.Func(actuallyAString); //calls Func(string) now
fooObj.Func(actuallyADouble); //calls Func(s) now
}
Using dynamic breaks type safety as all compile time type checking of dynamics are disabled. And by convention the dynamic keyword should be used only in rare cases such as supporting interoperability and hence may not be the ideal solution to enable double dispatching.
This Keyword in virtual methods
The "this" keyword refers to a reference to the object of the enclosing type. The type of "this" is understood at the compile time. And hence, using "this" keyword can allow dispatching based on the function parameter. And using "this" keyword based in the override methods can essentially achieve double dispatching.
BarBase actuallyBase = new BarBase();
BarBase actuallyDerivedA = new BarDerivedA();
BarBase actuallyDerivedB = new BarDerivedB();
var bv = new BarVisitor();
actuallyBase.AcceptFoo(bv);
actuallyDerivedA.AcceptFoo(bv);
actuallyDerivedB.AcceptFoo(bv);
public class BarVisitor
{
public void VisitFoo(BarBase b)
{
Console.WriteLine("BARBASE");
}
public void VisitFoo(BarDerivedA b)
{
Console.WriteLine("BARDERIVEDA");
}
public void VisitFoo(BarDerivedB b)
{
Console.WriteLine("BARDERIVEDB");
}
}
public class BarBase
{
public virtual void AcceptFoo(BarVisitor visitor)
{
visitor.VisitFoo(this);
}
}
public class BarDerivedA : BarBase
{
public override void AcceptFoo(BarVisitor visitor)
{
visitor.VisitFoo(this);
}
}
public class BarDerivedB : BarBase
{
public override void AcceptFoo(BarVisitor visitor)
{
visitor.VisitFoo(this);
}
}In the above example which of the VisitFoo overloads in the BarVisitor class is determined by the runtime time of BarBase.
Visitor Pattern in C#
Visitor pattern in C# is an application of the double dispatch which allows extending the existing class without changing the code. The class to be extended provides an Accept method accepting the Visitor, which the class responsible for extending functionalities. Which visitor function to be called is being determined by both the the runtime type of the visitor and the runtime type of the extending class.
for (int i = 0; i < 5; i++)
{
IBarVisitor visitor =
new Random().Next() % 2 == 0
? new BarVisitorA()
: new BarVisitorB();
Bar bar =
new Random().Next() % 2 == 0
? new BarConcreteA()
: new BarConcreteB();
bar.Accept(visitor);
//which to call depends on the runtime type of bar and visitor -> double dispatching!
}
public interface IBarVisitor
{
void Visit(BarConcreteA bar);
void Visit(BarConcreteB bar);
}
public class BarVisitorA : IBarVisitor
{
public void Visit(BarConcreteA bar)
{
Console.WriteLine("Doing something on BarConcreteA");
}
public void Visit(BarConcreteB bar)
{
Console.WriteLine("Doing something on BarConcreteB");
}
}
public class BarVisitorB : IBarVisitor
{
public void Visit(BarConcreteA bar)
{
Console.WriteLine("Doing something else on BarConcreteA");
}
public void Visit(BarConcreteB bar)
{
Console.WriteLine("Doing something else on BarConcreteB");
}
}
public abstract class Bar
{
public abstract void Accept(IBarVisitor visitor);
}
public class BarConcreteA : Bar
{
public override void Accept(IBarVisitor visitor)
{
//visitor.VisitBarConcrete is polymorphic
visitor.Visit(this);
}
}
public class BarConcreteB : Bar
{
public override void Accept(IBarVisitor visitor)
{
//visitor.VisitBarConcrete is polymorphic
visitor.Visit(this);
}
}*note that the extension methods in C# can serve similar purpose of visitor pattern in terms of extending the class features without changing the existing class and is more powerful and more prevalently used. Which is out of the scope of discussion in this post.
Comments