4

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?

1
  • 3
    I've copied that post to my new blog; I'll update your link! Dec 5, 2022 at 17:40

3 Answers 3

9

"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...).

2
  • 2
    I can't remember where I heard it, but a great and succinct way of explaining why we need variance and why it only matters in certain contexts is "variance is where subtyping and parametric polymorphism meet". Nov 27, 2022 at 7:20
  • 2
    @JörgWMittag - could be that it came from John Altidor - was able to find a couple places where a similar phrase was used: "Variance is concerned with the interplay of parametric polymorphism (i.e., templates, generics) and subtyping." E.g. his dissertation (pdf), or this conference paper (SpringerLink abstract, pdf) Nov 27, 2022 at 12:17
8

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 <⦂ BI<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 <⦂ BI<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.

5
  • What is the exact meaning of the character <⦂? As for your definition of contravariance, it sounds like you're saying that the more abstract class I<B> is almost like a subtype of the more derived class I<A> when we think of I<A> as a supertype of I<B>? I tried to find a definition for supertype, but I was only able to come up with this definition for top type.
    – Ramza
    Nov 29, 2022 at 14:49
  • @Ramza - A <⦂ B just means A is a subtype of B (or read right-to-left, B is a supertype of A - it's saying the same thing slightly differently), where "subtype" means that you can plug in A wherever B is expected (e.g. B could be a pure interface, or a base type with an existing implementation). But the crucial bit is that we would like some guarantees that doing so doesn't break the application (see the first paragraph here). A compiler might use a compatibility rule it's able to prove; a developer might want A to be LSP-compatible with B. 1/3 Dec 1, 2022 at 1:08
  • "it sounds like [...] the more abstract class I<B> is almost like a subtype of the more derived class I<A>" - that's the whole point: B being more abstract than A on its own doesn't guarantee that there's the same relationship between I<B> and I<A> - these are two types in their own right, constructed in part from B and A respectively; depending on what I<T> is doing (or rather, what its contract is with the clients), I<A> and I<B> might, in general, not be related as a subtype-supertype pair at all (either way). It's not something academic, it actually affects your program 2/3 Dec 1, 2022 at 1:09
  • I know it's counter-intuitive, but the concept of an Animal is more abstract than Bear because it's a restriction to the essential characteristics shared by all animals (if it can do these couple of things, it's an animal, if it can do these additional things, it's a bear). In the idealized world of programming, a subtype in this sense cannot constrain or loosen the supertype characteristics in an incompatible way. IPushable<Bear> adds a restriction to IPushable<Animal>, but IPushable<Animal> does all that IPushable<Bear> does, and more. 3/3 Dec 1, 2022 at 1:15
  • @Ramza: I find it helpful when explaining this to treat the relation that Jörg here (correctly) calls "subtyping" as the more specific relation "assignment compatibility of reference types", because that is possibly more clear to the reader who doesn't have a background in type theory. That is, A <% B can mean "A and B are reference types such that an expression of type A can be assigned to a variable of type B". Dec 6, 2022 at 19:37
5

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.

3
  • From what I can see, function F demonstrates both covariance and contravariance simultaneously. If we limit its output type to a smaller (more derived) type, then we preserve assignment compatibility. This is because any member expecting to receive a base type will be OK if it receives one of its derived types. In contrast, if we limit F's input type to a larger (less derived) type, function F will be ok receiving the base type or any of its derived types as input. (1/2)
    – Ramza
    Dec 7, 2022 at 1:43
  • Your example makes me think that the concept is almost circular, because F continually receives input of any specified base type (or its children) and can continually generate output of any specified derived type (or any of its children). (2/2)
    – Ramza
    Dec 7, 2022 at 1:44
  • @Ramza: That's correct. Functions are "covariant" in their output types and "contravariant" in their input types. Which is why we chose "in" and "out" as the annotations. Dec 7, 2022 at 22:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.