Mindful Coding — Covariance and Contravariance

As a Software Engineer, we should strive to understand the fundamental of the things that don’t work, and more importantly, be conscious about the things that work. That requires us to practice mindfulness when writing code. There is this fear of pursuing more because it makes us conscious of our ignorance, further aggravate the Impostor Syndrome. And the antidote to that is simply to pursue it.

This series is about discovering concepts through things that we’ve already known, dig deeper into the abyss to find things that we don’t know, and attempt to confront them.

Today, we’re exploring the basic of variance in Java. Variance is something that we work with almost on a daily basis, especially when dealing with generics. It requires no conscious effort because it works most of the time. Except when it doesn’t — we looked for a quick fix because the fundamentals are hard.

Photo by DAVIDCOHEN on Unsplash

Adding a Number to an Array

Let’s begin with a very simple task.

This code will compile successfully. However, when you run the program, you will get a runtime exception.

true
Error: java.lang.ArrayStoreException: java.lang.Double

“Seems like a no-brainer, you can’t put a Double into an Integer array, what’s there to talk about? Let’s just fix™️ that”

Well, let’s explore further and see where could this innocent looking code lead us. Try to observe the lines of code and its corresponding output.

Observations

1. We can assign an Integer[] to a Number[], just like you can do Number number = new Integer(1). Seems likeInteger[] is a subtype of Number[]?
2. At runtime, the compiler knows that numArray is an Integer[].
3. We can add a Double to numArray with no compilation error, but at runtime, you get ArrayStoreException.

Explanations

1. Array is covariant. Integer[] is indeed a subtype of Number[].
2. Array is a Reifiable Type. After compilation, numArray is reified to Integer[].
3. At compile-time, numArray is just a Number[], that's why we can add a Double into it. However, at runtime, since numArray is reified to Integer[], it can only store Integer or its subtype.

numArray is like a double agent, it acts as a Number[] at compile time, but as an Integer[] at runtime, fooling you into give it more that you should.

This is because Java Arrays are flawed, even Joshua Bloch admitted it, but this is another blog post in itself. The important lesson here is that arrays are covariant.

Arrays are Covariant

🐻 with the formal definition, it is actually a very simple concept!

If X is a subtype of Y, then f(X) is a subtype of f(Y).

A covariant function/type preserves the subtyping relation between x and y.

Concretely, because Integer is a subtype of Number, Arrays preserve this subtyping relation, that’s whyInteger[] is a subtype of Number[].

Btw

Since we are talking about Covariance, let’s also take a look at Contravariance, it will become useful later. Basically, Contravariance is the opposite of Covariance.

If X is a subtype of Y, then f(Y) is a subtype of f(X)

A contravariant function/type reverses the subtyping relation between x and y.

Arrays are not contravariant, so Number[] is not subtype of Integer[].

Pretty simple right?

pReTtY sImPLe RIght

Since Arrays allow unsafe operations, as demonstrated above. Let’s see how generic Lists overcomes this with invariance.

Generics are Invariant

A generic type, such as Lists, is invariant by nature.

Invariance disregard the subtyping relation, it is neither covariant or contravariant.

Concretely, List<Number> must be exactly a List<Number>. A List<Integer> is not a subtype of List<Number>, vice versa.

**The remaining of this post uses List and Number as concrete example, but the concept applies to all generics and types

The implication with List Invariance is that it is impossible to add a subtype/supertype of Number to a List. This solves the ArrayStoreException issue that we’ve encountered with Arrays.

When doing stupid things like adding incompatible types, with Arrays, you don’t get exception until runtime; with Lists, you get compilation error immediately, which is good.

This is cool, but an invariant List is quite limited. Imagine a function that takes a list of Integer and print its element, what if we want the function to also work with a list of Double/Float/BigDecimal, in general, a list of any subtypes of Number? Can we make a List covariant just like an Array?

Make Generics Flexible

It turns out that we can use bounded wildcard to allow subtyping flexibility when writing generic code. extends can be used to make a List covariant. I like to think of List<? extends Numbers> as a universe consists of all the lists of Number’s subtypes, i.e. List<Integer>, List<Double>, etc, are subtype of List<? extends Number>.

On the contrary, super can be used to make a List contravariant. I like to think of List<? super Numbers> as a universe consists of all the lists of Number's supertypes, i.e. List<Number> and List<Object> are both subtype of List<? super Number>.

Here is a code example to go with the egg diagram.

Like all things in life, the extra flexibility comes with a cost. Depending on whether a list is covariant or contravariant, there are restrictions on the kind of things you can do to the list. These rules exist to enforce generics type safety.

Covariant List

Extends, Upper-bound, Read-only, Covariance, Producer, Source.

You often see these terms used in the same context, but they are really just different terms referring to the same concept. The extends bound creates a covariant and read-only list, or a Producer of elements.

Let’s write a function that takes a list of Number, and print the elements. It uses extends to take advantages of covariance (can accept any subtypes of Number), but pays the price of the list being read-only.

1. You are allowed to get Number out of the list, because everything that extends Number must be a Number.
2. You are not allowed to add anything to the list, because it could be a list of Integer, Double, etc. It is unsafe to make any assumption about the list. You don’t want to add a BigDecimal into a List of Float.

Contravariant List

Super, Lower-bound, Write-only, Contravariance, Consumer, Sink.

The super bound creates a contravariant and write-only list, or a Consumer of elements.

Let’s write a function that adds any Number into a list. It uses super to take advantages of contravariance (can add any subtypes of Number), but pays the price of the list being write-only.

Hold up.

Why does a list needs to be contravariant in order for us to write something into it? We know that we can’t add anything to a List<? extends Number> because doing so may violate type safety. Then what is the criteria for us to write any Number to a list? Well, the list has to be general enough to accept any type of Number, obviously, only a list of Number and its supertype Object is capable of doing that, which is exactly what List<? super Number> is!

1. You are allowed to add any subtypes of Number into the list, because everything that is a supertype of Number, will be able to accept a Number.
2. You are not allowed to get Number out of the list, because it could be a List<Object>.

Read + Write

What if we want the function to be able to read and write to a list?

Fall Back to Invariant List

Invariance is the strictest form of variance, so an invariant list (without extends and super) will be able to support both read and write operation, because the list is guaranteed to hold only the declared type parameter, e.g. List<Integer> is guaranteed to hold only Integer, you can freely read and write Integer to it.

Covariant Source and Contravariant Destination

The function could accept a read-only source and a write-only destination. Take a look at this simplified extract from Java Collections’ copy method.

Bonus — P.E.C.S

Producer Extends, Consumer Super. Mnemonics are cool, it makes thing sounds important.

PECS is a rule of thumb for applying bounded wildcard to generic Collections. As we’ve seen above, if you need a read-only list (producer), use extends. If you need a write-only list (consumer), use super.

Follow me @ https://twitter.com/darrenbkl