What is the relationship between variance, generic interfaces, and input/output?

Question

There is a blog post by Eric Lippert where he describes how to define variance. In a general sense, covariance is achieved when the direction of assignment compatibility is preserved. Contravariance is achieved when the direction of assignment compatibility is reversed.

Now let's use a C# generic interface as an example. Consider the following code from C# In a Nutshell:

IPoppable<Animal> animals = bears;
Animal a = animals.Pop();

public interface IPoppable<out T> { T Pop(); }
public interface IPushable<in T> { void Push (T obj); }

class Animal {}
class Bear : Animal {}
class Camel : Animal {}

public class Stack<T> : IPoppable<T>
{
  int position;
  T[] data = new T [100];
  public void Push (T obj) => data [position++] = obj;
  public T Pop()           => data [--position];
}

The IPoppable interface uses <out T> to say that T can only be used in an output position. This makes sense in the context of the example code. Since the Stack<T> class inherits from IPoppable<out T>, Pop() should only return data from the stack. It should not add data as input.

Because of this, the above code illustrates how to achieve covariance with generic interfaces by using the out parameter. The out parameter limits the Pop() method to only use T in an output position.

The reverse can be achieved with the in parameter, which would allow us to achieve contravariance by limiting T to only input positions within a generic interface. This is displayed above with the IPushable interface.

With all of this in mind, how does limiting a type to an output position relate to Eric Lippert's definition that covariance is defined when assignment compatibility is preserved? Similarly, how does limiting a type parameter to an input position relate to the definition of contravariance?

Answer 1

"In a general sense, covariance is achieved when the direction of assignment compatibility is preserved. Contravariance is achieved when the direction of assignment compatibility is reversed."

You omitted an important part there. What Eric Lippert was saying, applied to this context, is that, given some set of types (like your Animal, Bear, Camel) that have assignment compatibility relationships already defined among them, when you use them to construct new kinds of corresponding types (like your Stack<Animal>, Stack<Bear>, IPoppable<Animal>, etc.), those new types may or may not preserve the compatibility at their level (or they might reverse it).

But let's back up a bit. Think about what happens when you use these types polymorphically.

For example, if you create a stack of Bear-s, that stack can only contain instances of Bear or of its derivatives, if any.

var bearStack = new Stack<Bear>();
bearStack.Push(new Bear("some generic bear"));
bearStack.Push(new GrizzlyBear());
bearStack.Push(new BlackBear());

// Pop returns an instance typed as a Bear (actual type could be a derived class)
Bear bear = bearStack.Pop();   

Now, can you assign this particular stack to a variable that has the type Stack<Animal>?

Stack<Animal> animalStack = bearStack;

It feels like you should be able to, but taking polymorphism into account, here's how you can run into problems.

(1) Any Stack<Animal> should allow you to push any kind of animal to it. That's the contract - that's what the type Stack<Animal> means, it's what it promises to deliver. That's what you expect when you see that type anywhere in code. However, remember, animalStack is actually a bearStack, and it doesn't accept anything other than bears.

animalStack.Push(new Camel());   // just doesn't work! 

(2) However, with Pop(), it's all good. Any client code that needs an Animal will be perfectly happy to accept a Bear. A bear is-an animal, so a Bear instance can be assigned to an Animal variable.

Animal someAnimal = animalStack.Pop();   // remember, actually bearStack

Or maybe you use Stack<Animal> as a function parameter:

// This would work with Animal-typed instances, if the language allowed it
void ReleaseToWilderness(Stack<Animal> animalStack) {
    while (!animalStack.IsEmpty()) {
        Animal animal = animalStack.Pop();   
        animal.MakeHappyNoises();
        //...
    }
}

// It'd work because it would be safe to call it with a bearStack
ReleaseToWilderness(bearStack);  

// ^ here, bearStack is being assigned to the animalStack parameter

However, the language requires you to constrain the interface:

void ReleaseToWilderness(IPoppable<Animal> animalStack) { /* ... */ }

ReleaseToWilderness(bearStack);  // now this works

The assignment direction that is being preserved here is from more concrete to the more abstract; the direction is the same for both the "base" types and "augmented" types.

Bear  ------------ can be assigned to -----> Animal
Stack<Bear>  ----- can be assigned to -----> IPoppable<Animal>

That is, the stack versions of the types are covariant with respect to the assignment compatibility of the original types.

(3) But notice also that, when it comes to the Push operation, any Animal stack can be passed to anything that only wants to do pushes to an object that is, as far as that other code is concerned, a push-only Bear stack:

void AddSomeBears(IPushable<Bear> aThingThatAcceptsBears) {
    aThingThatAcceptsBears.Push(new Bear());
    aThingThatAcceptsBears.Push(new GrizzlyBear());
    aThingThatAcceptsBears.Push(new BlackBear());
    //...
}

void AddSomeCamels(IPushable<Camel> aThingThatAcceptsCamels) {
    //...
}

var animalStack = new Stack<Animal>(); // NOTE: it's the real Animal stack now
AddSomeBears(animalStack);
AddSomeCamels(animalStack);

So, between the "base" types and "augmented" types, the assignment direction is reversed:

          Bear   ----- can be assigned to -----> Animal
IPushable<Bear>  <---- can be assigned from ---- Stack<Animal>

In other words, the stack versions of the types are contravariant with respect to the assignment compatibility of the original types.

---

More precisely

          Bear  ------ can be assigned to -----> Animal
IPoppable<Bear>  ----- can be assigned to -----> IPoppable<Animal>

A "thing that provides bears" is-also-a "thing that provides animals" (they just happen to all be bears, but that's fine because a bear is-an animal).

And

          Bear   ----- can be assigned to -----> Animal
IPushable<Bear>  <---- can be assigned from ---- IPushable<Animal>

A "thing that accepts any animal" is-also-a "thing that accepts bears" - but this is not true the other way around.

---

A Stack<Bear> instance can only be substituted for Stack<Animal> if the client code that uses the Stack<Animal> limits itself to only use the parts of the Stack<Animal> interface that allow for covariance - that is, outputs are fine, but inputs are not because they could be incompatible (can't push anything that's not a bear).

Similarly, a Stack<Animal> instance can be substituted for a Stack<Bear> given that the client code limits itself to only use the parts of the Stack<Bear> interface that allow for contravariance - providing bears as input is fine, but asking for a bear is not, cause you might get a camel, or a cat, or something.

As an aside: You can also see this as Liskov Substitution Principle in action (it's one manifestation of it).

In the LSP sense, by Liskov-Wing definition of subtype, IPoppable<Bear> (including Stack<Bear>) can be conceptually seen as a subtype of IPoppable<Animal>, while IPushable<Animal> (including Stack<Animal>) can be seen as a subtype of IPushable<Bear> (or IPushable<Camel>, or...).

Answer 2

Let's take a step back: what does variance actually mean?

Well, variance means "change" (think of words like "to vary" or "variable"). co- means "together" (think of cooperation, co-education, co-location), contra- means "against" (think of contradiction, counter-intelligence, counter-insurgency, contraceptive), and in- means "unrelated" or "non-" (think of involuntary, inaccessible, intolerant).

So, we have "change" and that change can be "together", "against" or "unrelated". Well, in order to have related changes, we need two things which change, and they can either change together (i.e. when one thing changes, the other thing also changes "in the same direction"), they can change against each other (i.e. when one thing changes, the other thing changes "in the opposite direction"), or they can be unrelated (i.e. when one thing changes, the other doesn't.)

And that's all there is to the mathematical concept of covariance, contravariance, and invariance. All we need are two "things", some notion of "change", and this change needs to have some notion of "direction".

Now, that's of course very abstract. In this particular instance, we are talking about the context of subtyping and parametric polymorphism. How does this apply here?

Well, what are our two things? When we have a type constructor such as I<A>, then our two things are:

1. The type argument A.
2. The constructed type which is the result of applying the type constructor I to A.

And what is our change with a sense of direction? It is subtyping!

So, the question now becomes: "When I change A to B (along one of the directions of subtyping, i.e. make it either a subtype or a supertype), then how does I<A> relate to I<B>".

And again, there are three possibilities:

• Covariance: A <⦂ B ⇒ I<A> <⦂ I<B>: when A is a subtype of B then I<A> is a subtype of I<B>, in other words, when I change A along the subtyping hierarchy, then I<A> changes with A in the same direction.
• Contravariance: A <⦂ B ⇒ I<A> ⦂> I<B>: when A is a subtype of B, then I<A> is a supertype of I<B>, in other words, when I change A along the subtyping hierarchy, then I<A> changes against A in the opposite direction.
• Invariance: there is no subtyping relationship between I<A> and I<B>, neither is a sub- nor supertype of the other.

In the context of Type Theory and Programming Languages, Variance is when Subtyping and Parametric Polymorphism meet: subtyping means that you have an ordering / compatibility relation between types and parametric polymorphism means that you have type constructors which construct new types out of existing types. This naturally poses the question: if I construct new types out of existing types that have a certain relationship, what is the relationship between the constructed types?

If you have only one of the two, that question does not come into play and therefore, you have no notion of variance. For example, Haskell has parametric polymorphism but no subtyping (well … it's complicated) and C♯ before version 2 and Java before version 5 had no parametric polymorphism (again … it's complicated since arrays are actually polymorphic in their element type), therefore neither Haskell nor pre-generics C♯ and Java have a notion of variance. (Again, arrays are actually covariant in both Java and C♯, even pre-generics.)

There are two questions you might ask yourself now:

1. Why is this useful?
2. Which one is the right one?

This is useful for the same reason subtyping is useful. In fact, this is just subtyping. So, if you have a language which has both subtyping and parametric polymorphism, then it is important to know whether one type is a subtype of another type, and variance tells you whether or not a constructed type is a subtype of another constructed type of the same type constructor based on the subtyping relationship between the type arguments.

Which one is the right one is trickier, but thankfully, we have a powerful tool for analyzing when a subtype is a subtype of another type: Barbara Liskov's Substitution Principle tells us that a type S is a subtype of type T IFF any instance of T can be replaced with an instance of S without changing the observable desirable properties of the program.

Let's take a simple generic type, a function. A function has two type parameters, one for the input, and one for the output. (We are keeping it simple here.) F<A, B> is a function that takes in an argument of type A and returns a result of type B.

And now we play through a couple of scenarios. I have some operation O that wants to work with a function from Fruits to Mammals (yeah, I know, exciting original examples!) The LSP says that I should also be able to pass in a subtype of that function, and everything should still work. Let's say, F were covariant in A. Then I should be able to pass in a function from Apples to Mammals as well. But what happens when O passes an Orange to F? That should be allowed! O was able to pass an Orange to F<Fruit, Mammal> because Orange is a subtype of Fruit. But, a function from Apples doesn't know how to deal with Oranges, so it blows up. The LSP says it should work though, which means that the only conclusion we can draw is that our assumption is wrong: F<Apple, Mammal> is not a subtype of F<Fruit, Mammal>, in other words, F is not covariant in A.

What if it were contravariant? What if we pass an F<Food, Mammal> into O? Well, O again tries to pass an Orange and it works: Orange is a Food, so F<Food, Mammal> knows how to deal with Oranges. We can now conclude that functions are contravariant in their inputs, i.e. you can pass a function that takes a more general type as its input as a replacement for a function that takes a more restricted type and everything will work out fine.

Now let's look at the output of F. What would happen if F were contravariant in B just like it is in A? We pass an F<Fruit, Animal> to O. According to the LSP, if we are right and functions are contravariant in their output, nothing bad should happen. Unfortunately, O calls the GetMilk method on the result of F, but F just returned it a Chicken. Oops. Ergo, functions can't be contravariant in their outputs.

OTOH, what happens if we pass an F<Fruit, Cow>? Everything still works! O calls getMilk on the returned cow, and it indeed gives milk. So, it looks like functions are covariant in their outputs.

And that is a general rule that applies to variance:

• It is safe (in the sense of the LSP) to make I<A> covariant in A IFF A is used only as an output.
• It is safe (in the sense of the LSP) to make I<A> contravariant in A IFF A is used only as an input.
• If A can be used either as an input or as an output, then I<A> must be invariant in A, otherwise the result is not safe.

In fact, that's why C♯'s designers chose to re-use the already existing keywords in and out for variance annotations and Kotlin uses those same keywords.

So, for example, immutable collections can generally be covariant in their element type, since they don't allow you to put something into the collection (you can only construct a new collection with a potentially different type) but only to get elements out. So, if I want to get a list of numbers, and someone hands me a list of integers, I am fine.

On the other hand, think of an output stream (such as a Logger), where you can only put stuff in but not get it out. For this, it is safe to be contravariant. I.e. if I expect to be able to print strings, and someone hands me a printer that can print any object, then it can also print strings, and I am fine. Other examples are comparison functions (you only put generics in, the output is fixed to be a boolean or an enum or an integer or whatever design your particular language chooses). Or predicates, they only have generic inputs, the output is always fixed to be a boolean.

But, for example, mutable collections, where you can both put stuff in and get stuff out, are only type-safe when they are invariant. There are a great many tutorials explaining in detail how to break Java's or C♯'s type-safety using their covariant mutable arrays, for example.

Note, however that it is not always obvious whether a type is an input or an output once you get to more complex types. For example, when your type parameter is used as the upper or lower bound of an abstract type member, or when you have a method which takes a function that returns a function whose argument type is your type parameter.

Answer 3

You have two good answers already; let me provide a more succinct third. Let's start by re-stating the question:

how does limiting a type to an output (or input) position achieve preservation (or reversal) of the assignment compatibility relation?

The key insight is to think about a simple function. Let's suppose every mammal has a friend who is also a mammal.

static Dictionary<Mammal, Mammal> friends = whatever;
static Mammal F (Mammal input) => friends[input];

The question is: how can we legally change (vary!) the type signature of F without changing the body or the declaration of friends? (Ignoring any existing callers of F; we're only concerned with the body of F staying legal.)

static Mammal F (Animal input) => friends[input];  
// WRONG, we could pass a Turtle
static Mammal F (Giraffe input) => friends[input];  
// RIGHT, this is fine
static Animal F (Mammal input) => friends[input];  
// RIGHT, this is fine
static Giraffe F (Mammal input) => friends[input];  
// WRONG, it might return a Tiger

The conclusion is that a Func<Mammal, Mammal> such as F could always be used in a context where, say, a Func<Giraffe, Animal> is required but not in a context where Func<Animal, Giraffe> is required.

That's why there is a connection between covariance and outputs, and contravariance and inputs. It follows from the basic facts about how function bodies work. Making an output type declaration bigger or an input type declaration smaller preserves the correctness of the body.