Bounded Polymorphism Language Design

[SamChou19815]

Rationale

Right now there is no way to efficiently implement something like a TreeMap in Java that only contains Comparable elements. As a reminder, the interface of TreeMap in Java is along the line of:

class TreeMap<K extends Comparable<K>, V> {}

The key of the missing feature is bounded polymorphism. Instead of accepting any object as key, we want it to have some guarantee. In the case of TreeMap, we want it to have the compare method so that we can compare it against other keys to find the right place for it in the self-balancing binary tree.

Similarly, it is also useful if we want to implement hash table in samlang. Unlike Java, equals and hashCode are not builtin methods on every object. Instead, we have to establish it through the same mechanism.

Prior Arts

Constrained Generics in Java

The syntax is shown in the examples above. At runtime, it will be type erased to contain the lower bound only, and appropriate type casts will be inserted to keep the type-erased code type check.

// Original
<N extends Number> void test(N n) {};

// Type erased
void test(Number n);

Unfortunately, Java's generics with subtyping is undeciable.

Functors in OCaml

module Map (M : Comparable) = struct
  (* Uses M *)
end

OCaml's functors are more powerful than Java's equivalent feature, due to the fact that you can use the type parameter as type constructor as well. This is due to the fact that the module argument exists as a real value and there are nothing like type erasure in OCaml functors.

Unfortunately, the module system with functors in OCaml also leads to undecidability.

Language Changes

Syntaxes Changes

Function calls now allow type arguments to be optionally specified.

Object constructors will now be required to start with the name of the class, with optional type parameters. Type arguments must be all inferred or all explicitly specified. In case there is any type parameter with bounds, all type arguments must be explicitly specified.

Obj { a: 3, b: "4" }
Obj<string, int> { a: 3, b: "4" }

Similarly, variant constructors will be required to be prefixed with class names. Same rules for type arguments applied.

Option.None<int>();
Option.Some();

These changes will allow us to loosen the restriction that objects and variants can only be constructed inside the same class.

Interface Declaration

Interface declarations will become the same toplevel constructs as classes. It can be imported, allows polymorphism. However, interface cannot be instantiated and all the declarations cannot have body. Unlike Java, interfaces can define abstract static methods.

Interfaces can extend any number of other interfaces. A class can implement any number of interfaces. Such rules are discussed in the next section.

interface A {}
interface B extends A {}
interface Monad<T> {}
interface Comparable<T> {}
class List<T> implements Monad<T>, Comparable<T> {}

Interface type can never be an assignment target. As a result, it can never appear in the place of type annotation. This design completely avoids subtyping asserting checks and helps to simplify the type system.

Comformance Checking

To tame generics with subtyping to be decidable, restrictions need to be made. According to this paper, banning contravariance of type parameters, expansive inheritance, and multiple instantiation inheritance seems to be a good idea. The first and third will be naturally impossible due to the current design of samlang, which should be sufficient to make type checking decidable.

In subterm comformance checking, no subtyping is allowed at all. After substitution is performed, signature must match exactly modulo alpha-transformation.

Bounds on Generic Type Parameters

Bounds on generic type parameters can be optionally added to class, method or function type parameters:

class BST<V extends Comparable<V>> {
  method <A extends List<String>> fff(): int;
  function <B extends List<String>> bbb(): int;
}

Comformance will be enforced. At compile time, the approach of generics specialization will be used.

Implementation Progress

• [x] Syntax Changes
  • [x] Function call
  • [x] Object
  • [x] Variant
• [ ] Interface Declaration
• [ ] Comformance Checking
• [ ] Bounds on Generic Type Parameters