Covariant and Contravariant

Covariant and Contravariant were always one of those complicated concepts that I was running away from! But one day I decided to learn it, and finally, free my soul! Here I describe it in an easy way and hope to help other people to free their soul too!

From wikipedia, the complicated definition (the reason for my fear to learn!) is this:

Within the type system of a programming language, a typing rule or a type constructor is:

  • covariant if it preserves the ordering of types (≤), which orders types from more specific to more generic;
  • contravariant if it reverses this ordering;
  • bivariant if both of these apply (i.e., both I<A> ≤ I<B> and I<B> ≤ I<A> at the same time);
  • invariant or nonvariant if neither of these applies.

But don’t worry, that was the complicated one, this blog is going to make it easy.

The Easy Story

Consider these classes and their inheritance:

This is good, as we explicitly said,  Cat is subtype of  Animal. Now consider some generic classes.

Once you declare a generic class, you are announcing lots of types, so you have these types available:

  • Trainer<Animal> ,  Trainer<Cat> ,  Trainer<Lion> .
  • PetStore<Animal> ,  PetStore<Cat> ,  PetStore<Lion> .

In this case, we have one class, and plenty of types. As these types are not explicitly declared, so their inheritance relationship is not declared explicitly and it should be inferred by the compiler. So the question is this:

Is  PetStore<Cat> a subtype of  PetStore<Animal> ?

Or a simpler question: Is this type casting valid?

This means that we are sure that  animalStore.Buy() returns an Animal. Are we!? We know animalStore internally stores an object of type  PetStore<Cat> with a Buy method like:  Cat Buy() . As Buy returns Cat and Cat is a valid Animal, the whole story makes sense.

Although it seems valid, but most of languages like Java and C# can not infer this fact. Why!? Is the compiler that stupid!? Isn’t it obvious that  PetStore<Cat> should be a subtype of  PetStore<Animal> ? No it’s not obvious! The following sample shows that this rule is not valid always.

Let’s check the other class: Trainer. Again the same question:

Is  Trainer<Cat> a subtype of  Trainer<Animal> ?

Or a simpler question: Is this type casting valid?

What’s really in animalTrainer variable is a  Trainer<Cat> . And what’s really behind animal is a  Lion . So basically, we are giving a lion to a cat trainer!!! Does is seem valid!? Of course not.

But what happened? Why  Trainer<Cat> is not a subtype of  Trainer<Animal> although Cat is still a subtype of Animal.

This basic difference is the reason that compilers can not infer the sub typing of generic classes by default.

In fact, in this case the sub typing is inverse:

What’s really in lionTrainer variable is a  Trainer<Animal> , and what’s really behind animal is a  Lion. So basically, we are giving a lion to a animal trainer. It seems valid. Having someone expert in training animals, and a lion which is an animal too, everything works fine.

A good summary of this concept is this diagram which is available here in Wikipedia:

Variance and Covariance

Implementation in Languages

So as you see, the Trainer characteristic and behavior is different than PetStore. In computer science, they call PetStoreCovariant generic type and TrainerContravariant generic type. As this is a characteristics of the type, this is our responsibility to tell about it to the compiler. There are 2 common approaches to handle this situation in different languages:

  1. Declaration-site variance annotations: like C#, Scala and OCaml
  2. Use-site variance annotations (wildcards): like Java

 

Declaration-site variance annotations

As the Covariant/Contravariant is a characteristic of  the Type, we could specify it when declaring  the type. This is happening by in/out keywords in C# and +/- keywords in Scala and OCaml like:

Use-site variance annotations (wildcards)

In this approach, the situation is handled when the casting is happening, like wildcards in Java:

Comparing declaration-site and use-site annotations

There is a good comparison available here. But briefly it can be summarized as this:

  • As Covariant/Contravariant is one of the type characteristics, the declaration-site is a better approach.
  • The decision about use-site approach in Java is taken because of some backward compatibility reasons.

Also from the reference:

In a conference presentation Joshua Bloch criticized them as being too hard to understand and use, stating that when adding support for closures “we simply cannot afford another wildcards”. Early versions of Scala used use-site variance annotations but programmers found them difficult to use in practice, while declaration-site annotations were found to be very helpful when designing classes. Later versions of Scala added Java-style existential types and wildcards; however, according to Martin Odersky, if there were no need for interoperability with Java then these would probably not have been included.

Wasn’t that easy!? I don’t know why I was so scared to learn such a simple concept in these years!

About the author

Mehran Davoudi

A former technology geek! Currently a mentor and software architect, working as a consultant for companies with large scale software development.
Why dvd? Read about me (uɒɹɥəɯ)!

View all posts

3 Comments

Leave a Reply

Your email address will not be published. Required fields are marked *