Tuesday, September 10, 2013

Variance Annotations in Scala

The purpose of this post, is to introduce the basics of parameterized classes, upper and lower bounds and variance subtyping in Scala.

Overview
Scala is a statically typed languages similar to Java and C++. Most of those concepts have been already introduced and commonly in Java with generics and type parameters wildcard. However Scala added some useful innovation regarding sub-typing covariance and contravariance. API designers and library developers are facing the dilemma of choosing between parameterized types and abstract types and which parameters should be invariant, covariant or contravariant.


Sub-classing
Like in Java, generic or parameterized type have been introduced to overcome the limitation of polymorphism. Moreover, understanding of concept behind the Scala type system help developers decipher and fix the occasional compilation failure related to typing.
Let's consider a simple collection class ,Container that adds and retrieves an array of items of type Item as follows.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Item
case class SubItem() extends Item
 
class Container {
  def add(items: Array[Item]) : Unit = 
    items.foreach( add(_) )
  def retrieve(items: Array[Item]) : Unit =
    Range(0, items.size).foreach(items.update(_, retrieve))

  def add(item: Item) : Unit = { }
  def retrieve : Item = new SubItem
}

The client code can invoke the add (lines 5 & 10) and retrieve (lines 7 & 11) methods passing an array of elements of type Item. However passing an array of type SubItem inherited from Item (line 2) will generate a compiling error!

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
val subItemsContainer = new Container
val array = Array[SubItem](new SubItem())
 
  // Compile error:
  // "type mismatch;  found   : Array[SubItem]  
  // required: Array[Item] 
  // Note: SubItem <: Item, but class Array is 
  // invariant in type T..."
 subItemsContainer.add(array)
 subItemsContainer.retrieve(Array[SubItem](new SubItem))

The Scala compiler throws a compiling error because the class Container does not have the adequate information about the sub type Item into SubItem in the add method (line 9). The invocation of the retrieve method, passing an argument of type SubItem generates also a compiler error.
Scala provides developers with upper bounds and lower bounds subtyping which is quite similar to the type variance available in Java.

Variance to the Rescue
The type T upper bounded by the type Item as defined by the following notation (line 1)
  T <: Item
can be processed as a 'producer' of type Item. The notation provides the Scala compiler that any type inheriting Item should be allowed to be passed as argument of the add method (lines 2 & 7).
Similarly, he type U with a lower bound type SubItem
   U >: SubItem
can be processed as a 'consumer' operation of type SubItem, in the retrieve method (lines 4 & 8).

1
2
3
4
5
6
7
8
9
class Container[T <: Item] {
  def add(items: Array[T]) : Unit = items.foreach( add(_) )
     
  def retrieve[U >: SubItem](items: Array[U]) : Unit = 
     Range(0, items.size)foreach(items.update(_, retrieve))
  
  def add(item: T): Unit = {}
  def retrieve: U = new SubItem
}

Container[T] is a covariant class for the type Item as argument of the method add. The method retrieve[U] is contravariant for the type SubItem.
This time around the compiler has the all the necessary information to subtype Item and super type SubItem, therefore the following code snippet won't generate a compiling error

val itemsContainer = new ContainerT[SubItem]
itemsContainer.add(Array[SubItem](new SubItem)))
itemsContainer.retrieve[Item](Array[Item](new SubItem))

Scala has a dedicated annotation for unvariance 'T', covariance '+T' and contravariance '-T'. Using this annotation the container class can be expressed as follow.

1
2
3
4
5
6
7
8
9
class Container[+T] {
  def add(items: Array[T]) : Unit = 
    items.foreach( add(_) )
  def retrieve[-U](items: Array[U]) : Unit = 
    Range(0, items.size).foreach(items.update(_, retrieve))
  
  def add(item: T) : Unit = { }
  def retrieve : U = new SubItem
}

In a nutshell, variances can be represented as functors:
Covariance: if (B inherit A) then (Container[B] inherit Container[A])
Contravariance: if( B inherit A) then (Container[A] super class of Container[B])
Univariance: No rule applies.
 

The subtyping rules above can be represented graphically


References
Programming in Scala M. Odersky, L. Spoon, B. Venners - Artima 2010
Effective Java - 2nd edition - J. Block Addison-Wesley 2008
github.com/prnicolas

1 comment:

  1. I am glad you mentioned Josh Bloch as reference. He has a great mnemonic called PECS which stands for Producer-Extends-Consumer-Super

    Wildcard variance can be also used as conversion
    class Valid[V <: T](val value: T) {
    def value: V = value.asInstanceOf[V]
    }
    You can even make it implicit

    ReplyDelete