Visitor and multiple dispatch via C# ‘dynamic’


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.


Comments (22)

  1. Alex Schearer says:

    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.

  2. Kris says:

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

  3. Dalibor Čarapić says:

    Very nice.

  4. Rinse says:

    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?

  5. Danny Tuppeny says:

    @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.

  6. Georgi Stoyanov says:

    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.

  7. Rinse says:

    @Danny Tuppeny

    Thanks bud, that filled the hole in the puzzle! 🙂

  8. LiorTal says:

    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# ?

  9. ShawnHargreaves says:

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

  10. Michael Chandler says:

    Nice one!

  11. Erzengel says:

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

  12. naraga says:

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

  13. default_ex says:

    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.

  14. Gaurav Sharma says:

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

  15. wiseen says:

    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);

  16. wiseen says:

    forgot to add m=> { if (m.Name != method) return false; …

  17. ShawnHargreaves says:

    > I think you could do this without dynamic dispatch

    Sure you can (how do you think the C# compiler itself implements the dynamic type?) but there are a lot of subtleties to creating a quality implementation.

    What if the types don't exactly match? Note how the last invocation from my example falls back on the default (Animal, Animal) overload, becuase no specific (Dog, Mouse) version is available. The C# compiler considers many things when deciding what method overload is the closest match:

    – Direct type match?

    – Method takes a base type of the actual type provided?

    – Method takes an interface implemented by the actual type provided?

    – Invoke an implicit constructor or conversion operator to convert argument types to what the method requires?

    – Box a value type?

    – Specialize a generic method?

    There will often be multiple possible matches (in fact there are in my example) so the C# spec defines complex rules for which take priority.

    Of course you can reimplement all that logic, but it'll be complex not to mention slow thanks to all that reflection. So, you could write code to cache the reflection results and optimize the dispatch for the common case where the same types are used many times in sequence. Now it's fast, but even more complex.

    The great thing about the "dynamic" keyword is that the C# compiler does all this work for you, generating a dispatcher that is both robust (exactly matching the regular C# method overload rules) and also efficient thanks to aggressive caching.

  18. wiseen says:

    I agree, but IIRC you couldn't run DLR code on WP7/Xbox compact framework, so I just want to point out that if anyone want's to use this pattern you can do it without the dynamic keyword if it's not available.

  19. Anon says:

    Delegates can defray the cost of the dynamic evaluation if you're worried about that.  Much like we used to use Reflection to get a MethodInfo to make a delegate to cache for later use we can now use dynamic to call a method that returns a delegate:

    protected override Action GetApplyDelegate(Effect effect)

    {

    return GetConcreteDelegate(effect as dynamic);

    }

    private Action GetConcreteDelegate(BasicEffect effect)

    {

    return () =>

    {

     effect.TextureEnabled = true;

     effect.Texture = _texture;

    };

    }

    If the type changes you'd have to get a new delegate but now instead of potentially using dynamic every frame, it's used only when the type changes.

  20. light says:

    eh i didn't know dynamic worked like that, wish i would have read this along time ago

    is this really faster then just figuring it out from a switch case though

  21. Ali Mohammadi says:

    It's cool and simple!

  22. Alex says:

    @Anon, According to Eric Lippert's comment on Apr 26 '12 at 13:50 on this question:  stackoverflow.com/…/c-sharp-multiple-dispatch-options , when using dynamic you are already getting a cached delegate for free, no need to implement it yourself.

Skip to main content