Type constructor polymorphism and higher kinded types (working branch)

[Heinz Hölzer]

Hey guys,

i'm currently working with simon on these features. It would be great to get some feedback (also compiler implementation feedback) and testing.

Hopefully (i'm looking at nicolas ;)) this will get accepted somewhere in the future ;)

you can find the current state of the repository here: https://github.com/frabbit/haxe-1/tree/dev_of

here you can find some type definitions: https://github.com/frabbit/haxe-1/blob/dev_of/tests/unit/MyTypeConstructor.hx

and here some tests: https://github.com/frabbit/haxe-1/blob/dev_of/tests/unit/TestTypeConstructor.hx

here is one example to get a glimpse of what you can do with it (the usage of typedefs is just an example, you can also use interfaces and classes):

typedef Mappable<M:Mappable<M,In>,T> = {

  public function map <B>(f:T->B):M<B>;

}

typedef Filterable<F:Filterable<F,In>,T> = {

  public function filter (f:T->Bool):F<T>;

}

typedef FilterAndMappable<M:FilterAndMappable<M,In>,T> = {

  > Mappable<M,T>,

  > Filterable<M, T>,

}

class Test {

        static function test () {

                // create an array and a list

var a = [1,2,3];

var b = new List(); b.add(1); b.add(2);

trace(filterAndMap(a));

trace(filterAndMap(b));

// notice, the actual return type doesn't get lost

trace(filterAndMap(a)[0]);

trace(filterAndMap(b).first());

}

static function filterAndMap <M:FilterAndMappable<M,In>>(x:M<Int>) 

{

return x.filter(function (x) return x > 1).map(function (x) return x + 2);

}

        // alternative with multiple constraints

static function filterAndMap2 <M:(Mappable<M,In>, Filterable<M,In>)>(x:M<Int>) 

{

return x.filter(function (x) return x > 1).map(function (x) return x + 2);

}

}

You may notice the strange "In" type, it actually represents the "missing" or not "applied" inner type. If you look at the unit tests you may also see "Of" types, a definition like M<T> is actually translated to Of<M, T> inside of the compiler, but in same cases it can be useful to use them directly this.

best,

h

[Stephane Le Dorze]

Awesome Heinz!!!

That would mean that we can factorize more code and have more typed Apis.

For those wondering (WTF?):

This line:

static function filterAndMap2 <M:(Mappable<M,In>, Filterable<M,In>)>(x:M<Int>) 

indicates that if a 'container' type M match both the definitions of Mappable and Filterable

which are:

typedef Mappable<M:Mappable<M,In>,T> = {

  public function map <B>(f:T->B):M<B>;

}

typedef Filterable<F:Filterable<F,In>,T> = {

  public function filter (f:T->Bool):F<T>;

}

more succinctly; that this container have both methods:

  public function map <B>(f:T->B):M<B>;

  public function filter (f:T->Bool):M<T>;

Then one could use this method (it will work):

static function filterAndMap2 <M:(Mappable<M,In>, Filterable<M,In>)>(x:M<Int>) 

and have the return type correspond to the specific M container.

for Instance you may use it with a List, Array, Hash, Tree, etc.. (any Monad actually for this particular signature :) )

Thanks again Heinz!

Stephane

P.S.: We can expect even shortest Js libraries outputs :)

[Laurence Taylor]

Good news indeed! congrats.

Laurence

--
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/groups/opt_out.

[Heinz Hölzer]

For everyone who wants to play with it i uploaded two binary (sorry no mac available) of the compiler + std lib here:

win64:   https://dl.dropboxusercontent.com/u/21847103/haxe_higher_kinded_types_win64.zip

linux64: https://dl.dropboxusercontent.com/u/21847103/haxe_higher_kinded_types_linux64.tar.gz

[Heinz Hölzer]

Another Example:

typedef Filterable<F:Filterable<F,In>,T> = {

  public function filter (f:T->Bool):F<T>;

}

// Haxes Maps has no filter method, so we have to write a wrapper for it

class MyStringMap<B> {

var elems : Map<String, B>;

public function toString ():String {

return "MyStringMap: " + elems.toString();

}

public function new (elems:Map<String,B>) {

this.elems = elems;

}

public function filter (f:B->Bool)

{

var x = [for (k in elems.keys()) if (f(elems.get(k))) k => elems.get(k)];

return new MyStringMap(x);

}

}

// now let's write a type that uses container that's filterable and has a toString method.

class Whatever<M:(Filterable<M, In>,ToString),T> {

// i don't care what's the concrete type of the container is, as long as it's a container with elements of type T

var container:M<T>;

public function toString ():String {

return "Whatever: " + container.toString();

}

public function new (container:M<T>) {

this.container = container;

}

public function filterBy (f:T->Bool) {

return new Whatever(container.filter(f));

}

}

// let's use this stuff:

class Main {

        public function main () {

                // use it with arrays

                var w = new Whatever([1,2,3]);

trace(w.filterBy(function (x) return x > 2));

trace(w.filterBy(function (x) return x < 2));

                // use it with lists

var l = new List();

l.add(1);l.add(2);l.add(3);

var w = new Whatever(l);

trace(w.filterBy(function (x) return x > 2));

trace(w.filterBy(function (x) return x < 2));

                // use it with StringMaps

var x = new MyStringMap(["foo" => 1, "bar" => 2]);

var w = new Whatever(x);

trace(w.filterBy(function (x) return x < 2));

     }

}

On Saturday, January 18, 2014 2:54:54 AM UTC+1, Heinz Hölzer wrote:

[dlots]

It's all very nice but typing and generics are utterly broken if these bugs regarding self constrained and nested generics aren't fixed:

https://github.com/HaxeFoundation/haxe/issues/2086
https://github.com/HaxeFoundation/haxe/issues/2085

Don't introduce typing features that facilitate the utterly mistaken presumption that generating a bunch of Dynamic to the targets is acceptable. I don't know whether this does or doesn't but if you do introduce additional Typing facilities please be preprared to support them in a correct way across targets.

As stated in that bug, at this time there is no generic typing in Haxe from my perspective which is absurd.

I truly don't understand how those bugs aren't of the highest priority.

[David Elahee]

I agree with dlots a lot of features are still partially broken or inconsistent. The abstracts are still not fully finished and proven solid imvho, so i would like us to stop adding abstraction hype feature that open new doors.

Thanks and sorry to play against the team.

[Heinz Hölzer]

hey guys,

it was actually my idea to implement this feature and simon helped me here and there. So it's not a team decision to implement this feature. I don't even know what's nicolas opinion on this. So it's currently not more than a proof of concept and I wanted to get some people testing who are interested in such a feature.

In my opinion higher kinded types are a very powerful concept, that's the reason why i was motivated to work on it. For me that was always a huge shortcoming of haxe, just like the problems with @:generic for you. 

As far as i know the changes that i've done doesn't affect any other feature, but this also needs testing. And from my point of view this feature doesn't really affect the problems that currently exist.

Don't introduce typing features that facilitate the utterly mistaken presumption that generating a bunch of Dynamic to the targets is acceptable. I don't know whether this does or doesn't but if you do introduce additional Typing facilities please be preprared to support them in a correct way across targets. 

like i said, it's a proof of concept and i'm also interested to get the most out of it if possible. Performance was not my first aim, as a first step i wanted to create a feature that works reliable, i'm currently in this phase and it's working quite well so far. If that's done i'm happy to optimize it.

 

best,

h

[Simon Krajewski]

Am 18.01.2014 20:58, schrieb David Elahee:
>
> I agree with dlots a lot of features are still partially broken or
> inconsistent. The abstracts are still not fully finished and proven
> solid imvho, so i would like us to stop adding abstraction hype
> feature that open new doors.
>
> Thanks and sorry to play against the team.
>

I don't get it, are you suggesting people should stop experimenting with
the compiler in their free time just because there are issues you
consider more important? That makes you sound a bit like a spoilsport.

Heinz has done a great job and it's amazing to see the possibilities
that arise from this! Cheer up and don't hijack his thread with your own
issues. ;)

Simon

[Heinz Hölzer]

and to be honest, it will always be the case that new features and bugfixes are implemented in parallel. It's an open source project, show my one example where this is not the case.

On Saturday, January 18, 2014 8:58:27 PM UTC+1, David Elahee wrote:

[Heinz Hölzer]

actually simon helped me a lot to get the foundation for this feature working ;)

[dlots]

I was going to post a further explanation as to what I meant but in the end it all just comes off as complaining for those 2 bugs (which I'm not in the sense that I am capable of averting those bugs in the meantime, the developers work on haxe is immense, I just actually literally don't understand why you guys would use non @:generic code in places where @:generic is the correct solution, ie quite a few).

I guess my point is that I'm wary of typing in haxe because I've had to workaround typing that was 100% logically sound (but this is certainly irrelevant to this great work in experiment) and, 2 I think it might be a good idea to limit facilitating unwarranted Dynamic generation sneek it's way into community libraries.

Sorry for hijacking this thread.

On Friday, January 17, 2014 8:54:54 PM UTC-5, Heinz Hölzer wrote:

[Stephane Le Dorze]

I though I already sent such an email but cannot see anything in the thread..

..so I guess I had to send it 'again' :)

May it make our next release as an experimental feature?

Best,

Stephane

[Heinz Hölzer]

I would love too see this as an experimental feature, but i don't decide ;).

[chunbiao huang]

cool  

2014/1/21 Heinz Hölzer <heinz....@googlemail.com>

[Jason O'Neil]

Looks like a cool feature! 

With "M:FilterAndMappable<M,In>", are the "In" and "M" parameters conventions from another language?  Having never really looked at higher kinded types it seems pretty foreign, and not very self explanatory, so I'm wondering if there is a specific reason for those parameters / names, or if there is somewhere else I can read up about it.

Thanks for working on it, I'm keen to learn more...

[Stephane Le Dorze]

'In' is a conventional type parameter; its meaning is: 'not defined yet', In scala for instance it is written '_' which clearly states it has a particular meaning.

M is not a conventional type parameter, it's your parametrized type (think container to help reason about it, like List or Array).

A Higher kind type means that the type is not fully defined and need another type param to be completely defined.

So it a function in the space of Types.

As we're in the space of Types, we don't say this function has a type but a 'Kind'.

In the space of types:

String kind is: *

List<String> kind is : *

List (which is T -> List<T> ) kind is: * -> *    so List is a 'type function' - with Heinz proposal it is written List<In>

One may think about kind: * -> * -> *  It has no additional value and is not required as it is equivalent to: (* -> *) -> * 

With Generics code you may not know the Type parameter of the element; List<T>; T is not known

With Higher Kind you may not know the the Type of the container; you just known you'll have one Type function (List is a type function) passed in to defined the type. (think the 'container')

M<In>; M is not known but we know his kind is * -> * so if you may pass an Int; it would then be M<Int> with M not known; (In Heinz implementation of the proposal, applying Int to the type M<In> would be written Of<M<In>, Int>; Of acting as an application at the type level)

Hopefully, he works on the type system to prevent us to have to deal with that boilerplate. :-)

If you think about it it's always just basic application.

This is the gist of the new abstraction.

The beauty of the thing is that you may still impose some constraints on it; say it's something I can filter on:     M:Filterable<M, In>, so M is something I can filter on whatever it is.

So there's a lot of valid programs you may now express with this abstraction.

Most of them exploiting a higher degree of factorization, leading to smaller code base, more reusability / less coupling.

It will ease the job of library writers / architects.

This new expressive power in the type system is a corner stone to fully implement Type Classes.

Type classes is a mechanism to extends a type non intrusively.

For instance, Imagine:

There is no Filter related method on List, we don't care, we can provide it afterwards.

- But we can already do that with Lambda!

- Yes but we loose the container type; I would like to have my filter function return a List if the source container type is a List or and Array if the source container is Array (that why Higher Kinds kicks in).

- Ah Ok..

- Ok so I would like to extends List / Array / Whatever without touching those (coz I don't want to fork and maintain the Std).

- But you can't.

- Yes, the only possible thing is to pass all the type specific filtering functions in each method I call in my own code..

- That is too much Boilerplate; hard to maintain, very verbose.. it would be better to just write the types constraints.. no?

- Yes!

- That's Type Classes?

- Yes! :)

- Wow.. o_O

I hope it helps seeing some use cases..

Best,

Stephane

You received this message because you are subscribed to a topic in the Google Groups "Haxe" group.

For more options, visit https://groups.google.com/groups/opt_out.

--

Stéphane Le Dorze

http://lambdabrella.blogspot.com/

http://www.linkedin.com/in/stephaneledorze

http://twitter.com/stephaneledorze

Tel: +33 (0) 6 08  76 70 15

[Heinz Hölzer]

The In type maps currently one to one to the implementation, but of course from the synatx side i would prefer _, so that you example would become M<M:FilterAndMappable<M,_>>. "?" would also be an option M<M:FilterAndMappable<M,?>>.

[Stephane Le Dorze]

I'm coming back on the subject.

Is it a good time to merge it on the trunk?

What's missing?

[blue...@gmail.com]

I'm used to the scala syntax _  and think it indeed looks nicer, as it looks like a placeholder :-)  Also in switch { case _ : .. } is the catch all case, so that would make it more uniform IMHO...

Op woensdag 22 januari 2014 10:27:48 UTC+1 schreef Heinz Hölzer:

[Stephane Le Dorze]

Any chance to get it considered for integration???

[Franco Ponticelli]

Is this still under construction? Will we ever see it in the compiler?

I'd really love to have it.

Franco

[Stephane Le Dorze]

I think this feature is not well understood by the community, so I would not be very positive on that outcome, sadly.. :'(

[Stephane Le Dorze]

Would love to hear about it from Heinz / Simon / Nicolas..

[Franco Ponticelli]

It would be a great feature for experienced developers and a really important learning tool for less experienced one. That together with arrow functions and I could be a happy man.

For more options, visit https://groups.google.com/d/optout.

[Stephane Le Dorze]

You may have more chance to becone happy by switching to purescript then..
It s been two years now..