Generics in Scala - Part 1

How big should a programming language be ? Well, that depends on what you would like to do with it. Common Lisp started out as a small elegant functional language, but with the proliferation of multiple dialects, the addition of object-oriented components (CLOS), generalized iteration construct (LOOP), full blown condition system etc., the current ANSI Common Lisp's specification is about 1,300 pages long and has 1,000 defined symbols [source: Patterns of Software - Gabriel].

Scala is a rich language targetted towards component based development - it offers a fusion of object oriented as well as the functional paradigms. The advanced type system of Scala backed by rich features like type inferencing and type annotations place Scala far ahead of its contemporaries. Scala's support of generics is the most advanced amongst all modern languages - it is possibly the only modern language that supports both parameterized types (originating from functional languages) and virtual types (from the OO paradigm).

Scala Parameterized Types Implemented through Erasure

This is similar to Java implementation where the generic type info gets erased after program compilation. Some efforts are on amongst the Scala designers towards reification of generics in Scala and have added an experimental support for interoperability with Java generics since Scala 2. Here is a simple example of a generic class in Scala :

object GenericsTest extends Application {

  abstract class Sum[t] {
    def add(x: t, y: t): t;
  }

  object intSum extends Sum[Int] {
    def add(x: Int, y: Int): Int = x + y;
  }

  class ListSum[a] extends Sum[List[a]] {
    def add(x : List[a], y : List[a]) : List[a] = x ::: y;
  }

  val s = new ListSum().add(List("a", "b"), List("c", "d"));
  val t = new ListSum().add(List(1, 2), List(3, 4));
  Console.println(s);
  Console.println(t);
}


Scala Parameterized Types Allow Variance Annotations

There is a strong relation between parameterized types and (co|contra|in)variance in type declarations / expressions. Java class declarations do not support any covariance annotations - List<Derived> is never a subtype of List<Base> in Java, even though Derived is a subtype of Base. However, Java allows covariance of generic types to be expressed by annotating every occurrence of List type to match the form List<? extends Base>. This implements a form of family polymorphism within all List types where the type argument is an arbitrary subtype of Base.

Scala allows variance annotations at class declaration (unlike Java). Consider the following declaration of an immutable Stack (adopted from Scala By Example) :

abstract class Stack[+a] {
  def push[b >: a](x: b): Stack[b] = new NonEmptyStack(x, this)
  def isEmpty: boolean
  def top: a
  def pop: Stack[a]
}

object EmptyStack extends Stack[Nothing] {
  def isEmpty = true
  def top = throw new Error("EmptyStack.top")
  def pop = throw new Error("EmptyStack.pop")
}

class NonEmptyStack[+a](elem: a, rest: Stack[a]) extends Stack[a] {
  def isEmpty = false
  def top = elem
  def pop = rest
}


The + in type argument for the class definition indicates that subtyping is covariant on that type parameter. A - in the same place changes the relationship to contravariance. The default (without any prefix) declaration indicates invariance of subtyping.

Along with variance annotations at class declarations, Scala's type checker verifies its soundness as well. Though safe for immutable data types, covariant subtyping is never safe for mutable data types, and the typechecker is quick to disallow such unsafe declarations. e.g. in the following declaration of a mutable Stack

class Stack[+T] {
  var elems: List[T] = Nil
  def push(x: T): Unit = elems = x :: elems
  def top: T = elems.head
  def pop: Unit = elems = elems.tail
}

The covariant argument for push() appears in a contravariant position - the Scala compiler will flag this as an error. Compare this approach with Java's covariant subtyping for arrays where we need to depend on runtime checks to ensure type safety of the underlying structure.

The question is how do we avoid a similar situation of push() method in the immutable version of the Stack definition. Immutable data structures are always candidates for covariant subtyping and Scala achieves this through specification of lower bounds for type parameters. Observe the contract def push[b >: a](x: b): Stack[b] in the functional version of the Stack definition above. In this contract the type parameter a does not appear in the contra variant position (parameter type of push()). The type parameter has been moved as a lower bound for another type parameter of a method, which is a covariant position. This lower bound of the type parameter makes it completely typesafe to implement covariant subtyping.


Subtyping with Generic Types - Scala, Java and C#

As I mentioned above, Scala supports covariant typing using annotations at class declaration, as opposed to Java, which allows annotations at type expressions. Thus Scala restricts annotations to the class designer, while Java leaves it to the users. The Scala designers found it difficult for users to maintain consistency of usage-site annotations as Odersky observes in his OOPSLA 05 paper on abstractions

In an earlier version of Scala we also experimented with usage-site variance annotations similar to wildcards. At first-sight, this scheme is attractive because of its extensibility. A single class might have covariant as well as non-variant fragments; the user chooses between the two by placing or omitting wildcards. However, this increased extensibility comes at price, since it is now the user of a class instead of its designer who has to make sure that variance annotations are used consistently.

However, Java implementation of generics achieves flexibility in typing through use of wildcards along with type-capture technique as detailed out in this wonderful exposition by Torgerson et. al. This paper is a strong justification of adding wildcard support in generics implementation and discusses all related issues of subtyping in the object oriented environment. Wild cards have added flexibility in Java typing in the sense that the user can now declare the same List class as covariant (List<? extends Number>) or contravariant (List<? super Number>). The other player to this game, Microsoft .NET does not use erasure and does not support wild cards in generics implementation - instead they have chosen to make the runtime support the implementation. Designers of C# do not consider subtyping to be an issue with generic types and do not feel wild card support an important offering. In his weblog Puzzling through Erasure II, Eric Gunnerson mentions that it is more important to be able to have generics over value types and performant implementations than to support wildcards.

In this entry I have discussed only one aspect of Scala's generics implementation - the parameterized types. In the next post, I will discuss the OO of generics - The Abstract Member Type which implements virtual types in Scala.