Dynamic Dispatch (Multimethods) in C#?

I’ve recently become enamored with the multimethods system of Clojure, as well as its approach to polymorphism and “type” hierarchies in general.  Having never heard the term, I consulted Wikipedia about multimethods, hoping to have its origins elucidated, though it appears it is simply a synonym of multiple dispatch.

Polymorphism, “the ability of one type to appear as and be used like another type”, is limited to inheritance with simple overloading semantics (and generics) in C#.  The ability to be “used as” another type is implemented by allowing subclasses to implement any virtual methods defined on their respective superclasses.  Then, at compile time, the method to be called is determined based on the actual types of the objects upon which the function/method is invoked; we call this compile-time binding or early-binding.

Let’s look at it from a more mechanical perspective.  In most OO languages, when we write obj.Foo() we are implicitly writing (Foo obj).  In other words, obj is the first argument in the invocation of Foo; an argument called this in many languages.  (See JavaScript’s call/apply.) So, in our inheritance example, the compiler looks at the actual type of this first argument obj (the target of the invocation) when determining the Foo to call. This is called single dispatch.

What about the other arguments to the function?  Can we vary which function is called based on the other arguments to a method besides the target (i.e. the first implicit argument)?  Well, of course, we can have method overloads that take a different number and/or type of arguments.  However, unlike the first argument, there’s no mechanism in C# to evaluate the the derived types of these other arguments to make a dispatch decision; there is no multiple dispatch in C#.

This blog article, “The Visitor Pattern and Multiple Dispatch”, usefully explains the problem in terms of the Visitor pattern.  As a means of implementing double dispatch the Visitor pattern has some shortcomings.  First, the targets must be aware of and receive the visitor, violating the single responsibility principle.  Second, the visitor itself must evaluate the type of the target and invoke the correct method. Though some suggest using reflection to invoke the correct method, that implementation, reflecting on the runtime type of the object and using dynamic invocation through the type to get to the right method can be expensive. 

We can simplify that approach using the dynamic keyword to effect dynamic dispatch.  Using the dynamic keyword to “box” the arguments to the target method (Foo above), we can let the runtime system do the reflection for us. In the code below, I build on the Visitor example in “The Visitor Pattern and Multiple Dispatch” article, see line 28.

Code Snippet

1. class Program
2. {
3.     abstract class Expression { }
4.  
5.     class ConstantExpression : Expression
6.     {
7.         public int constant;
8.     }
9.  
10.     class SumExpression : Expression
11.     {
12.         public Expression left, right;
13.     }
14.  
15.     class EvaluateVisitor
16.     {
17.         public int Visit(Expression e)
18.         {
19.             throw new Exception("Unsupported type of expression"); // or whatever
20.         }
21.  
22.         public int Visit(ConstantExpression e)
23.         {
24.             return e.constant;
25.         }
26.         public int Visit(SumExpression e)
27.         {
28.             return Visit(e.left as dynamic) + Visit(e.right as dynamic);
29.         }
30.     }
31.     
32.     static void Main(string[] args)
33.     {
34.         var one = new ConstantExpression { constant = 1 };
35.         var two = new ConstantExpression { constant = 2 };
36.         var sum = new SumExpression { left = one, right = two };
37.         var vistor = new EvaluateVisitor();
38.         Console.WriteLine("Visit result {0}", vistor.Visit(sum));
39.         Console.ReadKey();
40.     }

 

This technique has some utility but should be used wisely.  Obviously there will be some cost for “dynamic” dispatch.  It’s important to note that this isn’t a generalized system for multiple dispatch, just a great spot welding technique to make the Visitor pattern more palatable.

In contrast, Clojures multimethods allow you to define a function on the arguments that is evaluated and cached, while the “overloads” define the results of that evaluation that they correspond to.  In this way dispatch on multimethods in Clojure can consider not only the “types” and values of all the arguments, but really any sort of inspection or evaluation you choose.