haXe Polymorphism and Variance
posted on 2006-03-27I hacked a pretty interesting software on Friday, using haXe. The things I wanted to do were not so easy, and involved both ML-style-polymorphism and variance, two features that haXe don’t have right now but that can somehow be emulated using current type system.
Polymorphism : in ML, polymorphism enables you to write some code that will work for different kind of types. For example the following haXe function is building an array-pair from two values :
function pair(a,b) { return [a,b]; }
In ML, that would give a polymorphic type “'a -> 'a -> 'a array
” that would bind the types of the two values to the type of the array. Then for each usage of pair
, the first argument will be enough to guess the type of the second argument and the return array type.
In haXe, there is no per-function polymorphism. So-called type parameters can only be in classes, that’s per-class polymorphism. If then you want to emulate polymorphism in haXe, you can use static functions with type annotations :
class Pair<T> { public function make(a : T, b : T) : Array<T> { return [a,b]; } }
Please note that in that case specifying the return type Array<T>
is not mandatory since it will be inferred from a
and b
types. OTOH, the parameters types are mandatory because if there is no type specified the Pair.make
type will be monomorphic (it will use haXe type Unknown
) and then its first usage will set its type definitly, while we want each usage to be valid for a given type.
This now works, you can write Pair.make("hello","world!")
and Pair.make(0,1)
and they both get accepted by the typechecker. Pair.make("hello",0)
get rejected, saying that the Int 0 is not a String. Since everytime we’re accessing the Pair
class the type T becomes a monomorph, everything is working accordingly.
As a side note, this creates a type-hole when you have a contraint on the type T
(like T extends String
) since the constraint is lost when monomorphizing T
. In that case the typechecker should enforce that the user is giving the full type before accessing to any method/field. There is also another type-hole when type parameters are used in static variables. I need to fix that also, but that’s of course weird usages already.
Variance : when dealing with type parameters, you will soon hit in the Variance problem. It can simply be stated as the following : if B extends A, given a class C<T>
, does C<B>
extends C<A>
(covariance) ? the contrary (contravariance) ? or not at all ? (invariance)
In haXe there is right now no variance, all type parameters are considered invariant. It’s actually a bit difficult to implement, I gave it two tries on Friday but wasn’t satisfied with the way code was heading so I dropped the changes. Some people might thing that all types are always covariant, since it seems pretty much logical at first sight, let’s give some examples and counter-examples :
The following class type-parameter is covariant :
class C<T> { var x : T; }
This is the case for most of the classes that are only “storing” some values.
OTOH, the following class type-parameter is contravariant :
class C<T> { public function f( x : T ) : Void { } }
Why ? Because a Function that needs a B
as argument can’t take a A
, while the other-way is true (assuming that B extends A
). We have then C<A> "extends" C<B>
, the subtyping relationship is reversed.
Here’s then an invariant class, easily obtained by mixing one contravariant and one covariant case :
class C<T> { public function f( x : T ) : T { // .... } }
In that case B -> B
is not a subtype of A -> A
, and the other way is not true either.
Modelizing Covariance in haXe is a bit tricky, and needs to use type-parameters and creates classes instances only for the sake of type-correctness, but it works pretty well. It’s an interesting exercice if you like this kind of things, but I won’t put an answer there since it’s not so much beautiful and might not be 100% correct since some type-holes still exists (see the previous note).
The best would be to allow variance notation on type parameters (like OCaml +/-) but that’s a bit tricky, I need to think more about which data structure model would be the best fitted for integration inside the haXe compiler.