Type parameter bounds and variance

I have two cool new features of the Gypsum type system to show off: type parameter bounds and variance. I'll try to define these briefly, then explain with a longer example.

Bounds

Type parameters for functions and classes can now be defined with an optional upper bound, using the <: operator. If an upper bound type is specified for a parameter, the compiler will ensure that any type argument is a subtype of that upper bound. Because of this, it's safe to call methods and access fields defined in the upper bound type.

This could be used, for example, to create a hash table class. The elements of a hash table can be anything, as long as they are hashable.

abstract class Hashable
  abstract def hash-code: i32
  abstract def equals(other: Hashable): boolean

class HashTable[static T <: Hashable]
  ...

Bounds must be class types (no primitive types allowed for now). If no upper bound is specified, the default is Object, the root class type.

For comparison, upper bounds in Gypsum are basically the same as generic upper bounds in Java. C++ does not have explicit upper bounds for templates, but the compiler checks that any members you use from a template parameter are present in any template argument.

Unlike Java, Gypsum also allows you to specify a lower bound with the >: operator. When a lower bound type is specified, the compiler will guarantee any type argument is a supertype of that bound. Java lets you specify lower bounds for wildcards but not for generic parameters.

Covariance and contravariance

Type parameters for classes (not functions) may now be marked as covariant or contravariant. This is used to determine when a class type is a subtype of another.

Consider the following set of classes:

class Reader[static +T]
  def read: T = ...

class Writer[static -T]
  def write(x: T): unit = ...

class ReaderWriter[static T]
  def read: T = ...
  def write(x: T): unit = ...

Reader's type parameter is marked with a +, which makes it covariant. A class type with a covariant parameter is a subtype of another type of the same class if its type argument is a subtype of the corresponding type argument. In other words, Reader[String] is a subtype of Reader[Object] because String is a subtype of Object. If we have some method which expects a Reader[Object], we could give it a Reader[String] instead, because the read method returns an Object in either case.

Writer's type parameter is marked with a -, which makes it contravariant. This flips the rule mentioned above. Writer[Object] is actually a subtype of Writer[String] because String is a subtype of Object. The former can be used anywhere the latter can, but not vice versa.

If a type parameter is not marked with a + or -, it is invariant. A class type with an invariant parameter is only a subtype of another type of the same class if the type arguments are equal. So ReaderWriter[String] is neither subtype nor supertype of ReaderWriter[Object].

When a type parameter is marked covariant or contravariant, there are some restrictions on where it can be used. Covariant type parameters can be used for method return types and immutable field types. Contravariant type parameters can be used for method parameter types. Both kinds can be used freely in constructor parameters and in method bodies. Only invariant type parameters can be used in mutable fields.

Gypsum's type parameter variance is heavily inspired by Scala, which I think has an excellent type system. Java does not allow you to specify variance in a type parameter definition, but it does allow wildcards when a type is used, which gives you essentially the same effect (but with a lot more typing). So you could have a method which takes a Reader<? extends Object>, and you could pass it a Reader<String>, for example.

Extended example

I've added a new example in Github, list-sort.gy, which uses both of these features. It defines an immutable linked list with a covariant type parameter for the element type. It then defines a function which sorts a linked list of any type, as long as its elements can be compared to each other.

The linked list is defined using three classes. List represents linked lists in general. Nil-class is a singleton class, which represents the empty list. The singleton instance is called Nil. It's easier to deal with the Nil object instead of null because you can call methods on it and not worry about errors. Cons represents non-empty lists; it contains a value and a pointer to the result of the list.

abstract class List[static +T]
  // Returns the first element of the list.
  abstract def head: T

  // Returns everything after the first element.
  abstract def tail: List[T]

  // Returns the number of elements in the list.
  abstract def length: i64

  // Returns the first n elements of the list.
  abstract def take(n: i64): List[T]

  // Returns a list without the first n elements.
  abstract def drop(n: i64): List[T]

  // Returns a list with all the elements in reverse order.
  def reverse: List[T] =
    var reversed: List[T] = Nil
    var list: List[T] = this
    while (list !== Nil)
      reversed = Cons[T](list.head, reversed)
      list = list.tail
    reversed

  abstract def to-string: String


class Nil-class <: List[Nothing]
  def head = throw Exception
  def tail = throw Exception
  def length = 0

  def take(n: i64) =
    if (n == 0)
      Nil
    else
      throw Exception

  def drop(n: i64) =
    if (n == 0)
      Nil
    else
      throw Exception

  def to-string = "Nil"

let Nil = Nil-class


class Cons[static +T](value: T, next: List[T]) <: List[T]
  def head = value
  def tail = next
  def length = 1 + next.length

  def take(n: i64): List[T] =
    if (n == 0)
      Nil
    else
      Cons[T](value, next.take(n - 1))

  def drop(n: i64): List[T] =
    if (n == 0)
      this
    else
      next.drop(n - 1)

  def to-string =
    let value-str = value.to-string
    if (next === Nil)
      value-str
    else
      value-str + ", " + tail.to-string

Note that Nil-class is a subtype of List[Nothing]. Nothing is a special built-in type, which is a subtype of all class types. Because List's type parameter is covariant, this means Nil can be used anywhere any kind of List is expected. There are no instances of Nothing.

In the example, we want to sort a list of integers. Since integer types like i64 are primitive and only class types can be used as type arguments, we define a wrapper class Integer. We also want to make sure our list of integers can be sorted, so we define a base class, Ordered, for objects that can be compared to each other and make sure Integer subclasses it. The compare method is expected to return negative, zero, or positive for less, equal, or greater, respectively.

abstract class Ordered[static T]
  abstract def compare(other: T): i64


class Integer(value: i64) <: Ordered[Integer]
  def compare(other: Integer) = value - other.value
  def to-string = value.to-string

The sort function implements the standard merge sort algorithm. It ensures the elements of the list being sorted can be compared to each other using an upper bound.

def sort[static T <: Ordered[T]](list: List[T]): List[T] =
  if (list.length <= 1)
    // Base case: empty lists and single element lists 
    // are already sorted.
    list
  else
    // Recursive case
    // Divide the list in half.
    let length = list.length
    let first = list.take(length / 2)
    let second = list.drop(length / 2)

    // Sort each half.
    var first-sorted = sort[T](first)
    var second-sorted = sort[T](second)

    // Merge the two halves together in a single, sorted list. 
    var reverse-merged: List[T] = Nil
    while (first-sorted !== Nil || second-sorted !== Nil)
      if (first-sorted !== Nil &&
          (second-sorted === Nil ||
           first-sorted.head.compare(second-sorted.head) <= 0))
        reverse-merged = Cons[T](first-sorted.head,
                                 reverse-merged)
        first-sorted = first-sorted.tail
      else
        reverse-merged = Cons[T](second-sorted.head,
                                 reverse-merged)
        second-sorted = second-sorted.tail

    reverse-merged.reverse

The main function ties it all together.

def main =
  let list = Cons[Integer](Integer(3),
                 Cons[Integer](Integer(4),
                     Cons[Integer](Integer(1),
                         Cons[Integer](Integer(2), Nil))))
  let sorted-list = sort[Integer](list)
  print(sorted-list.to-string + "\n")

Conclusion

Type parameter bounds and variance provide a huge amount of flexibility and precision in the Gypsum type system. They let you handle many cases where you would normally have to fall back to casting and run-time type checking. Because the Gypsum can check these cases ahead of time, your code will be not only cleaner but also faster.