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.
Fabulous adventures in coding 
Great post and series! Waiting for more parts!
What “compiler” is one starting again at run-time? If one has code in one assembly which is compiled using one version of Roslyn, and code in another assembly which is compiled using a version whose overloading rules differ in some subtle corner case, what rules will be used in determining method bindings? I would guess that .NET 4.x has some C#-related logic built in which is distinct from the normal overload resolution rules associated with Reflection’s delegate-binding features, but it might help to clarify that.
It might also help to clarify what if anything the compiler can usefully do with return types. Given:
dynamic player,monster;
bool result;
player.Attack(monster, out result);
I would expect the compiler would ignore any Attack methods without a Boolean byref as the second parameter, but I don’t think there’s any equivalent behavior with return values. Are there any scenarios where a method call with some dynamic arguments can be regarded as yielding a definite return type (e.g. if it’s invoked on a class whose overloads with that name all have the same return type)? If not, would use of “out” parameters rather than return types be a good pattern when using dynamic dispatch?
Regarding which compiler, that’s a good question that embarrassingly enough, I do not know the answer to. In C# 4 we took a snapshot of the compiler and made a special version of the expression analyzer that used reflection Type objects as the “what is the type of this expression?” representation, instead of the C# compiler’s internal representation. I do not know how this was ported to Roslyn; when I left we had gotten as far as getting Roslyn to use the old analyzer, but I do not know if it was ever updated to use a more modern analyzer, perhaps based on Roslyn itself. Since we have the source code we can investigate; I have just never done so.
Regarding your question about “can the compiler deduce a non-dynamic type of an expression containing dynamic function calls”, the answer is yes, there are some scenarios in which the compiler deduces a more specific type than “dynamic” for a call that involves dynamic dispatch. Off the top of my head I do not recall what they are; they were controversial when designed and we went back and forth several times. The desire was to first, make a compiler that found bugs, and second, to make a compiler that honored the idea of “you asked for dynamic so you got dynamic”. These desires were in some cases in conflict and the compromises were tricky. I might have written about this in the past, and I believe my former colleagues Sam Ng and Chris Burrows, who worked directly on these features, also blogged about them. I’ll do some poking around and see what I can find.
Pingback: Wizards and warriors, part three | Fabulous adventures in coding
“we are trying to encode the rules of the system into the C# type system”
this is what seems to me to be the key issue. rules about “different classes have different weapon restrictions” or “different combinations of player and enemy have different bonuses” are things that should themselves be extracted into classes.
To me, the requirements sound like:
1. Every player can hold a wapon but
2. A player of a specific type of player can hold only a specific type of weapon
I would suggest to make the setter of the weapon field privat and let constructors of the player subtypes restrict, which kind of weapon to accept.
Fifth, it’s not at all clear, from looking at the code, what the code paths are. Unless you are intimately familiar with the rules dynamic dispatch. And who is, other than Eric Lippert and maybe five guys in Silicon Valley.
What I really miss is a way to make sure I’ve correctly handled all options with no ambiguities and no missed cases. Julia will warn me if I have ambiguous methods Attack(Player, Werewolf) and Attack(Paladin, Monster), but since inheritance is similar to an open tagged union type, it is impossible to check that I’ve handled all possible cases automatically.
As a better game-related example, I have a game engine that is turn-based, where GameModules generate available Actions and respond to an Action from that list. I can dispatch to the correct HandleAction() in multiple ways (if+cast, visitor, dynamic), but I cannot statically verify that I have a method for each possible subclass of Action this.GetAvailableActions() of this specific subclass of GameModule returns.
There’s a symmetrical problem in the user interface, since it has to distinguish between available Actions to show them on the screen, plus you cannot use double dispatch, since Actions shouldn’t know about the interface at all.
Nice series Eric! Noticed a small typo. After the wizard/vampire example, you say “it would call Player.ResolveAttack(Monster)” but meant “it would call Wizard.ResolveAttack(Vampire).”
I meant what I said, but I see why the sentence is confusing. I’ll fix it. Thanks for the note.
Can’t wait to see what happens next. Feels like I am watching a good TV show and can’t wait a week for the next episode.
Glad to hear it! And you will only have to wait four days.
I’m excited for the rest of these articles, because I ran into this issue when making a DICOM server, and I solved it basically the way this article does, and I didn’t really like it. I can’t wait to see what solutions you present so I can try to implement them!
> Designing good class hierarchies is all about capturing the semantics of the business domain in the type system, right?
The semantics yes, but not necessarily the logic.
How about an AttackResolverService which contains default implementations. Something like service.ResolveAttack(Player, Player). The provided players can be queried for any special rules which come into play for the attack.
The other issue here is that the resolve attack methods need to be public as dynamic will not skirt accessibility rules… Which is unfortunate in this case as exposing those methods breaks encapsulation.
Does C# need some new syntax for this?!
protected void Attack(Monster monster) { … }
protected void Attack((Werewolf)Monster werewolf) { … }
protected void Attack((Vampire)Monster vampire) { … }
Which could generate the diapatch method in the previous blog post?
I won’t pretend to guess what the implications are for method resolution here but it’s at least interesting in terms of formalising the pattern…
So now rules start stacking up, one could solve it by calling a “ApplyRules” at each object participating in the combat, or do as the next part will do, but that would be very boring, the most interesting part in this series for me was thinking about multiple dispatch and covariant/contravariant interfaces, I did a few tests, the dynamic call takes about the same time as an explicit interface cast, which is 10 times more than a virtual call, while implicit interface calls are free, and by using contravariant interfaces, the visitor (really need a new name for this) pattern won’t require so much typing while costing only 2 virtual calls in terms of performance, but still require a method on the other class, as an example:
interface IDoFoo<in T>
{
void Bar(T input);
}
class OtherClassBase
{
public virtual void DoBar(IDoFoo<OtherClassBase> instance)
{
instance.Bar(this);
}
}
class OtherClass : OtherClassBase
{
public override void DoBar(IDoFoo<OtherClassBase> instance)
{
IDoFoo<OtherClass> temp = instance;
temp.Bar(this);
}
}
class TheClassBase : IDoFoo<OtherClassBase>
{
void IDoFoo<OtherClassBase>.Bar(OtherClassBase input)
{
}
}
class TheClass : TheClassBase, IDoFoo<OtherClass>
{
void IDoFoo<OtherClass>.Bar(OtherClass input)
{
}
}
And finally, by calling OtherClass.DoBar(TheClass) it will call the most derived IDoFoo<OtherClass>.Bar(OtherClass input), interfaces have also an interesting way to solve conflicts (base, derived) vs (derived, base) if someone decides to go further than dual dispatch, the first interface in the inherited list have preference, unfortunately this still needs one method in the OtherClass for each dual dispatch method, so I prefer yet another variation of the visitor pattern (how about calling this one the handler pattern? Any previous work? Suggestions?):
interface IHandleable
{
R CreateHandler<R>(IHandler<IHandleable, R> handler);
}
interface IHandler<in T, R>
{
R CreateHandler(T input);
}
class Weapon : IHandleable
{
public virtual R CreateHandler<R>(IHandler<IHandleable, R> handler)
{
IHandler<Weapon, R> temp = handler;
return temp.CreateHandler(this);
}
}
class Staff : Weapon
{
public override R CreateHandler<R>(IHandler<IHandleable, R> handler)
{
IHandler<Staff, R> temp = handler;
return temp.CreateHandler(this);
}
}
class WeaponHandler
{
}
class Player : IHandler<IHandleable, WeaponHandler>
{
WeaponHandler IHandler<IHandleable, WeaponHandler>.CreateHandler(IHandleable input)
{
return null;
}
}
class WizardStaffHandler : WeaponHandler
{
public WizardStaffHandler(Wizard player, Staff weapon)
{
}
}
class Wizard : Player, IHandler<Staff, WeaponHandler>
{
WeaponHandler IHandler<Staff, WeaponHandler>.CreateHandler(Staff input)
{
return new WizardStaffHandler(this, input);
}
}
And then the WizardStaffHandler contains all methods required to handle the Wizard Staff relations, each at just 1 virtual call cost, still required a method implemented on every handleable object.
—
To me, This solution sounded interesting at first. But at compiletime, it doesn’t prevent a developer trying to let a wizard handle, let’s say a sword:
var wizard = new Wizard();
var weaponHandler = ((IHandler)wizard).CreateHandler(new Sword());
This will compile, but may throw at runtime because the handler will be null.
Also this solution doesn’t enforce that a player can handle only one weapon at a time. Ok, prehaps there coud be players using more than one weapon at a time, but that’s not a requirement by now.
the second line of code should be
var weaponHandler = ((IHandler)wizard).CreateHandler(new Sword());
sorry for that
On the other hand, because it doesn’t prevent a wizard from handling a sword, it leaves open the possibility that, provided other suitable run-time facilities exist, a wizard who finds the Sash of Strength in the Magnetic Palace would be able to wield a sword as long as he is within that venue.
Eric stated The player may use a weapon, but with restrictions, so Player class must check for Weapon type, derived classes must check if they support that Weapon or not, returning null is a way of telling “I do not support this”, of course, it isn’t an obvious way, I should have created a NotSupportedHandler, wich should be Player default implementation, The billion dolar mistake strikes again
The ideal approach from a consumer standpoint is to have three forms of query, analogous to the ContainsKey, GetValue and TryGetValue methods of Dictionary, but implementing three methods is more work than implementing one. If the intended semantics of a piece of code are “Act upon a retrieved item if it exists, or throw an exception if it doesn’t”, calling a method which will return the item or null and then invoking the method in question will achieve those semantics. The exception thrown in the null case may contain less helpful information than might a deliberately-thrown exception, but fail-fast semantics would have been achieved without requiring the caller to add code to handle the situation, and without requiring separate implementations for “Get data or throw” and “Try getting data and indicate whether successful”.
Perhaps the real “problem” with the NRE is the lack of any means by which code accessing a reference can include metadata allowing an NRE message to say “Null-reference exception while calling method ‘DoSomething’ of the value returned by method ‘GetValue’ of class ‘Fnord'”. The compiler would have all the information available to make an NRE produce such a message, and such an auto-generated message would generally be as informative (in some cases moreso) than a manually-coded `InvalidOperationException(“The requested key was not found”)`.
You can prevent the user from creating multiple handlers by making the ihandler class private to thw Wizard class, I just post an example, not fully working program
Pingback: The Morning Brew - Chris Alcock » The Morning Brew #1856
Pingback: Dew Drop – May 8, 2015 (#2010) | Morning Dew
I think the main issue that turns easy sounding requirements like shown in this series into a painful struggle over and over again is:
We skip designing a solution (because the requirements are so clear!) and jump right to implementation!
Attack resolution produces sideeffects some or even all of the participiants. As i see it, the participiants are
– the player
– the players weapon
– the monster
and there could be even more.
What exactly happens during attack-resolution may depend on
– the type and the state of the player, the players weapon, the monster
– the environment (time, location)
– the vector of player and monster (stabing a monster in the back may succseed, attacking it frontal may lead to a defense reaction)
– last but not least combinations of all of them.
There seems to be so much aspects in resolving an attack, that i would not try to handle this in a single even a single class.
Before trying to put all the domain logic in one class hierarchy, i would insist on modelling all the aspects of attack-resolution in the first place.
Prehabs after that, it will be obvious / transparent how to implement the single requirements.
Integration all these aspects will of cause be a responsibility of its own.
So to me, inheritance, multiple dispatch and so on are implementation details that are not relevant at all while designing the solution.
Nevertheless i have to say that i pretty much like this series and i am so curious, where this will lead to!
I’m guessing by “tools” you mean “the type system”. If we’re stepping away from using the type system this way, aren’t we also abandoning our goal of compile-time safety?
I think we can’t blame the type system. It’s the requirements that are contradictionairy. If we read yomething like “a player holds a weapon” we imply that a player can hold a weapon of any type. That conflicts with the requirement, that special type of player is restricted to a special type of weapon. This is, where the violation of the LSP originates (eric mentioned that in the first part i think).
Let me change the first requirement slightly an see where this leads to:
M”a player can POTENTIALLY hold a weapon of any type”
abstract class Player {
public Weapon weapon { get; private set; }
public abstract bool TrySetWeapon(Weapon weapon);
}
We lost compiletime typecheck. But the semantic is clear: the abillity to pick up a weapon is defined by the subtypes. The subtypes are now not more restrictive than the basetype.
Pingback: Wizards and warriors, part five | Fabulous adventures in coding
Pingback: Basic OOP is easy, isn’t it? | gerleim
FWIW, also:
https://github.com/waf/MultipleDispatchBenchmarks/pull/1
double dispatch-only, on Action’1 and Func’2 generics;
statically typed;
not using the dynamic keyword;
thread safe;
runtime perf comparable to dynamic;
CJ
Pingback: Polymorphism on Steroids – Dive Into Multiple Dispatch (Multimethods) - Vasil Kosturski