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.