Covariance and Contravariance in Generic Programming
This article explains covariance and contravariance in generic programming, with the help of Liskov substitution principle.
1. Generic programming
Generic programming is a style of computer programming in which algorithms are written in terms of types to-be-specified-later that are then instantiated when needed for specific types provided as parameters.
Wikipedia
Generics enable types (classes and interfaces) to be parameters when defining classes, interfaces and methods.
For example, in Scala, the scala.collection.immutable.List class is defined as abstract class List[+A] ….
Here, List is a generic class and A is the type parameter.
In other words, List is a complex type and A is its component type.
Type parameters provide a way to re-use the same code with different inputs.
For example, List[String] behaves like a list of strings.
List[Int] behaves like a list of integers.
However, the code of List class is same for List[String] and List[Int].
val strings: List[String] = List("One", "Two", "Three")
val integers: List[Int] = List(1, 2, 3)
val string: String = strings.head (1)
val integer: Int = integers.head (2)| 1 | strings.head is of type String. |
| 2 | integers.head is of type Int. |
The compiler applies strong type checking to generic code and issues errors if the code violates type safety.
A List[String] cannot contain an integer.
A List[Int] cannot contain a string.
The compiler throws error for the following code:
val strings: List[String] = List("One", "Two", "Three")
val integers: List[Int] = List(1, 2, 3)
val integer: Int = strings.head //compilation error
val string: String = integers.head //compilation error2. Liskov substitution principle
Let Φ(x) be a property provable about objects x of type T. Then Φ(y) should be true for objects y of type S where S is a subtype of T.
Wikipedia
In other words, if S is a subtype of T, then an object x of type T may be substituted with
any object y of the subtype S without altering the semantics of the program.
Consider the following program:
abstract class Polygon(numberOfEdges: Int) {
def printNumberOfEdges() = println(numberOfEdges)
}
class Quadrilateral extends Polygon(numberOfEdges = 4)
new Quadrilateral().printNumberOfEdges() (1)| 1 | Prints 4 |
A rectangle has the all the properties of a quadrilateral.
That is, a rectangle also has 4 edges.
Therefore, the semantics of program above won’t change if quadrilateral is substituted with a rectangle.
Therefore, by Liskov substitution principle, a Rectangle is a subtype of a Quadrilateral.
class Rectangle extends Quadrilateral
new Rectangle().printNumberOfEdges() (1)| 1 | Prints 4. The semantics of the program did not change when new Quadrilateral() was substituted with new Rectangle(); because Rectangle is a subtype of Quadrilateral. |
3. Variance
Variance refers to how subtyping between more complex types relates to subtyping between their components.
Wikipedia
For example, if Rectangle is a subtype of Quadrilateral, then variance determines whether a Factory[Rectangle] is a subtype of Factory[Quadrilateral] or not.
Here, Factory is the complex type, and, Rectangle and Quadrilateral are the component types.
3.1. Covariance
Consider the following program:
abstract class Factory[T] {
def create(): T
}
def createPolygons(factory: Factory[Polygon]): Unit = {
val p: Polygon = factory.create()
...
}
val rectangleFactory: Factory[Rectangle] = () => new Rectangle
createPolygons(rectangleFactory)Our intuitions tells us that this program should compile successfully.
createPolygons function creates polygon(s) using Factory[Polygon].
rectangleFactory which is of type Factory[Rectangle] creates a Rectangle.
Every Rectangle is a Polygon because Rectangle is a subtype of Polygon.
Therefore, we expect the semantics of the program to not change if Factory[Polygon] is substituted with Factory[Rectangle].
In other words, by Liskov substitution principle, we expect Factory[Rectangle] to be a subtype of Factory[Polygon].
So, we expect the program to compile successfully.
But, contrary to intuition, the Scala compiler throws following error for statement createPolygons(rectangleFactory):
Error:(46, 83) type mismatch;
found : A$A9.this.Factory[A$A9.this.Rectangle]
required: A$A9.this.Factory[A$A9.this.Polygon]
Note: A$A9.this.Rectangle <: A$A9.this.Polygon, but class Factory is invariant in type T. (1)
You may wish to define T as +T instead. (SLS 4.5)
def get$$instance$$res2 = /* ###worksheet### generated $$end$$ */ createPolygons(rectangleFactory)
^| 1 | Notice that the Scala compiler complains that the class Factory is invariant in type T. |
The Scala compiler does not consider Factory[Rectangle] to be a subtype of Factory[Polygon], and hence the error.
A class C is said to be covariant on type T, if C[A] is a subtype of C[B] when A is a subtype of B.
Rectangle is a subtype of Polygon.
We need Factory[Rectangle] to be a subtype of Factory[Polygon].
In other words, we need class Factory to be covariant on type T.
But the Scala compiler considers Factory to be invariant on type T, because the class is defined as Factory[T].
To make it covariant, we need to change the class definition to be Factory[+T]. Notice the plus (+) sign before T.
Once Factory becomes covariant on type T, Factory[Rectangle] becomes a subtype of Factory[Polygon] because
Rectangle is a subtype of Polygon. Hence, the following program compiles successfully:
abstract class Factory[+T] { (1)
def create(): T
}
def createPolygons(factory: Factory[Polygon]): Unit = {
val p: Polygon = factory.create()
}
val rectangleFactory: Factory[Rectangle] = () => new Rectangle
createPolygons(rectangleFactory)| 1 | Notice the + before T which makes Factory covariant on type T. |
3.2. Contravariance
Consider the following program:
class Rectangle(length: Int, width: Int) {
def area(): Int = length * width
}
class Square(side: Int) extends Rectangle(side, side) { (1)
override def area(): Int = side * side
}
abstract class AreaCalculator[T] {
def apply(t: T): Int
}
def printArea(square: Square, areaCalculator: AreaCalculator[Square]) = println(areaCalculator.apply(square)) (2)
val rectangleAreaCalculator: AreaCalculator[Rectangle] = (rectangle) => rectangle.area()
val squareAreaCalculator: AreaCalculator[Square] = (square) => square.area()
printArea(new Square(3), squareAreaCalculator) (3)
printArea(new Square(3), rectangleAreaCalculator) (4)| 1 | Square is a subtype of Rectangle. |
| 2 | printArea function uses AreaCalculator[Square] to get area of the square. |
| 3 | printArea function is passed a function of type AreaCalculator[Square]. |
| 4 | printArea function is passed a function of type AreaCalculator[Rectangle]. |
AreaCalculator[Square] calculates area of a Square.
AreaCalculator[Rectangle] calculates area of a Rectangle.
Every Square is a Rectangle because Square is a subtype of Rectangle.
Therefore, AreaCalculator[Rectangle] should also be able to calculate area of a Square.
Therefore, we expect the semantics of the program to not change if AreaCalculator[Square] is substituted with AreaCalculator[Rectangle].
In other words, by Liskov substitution principle, we expect AreaCalculator[Rectangle] to be a subtype of AreaCalculator[Square].
Therefore, we expect the program to compile successfully.
But, contrary to intuition, the Scala compiler throws following error for statement printArea(new Square(3), rectangleAreaCalculator):
Error:(64, 29) type mismatch;
found : AreaCalculator[Rectangle]
required: AreaCalculator[Square]
Note: Rectangle >: Square, but class AreaCalculator is invariant in type T. (1)
You may wish to define T as -T instead. (SLS 4.5)
printArea(new Square(3), rectangleAreaCalculator)
^| 1 | Notice that the Scala compiler complains that the class AreaCalculator is invariant in type T. |
The Scala compiler does not consider AreaCalculator[Rectangle] to be a subtype of AreaCalculator[Square], and hence the error.
A class C is said to be contravariant on type T, if C[B] is a subtype of C[A] when A is a subtype of B.
Square is a subtype of Rectangle.
We need AreaCalculator[Rectangle] to be a subtype of AreaCalculator[Square].
In other words, we need class AreaCalculator to be contravariant on type T.
But the Scala compiler considers AreaCalculator to be invariant on type T, because the class is defined as AreaCalculator[T].
To make it contravariant, we need to change the class definition to be AreaCalculator[-T]. Notice the minus (-) sign before T.
Once AreaCalculator becomes contravariant on type T, AreaCalculator[Rectangle] becomes a subtype of AreaCalculator[Square], because
Square is a subtype of Rectangle. Hence, the following program compiles successfully:
class Rectangle(length: Int, width: Int) {
def area(): Int = length * width
}
class Square(side: Int) extends Rectangle(side, side) {
override def area(): Int = side * side
}
abstract class AreaCalculator[-T] { (1)
def apply(t: T): Int
}
def printArea(square: Square, areaCalculator: AreaCalculator[Square]) = println(areaCalculator.apply(square))
val rectangleAreaCalculator: AreaCalculator[Rectangle] = (rectangle) => rectangle.area()
val squareAreaCalculator: AreaCalculator[Square] = (square) => square.area()
printArea(new Square(3), squareAreaCalculator)
printArea(new Square(3), rectangleAreaCalculator)| 1 | Notice the - before T which makes AreaCalculator contravariant on type T. |
4. Variance in Java programming language
The sample code in this article so far was written using Scala programming language. In those examples, variance is expressed at the declaration-site. That is, variance is expressed in class definition, where the type parameter is declared.
abstract class Factory[+T] {
^
//declaration-site variance
...
}The concepts of covariance and contravariance apply to other programming languages, such as Java, also.
Java, as of JDK 11, has use-site variance. That is, variance is expressed at the place where the generic type is used.
abstract class Factory<T> {
...
}
static void createPolygons(Factory<? extends Polygon> factory) {
^
//use-site variance
...
}| There is a JDK enhancement proposal - JEP 300 - to augment use-site variance in Java with declaration-site defaults. |
In Java covariance is expressed using extends keyword; example: Factory<? extends Polygon>.
Contravariance is expressed using super keyword; for example, AreaCalculator<? super Square>.
class Polygon {}
class Rectangle extends Polygon {}
interface Factory<T> { (1)
T create();
}
public class Main {
static void createPolygons(Factory<? extends Polygon> factory) { (2)
Polygon p = factory.create();
}
public static void main(String[] args) {
Factory<Rectangle> rectangleFactory = () -> new Rectangle();
createPolygons(rectangleFactory);
}
}| 1 | Notice that variance is not defined at declaration-site. |
| 2 | Notice that covariance is defined at use-site. |
class Rectangle {
private final int length;
private final int width;
Rectangle(int length, int width) {
this.length = length;
this.width = width;
}
int area() {
return length * width;
}
}
class Square extends Rectangle {
Square(int side) {
super(side, side);
}
}
interface AreaCalculator<T> { (1)
int apply(T t);
}
public class Main {
static void printArea(Square square, AreaCalculator<? super Square> areaCalculator) { (2)
System.out.println(areaCalculator.apply(square));
}
public static void main(String[] args) {
AreaCalculator<Rectangle> rectangleAreaCalculator = (Rectangle rectangle) -> rectangle.area();
printArea(new Square(3), rectangleAreaCalculator);
}
}| 1 | Notice that variance is not defined at declaration-site. |
| 2 | Notice that contravariance is defined at use-site. |
5. Summary
We learnt,
-
generic programming.
-
Liskov substitution principle.
-
covariance and contravariance with the help of Liskov substitution principle.
-
difference between declaration-site variance and use-site variance.
6. Further learning
This article does not explain invariance and bivariance. Read the Wikipedia article [3] to understand invariance and bivariance.