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.
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
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
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
-, 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
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.
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
Nil-class is a subtype of
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
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
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
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")
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.