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

With the help of co- and contravariance annotations in Scala you can derive relationships between parameterized classes from their type parameters . The compiler checks with specific rules how the type parameters are used in a generic class. In this, he checks if all uses of type parameters are legal, i.e. if the generic class is type safe.

Generic classes and co-/contravariant annotations are powerful tools that can be used on plentiful occasions when designing a class and while coding. However, where does it really makes sense to use these tools? This blog post presents my insights and my current opinion on this topic.

TL;DR

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

Applying Type Parameters and Variances Sensibly

In my programming career I have so far seen two sensible use cases for type parameters and variances: the first are frameworks such as Collections Frameworks and Concurrency Frameworks , and the second are type-parameterized methods. In all other cases where type parameters have been used (by myself included), I experienced them as adding unnecessary complexity and therefore reducing code comprehensibility without adding significant benefits. In two Java frameworks that I developed myself, I had programmed myself into a corner with Java Generics. I finally removed all type parameters from the code I wrote, and replaced them with instanceof-checks and casts. Meanwhile, I am fairly skeptical towards domain-specific code that makes heavy use of generic types.

Collection Frameworks

The archetype –use case for co- and contravariant type parameters are collections such as lists, sets, and maps. These use cases are often motivated by the fact that arrays are covariant in Java. This covariance is unsafe, due to the mutability of arrays through array assignments, as the following example demonstrates:

1String[] strings = new String[1];
2Object[] objects = strings;
3objects[0] = 1;
4strings[0].indexOf(" ");

By covariance of arrays, a String array is also an Object array, and the assignment in line 2 is valid. It is valid to add an arbitrary object to an Object array, so it is possible to add an Integer as well. The code is therefore rightfully accepted by the Java compiler. The array access in line 4 expects a String to be returned, and gets an Integer. Luckily, line 4 will never get executed, since the implementation of Array will throw an ArrayStoreException when trying to assign an Integer to the String array in line 3 (As a side note: this behavior follows the fail-fast principle , and significantly simplifies tracking down such issues in huge code bases).

The conclusion of this is meanwhile that mutable collections should be invariant; to avoid the above-mentioned problem, String Array should not be a subtype of Object Array. Immutable collections do not suffer from the same issue, and can be implemented to be covariant without risking type safety. An immutable list can be then created via copy-on-write, or as a linked list that is extended by prepending new elements. A Box-implementation as linked list may e.g. look as follows.

1abstract class Box[+A] {
2  def isEmpty: Boolean
3 
4  def contains[B] (item: B): Boolean
5  def prepend[B >: A](item: B): BoxItem[B] = new BoxItem[B](item, this)
6}
7 
8case class BoxItem[+A](item: A, next: Box[A]) extends Box[A] {
9  def isEmpty = false
10 
11  def contains[B] (item: B) = this.item == item || next.contains(item) 
12}
13 
14case class EmptyBox[+A]() extends Box[A] {
15  def isEmpty = true
16 
17  def contains[B] (item: B) = false
18}

The interesting part in this code is the Box.prepend-method: it is invalid to use the type parameter A as type of the method parameter item in Box.prepend, since this is a contravariant position. It is nevertheless allowed to use A as lower bound for the new and invariant type parameter B. With this workaround, the type parameter A can have a covariant annotation, and the following code is valid:

1var apple = new Apple
2var orange = new Orange
3var apples = new BoxItem(apple, new EmptyBox)
4var fruits: Box[Fruit] = apples.prepend(orange)
5 
6if(fruits.contains(apple))
7  println("box contains the apple")

This example also show that the compiler is able to infer the type of the sub-expression orange in apples.prepend(orange) as the smallest type that is a supertype of Apple and Orange. That is to say, in the call of the prepend-method, the type parameter B is not bound to Orange, bu to Fruit. The method invocation therefore returns an object of type BoxItem[Fruit], that is in turn a subtype of Box[Fruit].

All in all, type parameters and co-/contravariant annotations are powerful tools that are useful in the implementation of collection frameworks. It also helps clients of these frameworks to achieve type safety, and to better document their intent: a list can be declared to be a list of Fruit, instead of as a list of arbitrary objects.

Type-Parameterized Methods

Typ-parameterized methods are mainly found in code libraries, but can be also used in domain-specific code to document and enforce relationships between the types of parameters. For a sorting method that requires a sort ordering and a collection, this could look like this.

1trait Ordering[T] {
2  def compare(x: T, y: T): Int
3}
4 
5abstract class Boxes {
6  def sort[A, B >: A](box: Box[A], order: Ordering[B])
7}

In this example, we document and enforce with type parameters that the ordering order must be defined for a supertype B of type A. In several cases however, the question quickly arises whether the method should be moved to one of its parameters instead. For the sort example it would be an obvious solution to move the method to the class Box. Another question that arises is whether the method has too many parameters that should be combined into one object. In the case that none of the above applies, using type-parameterized methods remains a sensible solution for this use case.

Introducing Variances

After having decided to introduce generic classes and type parameters, the question remains whether variance annotations should be used as well. To answer this question, two impacts of variances needs to be considered.

The first impact of introducing variances is that it constrains the development of a class. Contravariant type parameters e.g. cannot be used as return types of methods. If a class is still in the early stage of development, or if the problem domain is not yet well understood, it can be expected that the class will experience heavy refactorings and modifications. In this context, constraints introduced by variance may become impeding. Once the interface of a class has stabilized, it is possible to check in a second pass whether variance annotations can be added to the type parameters of a class.

The second impact to consider when introducing variances is that client code of the generic class gains the possibility to transfer the type hierarchy of inserted types to the generic class. Instances of specific generic types can be assigned to variables of a more generic types by following the principle of subtype polymorphism. This means that removing variance annotations reduces the possible assignments in client code, and therefore is an incompatible change. Conversely, introducing variance annotations extends the possibilities of client code. Introducing variance annotations is a compatible change that does not break the type safety of existing clients. In total, this means that it can be easier to add variances to a generic class on demand than to introduce it from start and to take the risk of having to remove variances later down the road.

The Issue With Names

Phil Karlton once noted that giving names is one of the only two hard things in computer science . Naming type parameters is additionally exacerbated by naming conventions, since style guides often recommend to use a single uppercase letter for type parameters. In this way, they can be distinguished from class names, regular variables, and constants. At the same time, this reduces the readability of code significantly – especially when two or more type parameters are involved. Clauses of the form [E, S >: T] are just hard to read and understand, and rather deterring. Using this naming convention also entails the risk of neglecting type parameter naming and to just use successive letter, which can appear very arbitrary, e.g. A, B, C; or S, T, U; or U, V, W. I’ve used this naming convention excessively in this article series, and it therefore contains a lot of (hopefully discouraging) illustrative material.

In C# and C++ it is also common to name type parameters with a capitalized name prefixed by T (e.g. TElement). Scala allows also to use capitalized names, which can lead to confusion with regular class names. When naming concepts that are not yet generally established (as opposed to e.g. using E for the element type of a collection), I recommend using this naming convention even though there is a risk of confusion. When reading Scala code, you anyway have to keep in mind that type parameters can look just the same as classes.

When applying long names for type parameters to the sorting example from above, it gets longer, but also more comprehensible:

1trait Ordering[Type] {
2  def compare(x: Type, y: Type): Int
3}
4 
5abstract class Boxes {
6  def sort[Item, OrderedType >: Item](box: Box[Item], order: Ordering[OrderedType])
7}

The conventional use of single uppercase letters for type parameters makes code harder to read. These conventions needs to be considered in the decision for or against using type parameters. For me, these conventions are another reason to refrain from introducing type parameters.

Conclusion

The answer I gave here to the question where type parameters and variances are making sense is based on my personal point of view. This view has been influenced by the experiences I have made in my programming career. I can neither claim that my views are universally valid, nor that it will never change. Who knows, maybe a developer in the next Java project or the next Scala frameworks will bring me to new insights and extend my perspective on the topic.

For the moment, I believe that type parameters and co-/contravariant annotations of type parameters are theoretically interesting topics. Before applying them in real-life situations however, I think careful consideration is needed. If you introduce type parameters in the heat of the battle and add variance annotations right away, you can quickly sink several days of work to get to the conclusion that the generic construction you have created doesn’t work. If you happen to get it working, you may discover some weeks or months down the road that neither yourself nor another developer is able to understand the code you wrote, to extend it, or to debug it.

I have come to this conclusion through own practical experience: by creating generic types and using type parameters, I have at least twice managed to reduce the readability of my code base, and programmed myself into such a desperate corner that I had to do a complete type-parameter-clear-cutting over the code base. Current research results (full text paywalled) also support the perception that complex type systems do not only have positive effects. How have you used type parameters? Where did you find the use of variance annotations useful? Where useless? Share your experiences and opinions, I am looking forward to your input.

Condensed Results

These are the condensed results of all three 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.

Introducing Type Parameters and Variances

• Type-parameters are useful in the creation of basic frameworks and APIs (e.g. in Collection APIs and Concurrency Frameworks).
• Own generic classes with type parameters are hard to code, and the result is often hard to understand. I therefore recommend to avoid writing your own generic class.
• The co-/contravariance rules are hard to grasp and to obey, and the benefit is often small. Own parameterized types should be initially invariant, and modified if needed.
• In Scala, use capitalized names for type parameter, and keep in mind that type parameters can look like regular classes.