Complaining about .NET 3.5

I been doing some pretty serious functional programming with the .NET framework since the LINQ preview was released early last year. After rougly a year of use I feel that I now have the experience to confidently make a list of complaints. This is by no means a rant. The .NET framework is excellent but the following omissions are really needling me. 1. No IRandomAccessCollection<T> interface. We need a way of indicating that a collection is randomly accessible. This means it has an O(1) method to access a given element in an array and an O(1) count property. IList<T> and System.Array should both inherit from it. Often I want to perform a stream operation that requires random access to elements in order to do its job efficiently. Either an Array or a List will do. Copying a stream into an array is potentially expensive. If the stream is already an Array or a List it's worthwhile to attempt a run-time cast because it may save considerable time. As a result I end up doing two casts and writing an adapter. This is essentially what's done in ParallelFX today and I overhead that Joe Duffy was looking for feedback as to whether an interface like this one should be added to the BCL. Yes please. 2. No BigInteger. By this I mean an integer that grows to any size (until it uses up available memory). It was announced that this would be introduced in .NET 3.5 but it was made internal at the last second. Blog posts asking for an explanation were ignored. I believe I understand the reasoning. There is always a way of avoiding using a BigInteger and producing a more efficient algorithm. That said, sometimes I want to trade efficiency for elegance, reliability (no overflows), and speed of development. That's a decision that should be left up to me. Occasionally the lack of a BigInteger is inconvenient enough to make me use IronPython instead of C# for certain programs.* 3. Cost of Concat. Concatenating IEnumerable's together is costly. This is unacceptable because streams are a fundamental C# idiom. Wes Dyer explains more fully in this blog post. This problem has really affected the efficiency and elegance of my functional algorithms. To address this problem the following new C# syntax has been proposed: yield return someValue yield foreach someIEnumerable; I hope this is adopted. This is a big issue. 4. Having to implement IEnumerable.MoveNext() every time I implement IEnumerable<T>. C# already has syntactical support for streams (yield). Would it have been so hard for the compiler to generate this function if it didn't already exist? I know this is probably a non-starter and not that big a deal, but frankly it's an embarrassing amount of cruft to have to write. 5. Having to read/write "IEnumerable<IEnumerable<string>>" is awful. In the same vein as the previous complaint, why not provide syntactical support for declaring streams. C-Omega, the precursor to C#, used the asterisk to indicate a type was a stream in a similar way that [] indicates a type is an array. Streams are so pervasive in C# that I believe they are worthy of the same syntactical support as an array. I know the asterisk is out because C# already uses them for pointer arithmetic, but what about this: T[...][...] GetPermutations<T>(this T[...] stream) { // ... } That's just off the top of my head and there may be a better syntax but you see my point. 6. Lack of a non-null modifier. One of the unfortunate but necessary attributes of C# is that it has the concept of nullness. This is necessary because C# wants to play well with unmanaged code. Nevertheless nullness breaks polymorphism. A great way of mitigating this issue is to provide compiler support to prevent NullReferenceExceptions. C-Omega allowed you to add "!" to the end of a type and the compiler would enforce that a null value couldn't be assigned to it. Customer! cust = null; // compiler error I don't understand why this wasn't added to C#. I assume there's a good reason. Perhaps someone could explain it to me? That's all I can think of at the moment. I'll no doubt update this post as I run across further issues. *I like Python. I do think C#'s query comprehensions and its ubiquitous stream monad make it better suited for functional programming though.

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