Wednesday, April 12, 2006

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));

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("")
  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.


Zach Beane said...

Common Lisp was never small or functional. Lisp history is not rich with small or functional versions of the language, with the exception of Scheme.

"Elegant" is a loaded term.

Anonymous said...

Covariant parameters are officially evil, hence the wildcards and so on. But in practice, who cares? Maybe people trying to optimize things to perfect nondeterministic code execution order. But mostly, we don't do that, anyway.

We rarely get ClassCastExceptions with old-fashioned Lists and Maps. Even less so with happily covariant (runtime-checked) Java arrays. And arrays are much easier to understand and use than wildcards.

Java arrays are clear without being cumbersome. And they catch some mistakes at compile time. I think Java 5 went the wrong direction. But c'est la vie.

dibblego said...

"Scala's support of generics is the most advanced amongst all modern languages"

Back up a bit :)

dibblego said...

"Covariant parameters are officially evil, hence the wildcards and so on."

You aren't seriously going to back up that assertion with the existence of the wildcard in JSR-14?

Perhaps you mean, "Type systems such as that purported by Java are officially evil"?

Christian said...

A discussion about an interesting special case with storing classes (not instances) in a generic List can be found in the Scala Forum.

It looks as if it is not possible to make something like this in Scala:

class A

class B extends A

val classStore = new ListBuffer[Class[A]]

Anonymous said...

... and the solution:

To be able to store subclasses of a given class write:

List[Class[_ <: A]]

You can add then class A and subclasses thereof to the list.