Wizards and warriors, part four

Last time we saw that in order to decide what code to call based on the runtime type of one argument - single dispatch - we could use virtual dispatch. And we saw that we could use the inaptly-named Visitor Pattern to emulate double dispatch by doing a series of virtual and non-virtual dispatches. This works but it has some drawbacks. It's heavyweight, the pattern is difficult to understand, and it doesn't extend easily to true multiple dispatch.

I said last time that C# does not support double dispatch. That was a baldfaced lie! In fact C# supports multiple dispatch; you can dispatch a method call based on the runtime types of arbitrarily many arguments. Here, let's dispatch based on the runtime types of two arguments:

abstract class Player { // not virtual! public void Attack(Monster monster) { dynamic p = this; dynamic m = monster; p.ResolveAttack(m); } public void ResolveAttack(Monster monster) { // basic case code goes here }}sealed class Warrior : Player{ // not virtual! public void ResolveAttack(Werewolf monster) { // Warrior vs Werewolf code goes here }}

It does not get much more straightforward than this. We wish to resolve Warrior vs Werewolf and we get a method dispatched that does exactly that, with none of the overhead of the Visitor Pattern, and with the method in the class where it (allegedly) belongs.

How does this work? Remember, the fundamental rule of dynamic is do what the compiler would have done had the compiler known the runtime type of every dynamic expression. That certainly includes dispatching methods! If we have

Player player = new Warrior();Monster monster = new Werewolf();player.Attack(monster);

then the dynamic invocation inside Player.Attack will know that p and m are dynamic and interrogate their runtime types. Then it says OK, what would the compiler have done given"

((Warrior)p).ResolveAttack((Werewolf)m);

? Clearly it would call Warrior.ResolveAttack(Werewolf).

Similarly, if we had

Player player = new Wizard();Monster monster = new Vampire();player.Attack(monster);

then the dynamic call site is resolved at runtime as though it had been

((Wizard)p).ResolveAttack((Vampire)m);

and clearly it would call Player.ResolveAttack(Monster), since there is no Wizard.ResolveAttack(Vampire) method to call.

This extends smoothly to any number of arguments; if you want Attack to take a Weapon or Fruit or whatever, just convert the argument to dynamic and do a method call; the call will resolve to how it would have been resolved had the runtime type been known.

One note: in case this is not obvious, in order to get dynamic dispatch on a particular argument the argument must be dynamic. If we had written

 public void Attack(Monster monster) { dynamic p = this; p.ResolveAttack(monster); // argument is not dynamic }

then this is treated as

((Warrior)p).ResolveAttack(monster);

and clearly overload resolution would not choose Warrior.ResolveAttack(Werewolf).

Is this our panacea?

Not really. I don't much like this solution either.

First off, let us never forget that by doing dynamic dispatch, we are starting the compiler again at runtime. It's a pretty clever compiler; it caches the results of previous invocations of the compiler so that the second time a dynamic call site is invoke with the same types as an earlier invocation, it re-uses the output of the compiler. But of course a cache without an expiration policy is another name for a memory leak, and no matter how you optimize it, this is still significantly more expensive in both time and memory than single-virtual dispatch or the Visitor Pattern.

Second, remember how we got into this discussion in the first place: we are trying to encode the rules of the system into the C# type system so that the compiler can help us find problems early, and we've just abandoned that entirely! If there is a problem with the dispatch resolution here, it's not going to be found until runtime.

Third, let's talk about some of those potential problems I just alluded to. The C# overload resolution algorithm has many interesting quirks. Suppose we have a slightly more complicated problem to solve:

class Warrior : Player{ public void ResolveAttack(Werewolf monster, HolyGround location) { // Warrior vs Werewolf on Holy Ground code goes here }}sealed class Paladin : Warrior{ public void ResolveAttack(Monster monster, HolyGround location) { // Paladin vs any Monster on Holy Ground code goes here }}

If a Paladin attacks a Werewolf on Holy Ground, what happens? On the one hand we have the rule that the more specific argument type is better. Werewolf is more specific than Monster, but Paladin is more specific than Warrior, so which wins? C# says that the receiver is special; a method in a more derived class always wins. That might be unexpected.

Worse, you could easily end up in situations that would produce an error at compile time, and therefore in the dynamic invocation, produce an exception at runtime:

sealed class Paladin : Warrior{ public void ResolveAttack(Monster monster, HolyGround location) { // Paladin vs any Monster on Holy Ground code goes here } public void ResolveAttack(Werewolf monster, Location location) { // Paladin vs Werewolf in any location code goes here }}

Now if a Paladin attacks a Werewolf on Holy Ground, what happens? Neither method is clearly better than the other, and so the dynamic dispatch will produce an error at runtime.

Fourth, this is a bit of an abuse of the dynamic mechanism. We did not add dynamic to C# 4.0 in order to enable multiple dispatch; we added it to make it easier to interoperate between C# and object models designed for dynamically typed languages, like the HTML DOM (designed to work with JavaScript) or Word and Excel (designed to work with VB 6).

We started this series trying to represent the rule "a Player has a Weapon but a Wizard is restricted to using a Staff", and we pretty much failed to come up with a good way to do that; representing restrictions is hard in class-based inheritance. And lately we've tried to represent the idea of "dispatch to special logic for special cases, use regular logic for regular cases", and haven't gotten very far there either. It seems that our tools are resisting us; maybe we're using the wrong tools, or maybe we're coming at the problem in the wrong way. Now would be a good time to take a step back and ask if we've made some fundamental error.

Next time in this seris: We'll do just that.