Multimethods in C# (Part 1)

Have you ever needed to perform an action based on the run-time type of one or more objects? Let's take a hypothetical spaceship game for example. There are three types of objects: an Asteroid, an X-Wing and a TIE-Fighter. They are related in the following inheritance hierarchy:



We have a collection of SpaceObjects that we update in a tight loop. We need to handle collisions between these objects. For example if a TIE-Fighter collides with an asteroid we might want to apply damage to the space ship and replace the asteroid with several smaller asteroids. One way of doing this is to determine the concrete type of each SpaceObject and then call one of several overloads to handle the collision:

bool Collison(SpaceObject leftSpaceObject, SpaceObject rightSpaceObject)
{
TieFighter tieFighter = leftSpaceObject as TieFighter;
Asteroid asteroid = rightSpaceObject as Asteroid;
if (tieFighter != null && asteroid != null)
{
  return Collision(tieFighter, asteroid);
}

XWing xWing = leftSpaceObject as XWing;
if xWing != null && asteroid != null)
{
  return Collision(xWing, asteroid);
}

//try again with reversing left and right parameters

// and on and on for every combination of every object in every order...
}

bool Collision(TieFighter tieFighter, Asteroid asteroid)
{
// handle collision
}

bool Collision(XWing xwing, Asteroid asteroid)
{
// handle collision
}

The method that dispatches to the correct overload smells. It is error-prone because you have to be careful to cast in order from the most derived to least derived classes. Failure to do so will not result in the most correct method being selected. It is also repetitive because all of the information required to write this code can be inferred from information you've already declared in your overloads and your class definitions. It's also a maintenance nightmare because if we make any changes to the class hierarchy we will need to remember to update the method.

Multimethods

Essentially we want virtual method dispatch but we need it on multiple types and we need it bound at run-time because the compiler can't know enough information to do it at compile-time. This is exactly what multimethods allow us to do. In a compiler that supports multimethods you simply declare the various overloads and the compiler ensures the correct overload is called. Here's what this might look like if it were added to C#:

// when invoked this checks argument types and dynamically dispatches to overloads below
multimethod bool Collision(SpaceObject obj1, SpaceObject obj2);

bool Collision(TieFighter tieFighter, Asteroid asteroid)
{
// handle collision
}

bool Collision(XWing xwing, Asteroid asteroid)
{
// handle collision
}

bool Collision(TieFighter tieFighter1, TieFighter tieFighter2)
{
//handle collision
}

// and so on for all cominbations...

Unfortunately there is no "multimethod" modifier in C# and it's quite unlikely there ever will be. Thankfully C# 3.0 does have a feature which allows us to seamlessly add this feature: Expressions.

Adding Multimethods to C#

Let's create a library that examines our class hierarchy and a group of method overloads using reflection and then creates the method that does the dynamic dispatch for us. We'll design it so it has the following API:

var collision = DynamicDispatch.CreateFunc<SpaceObject,SpaceObject,bool>((obj1, obj2) => this.Collision(obj1,obj2));

// dispatches to Collision(XWing xWing, TieFighter tieFigher)
collision(new XWing(), new TieFighter());

What's going on here? The CreateFunc method accepts a lambda in which the most abstract version of the collision method is invoked. It returns an instance of Func<>, a new delegate type introduced in C# 3.0 that wraps a method that returns no arguments. How do I manage to generate the code required to do dynamic dispatch from a lambda function? I'll cover that in the next installment. Stay tuned. :-)