Showing posts with label subtyping. Show all posts
Showing posts with label subtyping. Show all posts

Wednesday, December 11, 2019

Variance Annotation in Scala 2.x

Target audience: Intermediate
Estimated reading time: 3'

The purpose of this post, is to introduce the basics of parameterized classes, upper and lower bounds and variance sub-typing in Scala.
Table of contents
Overview
Follow me on LinkedIn

Note: The code associated with this article is written using Scala 2.12.4

Overview

Scala is a statically typed language 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 contra-variance. 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 contra-variant.


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 sub-typing 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 with any type inheriting Item. It should be allowed to be passed as argument of the add method (lines 2 & 7).
Similarly, the 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 contra-variant 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 contra-variance '-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])
Contra-variance: if( B inherit A) then (Container[A] super class of Container[B])
Univariance: No rule applies.
 

The sub-typing rules above can be represented graphically 


Thank you for reading this article. For more information ...

References



---------------------------
Patrick Nicolas has over 25 years of experience in software and data engineering, architecture design and end-to-end deployment and support with extensive knowledge in machine learning. 
He has been director of data engineering at Aideo Technologies since 2017 and he is the author of "Scala for Machine Learning" Packt Publishing ISBN 978-1-78712-238-3