Subtyping and Variance


  • Subtyping is a kind of polymorphism that lets us define hierarchical relations on types, with specific types being subtypes of more generic types
  • Example: nat <: int <: num
  • Functions that accept int should accept nat too. This is known as Liskov substitution principle:

Let \(\phi(x)\) be a property provable about objects x of type T. Then \(\phi(y)\) should be true for objects y of type S where S is a subtype of T.

  • To indicate S is a subtype of T, we write S <: T
  • <: can be thought of “is less general”
  • <: is transitive and reflexive

Kinds of variance

Given types S and T with the relation S <: T, variance describes the relation between composite types:

  • Covariant: means the ordering is preserved: Composite<S> <: Composite<T>
  • Contravariant: means the ordering is reversed: Composite<T> <: Composite<S>
  • Invariant: means neither covariant nor contravariant

Covariant arrays in Java

Early on in the design of Java, before it had generics, it was decided that array types should be covariant. If sort accepted an Object[], you wouldn’t be able to pass in a String[] without covariant arrays!

  • In Java arrays are covariant
  • Since String <: Object, we have String[] <: Object[]
String strings[] = { "Apple", "Banana" };
// this type-checks!
Object objects[] = strings;

// works fine
objects[1] = "Watermelon";

// will throw a runtime exception!
objects[0] = 5;
  • From this point on objects is an array of Objects as far as the compiler is concerned
  • Assigning an integer fails because at runtime it is known that objects is an array of strings (arrays are homegeneous, they can only store elements of one type)
  • Covariance together with mutability makes array types, or any composite type, unsound!

Contravariance for function types

  • Let’s take a function: f : int -> int. Which function types are valid subtypes of f?
func user(f : int -> int) {
  x: int = f(...);

Function return types

  • Can we call user providing it a function of type int -> nat?
  • Yes, because nat <: int, so nat is also an int. In this case covariance for function return types works!
  • A function int -> num does not work, because the function could return 1.5 which is a num but not an int!
  • That is why function return types are not contravariant!

Function parameters

  • Can we pass in a function of type nat -> int?
  • No because user expects to be able to pass in any int to f and not just positive numbers
  • So function parameters are not covariant
  • What about num -> int?
  • This works because that function can take any int which use might pass to it

be liberal in what you accept and conservative in what you produce!