implicit type classes with scuts and some macro magic

[Heinz Hölzer]

hey guys,

i have also an alpha version of scuts which brings haskell/scalaz like typeclasses to macro. If you want to play around with this stuff take a look at:

https://github.com/frabbit/scuts

i'm still hoping that with some small compiler features (especially type constructor polymorphism) here and there we could introduce type classes in haxe.

take a look at the documentation and the samples to get the idea of type classes.

best,

h

[Stephane Le Dorze]

Great,

Very nice effort Heinz!

For the end user; what would better reduce the noise? Having Ctor polymorphism or some sort of support to help with resolution (call site resolution / injection into scopes)?

Thanks,

Stephane

[Heinz Hölzer]

both of them ;). Ctor polymorphism is needed to make higher order types compatible with a Ctor representation like Of, without hard wire boxing functions for common types: see https://github.com/frabbit/scuts/blob/master/scutsHt/src/scuts/ht/core/Of.hx.

If you write your own Monads, Functors etc you have to modify the Of type and add aditional casting operations to it, or you have to use boxing functions which lifts these types into an Of representation. It would be enough to have Ctor polymorphism integrated by 2 special abstract types like Of and In, where the following representations are compatible:

Array<T> <=> Of<Array<In>, T>

Option<T> <=> Of<Option<In>, T>

MyOwnContainer<T> <=> Of<MyOwnContainer<In>, T>

that would allow writing your own monads functions without special hooks like in scuts now.

for call site resolution it would be nice to have a macro based hook prior to a function call on the call side:

let's say you could define the following function with the hook implicitHook which is a macro.

@:hook(implicitCall) public static function eq (x:T, y:T, Eq<T>) { .... }

when this function is called like eq(1,2) the compiler checks if eq has metadata for an hook and if yes, it wraps a call to implicitCall around it:

eq(1,2) && someFlag becomes implicitCall(eq(1,2)) && someFlag

implicitCall could resolve the required type class and returns an appropriate expression like:

eq(1,2, TypeClassInstances.intEq)

these 2 features would be awesome together ;)

best,

h

[Stephane Le Dorze]

About the latter, I can see an usage for lazy params too.. :)

What about having that at param level? (and how would it compose? - think several hooks)

Maybe we should move that discussion to github then..

[Heinz Hölzer]

What about having that at param level?

in case of type classes you need the type information of the other params. I think having them at method level is more flexible and powerfull.

(and how would it compose? - think several hooks)

good question, have to think about it ;) and how about saving a pointer to this function ?

[Stephane Le Dorze]

Maybe there's a simpler and more powerful feature..

Why not consider we can just specify a block to inline at a function callsite *prior* to macro application.

@:inline({  return injectTypeClass(eq(x,y)); }) public static function eq (x:T, y:T, eq: Eq<T>) { .... }

injectTypeClass being a macro support for type classe.

with usage:

isEqual = eq(foo, bar);

then it would expand to something equivalent to:

isEqual =

  function (x, y) {

    return injectTypeClass(eq(x,y));

  }(foo, bar);

but beta reduced to this (before macro application):

isEqual = {

  injectTypeClass(eq(foo, bar));

};

This would enable a lot of new use case which would rely on call site context.

What do you think?

Stephane

[Heinz Hölzer]

yes, seems to be very powerful ;), but how about syntax sugar, @:inline({  return injectTypeClass(eq(x,y)); }) is very verbose. 

And how to deal with function assignments and bind?

var x = eq.bind(a,_) // must be expanded o something like injectTypeClass(eq(x,_))

[Heinz Hölzer]

but it general call site injection is very powerful:

@:inline({  return onlyAdmin(doSomething()); }) public static function doSomething () {

}

@:inline({  return loggedCall(foo()); }) public static function foo () {

}

doSomething() is translated to onlyAdmin(doSomething())

foo() is translated to loggedCall(foo())

just to point out some non type class related example ;)

[Heinz Hölzer]

we should think about good use cases and make a proper proposal.

[Juraj Kirchheim]

Hi Heinz,

I'm sure this is pretty cool stuff, but to be honest, I don't really understand it.

I've looked at the samples and was unable to see what the point of all this is. Could you maybe make samples where one can see the difference between the scuts approach and a "classical" approach, so the reasons to use this become evident? It doesn't need to be many samples. 

When you ask practitioners of functional programming what it's good at, they usually respond with "everything of course!" ;)

Now personally I don't really care that I can use scuts to calculate the sum over a list of integers in a different way. But I would assume that there is at least one application of scuts' higher types, where it's evident that the plain Haxe equivalent's complexity would scale much worse with growing scope. Or maybe there's a whole different point to using it. But it would greatly help me and hopefully also others to really see that point in one single example. Most people are capable of extrapolating a whole strategy from a single set of data :D

Regards,

Juraj

[Stephane Le Dorze]

For those with objectiveC experience, it's like Categories but much much powerful (can be multitype) and (again) really *unintrusive*.

[Heinz Hölzer]

the basic concept of type classes is the separation of data and functionality that works on this data. In OOP you put them together.

here is a short description for the motivation of type classes in scala (easier to grasp from a haxe perspective than haskell):

http://stackoverflow.com/questions/15926655/what-is-the-motivation-for-type-classes-in-scala

this is an interesting paper from martin odersky (creator of scala):

http://lambda-the-ultimate.org/node/4039

there are also some good videos that descriptes them type classes in scala (if you're not afraid of it ;))

http://www.youtube.com/watch?v=yYo0gANYViE

http://www.youtube.com/watch?v=sVMES4RZF-8

i try to find some good haxe examples when i have more time ;)

best,

h

[Laurence Taylor]

The secret to the monadic stuff is that because the outer type is always preserved, you never lose access to any scope (it‘s always the same), and you can always refactor (because it’s always the same).

From what I can tell, higher types are nice because they allow you to build little implicit machines that operate behind the scenes with types of known functionality, and all you have to do is implement how a particular function works in a given case and it gets done automatically when that case comes up.

For example, "hello" + "world" and ['hello'].concat(['world']) are kind of the same function, and normally you would have to write a function to handle each type.
With higher types you can have a type that unifies those ideas, called a SemiGroup and then a function append (a1:A, a2:A):A; which allows you to write more general functions relying SemiGroup as an idea, but implemented differently based on the specific type.

You can't specify this sort of construct without higher types, it snarfs up the type system (technical term)

any help?

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.
 
 

[Stephane Le Dorze]

Yes, very true.

maybe when there's no block define in the annotation, then a simple on line could work:

@:inline(injectTypeClasse(eq(x,y))) 

Also it seems we had another candidate usage here, involving abstracts which requiers to subtitue Type params:

https://groups.google.com/forum/#!topic/haxelang/lx_Se5sBeCQ

erk - that bind is indeed sad, (the simpler, homogenous  'eq(a, _)'   would have worked fine however).

Actually it would have been expanded to something lijke:

function (y) { return injectTypeClass(eq(x,y));}

I have nothing yet to propose here - the parameter solution would work fine, but does not covers the needs.

the proposed solution, however, works with the (more verbose) desugared version of bind so it is still usable.

[Heinz Hölzer]

maybe bind could be handled by the compiler because it's a special case anyway.

[Stephane Le Dorze]

Maybe we could wait the weekend to give one the ability to react on this before making a proposal if nothing else to discuss.

[Heinz Hölzer]

yes and we need another proposal for type constructor polymorphism. I think it would be enough to add two special abstract types e.g. Of and In (which could live in a package like haxe.tcp) so that the following rules apply:

Array<T>       are always convertible to and from      Of<Array<In>, T>
Option<T>      are always convertible to and from      Of<Option<In>, T>
Whatever<T> are always convertible to and from      Of<Whatever<In>, T>

this must also work for composed types:

X -> Whatever<T>              to and from       X -> Of<Whatever<In>, X>
Whatever<Whatever<T>>   to and from       Whatever<Of<Whatever<In>, T>>    
Whatever<Whatever<T>>   to and from       Of<Whatever<In>, Whatever<T>>

so that Of<Whatever<In>, T> acts like a typedef for Whatever<T> for example.

the following expressions have to be working:

var x:Of<Array<In>, Int> = [1];
x.concat([]);
x.concat([2]);

var z:Array<Int> = x;

then you can define a Functor like so:

interface Functor<F> {
    public function fmap <A,B> (a:Of<F, A>, f:A->B):Of<F,B>;
}
class ArrayFunctor implements Functor<Array<_>> {
    public function fmap <A,B> (a:Of<Array<In>, A>, f:A->B):Of<Array<In>,B> {}
}

and write static functions like:

static function fmap<F,A,B>(val : Of<F, A>, f:A->B, functor:Functor<F>) {
    return functor.fmap(val, f);
}

than we could also allow the syntax F<A> in functions which just maps to Of<F,A> like:

static function fmap<F,A,B>(val : F<A>, f:A->B, functor:Functor<F>) {
    return functor.fmap(val, f);
}


to get rid of the "In" marker type, you can think about syntax sugar like:

Array<_> <=> Array<In>

_->_ <=> In->In

do i miss something???

best,
h

--

[Heinz Hölzer]

i think we need this rules too:

Either<A,B> is always convertible to and from      Of<Of<Either<In, In>, A>, B>

Either<A,B> is always convertible to and from      Of<Either<A, In>, B>

Either<A,B> is always convertible to and from      Of<Either<In, B>, A>

A -> B  is always convertible to and from      Of<Of<In->In, A>, B>

A -> B  is always convertible to and from      Of<A->In, B>

A -> B  is always convertible to and from      Of<In->B, A>

i think we can limit higher order types to a degree of 2, or is this a bad idea? (should be easier to implement).

[Heinz Hölzer]

no not really, we just need:

Either<A,B> is always convertible to and from      Of<Either<A, In>, B>

Either<A,B> is always convertible to and from      Of<Either<In, B>, A>

A -> B  is always convertible to and from      Of<A->In, B>

A -> B  is always convertible to and from      Of<In->B, A>

A -> B -> C is always convertible to and from      Of<A->In->C, B>

A -> B -> C is always convertible to and from      Of<In->B->C, A>
A -> B -> C is always convertible to and from      Of<A->B->In, C>

Whatever<A,B,C,D> is always convertible to and from      Of<Whatever<In,B,C,D>, A>
Whatever<A,B,C,D> is always convertible to and from      Of<Whatever<A,In,C,D>, B>
Whatever<A,B,C,D> is always convertible to and from      Of<Whatever<A,B,In,D>, C>
Whatever<A,B,C,D> is always convertible to and from      Of<Whatever<A,B,C,In>, D>

etc.

everything else should be lifted manually, right?

[Stephane Le Dorze]

I find this quite confusing..

Of<Of<Either<In, In>, A>, B> could be converted to either Either<A, B> or Either<B, A>

To make it exclusive, we have to assume a specific type binding order (like you showed in your example).

Enforced by this proposition:

Of<T<In, In>, U> is convertible (to/from) T<U, In>

Imposing a limitation to a the degree of 2 is not necessary at this point as the compiler team may prove to be smarter than us.. :)

However, we can state it may be sufficient (until proven wrong).

[Heinz Hölzer]

hey juraj,

i created an example which compares the oop and the type class approach in haxe. It's just about type classes (you don't need to understand higher types at all, that's a different topic).

https://gist.github.com/frabbit/5885145

best,

h

On Tuesday, June 25, 2013 12:13:22 PM UTC+2, back2dos wrote:

[Juraj Kirchheim]

Thanks a lot Heinz, will have a read tonight ;)

--

[Juraj Kirchheim]

Ok, I think I got it. Let me try to put that into "OOP terms".

The way I understand it, this is about two things:

1. rather than bloating your individual objects, you write your code against abstract services (e.g. CompareX<T> is a "service" that compares two values of type T) that operate on those objects

2. you some mechanism, that automagically selects concrete implementation of those services

And the really nifty part is step 2 (which is what the `_` does or in Scala/Haskell the language semantics do). If we look at it from this angle, I think the idea is roughly equivalent to "dependency injection". Would that be fair to say?

Regards,

Juraj

[Heinz Hölzer]

1. that's correct.

2. yes it selects concrete implementation based on some rules (1. search in locals, 2. search in instance methods (if we are in an instance method), 3. search in statics of the current class, 4. search in the using context). And yes it's like dependency injection. In scala for example you have the implicit keyword that can be used to mark variables/functions as available for implicit resolution. You also can mark function parameters as implicit which means you can either pass them explicitly or let the compiler search for a compatible object in the context of the current call.

In scuts the function "_" or "resolve" does more or less the same as the implicit language feature in scala, it can be used to search for a compatible object (it doesn't have to be a type class (which are in haxe/scala just ordinary objects) at all.

e.g. you can mark a local variable as available for implicit resolution in scuts like this:

function add (a:Int, b:Int):Int return a + b;

Ht.implicit(5);

add._();

which gets translated to

var __implcit5 = 5;

add(__implcit5,__implcit5);

best,

h

[Heinz Hölzer]

And to understand higher order types it could be useful to try to abstract the function map found in list, array, map into an interface. Call it Mappable or whatever and try to return the concrete type (Array, List, Map) and not a common type like Iterable.

Something like this:

interface Mappable ...

class MyArray<A> implements Mappable ... {

  public function map <B>(f:A->B):Array<B>;

}

class MyList<A> implements Mappable ... {

  public function map <B>(f:A->B):List<B>;

}

class MyMap<K,A> implements Mappable ... {

   public function map <B>(f:A->B):Map<K, B>;

}

best,

h

On Friday, June 28, 2013 9:56:47 PM UTC+2, back2dos wrote:

[Heinz Hölzer]

the problem is that you want to have something like this:

interface Mappable<F, A> {

   public function map <B>(f:A->B):F<B>;

}

or 

interface Mappable<F<_>, A> {

   public function map <B>(f:A->B):F<B>;

}

to express that F is some kind of an abstract container (also called type constructor) without specifying exactly which container it is. A type constructor is a like a function which needs another type to become a concrete type. Array needs T to become Array<T>, Option needs T to become Option<T>. 

Functions can also be type constructors A -> needs B to become A -> B (think  Function<A,B> = A->B). To avoid confusion think about Function as a type constructor that needs 2 types (A and B). After applying A it is a type constructor that only needs one additional type (Function<A needs B to become Function<A,B>).

hope this helps.

[Heinz Hölzer]

the 5 in __implcit5 could also be some other random number, it just get's increased for every local implicit variable.

[Justin Donaldson]

Thanks for this Heinz, it's a very helpful overview.

I tried compiling your TypeClassDescription example to try and play around with it... I add the "using scuts.ht.Context" directive at the top, and changed the name of the file to TestX, but didn't change anything else.  I placed it in the root of your scuts repo, and added the right cp in a test build file, etc.

I'm getting an error around line 113:

// with using it becomes

new MyClassX(1).eq(new MyClassX(2), new MyClassXEq());

MyClassXEq should be scuts.ht.classes.Eq<MyClassX>

What did I do wrong?

Best,

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

--
blog: http://www.scwn.net
twitter: sudojudo

[Heinz Hölzer]

this is a working sample, there are still some issues with macros and private types (you know what i mean ;)), so it's better to separate definition from usage.

[Justin Donaldson]

I always forget about that problem, thanks!

-Justin

[Justin Donaldson]

I think I get the big picture a lot better now.  Just some general thoughts...

I suppose in case of a conflict (e.g., two classes implementing ArrayEq<T>), the last one defined is used to handle the  (eq) method?

It's very clever!

Is there a way to avoid using the underscore to specify the macro lookup method? e.g. new MyClassX(1).eq._([etc...]);

For some reason, that looks really strange to me.  I'd rather have a small named method that's giving a clue as to what's going on.

However, it's only a minor gripe, I really like the implementation overall.

Best,

-Justin

[Heinz Hölzer]

hey justin,

i added a sample on how to define your own type class and instances and how you can use it.

https://github.com/frabbit/scuts/tree/master/samples/src/scuts/ht/samples/jsonSample

I suppose in case of a conflict (e.g., two classes implementing ArrayEq<T>), the last one defined is used to handle the  (eq) method?

Yes currently the last one is used, the behaviour is oriented on import/using shadowing, however you can explicitly control which type class is used (take a look at the json example) when you need it. That's also the reason why there are 4 (at the moment) different scopes with different priorities: 1.local, 2. member fields/vars, 3.statics, 4.using context

It's also possible to add some compiler flags that looks for all matching type classes (takes longer, than returning the first compatible) and give some warning/error/info. 

Is there a way to avoid using the underscore to specify the macro lookup method? e.g. new MyClassX(1).eq._([etc...]);
For some reason, that looks really strange to me.  I'd rather have a small named method that's giving a clue as to what's going on.
However, it's only a minor gripe, I really like the implementation overall.

yes you can use  scuts.ht.core.Ht.resolve, but it's set to "noUsing" to not pollute the namespace. But you can remove "noUsing" or write your own macro which does the same (it's a one liner macro).

However, it's only a minor gripe, I really like the implementation overall.

thx a lot, one problem currently is that it's not that easy to write your own monads, functors, etc. (that's why we need type constructor polymorphism), but that's a different topic ;)

best,

h

[Stephane Le Dorze]

and one could start thinking about a Bijection<T, U> type classe to map from/to json compositionnaly..

..real power! so happy :)

[Heinz Hölzer]

if you find some time, feel free to add an example ;)