Saturday, May 3, 2008

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. :-)

8 comments:

Jonathan Allen said...

If you want an easy multimethod, just use VB's CallByName.

Jafar Husain said...

CallByName has three disadvantages. Here they are in order of importance (IMHO):

1. You put code into a string. Let's say you refactor your method name. CallByName will cause a run-time error.

When you use my method the C# compiler takes the lambda, statically type checks it and then converts it into data. I then use this data to dynamically generate a function. This means the code is statically typed* but dynamically generated.

2. CallByName is slow. It uses reflection. My solution actually generates the code you would've written yourself manually and compiles it.

3. It's in the Microsoft.VisualBasic namespace which doesn't make it convenient for C# users to use.


*Technically it is possible to cause a run-time error by passing in a lambda that does not invoke a method. Example x => 3.

May 5, 2008 6:58 AM

Anonymous said...

Please post the solution! I'd love to be able to do this on my pet project.

Anonymous said...

just a thought... why wouldn't you implement an interface.

interface ISpaceObject
{
bool CollidesWith(ISpaceObject SpaceObject)
}

then for each object handle the collision respectively
class XWing:ISpaceObject
{
bool CollidesWith(ISpaceObject SpaceObject)
{
switch (SpaceObject.GetType().Name)
case "XWing"
do someting
case "Asteroid"
do something
etc.
}

then you dont have strong casting of objects, each object is aware of how it interacts with another space object and can be affected respectively.
}

just a thought.

Anonymous said...

edit on the last paragraph... you HAVE strong types and no need for casting whatsoever.

Guille said...

The sense of multimethods is stay thinking in objects. If your solutions has a lot of switchs of the class names, you lose something i like, what name is "polymorphism".

The solution without multimethods is the use of multiple dispatch, but it is dirty sometimes too.

Anonymous said...

Women’s nike tn Shox Rivalry est le modèle féminin le plus tendance de baskets pour le sport. tn chaussuresConcernant la semelle :Cheap Brand Jeans ShopMen Jeans - True Religion Jeans nike shoes & Puma Shoes Online- tn nike, le caoutchouc extérieur, l’EVA intermédiaire et le textile intérieur s’associent pour attribuer à la.ed hardy shirts pretty fitCharlestoncheap columbia jackets. turned a pair of double plays to do the trick.Lacoste Polo Shirts, , Burberry Polo Shirts.wholesale Lacoste polo shirts and cheap polo shirtswith great price.Thank you so much!!cheap polo shirts men'ssweate,gillette mach3 razor bladesfor men.As for

Anonymous said...

情趣用品|情趣用品|情趣用品|情趣|情趣用品|情趣

About Me

My photo
I'm a software developer who started programming at age 16 and never saw any reason to stop. I'm working on the Presentation Platform Controls team at Microsoft. My primary interests are functional programming, and Rich Internet Applications.