The Scala Type System: Parameterized Types and Variances, Part 2

What is the Scala type checker trying to say with the error message that a covariant type occurs in contravariant position? Which rules apply behind the scenes? How can these rules be explained by the known principle of subtype polymorphism? This post addresses this questions, not that the previous post has dealt with introducing type parameters and their variance annotations.

Introduction

Co- and contravariant annotations allow to infer the type hierarchy of a generic type from the hierarchy of its type parameter. Using these annotations restricts the possible uses of type parameters in generic classes; the Scala-Compiler rejects several constellations in generic classes, and produces error messages of the form covariant type T occurs in contravariant position or contravariant type T occurs in covariant position. These error messages are based on rules that apply to the type checking of generic classes. One aspect of these checking rules that is fascinating to me is that they seem to be incomprehensible, and at the same time, they can be motivated by subtype polymorphism.

To understand how the Scala type checker tries to guarantee the type safety of a code base, and how the rules that are applied in the process can be traced back to the familiar concept of subtype polymorphism, I will first discuss what is meant by subtype polymorphism. In the next step, we will see how this concept can be applied to the overriding of methods to allow co- and contravariance modification of method signatures. The insights we get from there will then be applied to better understand how variances of type parameters are checked, and where variance-annotated type parameters can be used. Finally, we will discuss how the rules apply to lower type bounds, and why the combinations that pass type checking are actually type safe.

TL;DR

No time? The results are condensed at the end of this post .

Subtype Polymorphism

Before we get to the rules used by the Scala type checker when dealing with type parameters, I will first step back and outline the principle of subtype polymorphism that are at the foundations of these rules (more comprehensive coverage can be found in this blog , on Wikipedia , and in in this Book ). Consider (again) the following class hierarchy of boxes and fruits.

1abstract class Fruit { def name: String }
2class Orange extends Fruit { def name = "Orange" }
3class Apple extends Fruit { def name = "Apple" }
4 
5abstract class Box {
6 
7  def fruit: Fruit
8 
9  def contains(aFruit: Fruit) = fruit.name.equals(aFruit.name)
10}
11 
12class OrangeBox(orange: Orange) extends Box {
13  def fruit: Orange = orange
14}
15 
16class AppleBox(apple: Apple) extends Box {
17  def fruit: Apple = apple
18}

With this class hierarchy, the Scala compiler allows to assign an object of type AppleBox (or OrangeBox) to a variable of type Box. The reasoning behind this is that due to the inheritance relation, it is guaranteed that the assigned object has all methods and fields that are implemented in Box (such as the method contains), or that are required by Box and implemented in concrete subclasses (such as the method fruit). Along the same reasoning, an Apple or Orange-object can be used as actual parameter wherever a Fruit-object is expected:

1var apple = new Apple
2 
3// An AppleBox can be assigned to a Box-typed variable.
4var box: Box = new AppleBox(apple)
5 
6// 'contains' expects a Fruit-object, an Apple-object is also fine.
7if (box contains apple) {
8  // box.fruit returns an object of type Fruit, this object has a 'name'-method.
9  var fruitName = box.fruit.name
10  println("box contains an $fruitName") 
11}

The concept that it is always allowed to replace an object of a type by an object of a subtype is called subtype polymorphism.

Subtype Polymorphism Applied to Method Overriding

The concept of subtype polymorphism that we have seen on variable assignments and method invocations can be applied to method signatures as well. Consider the following modified AppleBox-class.

1class AppleBox(apple: Apple) extends Box {
2  // subclass Apple instead of Fruit as return type is allowed.
3  def fruit: Apple = apple
4}
5 
6var apple = new Apple
7var box: Box = new AppleBox(apple)
8 
9// box.fruit returns an Apple, i.e. a subclass of Fruit.
10println("box contains an $box.fruit.name")

By having the return type Apple, the AppleBox.fruit-method fulfills the requirements of the Box.fruit-method: Every client that expects a Fruit-object when calling the AppleBox.fruit-method will get an Apple-object. She will therefore get an instance of a subtype, which is okay according to subtype polymorphism. This language feature is called Covariant Return Type , and was introduced to Java in version 5, and exists in Scala as well as in in C++.

By similar reasoning, a type safe language could allow to generalize the type of method parameters when overriding a method. This feature is called Contravariant method argument type , and cannot be currently supported by languages running on JVM. The following sample code is therefore not allowed in Scala, even though it would be type safe (the explanation follows after the code).

1abstract class Box {
2 
3  def fruit: Fruit
4 
5  def contains(apple: Apple) = fruit.name.equals(apple.name)
6}
7 
8class AppleBox(apple: Apple) extends Box {
9 
10  def fruit: Apple = apple
11 
12  // more generic class Fruit instead of Apple: would be type safe, but isn't allowed.
13  override def contains(aFruit: Fruit) = fruit.name.equals(aFruit.name)
14}

Since the method Box.contains expects an object of type Apple, it is not allowed to pass an object of type Fruit on invocation. The concrete implementation of AppleBox.contains can relax this constraint and only require an object of the supertype Fruit: Every client-code having a variable of type Box is bound to pass an instance of the more specific type (Apple). If an object of type AppleBox is assigned to that variable, the method AppleBox.contains will be called on invocation of contains. This method can handle objects of type Apple, since Apple is a subclass of Fruit.

Client-code having a reference to the more specific type AppleBox can additionally invoke the AppleBox.contains-method with objects of type Fruit, e.g. with Orange-objects.

All in all, we can see that the principle of covariance and contravariance already applies on the level of method signatures, and that it is based on the idea of subtype polymorphism. In method overriding, it makes sense to allow the covariant specialization of return types, and the contravariant generalization of method parameter types.

Allowed Variance Annotations

Variance annotations are checked by the Scala compiler, and not all variance annotations are always usable. When checking annotations, the compiler uses the same principle that was describe in the last section: return types may be only invariant or covariant, and method parameter types may be only invariant or contravariant. If these constraints are met, the type checker can guarantee that the polymorphic assignment of type-parameterized classes is indeed type safe. To see that more clearly, consider the following example.

1abstract class Box[+F <: Fruit] {
2 
3  def fruit: F
4 
5  def contains(aFruit: Fruit) = fruit.name.equals(aFruit.name)
6}
7 
8class OrangeBox(orange: Orange) extends Box[Orange] {
9  def fruit = orange
10}
11 
12class AppleBox(apple: Apple) extends Box[Apple] {
13  def fruit = apple
14}
15 
16var fruitBox: Box[Fruit] = new AppleBox(new Apple)
17 
18var fruit: Fruit = fruitBox.fruit

In this example, the type parameter of Box[+F] is covariant. It is therefore valid to assign an object of type Box[Apple] to the Box[Fruit]-type variable fruitBox. This is fine as long as the type variable F is used only in return types of methods, as in the method Box.fruit. On invocation of the fruitBox.fruit-method it is guaranteed that an object of type Fruit or of a more specific type will be returned: Since the type parameter is covariant, it can only be bound to a more specific type than Fruit in the actually referenced object (or to Fruit itself).

Now assume that we had a method replace, that uses F as type of a method parameter:

1abstract class Box[+F <: Fruit] {
2 
3  def fruit: F
4 
5  // F as type of 'replacement' is rejected by the type checker.
6  def replace(replacement: F)
7}
8 
9// would be ok by covariance of F
10var fruitBox: Box[Fruit] = new AppleBox(new Apple)
11 
12// would be ok by subtype polymorphism, since Orange is a subtype of Fruit
13fruitBox.replace(new Orange)

We have a problem here: while an object of type Orange is passed in the invocation of replace, the method AppleBox.replace will only accept Apple-objects. The type checker is therefore right when rejecting the use of F as type of the method parameter replacement.

By covariant annotation, the type that is bound to F can be more specific than Fruit, but we need it to stay the same or be more generic. If we had annotated F to be contravariant, this would have been ensured. The call to fruitBox.replace(new Orange) would have been possible, but the assignment var fruitBox: Box[Fruit] = new AppleBox(new Apple) would have been rejected by the type checker, since Box[Apple] then became a supertype of Box[Fruit], not a subtype.

Depending on the usage of a type parameter in a type-parameterized class, some variance annotations can be allowed or forbidden. In the Box[+F <: Fruit]-class for example, the type parameter F is used as return type of the method Box.fruit; therefore, the type parameter F may only be annotated as invariant or covariant.

The Scala compiler tracks all uses of type parameters when checking a generic class, and determines the allowed variances depending on the position in the code. The error message of the Scala compiler that a type occurs in in a forbidden position means that an occurrence of the type parameters only allows a specific type of variance (e.g. contravariant), but another variance annotation that was used in the class header (e.g. covariant).

The checking rules can be found in the Scala Language Specification , and the summary by Marko Bonaci gives a nice introduction to the logic of this specification. The logic goes roughly as follows: the allowed variance of a type parameter is initially covariance, and flips back and forth between covariance and contravariance by inversion in specific contexts.

For example, the allowed variance flips at

1. method parameters (from covariant to contravariant),
2. type parameter clauses of methods,
3. low bounds of type parameters, and
4. actual type parameters of parameterized classes, if the corresponding formal parameter is contravariant.

The following examples illustrate these four rules:

• In def method(parameter: T), the parameter T is in contravariant position, since rule 1 applies.
• In def method[U <: T](), the parameter T is in contravariant position, since rule 2 applies.
• In def method[U >: T](), the parameter T in in covariant position, since rules 2 and 3 apply.
• Assume that the type parameter of class Box is declared contravariant by class Box[-A]. In this case, T is in covariant position in def method(parameter: Box[T]), since rules 1 and 4 apply.

The four example rules already produce interesting possibilities and constraints. One example is discussed at the beginning of this section. In the next section, we will have a closer look at lower type bounds.

Variance Positions in Lower Type Bounds

Why does it make sense to flip the position from contravariant to covariant in lower bounds of a type parameter clause of a method? Well, a covariant type parameter T in a class Box[+T] may only become more specific by applying subtype polymorphism. This means that the actual type bound to T may only move down in the type hierarchy. If T is now used in a lower type bound of U, this movement only relaxes the type constraint on U. There is no risk of violating a previously successful check of U >: T by applying subtype polymorphism on Box[+T]. Let’s have a look at an example:

1class Box[+T] {
2  def method[U >: T](p: U) = { /* here be code */ }
3} 
4var apple: Apple = new Apple
5var box: Box[Fruit] = new Box[Orange]
6box.method(apple)

The invocation of Box.method remains valid even if box is replaced by an object of a subtype (e.g. Box[Orange]), since T is then only bound to a more specific type. The type parameter U has no upper bound. If the actual type of the method parameter p now differs heavily from T, the compiler is free to use an arbitrarily generic type for U, even going as far up in the type hierarchy as scala.Any. There is no risk to violate type safety here, the only risk is that the actual type of U may become very generic.

Conclusion

We have seen how co- and contravariant type parameters are handled in the type checker. In this, it is fascinating to see that the rules that apply can be explained by applying the principles of subtype polymorphism, even though this explanation needs a detour. This detour consists of considering how subtype polymorphism applies to method overriding. Here, we have seen that it is sensible to allow contravariant generalization of method parameter types, and covariant specialization of return types. The latter was introduced with Java 5. I suspect that this language feature is quite well known now, but rarely used.

We have now seen what variance annotations of type parameters are and how they are handled by the type checker. In the next post , I will cover how type parameters and variance annotations can be used sensibly in Scala.

Condensed Results

These are the condensed results of both post .

Subtype Relationships

Assume that class Orange extends Fruit holds. If class Box[A] is declared, then A can be prefixed with + or -.

• A without annotation is invariant, i.e.:
  • Box[Orange] has no inheritance relationship to Box[Fruit].
• +A is covariant, i.e.:
  • Box[Orange] is a subtype of Box[Fruit].
  • var f: Box[Fruit] = new Box[Orange]() is allowed.
• -A is contravariant, i.e.:
  • Box[Fruit] is a subtype of Box[Orange].
  • var f: Box[Orange] = new Box[Fruit]() is allowed.

Allowed Variance Positions

• Invariant type parameters can be used everywhere:
  • abstract class Box[A] { def foo(a: A): A } is allowed.
  • abstract class Box[A] { var a: A } is allowed.
• Covariant type parameters can be used as return types only:
  • abstract class Box[+A] { def foo(): A } is allowed.
• Contravariant type parameters can be used as types of method parameters only:
  • abstract class Box[-A] { def foo(a: A) } is allowed.
• Workaround to use a covariant type in a method parameter type:
  • abstract class Box[+A] { def foo[B >: A](b: B) } is allowed.
• Workaround to use a contravariant type in a return type:
  • abstract class Box[-A] { def foo[B <: A](): B } is allowed.
• The full rules are more complex than summarized here. The full article discusses them in more details.