C# implements variance in two ways. Today, the broken way.

Ever since C# 1.0, arrays where the element type is a reference type are covariant. This is perfectly legal:

Animal[] animals = new Giraffe[10];

Since Giraffe is smaller than Animal, and “make an array of” is a covariant operation on types, Giraffe[] is smaller than Animal[], so an instance fits into that variable.

Unfortunately, this particular kind of covariance is broken. It was added to the CLR because Java requires it and the CLR designers wanted to be able to support Java-like languages. We then up and added it to C# because it was in the CLR. This decision was quite controversial at the time and I am not very happy about it, but there’s nothing we can do about it now.

Why is this broken? Because it should always be legal to put a Turtle into an array of Animals. With array covariance in the language and runtime you cannot guarantee that an array of Animals can accept a Turtle because the backing store might actually be an array of Giraffes.

This means that we have turned a bug which could be caught by the compiler into one that can only be caught at runtime. This also means that every time you put an object into an array we have to do a run-time check to ensure that the type works out and throw an exception if it doesn’t. That’s potentially expensive if you’re putting a zillion of these things into the array.

Yuck.

Unfortunately, we’re stuck with this now. Giraffe[] is smaller than Animal[], and that’s just the way it goes.

I would like to take this opportunity to clarify some points brought up in comments to Part One.

First, by “subtype” and “supertype” I mean “is on the chain of base classes” for classes and “is on the tree of base interfaces” for interfaces. I do not mean the more general notion of “is substitutable for”. 

By “bigger than” and “smaller than” I explicitly do not mean “is a base class of” and “is a derived type of”. It is the case that every subclass is smaller than its superclass, yes. But it is not the case that every smaller type is derived from its larger type. 

Giraffe[] is smaller than both Animal[] and System.Array. Clearly Giraffe[] is derived from System.Array, but it is not derived from Animal[].

The “is smaller than” relationship I am defining is more general than the “is a kind of” relationship. I want to draw a distinction between assignment compatibility (smaller than) and inheritance (subtype of).

Next time on FAIC: we’ll discuss a kind of variance that we added to C# 2.0 which is not broken.

Archive of original post

The other morning I got the following question from a reader:

     I have created a client-server application in C# using asynchronous socket methods [… blah blah blah, a long description of a scenario in which the socket misses packets under certain conditions]

Today, the answer to Friday’s puzzle. It prints Int32. But why?

Some readers hypothesized that M would print out Int32 because the declaration B : A<int> somehow tells B that T is to be treated as int, now and forever.

Though the answer is right, the explanation is not quite right. One can illustrate this by taking C out of the picture. If you say (new A<string>.B()).M(), you’ll get String. The fact that B is an A<int> doesn’t make T always int inside B!

The always-keen Stuart Ballard was the first to put his finger upon the real crux of the problem — but he’s seen this problem before, so he had an advantage. Eamon Nerbonne was the first to post a complete and correct explanation.

The really thorny issue here is that the declaration class C : B is upon close inspection, somewhat ambiguous. Is that equivalent to class C : A<T>.B or class C : A<int>.B?

Clearly it matters which we choose. A method group can only be treated as a member if the method is on a base class. Merely being on an outer class doesn’t cut it:

public class X 
{ 
  public void M() { } 
}
public class Y 
{
  public void N() { }
  public class Z : X { }
}
...
// legal, from base class
(new Y.Z()).M(); 
// illegal -- outer class members are not members of inner classes.
(new Y.Z()).N(); 

In our example, when we called M on an instance of A<string>.B.C, it was calling a method of the base class of C. If the base class of C is A<T>.B, then that should call A<T>.B.M, and it should print out whatever the current value of T is — in this case, String. If the base class of C is A<int>.B, then that should call A<int>.B.M, so it should print out Int32.

We choose the latter as the base class. That was certainly a surprise to me. And Stuart Ballard. And, amusingly enough, when I sprang this one upon Anders and didn’t give him time to think about it carefully, it was a surprise to him as well. When I sprang it on Cyrus, he cheerfully pointed out that he already posted a harder version of this problem back in 2005, the solution of which Stuart characterized back then as “Insanely complex, but it makes perfect sense.” I couldn’t agree more, though at least my version of the puzzle is somewhat simpler.

Anyway, why on earth ought that to be the case? Surely the B in class C : B means the immediately containing class, which is A<T>.B, not A<int>.B! And yet it does not.

These generics are screwing up our intuitions. Let’s look at an example which has no generics at all:

public class D 
{
  public class E {}
}
public class F 
{
  public class E { }
  public class G 
  {
    public E e; // clearly F.E
  }
}
public class H : D 
{
  public E e; // clearly D.E
}

This is all legal so far, and should be pretty clear. When we are binding a name to a type, the type we get is allowed to be a member of any base class or a member of any outer class. But what if we have both to choose from?

public class J 
{
  public class E { }
  public class K : D 
  {
    public E e; // Is this J.E or D.E?
  }
}

We could just throw up our hands and say that this is ambiguous and therefore illegal, but we’d rather not do that if we can avoid it. We have to prefer one of them, and we’ve decided that we will give priority to base classes over outer classes. Derived classes have an “is a kind of” relationship with their base classes, and that is logically a “tighter” binding than the “is contained in” relationship that inner classes have with outer classes.

Another way to think about it is that all the members you get from your base class are all “in the current scope”; therefore all the members you get from outer scopes are given lower priority, since stuff inside inner scopes takes priority over stuff in outer scopes.

The algorithm we use to search for a name used in the context of a type S is as follows:

• search S’s type parameters
• search S’s accessible inner classes
• search accessible inner classes of all of S’s base classes, going in order from most to least derived
• S←S’s outer class, start over

(And if that fails then we invoke the whole mechanism of searching the namespaces that are in scope, checking alias clauses, etc.)

With that in mind, now the solution should finally make some sense. At the point where we are resolving the base class of C we know that C has no type parameters. We do not know what the base class or inner classes of C are — that’s what we’re trying to figure out — so we skip checking them.

The next thing we check is the outer class, which is A<T>.B, but we do NOT say, aha, the outer class is called B, we’re done. That is not at all what the algorithm above says. Instead, it says check A<T>.B to see if it has a type parameter called B or an inner type called B. It does not, so we keep searching.

The base type of A<T>.B is A<int>. The outer type of A<T>.B is A<T>. Both have an accessible inner class called B. Which do we pick? The base type gets searched first, so B resolves to A<int>.B. Obviously.

Having members of base classes bind tighter than members from outer scopes can lead to bizarre situations but they are generally pretty contrived. For example:

public class K 
{ 
  public class L { } 
}
public class L : K 
{
  L myL; // this is K.L!
}

And of course, you can always get around these problems by eliminating the ambiguity:

public class A<T> 
{
  public class B : A<int> 
  {
    public void M() { ... }
    // no longer ambiguous which B is picked.
    public class C : A<T>.B { } 
  }
}

Finally, the specification of this behaviour is a bit tricky to understand. The spec says:

Otherwise, if T contains a nested accessible type having name I and K type parameters, then the namespace-or-type-name refers to that type constructed with the given type arguments. If there is more than one such type, the type declared within the more derived type is selected.

By “if T contains a nested accessible type”, it means “if T, or any of its base classes, contains a nested accessible type”. I completely failed to comprehend that the first n times I read that section. I’ll see if I can get that clarified in the next version of the standard.

A language design question was posted to the Microsoft internal C# discussion group this morning: “Why must overloaded operators be static in C#? In C++ an overloaded operator can be implemented by a static, instance or virtual method. Is there some reason for this constraint in C#?“

Before I get into the specifics, there is a larger point here worth delving into, or at least linking to. Raymond Chen immediately pointed out that the questioner had it backwards. The design of the C# language is not a subtractive process; though I take Bob Cringely’s rather backhanded compliments from 2001 in the best possible way, C# is not Java/C++/whatever with the kludgy parts removed. Former C# team member Eric Gunnerson wrote a great article about how the process actually works.

Rather, the question we should be asking ourselves when faced with a potential language feature is “does the compelling benefit of the feature justify all the costs?” And costs are considerably more than just the mundane dollar costs of designing, developing, testing, documenting and maintaining a feature. There are more subtle costs, like, will this feature make it more difficult to change the type inferencing algorithm in the future? Does this lead us into a world where we will be unable to make changes without introducing backwards compatibility breaks? And so on.

In this specific case, the compelling benefit is small. If you want to have a virtual dispatched overloaded operator in C# you can build one out of static parts very easily. For example:

public class B {
    public static B operator+(B b1, B b2) { return b1.Add(b2); }
    protected virtual B Add(B b2) { // …

And there you have it. So, the benefits are small. But the costs are large. C++-style instance operators are weird. For example, they break symmetry. If you define an operator+ that takes a C and an int, then c+2 is legal but 2+c is not, and that badly breaks our intuition about how the addition operator should behave.

Similarly, with virtual operators in C++, the left-hand argument is the thing which parameterizes the virtual dispatch. So again, we get this weird asymmetry between the right and left sides. Really what you want for most binary operators is double dispatch — you want the operator to be virtualized on the types of both arguments, not just the left-hand one. But neither C# nor C++ supports double dispatch natively. (Many real-world problems would be solved if we had double dispatch; for one thing, the visitor pattern becomes trivial. My colleague Wes is fond of pointing out that most design patterns are in fact necessary only insofar as the language has failed to provide a needed feature natively.)

And finally, in C++ you can only define an overloaded operator on a non-pointer type. This means that when you see c+2 and rewrite it as c.operator+(2), you are guaranteed that c is not a null pointer because it is not a pointer! C# also makes a distinction between values and references, but it would be very strange if instance operator overloads were only definable on non-nullable value types, and it would also be strange if c+2 could throw a null reference exception.

These and other difficulties along with the ease of building your own single (or double!) virtual dispatch mechanisms out of static mechanisms, makes it easy to decide to not add instance or virtual operator overloading to C#.