[C++][Java] Kinds of variance in subtyping

Reference:
https://eli.thegreenplace.net/2018/covariance-and-contravariance-in-subtyping

I've to say I admire Eli Bendersky a lot. Not only he could make complicated stuff in plain English, but also broadly read.

Covariant is a well known concept among expert C++ engineers, which includes the type system as well as the memory model. (Object memory layout.)
Even in 2018, I would recommand anyone who are into programming languages to give a quick read on Stanley B, Lippman's Inside The C++ Object Model.

Liskov substitution principle

Given types S and T with the relation S <: T, variance is a way to describe the relation between the composite types:

• Covariant means the ordering of component types is preserved: Composite<S> <:Composite<T>.
  C++: works for function return type.
• Contravariant means the ordering is reversed: Composite<T> <: Composite<S>.
  C++: works for function parameter. i.e Argument type should be no deeper then function's parameter's signature type.
• Bivariant means both covariant and contravariant.
• Invariant means neither covariant nor contravariant.

Consider this code:

struct MammalClinic {
  virtual void Accept(Mammal* m);
};

struct CatClinic : public MammalClinic {
  virtual void Accept(Cat* c);
};

The CatClinic::Accept is an overload, not override, and this is exactly the keyword: 'override' is created for: to spot this kind of error.
The reality is that function overrides are not covariant for pointer types.
They are invariant.
In fact, the vast majority of typing rules in C++ are invariant;
std::vector<Cat> is not a subclass of std::vector<Mammal>, even though Cat <: Mammal.
There's a good reason for that.

Let's look into the example from Java:

class Main {
  public static void main(String[] args) {
    String strings[] = {"house", "daisy"};
    Object objects[] = strings; // covariant

    objects[1] = "cauliflower"; // works fine
    objects[0] = 5;             // throws exception at runtime.
  }
}

Assigning an integer fails because at run-time it's known that objects is actually an array of strings.
Thus, covariance together with mutability makes array types unsound.
Note, however, that this is not just a mistake - it's a deliberate historical decision made when Java didn't have generics and polymorphism was still desired; the same problem exists in C#.

Other languages have immutable containers, which can then be made covariant without jeopardizing the soundness of the type system.


Contravariant example in std::function:

#include <functional>

struct Vertebrate {};
struct Mammal : public Vertebrate {};
struct Cat : public Mammal {};

Cat* f1(Vertebrate* v) {
  return nullptr;
}

Vertebrate* f2(Vertebrate* v) {
  return nullptr;
}

Cat* f3(Cat* v) {
  return nullptr;
}

void User(std::function<Mammal*(Mammal*)> f) {
  // do stuff with 'f'
}

int main() {
  User(f1);       // works
  User(f2);       // return type covariance failed, since Vertebrate is base type of Mammal.
  User(f3);       // Argument type contravariance failed, since Cat is deeper then Mammal.

  return 0;
}