Visitor and multiple dispatch via C# 'dynamic'

Visitor and multiple dispatch via C# 'dynamic'

  • Comments 21

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.

  • One disadvantage I see to this approach is you move the responsibility for reacting outside of the Animal class (or subclass). Another alternative is to create a traditional virtual method. Then in implementations which need to respond to a custom type use a Dictionary mapping Types to strings (or whatever your situation requires). This avoids a messy switch statement and keeps the code where it belongs. Of course, this solution doesn't work as gracefully if the order of the parameters is not important.

  • @ Alex: There is no messy switch statement, that's the point of this article.

  • Very nice.

  • Hmmm, I don't think I understand this.

    The React method seems redundant to me because substituting the calls for React with ReactSpecialization would give the same output.

    ReactSpecialization(cat, dog);

    ReactSpecialization(cat, mouse);

    ReactSpecialization(dog, cat);

    ReactSpecialization(dog, mouse);

    I'm missing the point right?

  • @Rinse I think you're right, however if you changed the types on the left, eg:

    Cat cat = new Cat();

    Dog dog = new Dog();

    Mouse mouse = new Mouse();

    becomes

    Animal cat = new Cat();

    Animal dog = new Dog();

    Animal mouse = new Mouse();

    Then your way would no longer work - the compiler would always pick the (Animal, Animal) overload. Whereas using dynamic as Shawn showed would continue to work. Maybe Shawn could update it to make it clearer.

  • First of all, I should say this does look like a very interesting idea :)

    @Danny Tuppeny Exactly! I wrote a rather long comment on why all the variables in Test() should be of type Animal to illustrate the whole point of this approach, but I see you have beaten me to it ;)

    @Alex Schearer The whole idea is to have the functionality outside of the Animal class. That's part of the problem the visitor pattern (and the alternative approach here) is designed to solve. If you have the functionality directly in the 'animals' classes, you needn't use a double dispatch at all. But sometimes you don't want to (or can't) put the relevant functionality there.

  • @Danny Tuppeny

    Thanks bud, that filled the hole in the puzzle! :)

  • Awesome stuff!

    I never had the chance of using the 'dynamic' keyword since most of the code i'm doing at work runs on .NET 4

    Is this topic related in any way to Dynamic Proxy? can this help implementing such a concept in C# ?

  • Good feedback on the example Test function - I've updated it to avoid that confusion. Thanks all!

  • Nice one!

  • That's awesome stuff, I guess I'll hop on MSDNAA and get VS2010 now.

  • absolutely great idea. i havent realized that kind of magic could mbe done with dynamic.

  • The example given for this trick isn't so clear as the implications, because if you were to run that example calling ReactSpecialized() without the 'dynamic' cast it will yield the same results since the types are known at compile time in that Test() function.

    A better demonstration of how nice of a trick it is:

    List<Animal> animals = new List<Animal>();

    animals.Add(new Dog());

    animals.Add(new Cat());

    animals.Add(new Mouse());

    React(animals[0], animals[1]);

    React(animals[1], animals[2]);

    The above would have without the 'dynamic' cast resulted in calling the overload of ReactSpecialized() that accepts two animals despite the fact that they are Dog, Cat, and Mouse, because in this context the compiler can't make assumptions of what those types are.

  • There's as typo in there, should be "They're" not "They".

  • I think you could do this without dynamic dispatch (for platforms that don't support it) :

    public static object Dispatch(this Type type, string method, object a, object b)

    {

       return type.GetMethods().First(m =>

       {

           var methodParams = m.GetParameters();

           return methodParams[0].ParameterType == a.GetType() && methodParams[1].ParameterType == b.GetType();

       }).Invoke(null, new[] { a, b });

    }

    typeof(Animal).Dispatch("React", cat, dog);

Page 1 of 2 (21 items) 12
Leave a Comment
  • Please add 2 and 2 and type the answer here:
  • Post