Covariance and Contravariance in C#

Today: what do we mean by “covariance” and “contravariance”?

The first thing to understand is that for any two types T and U, exactly one of the following statements is true:

• T is bigger than U.
• T is smaller than U.
• T is equal to U.
• T is not related to U.

For example, consider a type hierarchy consisting of Animal, Mammal, Reptile, Giraffe, Tiger, Snake and Turtle, with the obvious relationships. ( Mammal is a subclass of Animal, etc.) Mammal is a bigger type than Giraffe and smaller thanAnimal, and obviously equal to Mammal. But Mammal is neither bigger than, smaller than, nor equal to Reptile, it’s just different.

Why is this relevant? Suppose you have a variable, that is, a storage location. Storage locations in C# all have a type associated with them. At runtime you can store an object which is an instance of an equal or smaller type in that storage location. That is, a variable of type Mammal can have an instance of Giraffe stored in it, but not a Turtle.

This idea of storing an object in a typed location is a specific example of a more general principle called the “substitution principle”. That is, in many contexts you can often substitute an instance of a “smaller” type for a “larger” type.

Now we can talk about variance. Consider an “operation” which manipulates types. If the results of the operation applied to any T and U always results in two types T’ and U’ with the same relationship as T and U, then the operation is said to be “covariant”. If the operation reverses bigness and smallness on its results but keeps equality and unrelatedness the same then the operation is said to be “contravariant”.

That’s totally highfalutin and probably not very clear. Next time we’ll look at how C# 3 implements variance at present.

Array Covariance

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 thanAnimal[], 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". And by “bigger than” and “smaller than” I explicitly do NOT mean “is a supertype of” and “is a subtype of”. It is the case that every subclass is smaller than its superclass, yes, but not vice versa. That is, it is not the case that every smaller type is a subtype of its larger type.Giraffe[] is smaller than both Animal[] and System.Array. Clearly Giraffe[] is a subtype of System.Array, but it is emphatically not a subtype of Animal[]. Therefore 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 we’ll discuss a kind of variance that we added to C# 2.0 which is not broken.

Method Group Conversion Variance

Last time I discussed how array covariance is broken in C# (and Java, and a number of other languages as well.) Today, a non-broken kind of variance supported by C# 2.0: conversions from method groups to delegates. This is a more complicated kind of variance, so let me spell it out in more detail.

Suppose that you have a method which returns a Giraffe:

static Giraffe MakeGiraffe() { …

Suppose further that you have a delegate type representing a function which takes no arguments and returns an Animal. Say, Func<Animal>. Should this implicit conversion from method group to delegate be legal?

Func<Animal> func = MakeGiraffe;

The caller of func is expecting an Animal to be returned. The actual function captured by the delegate always returns aGiraffe, which is an Animal, so the caller of func is never going to get anything that they’re not capable of dealing with. There is no problem in the type system here. Therefore we can make method group to delegate conversions covariant (‡) in their return types.

Now suppose you have two methods, one which takes a Giraffe and one which takes an Animal:

void Foo(Giraffe g) {}
void Bar(Animal a) {}

and a delegate to a void-returning function that takes a Mammal:

Action<Mammal> action1 = Foo; // illegal
Action<Mammal> action2 = Bar; // legal

Why is the first assignment illegal? Because the caller of action1 can pass a Tiger, but Foo cannot take a Tiger, only aGiraffe! The second assignment is legal because Bar can take any Animal.

In our previous example we preserved the direction of the assignability: Giraffe is smaller than Animal, so a method which returns a Giraffe is smaller than a delegate which returns an Animal. In this example we are reversing the direction of the assignability: Mammal is smaller than Animal, so a method which takes an Animal is smaller than a delegate which takes aMammal. Because the direction is reversed, method group to delegate conversions are contravariant in their argument types.

Note that all of the above applies only to reference types. We never say something like “well, every int fits into a long, so a method which returns an int is assignable to a variable of type Func<long>”.

Next time: a stronger kind of delegate variance that we could support in a hypothetical future version of C#.

(‡) A note to nitpickers out there: yes, I said earlier that variance was a property of operations on types, and here I have an operation on method groups, which are typeless expressions in C#. I’m writing a blog, not a dissertation; deal with it!

Real Delegate Variance

In the last two posts I discussed the two kinds of variance that C# already has -- array covariance and member-group-to-delegate conversion covariance (on return types) and contravariance (on formal parameter types).

Today I want to generalize the latter kind of variance.

In C# 3.0 today, even though it is legal to assign a typeless method group for a function that returns a Giraffe to a variable of type Func<Animal>, it is not legal to assign a typed expression of type Func<Giraffe> to a Func<Animal>. Generic delegate types are always invariant in C# 3.0. That seems weak.

Suppose we had the ability to declare type parameters of generic delegate types as being covariant or contravariant. For the sake of brevity (and consistency with existing notation in the CLR specification) I will notate a covariant type parameter with a + and a contravariant type parameter with a -.

This is not a particularly compelling notation; I will discuss its deficiencies in a later post. But for now we'll stick with it.The way to remember what it means is that a plus means "this type argument is allowed to get bigger upon assignment", and similarly for minus.

Consider for example our standard function:

delegate R Func<A, R>(A a);

Since R appears only in the returns and A appears only in the formal parameter list, we can make R covariant and Acontravariant(‡):

delegate R Func< -A, +R >(A a);

So again, you can think of this as "you can make A smaller or R bigger" (or, of course, both). For example:

Func<Animal, Giraffe> f1 = whatever;
Func<Mammal, Mammal> f2 = f1;

Normally in C# this assignment would be illegal because the delegates are parameterized by different types. But since we have made Func variant in both its type parameters, this assignment would become legal were we to add this kind of variance to a hypothetical future version of C#.

Does that make sense so far?

(‡) This rule of thumb is not always correct! Sometimes the input parameters need to be of a covariant type parameter. I shall discuss just such a situation next time, and I promise that it will hurt your brain.

Higher Order Functions

Last time I discussed how we could in a hypothetical future version of C# allow delegate types to be covariant in their return type and contravariant in their formal parameter types. For example, we could have a contravariant action delegate:

delegate void Action< -A > (A a);

and then have

Action<Animal> action1 = (Animal a)=>{ Console.WriteLine(a.LatinName); };
Action<Giraffe> action2 = action1;

Because action2’s caller will always pass in something that action1 can handle.

Based on my discussion so far, I hope that you have a strong intuition that the normal, sensible use of variance is “stuff going ‘in’ may be contravariant, stuff going ‘out’ may be covariant”. Though I believe that would be the most common use of variance were we to enable this feature in a hypothetical future version of C#, the real situation would actually be rather more complicated than that. There is a situation where it is legal to use a covariant parameter in the formal parameter of a delegate. Doing so makes my brain hurt, but this also builds character, so here we go!

Suppose you want to do "higher order" functional programming. For example, perhaps you want to define a meta-action – a delegate which takes actions and does something with them:

delegate void Meta<A> (Action<A> action);

for example,

Meta<Mammal> meta1 = (Action<Mammal> action)=>{action(new Giraffe());};
// The next line is legal because Action<Animal> is smaller than Action<Mammal>;
// remember, Action is contravariant
meta1(action1);

So this Meta thing takes an Action on Mammals – say, action1 above, which prints the Latin name of any Animal, and therefore can do so to any Mammal – and then invokes that action on a new Giraffe.

Clearly the type parameter A is used in an input position in the definition of Meta<A>, so we should be able to make itcontravariant, right? Suppose we did so. That would mean that this assignment would be legal:

Meta<Tiger> meta2 = meta1; // would be legal if Meta were contravariant in its parameter

But that means that this would then be legal:

Action<Tiger> action3 = tiger=>{ tiger.Growl(); };
meta2(action3);

Follow the logic through and you’ll see that we end up calling (new Giraffe()).Growl(), which is clearly a violation of both the type system and of nature’s laws.

Thus Meta<A> cannot be contravariant in A. It can however be covariant:

Meta<Animal> meta3 = meta1; // legal if Meta were covariant

Now everything works. meta3 takes an Action on Animals and passes a Giraffe to that Action. We’re all good.

Contravariance is tricky; the fact that it reverses the bigger/smaller relationship between types means that a type parameter used in a "doubly contravariant" position (being an input of Action, which is itself an input of Meta) becomes covariant. The second reversal undoes the first.

We do not expect that most people will use variance in this manner; rather, we expect that people will almost always use covariant parameters in output positions and contravariant parameters in input positions. As we’ll see a bit later in this series, whether this expectation is reasonable or not would influence the syntax we might choose were we to add variance to a hypothetical future version of C#.

Interface Variance

Over the last few posts I’ve discussed how it is possible to treat a delegate as contravariant in its arguments and covariant in its return type. A delegate is basically just an object which represents a single function call; we can do this same kind of thing to other things which represent function calls. Interfaces, for example, are contracts which specify what set of function calls are available on a particular object.

This means that we could extend the notion of variance to interface definitions as well, using the same rules as we had for delegates. For example, consider

public interface IEnumerator<T> : IDisposable, IEnumerator {
  new T Current { get; }
}

Here we have a generic interface where the sole use of the parameter is in an output position. We could therefore make the parameter covariant. That would mean that it would be legal to assign an object implementing IEnumerator<Giraffe> to a variable of type IEnumerator<Animal>. Since the user of that variable will always expect an Animal to come out, and the actual backing implementation always produces a Giraffe, everyone is happy.

Once we’ve got IEnumerator<+T>, we can then notice that IEnumerable<T> is defined as:

public interface IEnumerable<T> : IEnumerable {
  new IEnumerator<T> GetEnumerator();
}

Again, the parameter appears only in an output position, so we could make IEnumerable<+T> covariant as well.

This then opens up a whole slew of nice scenarios. Today, this code would fail to compile:

void FeedAnimals(IEnumerable<Animal> animals) {
  foreach(Animal animal in animals)
    if (animal.Hungry)
      Feed(animal);
}
...
IEnumerable<Giraffe> adultGiraffes = from g in giraffes where g.Age > 5 select g;
FeedAnimals(adultGiraffes);

Because adultGiraffes implements IEnumerable<Giraffe>, not IEnumerable<Animal>. With C# 3.0 you’d have to do a silly and expensive casting operation to make this compile, something like:

FeedAnimals(adultGiraffes.Cast<Animal>());

or

FeedAnimals(from g in adultGiraffes select (Animal)g);

Or whatever. This explicit typing should not be necessary. Unlike arrays (which are read-write) it is perfectly typesafe to treat a read-only list of giraffes as a list of animals.

Similarly, we could make

public interface IComparer<-T> {
  int Compare(T x, T y);
}

into a contravariant interface, since the type parameter is used only in input positions. You could then implement an object which compares two Animals and use it in a context where you need an object which compares two Giraffes without worrying about type system problems.

Next time: Suppose we were to do interface and delegate variance in a hypothetical future version of C#. What would the syntax look like? Is this goofy plus and minus really the best we can do? Do we need any syntax at all?

Why Do We Need A Syntax At All?

Suppose we were to implement generic interface and delegate variance in a hypothetical future version of C#. What, hypothetically, would the syntax look like? There are a bunch of options that we could hypothetically consider.

Before I get into options though, let’s be bold. What about “no syntax at all”? That is why not just infer variance on behalf of the user such that everything magically just works?

Unfortunately this doesn’t fly, for several reasons.

First, it seems to me that variance ought to be something that you deliberately design into your interface or delegate. Making it just start happening with no control by the user works against that goal, and also can introduce breaking changes. (More on those in a later post!)

Doing so automagically also means that as the development process goes on and methods are added to interfaces, the variance of the interface may change unexpectedly. This could introduce unexpected and far-reaching changes elsewhere in the program.

Second, attempting to do so introduces a new kind of cycle to the language analysis. We already have to detect things like cycles in base classes, cycles in base interfaces and cycles in generic type constraints, so this is in theory nothing new. But in practice, there are some issues.

In my previous post I did not discuss what additional restrictions we’d need to put on variant interfaces; one important restriction is that a variant interface which inherits from another variant interface must do so in a manner which does not introduce problems in the type system. Basically, all the rules for when a type parameter can be covariant or contravariant need to "flow through" to base interfaces. (This is vague, I know. I have a precise formal definition of what all the rules are which I may post at a later date. The exact rules are not important for the purposes of this discussion.)

For example, suppose the compiler was trying to deduce variance in this program:

interface IFrob<T> : IBlah<T> { }
interface IBlah<U> {
  IFrob<U> Frob();
}

We might ask ourselves “is it legal for T to be variant in IFrob<T>?” To answer that question, we need to determine whether it is legal for U to be variant in IBlah. To answer that question we need to know whether it is legal for U to be variant in output type IFrob<U>, and hey, we’re back where we started!

I would rather the compiler not go into an infinite loop when given this program. But clearly this is a perfectly legalprogram. When we detect a cycle in base classes, we can throw up our hands and say "you've got an illegal program". We cannot do that here. That complicates matters.

Third, even if we could figure out a way to solve the cycle problem, we would still have a problem with the case above. Namely, there are three possible logically consistent answers: “both invariant”, “+T, +U” and “-T, -U” all produce programs which would be typesafe. How would we choose?

We could get into even worse situations:

interface IRezrov<V, W> {
  IRezrov<V, W> Rezrov(IRezrov<W, V> x);
}

In this crazy interface we can deduce that “both invariant”, “ <+V, -W> and <-V, +W> are all possibilities. Again, how to choose?

And fourth, even if we could solve all those problems, I suspect that the performance of such an algorithm would be potentially very bad. This has “exponential growth” written all over it. We have other exponential algorithms in the compiler, but I'd rather not add any more if we can avoid it.

Thus, if we do add interface and delegate variance in some hypothetical future version of C#, we will provide a syntax for it. Next time, some ideas on what that syntax could look like. (If you have bright ideas yourself, feel free to post them in comments!)

Syntax Options

As I discussed last time, were we to introduce interface and delegate variance in a hypothetical future version of C# we would need a syntax for it. Here are some possibilities that immediately come to mind.

Option 1:

interface IFoo<+T, -U> { T Foo(U u); }

The CLR uses the convention I have been using so far in this series of “+ means covariant, - means contravariant”. Though this does have some mnemonic value (because + means “is compatible with a bigger type”), most people (including members of the C# design committee!) have a hard time remembering exactly which is which.

This convention is also used by the Scala programming language.

Option 2:

interface IFoo<T:*, *:U> { …

This more graphically indicates “something which is extended by T” and “something which extends U”.  This is similar to Java’s “wildcard types”, where they say “? extends U” or “? super T”.

Though this isn’t terrible, I think it’s a bit of a conflation of the notions of extension and assignment compatibility. I do not want to imply that IEnumerable<Animal> is a base of IEnumerable<Giraffe>, even if Animal is a base of Giraffe. Rather, I want to say that IEnumerable<Giraffe> is convertible to IEnumerable<Animal>, or assignment compatible, or some such thing. I don’t want to conceptually overwork the inheritance mechanism. It's bad enough IMO that we conflate base classes with base interfaces.

Option 3:

interface IFoo<T, U> where T: covariant, U: contravariant { …

Again, not too bad. The danger here is similar to that of the plus and minus: that no one remembers what “contravariant” and “covariant” mean. This has the benefit at least that you can do a web search on the keywords and get a reasonable explanation.

Option 4:

interface IFoo<[Covariant] T, [Contravariant] U>  { …

Similar to option 3.

Option 5:

interface IFoo<out T, in U> { …

We are taking a different tack with this syntax. In all the options so far we have been describing how the user of the interface may treat the interface with respect to the type system rules for implicit conversions – that is, what are the legal variances on the type parameters. Here we are instead describing this in the language of how the implementer of the interface intends to use the type parameters.

I like this one a lot; the down side of this is of course that, as I described a few posts ago, you end up with situations like

delegate void Meta<out T>(Action<T> action);

where the "out" T is clearly used in an input position.

Option 6:

Do something else I haven’t thought of. Anyone who has bright ideas, please leave comments.

Breaking Changes

Today in the last entry in my ongoing saga of covariance and contravariance I’ll discuss what breaking changes adding this feature might cause.

Simply adding variance awareness to the conversion rules should never cause any breaking change. However, the combination of adding variance to the conversion rules and making some types have variant parameters causes potential breaking changes.

People are generally smart enough to not write:

if (x is Animal)
  DoSomething();
else if (x is Giraffe)
  DoSomethingElse(); // never runs

because the second condition is entirely subsumed by the first. But today in C# 3.0 it is entirely sensible to write

if (x is IEnumerable<Animal>)
  DoSomething();
else if (x is IEnumerable<Giraffe>)
  DoSomethingElse();

because there did not used to be any conversion between IEnumerable<Animal> and IEnumerable<Giraffe>. If we turn on covariance in IEnumerable<T> and the compiled program containing the fragment uses the new library then its behaviour when given an IEnumerable<Giraffe> will change. The object will be assignable to IEnumerable<Animal>, and therefore the “is” will report “true”.

There is also the issue of existing source code changing semantics or turning compiling programs into erroneous programs. For example, overload resolution may now fail where it used to succeed. If we have:

interface IBar<T>{} // From some other assembly
...
void M(IBar<Tiger> x){}
void M(IBar<Giraffe> x){}
void M(object x) {}
...
IBar<Animal> y = whatever;
M(y);

Then overload resolution picks the object version today because it is the sole applicable choice. If we change the definition of IBar to

interface IBar<-T>{}

and recompile then we get an ambiguity error because now all three are applicable and there is no unique best choice.

We always want to avoid breaking changes if possible, but sometimes new features are sufficiently compelling and the breaks are sufficiently rare that it’s worth it. My intuition is that by turning on interface and delegate variance we would enable many more interesting scenarios than we would break.

What are your thoughts? Keep in mind that we expect that the vast majority of developers will never have to define the variance of a given type argument, but they may take advantage of variance frequently. Is it worth our while to invest time and energy in this sort of thing for a hypothetical future version of the language?

Dealing With Ambiguity

OK, I wasn’t quite done. One more variance post!

Smart people: suppose we made IEnumerable<T> covariant in T. What should this program fragment do?

class C : IEnumerable<Giraffe>, IEnumerable<Turtle> {
    IEnumerator<Giraffe> IEnumerable<Giraffe>.GetEnumerator() {
        yield return new Giraffe();
    }
    IEnumerator<Turtle> IEnumerable<Turtle>.GetEnumerator() {
        yield return new Turtle();
    }
// [etc.]
}

class Program {
    static void Main()  {
        IEnumerable<Animal> animals = new C();
        Console.WriteLine(animals.First().GetType().ToString());
    }
}

Options:

1) Compile-time error.
2) Run-time error.
3) Always enumerate Giraffes.
4) Always enumerate Turtles.
5) Choose Giraffes vs Turtles at runtime.
6) Other, please specify.

And if you like any options other than (1), should this be a compile-time warning?

To infinity, but not beyond

UPDATE: Andrew Kennedy, author of the paper I reference below, was good enough to point out some corrections and omissions, which I have addressed. Thanks Andrew!

As I've discussed at length in this space, we are considering adding covariance and contravariance on delegate and interface types parameterized with reference types to a hypothetical future version of C#. (See my earlier articles in this series for an explanation of the proposed feature.)

Variance is highly useful in mainstream cases, but exposes a really irksome problem in certain bizarre corner cases. Here's just one example.

Consider a "normal" interface contravariant in its sole generic type parameter, and a "crazy" invariant interface which extends the normal interface in a strange way:

public interface IN<in U> {}
public interface IC<X> : IN<IN<IC<IC<X>>>> {}

This is a bit weird, but certainly legal.

Before I go on, I want to digress and talk a bit about why this is legal. Most people when they first see such a beast immediately say "but an interface cannot inherit from itself, that's an illegal circularity in the inheritance chain!"

First off, no, that is not correct. Nowhere does the C# specification make this kind of inheritance illegal, and in fact, a weak form of it must be legal. You want to be able to say:

interface INumber<X> : IComparable<INumber<X>> { ... }

that is, you want to be able to express that one of the guarantees of the INumber<X> contract is that you can always compare one number with another one. Therefore, it must be legal to use a type's name in a type argument of a generic base type.

However, all is not rosy. This particularly gross kind of inheritance that I give as an example is in fact illegal in the CLR, even though it is not illegal in C#. This means that it is possible to have the C# compiler generate an interface type which then cannot be loaded by the CLR. This unfortunate mismatch is troubling, and I hope in a future version of C# to make the type definition rules of C# as strict or stricter than those of the CLR. Until then, if it hurts when you do that, don't do it.

Second, unfortunately, the C# compiler presently has numerous bugs in its cycle detector such that sometimes things which kinda look like cycles but are in fact not cycles are flagged as cycle errors. This just makes it all the more difficult for people to understand what is a legal cycle and what isn't. For example, the compiler today will incorrectly report that this is an illegal base class cycle, even though it clearly is not:

public class November<T> {}
public class Romeo : November<Romeo.Sierra.Tango> {
   public class Sierra {
       public class Tango {}
    }
}

I have devised a new (and I believe correct!) cycle detection algorithm implementation, but unfortunately it will not make it into the service release of the C# 3 compiler. It will have to wait for a hypothetical future release. I hope to address the problem of bringing the legal type checker into line with the CLR at the same time.

Anyway, back to the subject at hand: crazy variance. We have the interfaces defined as above, and then give the compiler a little puzzle to solve:

IC<double> bar = whatever;
IN<IC<string>> foo = bar;  // Is this assignment legal?

I am about to get into a morass of impossible-to-read generic names, so to make it easier on all of us, I am going to from now on abbreviate IN<IC<string>> as NCS. IC<double> will be abbreviated as CD. You get the idea I'm sure.

Similarly, I will notate "is convertible to by implicit reference conversion" by a right-pointing arrow. So the question at hand is true or false: CD→NCS ?

Well, let’s see. Clearly CD does not go to NCS directly. But (the compiler reasons) maybe CD’s base type does.

CD’s base type is NNCCD. Does NNCCD→NCS? Well, N is contravariant in its parameter so therefore this boils down to the question, does CS→NCCD ?

Clearly not directly. But perhaps CS has a base type which goes to NCCD. The base type of CS is NNCCS. So now we have the question does NNCCS→NCCD ?

Well, N is contravariant in its parameter, so this boils down to the question does CCD→NCCS ?

Let’s pause and reflect a moment here.

The compiler has “reduced” the problem of determining the truth of CD→NCS to the problem of determining the truth of CCD→NCCS! If we keep on “reducing” like this then we’ll get to CCCD→NCCCS, CCCCD→NCCCCS, and so on.

I have a prototype C# compiler which implements variance – if you try this, it says “fatal error, an expression is too complex to compile”.

I considered implementing an algorithm that is smarter about determining convertibility; the paper I reference below has such an algorithm. (Fortunately, the C# type system is weak enough that determining convertibility of complex types is NOT equivalent to the halting problem; we can find these bogus situations both in principle and in practice. Interestingly, there are type systems in which this problem is equivalent to the halting problem, and type systems for which the computability of convertibility is still an open question.) However, given that we have many other higher priorities, it’s easier to just let the compiler run out of stack space and have a fatal error. These are not realistic scenarios from which we must sensibly recover.

To read original article click here