haXe Polymorphism and Variance

posted on 2006-03-27

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

Javascript and W3C DOM

posted on 2006-03-11

I’m currently writing the haXe interfaces for Javascript DOM Api. What a mess ! There is the W3C DOM, which is a recommended standard, with several versions, not completely implemented on different browsers, then each browser comes with its own extensions, sometimes compatible accross browsers, sometimes incompatible.

It is then not easy to comeup with a single interface. What I’m doing for haXe is the following :

  • have the standard interface supporting the things supported by both IE6 and Firefox 1.0.x
  • have several compilation flags to disable some fields and ensure more strict compatibility
  • the ie5 flag will ensure ie5 compatibility by disabling ie6-specific fields
  • the w3c flag will disable fields that are not w3c compatible

Conditional compilation is really a great help there. In the future when interfaces improve I will add the latest FireFox 1.5 APIs that will be turned ON with ff15 or another flag.

Other problem is inherent dynamicity of some fields, that can be of several types (Integer or String, with different formats). Having more strictly typed and sound API will be something interesting, but difficult to do. If I could get a hold on the guy responsible for all of this, I would have a few words to say to him :)

Hopefully haXe will greatly help developers to go through this jungle.