Loyc

Language of your choice

.NET just keeps getting more annoying

23 Jul 2014

It seems like the little design flaws of .NET get on my nerves more and more every week.

Today I realized that I wanted to do a binary search. No problem–I put a binary search method in Loyc.Essentials; four independent implementations, in fact, one for IList<T>, one for T[], and two for more obscure scenarios. But the list I wanted to search implemented IReadOnlyList<T>, not IList<T>. Since IReadOnlyList<T> is strangely not a subtype of IList<T>, I realized I would have to add another overload with a verbatim copy of the existing implementation. And of course I’d need to add not one new overload, but three, to support .NET’s three standard kinds of comparisons: T implementing IComparable<T>, independent IComparer<T>, and independent Comparison<T>:

public static int BinarySearch<T>(this IReadOnlyList<T> list, T value) where T : IComparable<T>
{
    return BinarySearch<T>(list, value, G.ToComparison<T>());
}
public static int BinarySearch<T>(this IReadOnlyList<T> list, T value, IComparer<T> comparer)
{
    return BinarySearch<T>(list, value, G.ToComparison(comparer));
}
public static int BinarySearch<T>(this IReadOnlyList<T> list, T find, Comparison<T> compare)
{
    // Duplication of code for IList<T>
}

And then my build broke because some code had called BinarySearch with a list that implemented both IReadOnlyList<T> and IList<T>, so I fixed that by adding the usual set of disambiguating overloads, raising the total number of BinarySearch methods in Loyc.Essentials somewhere north of 15.

Next, I realized that the kind of binary search I wanted was a bit unusual. I was writing a Visual Studio syntax highlighting extension and the list being searched was a list of ITagSpan<T> objects, which are Visual Studio objects that combine a “tag” object with a “span” (which is a range of characters in a text file). So I did not actually want to search for a particular ITagSpan<T> object in the list, I wanted to search for an integer such that the ITagSpan matched it in a certain way, e.g.

int i = _tagSpanList.BinarySearch(span.Start.Position, 
    (tspan, start) => (tspan.Span.End.Position-1).CompareTo(start));

This does not change the binary search algorithm at all, but it does change the method signature. Instead of this:

public static int BinarySearch<T>(this IReadOnlyList<T> list, T find, Comparison<T> compare)

what I actually wanted was this:

	public static int BinarySearch<T, K>(this IReadOnlyList<T> list, K find, Func<T, K, int> compare)

The delegate type Comparison<T> only supports symmetrical comparisons; in order to support asymmetrical comparisons I had to change Comparison to Func. Of course, if T = K then Comparison<T> and Func<T, K, int> are exactly equivalent… or they should be, but in fact are not, because Microsoft said so. You cannot pass a Comparison<T> into a method that expects Func<T, T, int> or vice versa. It’s possible to convert between the two types, but you have to allocate an extra heap object to do so.

But I figured no one else was using my library (much as I wish they would), so I changed the signature… problem solved, and I was able to finish my multi-language syntax highlighter (which currently supports EC# and LES).

But Loyc.Essentials still offers other methods that use Comparison<T>, such as Sort:

public static void Sort<T>(this IList<T> list, Comparison<T> comp) {...}

So imagine you are writing a module that needs to sort and repeatedly search a list. You want it to be generic, so you accept a delegate passed from the outside. What should the type of the delegate be? If you choose Comparison<T>, you can’t call BinarySearch and if you choose Func<T,T,int> you can’t call Sort. Wonderful.

So I realized that I had made a mistake. While clearly we need a version of BinarySearch that is asymmetrical, we clearly also need a version that accepts Comparison<T>. But this raises the minimum number of Binary Search implementations to four:

All with identical code inside. Now, I could pick one canonical implementation and use wrappers or adapters for the others, but such things require heap allocations. Do you think a binary search should require heap allocation? Well I don’t (I accept a single delegate allocation for the IComparer<T> overloads, which I personally never use.)

Meanwhile eight additional method overloads are provided, which just forward to one of the implementations above:

With 12 overloads, we haven’t even covered the case that you want to search a slice of the list rather than the entire list (you can do that by calling list.Slice(start, length).BinarySearch(item), of course, but it does have the disadvantage of boxing the slice structure.)

Oh, and one more thing. The version that takes Comparison<T> cannot have the same method name as the version that takes Func<T,K,int> because if you pass a lambda to BinarySearch, the C# compiler will error out because it is “ambiguous” which version to call, even though, of course, it doesn’t matter at all which version is called. So I decided to call the Comparison<T> version BinarySearch and renamed the Func<T,K,int> version BinarySearch2.

So this is my problem with .NET. We shouldn’t need 12 overloads (including 3 under a different name), we should only need 2 overloads and a single implementation:

As the author of a library that is highly generic, the unnecessary incompatibilities in .NET make me more and more uneasy every year. Today I’ve discussed two issues; here are some others, most of which I have discussed before:

These are mostly limitations of the CLR. If we add limitations of C#, or limitations of the BCL, the list becomes considerably longer.

I really believe a “managed environment” for software development should be available, in which developers can easily use dynamic loading, reflection, garbage collection and run-time code generation, and in which programs written in different languages are interoperable without hassles. But it is clear to me that both the Java and .NET implementations of this concept are flawed. That’s why I have called for a new VM to fix all these problems and supplant JavaScript, to boot. Now if only someone would hire me to help build it…

Published on

Possibly Related Posts

Comments