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.

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

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

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

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

  • 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

  • It's cool and simple!

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