Wednesday, July 2, 2008

Multimethods in C# (Part 2)

In part 1 I demonstrated how to use my multimethod library in C#:

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());

Although it appears that CreateFunc accepts a lambda function, in reality the type of its argument is a lambda expression. A Lambda expressions is the data representation of a lambda function. The CreateFunc functions analyzes the lambda expression and retrieves the overloads of the function invoked in the expression. Finally it generates the code to do a dynamic dispatch based on the argument types and returns a delegate of type Func<>.

Based on the type of the arguments passed to the collision delegate it invokes the correct method overload at run-time. In order to generate the code for this delegate I use the objects defined in the System.Linq.Expressions namespace. The code for the collision method looks something like this:

This may look a little complicated but really it's not. I simply create a function for each overload that attempts to cast the arguments to the concrete types expected. If any of the arguments are null, which they will be if the "as" operator fails, the process is repeated for the next overload until finally it reaches the most abstract overload.

So how is this done? Well first we must get a list of all the overloads and sort them in the appropriate order, from most abstract to most derived.

Some of the functions used here warrant some explanation. Iterate is a function that accepts a starting argument and a function and then generates a stream that takes an initial value, returns it, and then returns the results of recursively applying the function to the previous value. In other words FP.Iterate(0, x => x + 1) yields the following stream: 0,1,2,3,4,etc. In this case I use Iterate to walk up the inheritance tree of a type and find out what its depth is. Since the Iterate function is stateless and returns a stream I can use it in a Linq query. I sort the overloads by the max depth of any type in a given overload, and then by the sum of all the argument depths. Note that I sort the overloads in ascending order from most abstract to most derived instead of vice-versa. The reasons for this are clear when you examine how I build the expression.

Due to the fact that I want to build the expression using functional programming I will have to build it inside out recursively, starting with the most abstract function and ending with the most derived function. The reason for this is that more derived functions must call the most abstract functions, meaning they must exist before the derived functions are created. In order to achieve this I use a very versatile function: Enumerable.Aggregate. Aggregate takes an initial value, a function that accepts two arguments, and a stream. The first argument to the function is the initial value passed to the Aggregate. The second argument is the current item in the stream. Every time the function passed to aggregate is run the result is used for the accumulator variable. For example the following code yields 10:

var nums = new[]{1,2,3,4};
var output = nums.Aggregate(0, (x,y) => x + y);

Aggregate can work on anything, not just numbers. In this case my stream contains all the overloads, my accumulator variable is the expression I've built so far, and the function creates a new expression that invokes the current overload if the types match or invokes the expression in the accumulator if they don't.

This approach works well and is very elegant, but aren't we forgetting something?

What if instead of this...

collision(new XWing(), new TieFighter());

...the following code is run:

collision(new TieFighter(), new XWing());

Whoops! It wont match our first overload even though that would probably make the most sense under the circumstances. Within each handler we could write some manual code to try and reverse the arguments but that is exactly the kind of drudgery we want to avoid. Next time I'll show you how to modify our algorithm to generate code to try all the various combinations of argument orders.


Christopher Bennage said...

Beautiful! I want more! :-)

Affordable Luxurious Wedding Dress Blog said...
This comment has been removed by a blog administrator.
Anonymous said...
This comment has been removed by a blog administrator.
Anonymous said...
This comment has been removed by a blog administrator.
Anonymous said...
This comment has been removed by a blog administrator.

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.