Файл: Programming_in_Scala,_2nd_edition.pdf

Or more generally, if S is a subtype of type T, then should Queue[S] be considered a subtype of Queue[T]? If so, you could say that trait Queue is covariant (or “flexible”) in its type parameter T. Or, since it just has one type parameter, you could say simply that Queues are covariant. Covariant Queues would mean, for example, that you could pass a Queue[String] to the doesCompile method shown previously, which takes a value parameter of type Queue[AnyRef].

Intuitively, all this seems OK, since a queue of Strings looks like a special case of a queue of AnyRefs. In Scala, however, generic types have by default nonvariant (or, “rigid”) subtyping. That is, with Queue defined as in Listing 19.4, queues with different element types would never be in a subtype relationship. A Queue[String] would not be usable as a Queue[AnyRef]. However, you can demand covariant (flexible) subtyping of queues by changing the first line of the definition of class Queue like this:

trait Queue[+T] { ... }

Prefixing a formal type parameter with a + indicates that subtyping is covariant (flexible) in that parameter. By adding this single character, you are telling Scala that you want Queue[String], for example, to be considered a subtype of Queue[AnyRef]. The compiler will check that Queue is defined in a way that this subtyping is sound.

Besides +, there is also a prefix -, which indicates contravariant subtyping. If Queue were defined like this:

trait Queue[-T] { ... }

then if T is a subtype of type S, this would imply that Queue[S] is a subtype of Queue[T] (which in the case of queues would be rather surprising!). Whether a type parameter is covariant, contravariant, or nonvariant is called the parameter’s variance . The + and - symbols you can place next to type parameters are called variance annotations.

In a purely functional world, many types are naturally covariant (flexible). However, the situation changes once you introduce mutable data. To find out why, consider the simple type of one-element cells that can be read or written, shown in Listing 19.5.

The Cell type of Listing 19.5 is declared nonvariant (rigid). For the sake of argument, assume for a moment that Cell was declared covariant instead—i.e., it was declared class Cell[+T]—and that this passed the

Cover · Overview · Contents · Discuss · Suggest · Glossary · Index

class Cell[T](init: T) { private[this] var current = init def get = current

def set(x: T) { current = x }

}

Listing 19.5 · A nonvariant (rigid) Cell class.

Scala compiler. (It doesn’t, and we’ll explain why shortly.) Then you could construct the following problematic statement sequence:

val c1 = new Cell[String]("abc") val c2: Cell[Any] = c1 c2.set(1)

val s: String = c1.get

Seen by itself, each of these four lines looks OK. The first line creates a cell of strings and stores it in a val named c1. The second line defines a new val, c2, of type Cell[Any], which initialized with c1. This is OK, since Cells are assumed to be covariant. The third line sets the value of cell c2 to 1. This is also OK, because the assigned value 1 is an instance of c2’s element type Any. Finally, the last line assigns the element value of c1 into a string. Nothing strange here, as both the sides are of the same type. But taken together, these four lines end up assigning the integer 1 to the string s. This is clearly a violation of type soundness.

Which operation is to blame for the runtime fault? It must be the second one, which uses covariant subtyping. The other statements are too simple and fundamental. Thus, a Cell of String is not also a Cell of Any, because there are things you can do with a Cell of Any that you cannot do with a Cell of String. You cannot use set with an Int argument on a Cell of String, for example.

In fact, were you to pass the covariant version of Cell to the Scala compiler, you would get a compile-time error:

Cell.scala:7: error: covariant type T occurs in contravariant position in type T of value x

def set(x: T) = current = x

ˆ

Cover · Overview · Contents · Discuss · Suggest · Glossary · Index

Variance and arrays

It’s interesting to compare this behavior with arrays in Java. In principle, arrays are just like cells except that they can have more than one element. Nevertheless, arrays are treated as covariant in Java. You can try an example analogous to the cell interaction above with Java arrays:

// this is Java

String[] a1 = { "abc" }; Object[] a2 = a1;

a2[0] = new Integer(17); String s = a1[0];

If you try out this example, you will find that it compiles, but executing the program will cause an ArrayStore exception to be thrown when a2[0] is assigned to an Integer:

Exception in thread "main" java.lang.ArrayStoreException: java.lang.Integer

at JavaArrays.main(JavaArrays.java:8)

What happens here is that Java stores the element type of the array at runtime. Then, every time an array element is updated, the new element value is checked against the stored type. If it is not an instance of that type, an ArrayStore exception is thrown.

You might ask why Java adopted this design, which seems both unsafe and expensive. When asked this question, James Gosling, the principal inventor of the Java language, answered that they wanted to have a simple means to treat arrays generically. For instance, they wanted to be able to write a method to sort all elements of an array, using a signature like the following that takes an array of Object:

void sort(Object[] a, Comparator cmp) { ... }

Covariance of arrays was needed so that arrays of arbitrary reference types could be passed to this sort method. Of course, with the arrival of Java generics, such a sort method can now be written with a type parameter, so the covariance of arrays is no longer necessary. For compatibility reasons, though, it has persisted in Java to this day.

Cover · Overview · Contents · Discuss · Suggest · Glossary · Index

Scala tries to be purer than Java in not treating arrays as covariant. Here’s what you get if you translate the first two lines of the array example to Scala:

scala> val a1 = Array("abc")

a1: Array[java.lang.String] = Array(abc)

scala> val a2: Array[Any] = a1 <console>:5: error: type mismatch;

found : Array[java.lang.String] required: Array[Any]

val a2: Array[Any] = a1

ˆ

What happened here is that Scala treats arrays as nonvariant (rigid), so an Array[String] is not considered to conform to an Array[Any]. However, sometimes it is necessary to interact with legacy methods in Java that use an Object array as a means to emulate a generic array. For instance, you might want to call a sort method like the one described previously with an array of Strings as argument. To make this possible, Scala lets you cast an array of Ts to an array of any supertype of T:

scala> val a2: Array[Object] = a1.asInstanceOf[Array[Object]]

a2: Array[java.lang.Object] = Array(abc)

The cast is always legal at compile-time, and it will always succeed at runtime, because the JVM’s underlying run-time model treats arrays as covariant, just as Java the language does. But you might get ArrayStore exceptions afterwards, again just as you would in Java.

19.4 Checking variance annotations

Now that you have seen some examples where variance is unsound, you may be wondering which kind of class definitions need to be rejected and which can be accepted. So far, all violations of type soundness involved some reassignable field or array element. The purely functional implementation of queues, on the other hand, looks like a good candidate for covariance. However, the following example shows that you can “engineer” an unsound situation even if there is no reassignable field.

Cover · Overview · Contents · Discuss · Suggest · Glossary · Index

To set up the example, assume that queues as defined in Listing 19.4 are covariant. Then, create a subclass of queues that specializes the element type to Int and overrides the enqueue method:

class StrangeIntQueue extends Queue[Int] { override def enqueue(x: Int) = {

println(math.sqrt(x)) super.enqueue(x)

}

}

The enqueue method in StrangeIntQueue prints out the square root of its (integer) argument before doing the append proper. Now, you can write a counterexample in two lines:

val x: Queue[Any] = new StrangeIntQueue x.enqueue("abc")

The first of these two lines is valid, because StrangeIntQueue is a subclass of Queue[Int], and, assuming covariance of queues, Queue[Int] is a subtype of Queue[Any]. The second line is valid because you can append a String to a Queue[Any]. However, taken together these two lines have the effect of applying a square root method to a string, which makes no sense.

Clearly it’s not just mutable fields that make covariant types unsound. The problem is more general. It turns out that as soon as a generic parameter type appears as the type of a method parameter, the containing class or trait may not be covariant in that type parameter. For queues, the enqueue method violates this condition:

class Queue[+T] {

def enqueue(x: T) =

...

}

Running a modified queue class like the one above through a Scala compiler would yield:

Queues.scala:11: error: covariant type T occurs in contravariant position in type T of value x

def enqueue(x: T) =

ˆ

Cover · Overview · Contents · Discuss · Suggest · Glossary · Index

Reassignable fields are a special case of the rule that disallows type parameters annotated with + from being used as method parameter types. As mentioned in Section 18.2, a reassignable field, “var x: T”, is treated in Scala as a getter method, “def x: T”, and a setter method, “def x_=(y: T)”. As you can see, the setter method has a parameter of the field’s type T. So that type may not be covariant.

The fast track

In the rest of this section, we’ll describe the mechanism by which the Scala compiler checks variance annotations. If you’re not interested in such detail right now, you can safely skip to Section 19.5. The most important thing to understand is that the Scala compiler will check any variance annotations you place on type parameters. For example, if you try to declare a type parameter to be covariant (by adding a +), but that could lead to potential runtime errors, your program won’t compile.

To verify correctness of variance annotations, the Scala compiler classifies all positions in a class or trait body as positive, negative, or neutral. A “position” is any location in the class (or trait, but from now on we’ll just write “class”) body where a type parameter may be used. Every method value parameter is a position, for example, because a method value parameter has a type, and therefore a type parameter could appear in that position. The compiler checks each use of each of the class’s type parameters. Type parameters annotated with + may only be used in positive positions, while type parameters annotated with - may only be used in negative positions. A type parameter with no variance annotation may be used in any position, and is, therefore, the only kind of type parameter that can be used in neutral positions of the class body.

To classify the positions, the compiler starts from the declaration of a type parameter and then moves inward through deeper nesting levels. Positions at the top level of the declaring class are classified as positive. By default, positions at deeper nesting levels are classified the same as that at enclosing levels, but there are a handful of exceptions where the classification changes. Method value parameter positions are classified to the flipped classification relative to positions outside the method, where the flip of a positive classification is negative, the flip of a negative classification is positive, and the flip of a neutral classification is still neutral.

Besides method value parameter positions, the current classification is also flipped at the type parameters of methods. A classification is sometimes

Cover · Overview · Contents · Discuss · Suggest · Glossary · Index

flipped at the type argument position of a type, such as the Arg in C[Arg], depending on the variance of the corresponding type parameter. If C’s type parameter is annotated with a + then the classification stays the same. If C’s type parameter is annotated with a -, then the current classification is flipped. If C’s type parameter has no variance annotation then the current classification is changed to neutral.

As a somewhat contrived example, consider the following class definition, where the variance of several positions is annotated with + (for positive) or (for negative):

abstract class Cat[-T, +U] {

def meow[W ](volume: T , listener: Cat[U+, T ] ) : Cat[Cat[U+, T ] , U+]+

}

The positions of the type parameter, W, and the two value parameters, volume and listener, are all negative. Looking at the result type of meow, the position of the first Cat[U, T] argument is negative, because Cat’s first type parameter, T, is annotated with a -. The type U inside this argument is again in positive position (two flips), whereas the type T inside that argument is still in negative position.

You see from this discussion that it’s quite hard to keep track of variance positions. That’s why it’s a welcome relief that the Scala compiler does this job for you.

Once the variances are computed, the compiler checks that each type parameter is only used in positions that are classified appropriately. In this case, T is only used in negative positions, and U is only used in positive positions. So class Cat is type correct.

19.5 Lower bounds

Back to the Queue class. You saw that the previous definition of Queue[T] shown in Listing 19.4 cannot be made covariant in T because T appears as a type of a parameter of the enqueue method, and that’s a negative position.

Fortunately, there’s a way to get unstuck: you can generalize enqueue by making it polymorphic (i.e., giving the enqueue method itself a type parameter) and using a lower bound for its type parameter. Listing 19.6 shows a new formulation of Queue that implements this idea.

Cover · Overview · Contents · Discuss · Suggest · Glossary · Index