Wizards and warriors, part three

So let's digress for a few episodes here. We'll temporarily leave aside the problem of how we can have both a Player that has a Weapon and a Wizard that has a Staff. (Or Dagger.) Supposing that we can figure out how to get that all represented, here's another problem. Suppose we've also got Werewolf and Vampire classes that are a kind of Monster. We want a rule that says that if a Warrior tries to hit a Werewolf after midnight then the probability of success is lowered. (Wizards have no such penalty because" magic? Work with me here.)

Wait a moment - isn't it always after midnight? When could you safely feed a mogwai, anyway?

Though that is a fascinating problem I'm sure, that's not the problem I want to talk about today. The problem for today is: where exactly does the code go that determines whether the Warrior successfully hits the Werewolf? We have four classes involved: Player, Warrior, Monster, Werewolf. Somewhere there is a method, let's call it Attack; what does that method look like?

Well, we're object-oriented programmers programming objects in an object-oriented language; methods are the verbs and classes are the nouns, the player is the thing doing the attacking, so plainly Attack needs to be a method on Player. Since the rule for a Warrior is evidently different than that for a Wizard, it had better be virtual:

abstract class Player{ public virtual void Attack(Monster monster) { // Basic rules go here } ...}sealed class Warrior : Player{ public override void Attack(Monster monster) { if (monster is Werewolf) this.ResolveWerewolfAttack((Werewolf)monster); else base.Attack(monster); } private void ResolveWerewolfAttack(Werewolf monster) { // Special rules go here } ...

I don't like it.

Fundamentally, Attack takes a compile-time-typed Player and an Monster, and then resolves the attack based on the runtime types of the two arguments. The virtual method mechanism dispatches the method call based on the runtime type of only one of the two arguments; that method is then left to its own devices to do a second dispatch by interrogating the argument's runtime type explicitly.

Why is Player so special that it gets to have the dispatch handled by the language itself?

Designers of method resolution systems call C# (and C++, and Java, and many similar languages) "single dispatch" languages. That is, there must be one very special argument, and the method which is invoked at runtime is determined by the runtime type of that argument, and the compile time types of all the other arguments. That argument in all the languages that I mentioned is so special that it gets a keyword reserved for it - this - and the argument is placed to the left of the method name, rather than in the argument list with the second-class citizen arguments who only matter for their compile-time types.

That's why our solution seems so inelegant in C#; in order to solve this problem elegantly we'd need a language that supported double dispatch.

Before I go on, a quick jargon note. By dispatch I mean making a decision, either at compile time or runtime, about which method to invoke among several choices. By single, double or multiple dispatch, I mean that the decision is based on the runtime type of one, two, or several arguments. By virtual dispatch I mean the specific technique that C# uses to achieve single dispatch: a method invocation looks up which method to actually invoke in a table associated with the receiver. ("Virtual" is an unfortunate term; it would have been more clearly called an "indirect" method call, but we're stuck with it.)

C# does not support double dispatch, but we can emulate it like this:

abstract class Player{ public abstract void Attack(Monster monster);}sealed class Warrior : Player{ public override void Attack(Monster monster) { monster.ResolveAttack(this); }}sealed class Wizard : Player{ public override void Attack(Monster monster) { monster.ResolveAttack(this); }} abstract class Monster{ private void ResolveAttack(Player player) { // default implementation goes here } public virtual void ResolveAttack(Warrior player) { this.ResolveAttack((Player)player); } public virtual void ResolveAttack(Wizard player) { this.ResolveAttack((Player)player); }}sealed class Werewolf : Monster{ public override void ResolveAttack(Warrior player) { // special logic for Warrior vs Werewolf goes here }}sealed class Vampire : Monster{}

Follow the logic along; suppose we have

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

We have no compile-time information about how to dispatch this to the appropriate method. We invoke the abstract method Player.Attack(Monster), which at runtime does virtual dispatch to Warrior.Attack(Monster). That method calls Monster.ResolveAttack(Warrior), which does virtual dispatch to Werewolf.ResolveAttack(Warrior) and we're set; we've dispatched to the method that has the logic we need.

If instead we had

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

Then again, Player.Attack(Monster) does virtual dispatch to Wizard.Attack(Monster), which calls Monster.ResolveAttack(Wizard), which does virtual dispatch. Vampire did not override that method, so we get the base class implementation, which in turn does a call to Monster.ResolveAttack(Player), and we get the no-special-rules logic.

This pattern - which has many, many variations - is called the Visitor Pattern. Whether you've seen this pattern before or not, you could be excused for being confused by the name; it is by no means clear why emulating double dispatch using a series of single dispatch calls has to do with "visiting" anything.

One of the most common usages of this pattern is for the scenario where you've got a complex tree where tree nodes can be of many types, and you wish to traverse the tree - that is, visit every node in the tree - taking some actions or performing some computations as you go. The "double dispatch" part of it is that the actions you take as you visit nodes in the tree can depend on the runtime types of both the nodes in the tree, and the code performing the action.

This pattern is very common in compilers, because of course we often have trees with lots of different kinds of nodes in the trees (expressions and statements and types") and we wish to take different actions on those trees (optimizing, lowering, generating code, seeking error cases). The Roslyn C# and VB compiler semantic analyzers make heavy use of this pattern.

OK, so, have we actually solved the problem of dispatching to the right logic for our warrior vs werewolf problem? This solution works, but it has some major shortcomings.

• It seems a bit weird that we started out saying that "attack is a verb on players, so the logic should go in the player class hierarchy", and then ended up doing exactly the opposite; all the code to handle the basic and special attacks ended up in the Monster hierarchy. Of course there are many ways we could reorganize the code to fix that, but still, it's odd. Basically, the Monster is what in Roslyn would be the analyzer, and the Player is the syntax tree, so it makes sense that the fancy logic would go in the Monster. But it seems completely arbitrary in our example whether the Monster is the visitor or the visitee.
• Holy goodness look at all the mechanisms! I've already said recently that I think that it's ok to be WET instead of DRY when you are building a mechanism, but still, there is an absolutely huge amount of overhead here. And this is a very simple case! For Roslyn we made a little type description language out of XML and then built a code generator to automatically spit all the mechanism code for the visitor passes, because we didn't trust ourselves to always get all the bits of the visitors right when making changes to the syntax nodes. It seems likely that all this mechanism code will overwhelm the reader, obscure the business logic, confuse the novice programmer not used to the pattern, and provide ample opportunity for bugs.
• Did I mention that we also care about the runtime type of the Weapon being used? And the Location that the battle is taking place in? And the Weather. And" OK, maybe some of these do not require the full mechanisms of virtual dispatch, but suppose we did want to do multiple dispatch? You can probably see how there are ways to extend this pattern to use more single dispatch calls to emulate triple, quadruple, and so on, but it's not going to be pretty.

This pattern works, and like I said, I've made heavy use of it to great effect in the past. But it seems both very heavyweight and very inflexible in a lot of ways. Is there an easier way to get multiple dispatch in C#?

Next time on FAIC we'll look at a completely different way to do multiple dispatch in C#.