Calendar

September 2017
Mo Tu We Th Fr Sa Su
<< >>
123
45678910
11121314151617
18192021222324
252627282930

Langs

Haxe Polymorphism and Variance

Posted on Mar 27 2006

I 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 definitely, 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 type checker. Pair.make("hello",0) get rejected, saying that the Int 0 is not a String. Since every time 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 constraint on the type T (like T extends String) since the constraint is lost when monomorphizing T. In that case the type checker 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.

Modeling 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 exercise 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.

0 comment
Name : Email : Website : Message :