Unification on an Array -- another Haxe surprise

[Jeff Ward]

Ok, so I'm running into fewer and fewer surprises the longer I work with Haxe. But this one still got me today.

See this example: https://try.haxe.org/#f4151

If unification can unify a typed Person to a HasAnAge, why can't it unify an Array<Person> to an Array<HasAnAge>? Seems quite natural to me.

Oddly, it can unify a literal [p,p2,p3] to Array<HasAnAge>, but not if it's already been assigned to a typed variable.

Even more insane, if you write your function with a generic, you can coax the compiler into realizing the unification should work, and it does:

  static function sum_age(people:Array<HasAnAge>) { } // Doesn't work

  static function sum_age<T:HasAnAge>(people:Array<T>) { } // Works!!

This wreaks of lore, surprises, and layers of features that work oddly together. This is (yet another) good example of the confusing surprises in Haxe.

Best,

-Jeff

[Justo Delgado]

Let's see, the first sum_age call array is Array<HasAnAge> because the type of the array is the type of the function parameter. The second one, the one that doesn't work, makes total sense to me because imagine you have a class Animal which also have an age field and that function tries to modify the Array<Person> you pass as a parameter, what's the type of the original array now? It's not Array<Person> because you pushed an Animal so it would break.

Remember that generics are a compiler-time feature, it will work because what you are telling the compiler is "hey, this function will only accept arrays which values have an age field, I don't care about anything else" At runtime that array would be an Array<Dynamic>

You can find a more technical explanation here https://haxe.org/manual/type-system-variance.html

[Justin Donaldson]

You're running into a very elementary aspect of type variance.  

https://en.wikipedia.org/wiki/Covariance_and_contravariance_(computer_science)

Without this restriction, you can run into this scenario E.g:

var arr = new Array<Person>();

arr.push(new Person());

var f = function(a:Array<HasAnAge>){
   a.push({age:12}); // not a person, just an object with an age.

}

f(arr); // arr now contains an invalid person!

Languages like Java work around this issue by doing runtime checking.  Haxe really can only rely on information at compile-time, so it prevents the type check from succeeding.

The anonymous array of People objects approach works because the Haxe compiler types the entire thing as HasAnAge.

-Justin

--
To post to this group haxe...@googlegroups.com
http://groups.google.com/group/haxelang?hl=en
---
You received this message because you are subscribed to the Google Groups "Haxe" group.
For more options, visit https://groups.google.com/d/optout.

[Juraj Kirchheim]

A literal array may get its type through top down inference. Assume you have this:

  var a:Array<HasAnAge> = [p, p2, p3]; 

The compiler thus knows to check every entry in the literal against HasAnAge, so it is not unlike writing this:

  var a = [(p:HasAnAge), (p2:HasAnAge), (p3:HasAnage)];

The next question is thus, why are Array<Person> and Array<HasAnAge> incompatible? The answer is, because Array is mutable and thus doesn't allow for variance. Here's why:

  var a:Array<Person> = [p, p2, p3];

  var b:Array<HasAnAge> = a;//let's assume this works

  b.unshift({ age: 12 });

  trace(Std.is(a[0], Person));//traces false

If it worked, it would create a type hole. But using an readonly type will work:

  var a:Array<Person> = [p, p2, p3];

  var b:Iterable<HasAnAge> = a;//this works

That's one way to tackle it. Another one would be this:

  static function sum_age<A:HasAnAge>(people:Array<A>) {

    var sum = 0;

    for (a in people) sum += a.age;

    a.push(a.pop());//not a problem, because all operations are performed on type A

    trace('The sum of your ages is $sum');

  }

I hope this clarifies things ^^

Best,

Juraj

[Juraj Kirchheim]

Well, that should answer it ^^

[Jeff Ward]

Thanks for the input guys.

Ok, I get the variance issue -- the compiler is providing safety against a potential situation with a mutable structure, the Array.

In this case, sum_age(people:Iterable<HasAnAge>) works great, as it allows me to express that I don't intend to modify the array. However, I could want to define a typedef which gives me something closer to an ImmutableArray. But oddly, typedef'ing some of the functions work fine (iterate, join, toString, etc), while others cause the unification to break (try uncommenting concat, indexOf, copy, etc) -- any ideas why?

Juraj, I didn't quite understand your explanation of why the type generic worked, but trying it myself, and trying to illegally arr.push({age:12}) -- the error is { age : Int } should be sum_age.T. Ah, fantastic, so inside the function we're strongly typed to T, and HasAnAge no longer applies. I can't push anything into the array that doesn't match the type that I called the function with (which defined T). Fascinating.

Best,

-Jeff

[Justo Delgado]

For the first issue, the same problem as before happens. Notice what the compiler errors tell you:

Test.hx:18: characters 16-25 : Invalid type for field concat :
Test.hx:18: characters 16-25 : a : Array<Person> -> Array<Person> should be a : Array<HasAnAge> -> Array<HasAnAge>
Test.hx:18: characters 16-25 : Cannot unify return types
Test.hx:18: characters 16-25 : Array<Person> should be Array<HasAnAge>
Test.hx:18: characters 16-25 : Type parameters are invariant

It tells you that the concat type you are passing to the function is not the same as the one the function expect and they can't be unified. Type Person isn't type HasAnAge so we are back to the initial problem we had before.


For the second issue, what you are using are type parameter constraints https://haxe.org/manual/type-system-type-parameter-constraints.html which just let the compiler know that what you are passing it has to have an age field not that the type is a HasAnAge type. Juraj example works because he's still working with type A: array.push(a:A) and array.pop():A are still working with the same type A. When you say array.push({age:12}) {age:12} isn't the same type as A

[Jeff Ward]

Thanks for the explanation, Justo. Honing in on those error messages is helpful, though I'm still trying to get my head around exactly why iterator works, while concat doesn't, and most perplexingly why indexOf doesn't. I'll have to think about it for a while. In the meantime, I'll mark this issue complete. Thanks all!

Man, this type stuff can be confusing. No wonder dynamic languages are so appealing. ;)

[Justo Delgado]

Basically the same happens with indexOf and all those functions, what's the result you expect from an Array<Person> when you ask it indexOf({age:12})? The types can't be unified http://haxe.org/manual/type-system-unification.html You can go from Person to HasAnAge but not the other way around. In the concat():T function the type that can't be unified is the return type. In the indexOf(a:T, ?fromIndex:Int):Int function they type that can't be unified is the first argument type.

Juraj's answer using an iterable works because the Iterable is immutable, you can read from it but not write to it.

[Jeff Ward]

Well, technically indexOf and concat are immutable operations on the Array. Besides, the compiler doesn't know whether a function's operation is immutable (unless there's some metadata I'm missing.) All it knows is the function signatures / types. Perhaps anything that uses T (except for iterator is a typedef, and map has a separate type generic) is not unifyable. Hmm...

[Justin Donaldson]

On Wed, May 24, 2017 at 3:02 PM, Jeff Ward <jeff...@gmail.com> wrote:

Well, technically indexOf and concat are immutable operations on the Array. Besides, the compiler doesn't know whether a function's operation is immutable (unless there's some metadata I'm missing.) All it knows is the function signatures / types. Perhaps anything that uses T (except for iterator is a typedef, and map has a separate type generic) is not unifyable. Hmm...

This isn't about immutability per se, it's really more of a general type theory thing.   Once a parameter is specified, then it will only accept that type (or something more specific) as an argument or return value.  If you're trying to unify types (e.g. merging two typed containers), you might break things out into a a static helper method:

https://try.haxe.org/#C5878

In order to drive the point home, try changing the order of arguments to that new "concat" method.  The parameter T will bind to first argument, and if it's less specific than the second argument then you can successfully create a container type that contains both argument types.   Reverse the arguments and it will fail.  Also note that we're specifying the container type to be returned in a very generic way.  All we need there is an instance with a "push" method, and there's examples of this working with a list and an array as the return value.  We've neatly decoupled all of the components and logic into simpler types, and lo, the gods of static type theory are pleased.

Hope this helps, and for the record I think stuff like this is an obstacle to Haxe adoption as well.   But, I don't want to go down the road of fudging types and being overly permissive with our collection library.  This tends to drive the maintainers insane.  (E.g.  https://youtu.be/uiJycy6dFSQ?t=1734 )

I would rather we continue to churn out good learning resources, even if that's a mostly thankless task.