Visitor and multiple dispatch via C# 'dynamic'

Originally posted to Shawn Hargreaves Blog on MSDN, Tuesday, April 5, 2011

There is a somewhat convincing argument that software design patterns are really just an attempt to emulate missing language features.

Eric Lippert recently wrote a series of articles exploring how one might attempt to implement the "virtual method pattern", if that was not already built in to C#.  While interesting to see how such things work behind the scenes, it would of course be crazy to actually do this by hand, when the language already provides a convenient "virtual" keyword!

Ah, the codification of convenience, wherein we cheerfully constrain our choices in order to conceal complexity...

Virtual methods allow us to dynamically choose which code to execute depending on what type of object we are dealing with. They so ubiquitous in modern object oriented languages that it is easy to forget they are missing a couple of sometimes important features:

What if you want to run code that is not a member function of the type in question? Perhaps you don't own the type so cannot modify it, or maybe it just doesn't make sense to implement this code as a member. This is the problem the visitor pattern was designed to solve, but I've never seen a visitor implementation that didn't strike me as ugly and overly complex.

Or what if you want to choose code based on the types of more than one object? This is a feature called multiple dispatch, but Lisp is the only programming language that directly supports it.

C# to the rescue...

The 'dynamic' keyword, added in C# 4.0, was designed to simplify interop between statically typed C# and dynamically typed languages or COM components. It does this by deferring method resolution from compile time until runtime, dynamically applying the same overload selection logic that the C# compiler would normally use at compile time. Interestingly, this is exactly what we need to implement both multiple dispatch and virtual dispatch of non instance methods (aka visitor pattern).

Consider this simple class hierarchy:

    class Animal 
{
}

class Cat : Animal
{
}

class Dog : Animal
{
}

class Mouse : Animal
{
}

We can create several overloads of the same method, specialized according to different combinations of their parameter types:

    void ReactSpecialization(Animal me, Animal other) 
{
Console.WriteLine("{0} is not interested in {1}.", me, other);
}

void ReactSpecialization(Cat me, Dog other)
{
Console.WriteLine("Cat runs away from dog.");
}

void ReactSpecialization(Cat me, Mouse other)
{
Console.WriteLine("Cat chases mouse.");
}

void ReactSpecialization(Dog me, Cat other)
{
Console.WriteLine("Dog chases cat.");
}

And now the magic part:

    void React(Animal me, Animal other) 
{
ReactSpecialization(me as dynamic, other as dynamic);
}

This works because of the "as dynamic" cast, which tells the C# compiler, rather than just calling ReactSpecialization(Animal, Animal), to dynamically examine the type of each parameter and make a runtime choice about which method overload to invoke.

To prove it really works:

    void Test() 
{
Animal cat = new Cat();
Animal dog = new Dog();
Animal mouse = new Mouse();

React(cat, dog);
React(cat, mouse);
React(dog, cat);
React(dog, mouse);
}

Output:

Cat runs away from dog.
Cat chases mouse.
Dog chases cat.
Dog is not interested in Mouse.

Note especially that last (Dog, Mouse) call. We did not provide a specialized method with these parameter types, so it automatically fell back on the closest matching alternative, which in this case was the (Animal, Animal) overload. If there was no suitable fallback overload, it would have raised a runtime exception instead.

Of course, dynamic invoke is not free, so this probably isn't something you want to rely on in a core game loop. But I've used this technique heavily in a build time processing tool, where it was plenty fast enough to not even show up in the profiler, and vastly simplified what would otherwise have been complex type dispatch logic.

Blog index   -   Back to my homepage