Traits in Gypsum
I'm happy to announce the launch of a major new language feature in Gypsum: traits.
Traits are like interfaces in Java. They provide a form of multiple inheritance. When you define a trait, you create a new type and a set of methods that go with it, some of which may be abstract. Classes and other traits that inherit from a trait will inherit those methods.
New traits in the standard library
It's probably better to explain traits by example. Below are several new traits I've added to the standard library.
Eq - structural equality
public trait Eq[static -T] public abstract def == (that: T): boolean public def != (that: T): boolean = !(this == that)
Eq provides methods (== and !=) for checking structural equality between objects of a given type. Note that the == method is abstract (deriving classes must implement it), but the != method has a default implementation. != is not marked final, so subclasses can override it if they want.
The Gypsum root class, Object, only provides methods for checking referential equality (=== and !==). Structural equality is not a meaningful concept for many classes. For example, it doesn't make sense to ask whether a socket is equal to another socket. Because structural equality is not universally meaningful, it doesn't make sense to put structural equality operators in the root class.
For types where structural equality is a meaningful concept, it's generally only meaningful for certain other types. For example, it makes sense to compare a String with another String, but not with an F32Array. That should result in a type error. This is why Eq has a contravariant type parameter.
Hash - Hash table keys
public trait Hash[static -T] <: Eq[T] public abstract def hash: i32
Hash provides a single abstract method that returns a 32-bit integer hash code. This is used with Dict and Set, which are backed by hash tables. Note that Hash derives from Eq, since hash tables always require their keys to support both operations.
For convenience, the standard library provides a HashBuilder class that can be used to implement hash functions. It's based on MurmurHash3.
Iter and Iterator
public trait Iter[static +T] public abstract def iter: Iterator[T] public trait Iterator[static +T] public abstract def has-next: boolean public abstract def next: T
An Iterator is an object that returns a sequence of values, usually retrieved from some collection (e.g., the elements of a list or a set). The Iter trait should be inherited by classes which can be iterated over (e.g., lists and sets).
I plan to add for loops to Gypsum which will have syntactic sugar for iterating over collections using these traits.
If you'd like to see these traits in action, HashTable has a non-trivial implementation of both Iter and Iterator.
Reader, Writer, Closeable
public trait Reader public def read(buffer: I8Array): i32 = read(buffer, 0i32, buffer.length) public def read(buffer: I8Array, offset: i32, count: i32): i32 public trait Writer public def write(buffer: I8Array): unit = write(buffer, 0i32, buffer.length) public def write(buffer: I8Array, offset: i32, count: i32): unit public trait Closeable public def close: unit public def is-closed: boolean
Reader and Writer represent general input and output streams of bytes. These can be used for accessing files, sockets, IPC channels, etc. Closeable is a separate trait for streams that can be closed.
Reader and Writer both provide methods for reading / writing an arbitrary slice of a byte array. These are the main methods that subclasses should implement. They also provide convenience methods with default implementations for reading / writing a whole array.
Subtleties of multiple inheritance
Adding multiple inheritance to a language is not easy, especially a language that already has parametric polymorphism. Instead of having a tree of classes, we now have a directed acyclic graph of type definitions. This causes a lot of subtle problems.
The diamond problem
The most obvious challenge is dealing with the diamond problem. Basically, a class or trait may be inherited along multiple paths.
When a Gypsum class or trait is compiled, the compiler builds a list of all types it inherits, directly or indirectly. The list is constructed by performing a depth-first-search over the inheritance graph. If we see that we've already inherited something, we handle it by ignoring it: each class or trait may only appear in the supertype list once.
There is one important restriction needed to keep us sane: if a parameterized class or trait is inherited along multiple paths, it must always be inherited with the same type arguments. So we cannot inherit both Eq[String] and Eq[I32].
Method overrides
Method overrides were fairly easy to deal with before traits. A method could only override one method in one superclass. With traits, a method can now override multiple methods in multiple traits. For example, if you write a class that inherits two unrelated traits that define an abstract length method, you can override both with a single implementation in your class.
Least upper bound is not unique
The least upper bound (lub for short) of two types is the most specific supertype of both types. Lub is used to find the type of if and match expressions: the type of an if expression is the lub of the types of the true and false expressions. With single inheritance, the lub of two class types was fairly easy to compute (though there are some subtleties with type arguments). You just needed to find the lowest class in the inheritance tree that both types derive from.
In the figure below, B is the lub of C and D.
Multiple inheritance turns the inheritance graph into a directed acyclic graph instead of a tree. We're no longer guaranteed to have a unique lub for any pair of types.
In the figure below, both B and D are lubs of C and E.
There may be multiple valid lub types, but we can only choose one. In this scenario, there's no reason to favor one over the other, so we have to pick something higher up in the inheritance graph like A. This is not technically a least upper bound, but hopefully it's good enough in most situations.
Trait method calls are dynamic
When a virtual method is called, the interpreter can look up the method to be called in the receiver object's vtable. For receivers of class type, methods can be looked up using a fixed integer index, based on the order that methods were defined in. This is much more complicated for traits, since for a given receiver of trait type, we don't know what order the trait was inherited in or where the method is located in the receiver class's main vtable.
There are probably a lot of ways to implement trait methods calls, but the simplest solution, at least at the bytecode level, is to generate a hash table of all methods in a class, then look methods up by name when they are called. I chose to do this both for class and trait receiver types, since this has the added benefit of preserving binary compatibility when the order of methods changes in foreign classes.
I'll admit this isn't very efficient: hash table lookups add a lot of overhead to method calls. In the future, when CodeSwitch gets an optimizing compiler, call sites will be optimized for a small number of receiver types. In practice, most call sites are monomorphic or slightly polymorphic, so we just do a quick type check and then a static method call. We can even inline methods if it seems beneficial.
Planned improvements
Traits are already a powerful feature, but there are a lot of ways they can be improved.
Trait fields
I'd like to allow instance fields to be defined within traits, the same way Scala does. This would allow traits to provide a more complete implementation. For example, you could define a Lockable trait that comes with a mutex or an Observable trait that comes with a list of observers.
Conditional traits
It frustrates me that Dict, List, and Set can't implement the Eq trait without requiring their element type to be a subtype of Eq. I'd like to be able to inherit a trait conditionally: if the element type is a subtype of Eq, then the container type is also a subtype of Eq. The == method would be conditionally overridden and could only be called if the type condition were satisfied.
Union and intersection types
A union type would be a combination of two or more class or trait types. A type would be a subtype of a union type if it is a subtype of any of the types in the union. Only the common members of all classes or traits in a union type could be accessed. This would solve the least upper bound problem mentioned above. It might also provide a convenient way to match multiple types in one match case.
An intersection type would be similar except a type would be a subtype of an intersection type if it is a subtype of all of the types in the intersection. All members could be accessed. This would be a convenient way to compose traits without necessarily defining another class or trait.
Implicit traits
Most object-oriented languages (Java, C#, Python, Scala) have
I like the idea of structural subtyping, though I think it might be confusing in some cases. It lets you define an interface that other classes (possibly not under your control) implement automatically.
I'd like to experiment with having optional structural subtyping, possibly using a new implicit attribute on trait definitions. If that works out well, it's possible that structural subtyping will be the default in Gypsum. It probably will never be required in CodeSwitch, since CodeSwitch is intended to support many languages.