Higher Logics

I've written about quite a few irritations of C#/CLR, including asymmetries in CIL , oddly unverifiable CIL instructions , certain type constraints are forbidden for no reason , delegate creation bugs , the lack of higher-kinded types , equality asymmetries between events and IObservable , generics/type parameter problems , lack of usable control over object layouts , and just overall limitations of the CLR VM . I've just smack into yet another annoying problem: type parameter unification is forbidden . The Microsoft Connect bug filed in 2004 was closed as By Design . Here's a simple code fragment demonstrating the problem: class ObserveTwo<T0, T1> : IObservable<T0>, IObservable<T1> { } This will fail with the error: 'ObserveTwo<T0,T1>' cannot implement both 'System.IObservable<T0>' and 'System.IObservable<T1>' because they may unify for some type parameter substitutions This is frankly nonsense. What's...

A recent discussion on LtU brought up a common limitation of modern languages and runtimes. Consider some set of abstractions A, B, ..., Z that we wish supported some custom operation Foo(). Languages like C# give only two straightforward possibilities: inheritance and runtime type tests and casts. Inheritance is straightforward: we simply inherit from each A, B, ..., Z to make A_Foo, B_Foo, ..., Z_Foo, with a custom Foo() method. Unfortunately, inheritance is sometimes forbidden in C#, and furthermore, it sometimes prevents us from integrating with existing code. For instance, say we want to integrate with callback-style code, where the existing code hands our program an object of type A. We can't call Foo() on this A, because it's not an A_Foo, which is what we really wanted. This leaves us with the undesirable option of using a large set of runtime type tests. Now type tests and casts are actually pretty fast , faster than virtual dispatch in fact, but the danger is i...

Concurrent programming is hard, and many abstractions have been developed over the years to properly manage concurrent resources. The .NET base class libraries have mutexes, spinlocks, semaphores, compare-and-set (CAS) instructions, and more. The Problem Unfortunately, many of these standard abstractions are rather opaque, so predicting their behaviour is difficult, and enforcing a particular thread schedule is nearly impossible. For example, consider the issue of "fairness". Many abstractions to deal with threads are not fair, which is to say that they are not guaranteed to release threads in FIFO order, so a thread could starve . Furthermore, these opaque abstractions do not allow the application to easily specify domain-specific scheduling behaviour. Suppose threads T0, T1, and T2 are blocked on a resource X, in that order. X becomes available, and according to FIFO order, T0 should acquire control next. However, a domain-specific requirement may state that T2 should...

Jeroen Frijters helpfully pointed out that the CLR implements some hard limits on nesting generics, which is 99 for .NET 4 based on my tests. My previous implementation of ThreadScoped<T> was thus limited to 99 instances. Not very useful! The solution is actually quite simple, which I briefly outlined on Jeroen's blog: add more type parameters and use a simple base-99 counting scheme to generate new instances. Each additional type parameters thus increases the permutations 99 fold. One type index parameter yields 99 1 instances, two type index parameters yields 99 2 instances, three type index parameters yields 99 3 , and so on. No one in the foreseeable future will require more than 99 3 , which is almost a million thread-local variables, so I've added two more type index parameters to make Ref<T0, T1, T2> . The instance allocation function is now: internal override ThreadScoped<T> Allocate() { // If 'next' is null, we are at the end of th...

Awhile ago, Jeroen Frijters blogged about .NET 4's new ThreadLocal<T>, and how it was implemented. It was based on a neat generics trick exploiting the fact that the CLR does not erase types. Indexing a generic type X with a type T, means X<string> has distinct static and thread-local fields from say, X<int>. I've actually used this trick before to implement a type of safe reflection. Jeroen's sample implementation exploiting this trick for thread-local instance variables seemed far too complicated however, and it suffered from a number of limitations that he notes in his post. If Microsoft's implementation was even more complicated as was claimed, I wasn't confident it would perform very well at all. I decided to do my own implementation, without conforming the ThreadLocal<T>'s interface since I have very specific applications in mind. ThreadScoped<T> As I suspected, my implementation was considerably simpler , coming in a...

There's a great post on implementing idioms with LINQ, and the example application was to implement formlets, as WebSharper does for F#. Tomas's post is well written, so if you're unclear on the above concepts I recommend reading it first before proceeding with this article. The claim in that post is that idioms can only be encoded via LINQ's 'join' operators. While strictly true if you stick to all the LINQ rules, because LINQ queries are just naive syntactic transforms you don't have to follow the rules. You can thus exploit this to hijack the signatures for the SelectMany overloads to yield idiom signatures. It's not all sunshine and roses though, as there are consequences. Overview LINQ is a standard set of methods one can implement that the C# compiler can use to provide "query patterns". This query: var foo = from x in SomeFoo from y in foo.Values select y; is translated by the C# compiler to: var foo = Some...

Equality and identity are often intermingled in the .NET framework. .NET delegates correctly implement a straightforward structural equality , where if two delegates are equal if they designate the same method and the same object, regardless of whether the delegate is a unique instance: class Bar { public void Foo(int i) { } } var bar = new Bar(); Action<int> a1 = bar.Foo; Action<int> a2 = bar.Foo; Console.WriteLine("Delegate Equality: {0}", a1 == a2); // prints: // Delegate Equality: True However, an IObservable<T> created from delegates does not respect structural equality, and reverts to an identity criterion: // use a1 and a2 from previous code sample var o1 = Observer.Create<int>(a1); var o2 = Observer.Create<int>(a2); Console.WriteLine("Observable Equality: {0}", o1 == o2 || o1.Equals(o2) || EqualityComparer<IObserver<int>>.Default.Equals(o1, o2)); //prints: // Obs...