20.7k
views20
comments

This post is mostly targeted F# team, but public debates are welcome.

Since F# source code is public domain, a community can take part in development process. I've already seen here some posts about type class feature. So, IMHO, it would be nice to bring it to F#.

Current state

After a couple of weeks rushing into a "type class feature in .NET" problem, I can now propose a way to make it possible. I've started with mapping type classes to OO model of CLR. Here is the result.

As you can see from docs, I've mapped type class to abstract generic class, and type class parameters to generic class parameters. Usage is listed in docs. Implementation uses reflection API.

To use a type class feature, you must access NTypeClasses.TypeClass<YourTypeClass<arg1, arg2, ...>>.Instance. This is the only object of dynamically generated type derived from YourTypeClass<arg1, arg2, ...>. For each virtual method in your type class (including get_PropertyName and set_PropertyName methods generated from properties), implementation is searched in arg1, arg2, ... classes and in all classes marked with NTypeClasses.TypeExtensionAttribute. If one is found, the corresponding method in YourTypeClass<...> is overriden with single call instruction that passes arguments to implementation method. If method is abstract, such an implementation must exist or you'll get TypeLoadException.

I've also made a program to check if all type arguments used in type classes have such an abstract methods implemented. This can be called on assembly after successful compilation to check that all type class usages is valid. So it is possible to check types after compilation in any .NET language.

Ok then, it seems I'm not very good in explanation, but I hope you got that.

To be done, integrating to F#

Now I'm willing to bring some syntactic sugar for this feature into F#. Here's an example of what I'm trying to make work:

// defining type class Eq with = and <> operations
[<AbstractClass>]
type Eq<'a> =
    abstract member (=): 'a * 'a -> bool
    abstract member (<>): 'a * 'a -> bool
    default this.(<>)(a, b) = not(this.(=)(a, b))
    
// defining generic vector which requires 'a to be from Eq
type Vector3D<'a when Eq<'a>> =
    [<DefaultValue>]
    val mutable X: 'a
    [<DefaultValue>]
    val mutable Y: 'a
    [<DefaultValue>]
    val mutable Z: 'a
    
    static member (=)(Vector3D<'a> a, Vector3D<'a> b) =
        // resolving = from Eq, using TypeClass<Eq<'a>>.Instance.(=)
        a.X = b.X && a.Y = b.Y && a.Z = b.Z

Problems and things to discuss

The first problem is lack of documentation on how F# compiler works internally. Since its code is pretty large, it seems hard to find right places to insert new code, and what part of existing code could be reused in new code. I've put "when TypeClassName<args>" support into parser, so that it produces an AST node for this. There are some things to be done: write this constraint into class's info, inherit constraints from type class, fix method and operator resolution so that type class's members can be used, and check that all methods and properties are implemented with type class args with fully instantiated type class. Also, currently, there's a possibility in F# compiler to add a constraint to typar, but this feature requires single constraint for multiple typars (though one can always add the same constraint instance for multiple typars).

The second problem is that current F# implementation does not support defining static read-only fields I've used in many cases for NTypeClasses implementation. So, I can't integrate the code into FSharp.Core as is.

The third problem is compatibility with other .NET languages. There are some ways: integrate support code into FSharp.Core and require all other languages to reference it to use type classes, develop FSharp.Core integration in parallel with NTypeClasses, and use NTypeClasses from F# compiler.
---
"I think this will never be possible in any .NET language" by Brian McNamara

In my opinion type classes are not really helpful without higher-kind generics abstraction. And F# does not have that, nor does .NET. In fact, I would probably be more happy with ML-style modules (and their flavor of higher kinds) than with type classes. If I were to design a better language than F# right now, I would go for OCaml-like core with modules (and therefore higher-kinded generics), and I would probably opt for the modules to be erased by abstract interpretation like MLton does. This would leave core ML which the compiler could then handle the same way as F#.

The problem with F# is the extra complexity of objects and subtyping. Treating F# extended with higher kinds and modules formally in presence of OO sounds like a real challenge. Again, if you ask me, I'd throw OO out..

By Anton Tayanovskyy on 12/7/2011 10:29 AM (permalink)

I agree, if at some point the F# team decides to implement Typeclasses at CLR level or at least as an F# compiler feature, they should first upgrade the type system in order to support Higher Kinds.

However the technique I use still allowed me to define (kind-of) typeclasses of higher kind types like Monad, Category, etc.
But it's true that becomes a little bit tricky to figure out how to specify types for Haskell wrappers (i.e. Kleisli) with a "hat" type, where the original type is HK.

By Gustavo Leon on 12/9/2011 3:11 PM (permalink)

Adding HK types to the CLR is a popular request, but has been officially declined by MS.

By Daniel Robinson on 2/14/2012 8:37 AM (permalink)

Just looked at your code. Inlining is nice. However, here:

type Ap = Ap with
    static member (?<-) (f:option<_>, _Applicative:Ap, x:option<_>) = ap f x
    static member (?<-) (f:list<_>  , _Applicative:Ap, x:list<_>  ) = ap f x
    static member (?<-) (f:IO<_>    , _Applicative:Ap, x          ) = ap f x
    static member (?<-) (f:_ -> _   , _Applicative:Ap, g: _ -> _  ) = ap f g

Does not this mean that one can't add new instances without recompiling the whole project? That would be a deal-breaker for me at least. The point is code reuse: if instance set is fixed, you can't reuse nice functions like `sequence` for arbitrary monads.

By Anton Tayanovskyy on 12/9/2011 3:28 PM (permalink)

You can add instances later, in another module or even another assembly, that's not a problem, except if you try to add an instance outside it's own type definition, see my previous answer about the orphan instances limitation.
That code could be perfectly split this way:

type Ap = Ap with
    static member (?<-) (f:option<_>, _Applicative:Ap, x:option<_>) = ap f x
    static member (?<-) (f:list<_>  , _Applicative:Ap, x:list<_>  ) = ap f x
    static member (?<-) (f:_ -> _   , _Applicative:Ap, g: _ -> _  ) = ap f g
let inline (<*>) x y = x ? (Ap) <- y

in another module

type IO<'a> = IO of (unit->'a) with
// ...  implement Bind and Return 
    static member (?<-) (f:IO<_>    , _Applicative:Ap, x          ) = ap f x
// ...

// now you can use <*> with IO

But for option , list and (->) you can't because they're already defined, so either you add the instances in the Ap definition or you do it later with a wrapper type (as I did with ZipList in that project).

See the example in the section Adding new instances to existing Typeclasses

In short: yes, you will be able to re-use sequence without recompiling, as long as new operators as static member come into scope, because they will be included in the operator overloading resolution.
If you find errors while trying to do this please tell me, I will be interested to be able to reproduce it.

By Gustavo Leon on 12/9/2011 4:41 PM (permalink)

Nice! Did not realize this.

By Anton Tayanovskyy on 12/12/2011 8:56 AM (permalink)

Could you explain what type classes would be like in F# without higher-kinded types? I always thought have the former required the latter. Would they be useful at all?

Also, do you know of any resources that compare the type class approach of Haskell to the module approach of Ocaml? I'd like to fully understand the trade-offs.

Thank you!

By Bryan Edds on 12/7/2011 10:11 PM (permalink)

Without higher kinds type classes could be somewhat useful, since F#'s primary problem is lack of HK not TC I think we should look in that direction first.

In Haskell parlance, for example, without HK, Monad and even Functor classes are not definable. Num and Eq are definable. This can be useful of course in its own way. But I maintain that the biggest problem is lack of HK and therefore true monads. ML easily has true monads with modules.

There is a nice proposal to integrate TC into the ML module system that also compares TC and modules, see the Modular Type Classes paper:
[link:www.mpi-sws.org]

Disclaimer: I may sound like an expert but I am not (yet) one, I have not yet implemented either TC or even ML modules myself.

By Anton Tayanovskyy on 12/8/2011 7:23 AM (permalink)

I have seen lots of people thinking about typeclasses for F# lately, and have wondered if it would be possible to implement it elegantly using macros (see my blog post). The good thing about macros that could help with typeclasses, is that you can have short and readable code, while the compiler actually does a lot of work. This means that the solution doesn't have to be simple, as long as a computer can generate code to make it work.

By Ramon Snir on 12/7/2011 1:32 AM (permalink)

My suggestion for higher-order modules might help you/give you ideas.

By Ramon Snir on 12/10/2011 8:00 AM (permalink)

I really want to see type-classes in .net but I think you have to support them at CLR-level to make them work

By Carsten Koenig on 1/12/2011 11:37 PM (permalink)

I would like to share my approach to Typeclasses in F#.
It doesn't work at CLR level but it's type-safe because it works at compile-time.
I use inline functions and operators (in fact just one) to avoid writing ugly "when" constraints.
Playing with this technique I was able to define most Typeclasses from Haskell including Monad Transformers.
I have a post here that explains the approach and a project at code.google that mimics Haskell Typeclasses using this technique, which I use sometimes as base library for my F# projects.
Your feedback is much appreciated.

By Gustavo Leon on 12/6/2011 12:35 PM (permalink)

This is a very interesting workaround indeed.

I played with it a little, and I found that the following also works:

#nowarn "64"
type Fmap = Fmap with
  static member fmap (Fmap, x : option<'a>) = fun f -> Option.map f x
  static member fmap (Fmap, x : list<'a>) = fun f -> List.map f x

let inline fmap f x =
  ((^a or ^b) : (static member fmap : ^a * ^b -> _) (Fmap, x)) f

It's a little more verbose and requires a nowarn to compile flawlessly; but it avoids the need to use operators. This should remove the limitation of two polymorphic parameters, in case someone ever needs a typeclass with many parameters.

I believe it would also make it readable enough to have several methods in the same class, like this:

type Monad = Monad with
    static member return' (Monad, _ : 'a option) = fun (x:'a) -> Some x
    static member bind (Monad, x : 'a option) = fun f -> Option.bind f x

let inline return' x =
    ((^a or ^b) : (static member return' : ^a * ^b -> _)
                    (Monad, Unchecked.defaultof<'b>)) x
let inline (>>=) x f = ((^a or ^b) : (static member bind : ^a * ^b -> _)
                                        (Monad, x)) f

By Loïc Denuzière on 12/22/2011 8:32 AM (permalink)

Thanks a lot for your suggestion.
Indeed I'm spending lot of time trying to figure out how to get rid of the operators using techniques like this.
I would love to write code that way, I agree with you it's much more readable.
But while for basic stuff like bind and return works fine, when you get into Monad Transformers, Arrows things get more complicated and some static constraints get solved before hand.
I think the main problem is the inability to specify a triple or constraint, something like:
(^a or ^b or ^c).
The only way I found at the moment to generate it is using the ternary operator.
I will keep researching, more suggestions are welcome.
Feel free to clone the fsharp-typeclasses project and try to re-write the code in a better way.

By Gustavo Leon on 2/14/2012 12:46 AM (permalink)

This is one of the coolest workarounds I've seen. I played with this technique a bit but still haven't been able to make it extensible, as type extensions can't provide operator overloads. Example: [link:gist.github.com]
What am I missing?
BTW do you know any other F# programmers in Argentina? Maybe we could form a user group...

By Mauricio Scheffer on 12/7/2011 2:03 PM (permalink)

Thanks a lot for your feedback, I don't know any F# developer in Argentina (I live in Switzerland).

I'm not extending with Extension methods.
Extensions methods don't fit in this approach.
Maybe it's confusing, because the example I have in the post defines the type IO, then some variables, then it re-takes the IO type definition and finish defining the overloads for IO.
Despite it uses the same syntax as Extension Methods F# compiles them as normal methods because they are in the same module as the type definition.

The instance methods should be defined either in the Typeclass definition or in the Type definition.
In your code you don't include List in the Fmap type and you don't have the source code for List to add the overload there.

Basically what you' re trying to define is like an orphan instance in Haskell. I'm not sure if it's impossible to implement* but anyway even in Haskell is not a good practice.
Of course you can extend it with a wrapper type (i.e. ZipList), but instances for native types should be defined in the typeclass definition.

Have a look at the Script I have in the project with tests.
There you'll find samples with some new instance definitions for new types.

(*) Maybe there is a way to support orphan instances given that I was able to extend F# binary operators using the ternary operator.
I played a bit using this technique but still don't get the right static member constraints.
The main problem I face here is that F# don't compile when it finds more that one matching overload.
It will be fine if it just take the most specific definition, or even the first one and then issue a warning.

By Gustavo Leon on 12/7/2011 3:00 PM (permalink)

open System

type TypeClass<'a> =
  static member Instance = Unchecked.defaultof<'a>

type TypeClassAttribute() =
  inherit Attribute()

[<AbstractClass>]
type Eq<'a when 'a :> IComparable<'a>> =
  member x.AreEqual (a: 'a) b = a.CompareTo b = 0

type Vector2D<'a when 'a:> IComparable<'a>>(x: 'a, y: 'a) =
  typeclass eq = Eq<'a>
    
  member this.X = x
  member this.Y = y
    
  member this.TypeClassEq(other: Vector2D<'a>) =
    AreEqual x other.X && AreEqual y other.Y
  override this.ToString() = "(" + x.ToString() + "; " + y.ToString() + ")"

let a = Vector2D(1, 0)
let b = Vector2D(1, 0)
let c = Vector2D(0, 1)

printfn "%A = %A is %b" a b (a.TypeClassEq b)
printfn "%A = %A is %b" a c (a.TypeClassEq c)
Console.ReadKey() |> ignore

This code now prints: (1; 0) = (1; 0) is true
(1; 0) = (0; 1) is false

It uses stubs for TypeClass<'a>.Instance and TypeClassAttribute since I've not added their implementation to FSharp.Core.
It seems for me a bit strange that this code works, because eq should be null. Looks like F# emits call instruction to do an instance call (C# emits callvirt to check if this poiter is not null).

1
2
3

typeclass eq = Eq<'a> expands to
[<TypeClass>]
static let eq = TypeClass<eq<'a>>.Instance

and AreEqual is searched among eq members since it can't be resolved and typechecked itself.

This is just a proof of concept. I'm going to replace 'typeclass' with 'constraint' to preserve compatibility with old code, add instance member lookup and do something with the fact that in F# expression 'a + b' (+) has type 'a -> 'a -> 'a, but in C# it would has type 'a * 'a -> 'a. Finally, type class checking must be implemented at compile time.

Suggestions and critics are welcome.

By LOST on 1/9/2011 4:39 AM (permalink)

I've added required classes to FSharp.Core, modified sources lies here: [link:bitbucket.org]

Here is an example source, note Arithmetics has default constructor and MathExt provides (+) operator for int type (resolution does not add it by now):

[<AbstractClass>]
type Arithmetics<'a> () =
    abstract member (+): 'a * 'a -> 'a

[<TypeClassExtension>]
type MathExt =
    static member (+)(a, b) = (+) a b

type Vector2D<'a>(x: 'a, y: 'a) =
    typeclass ar = Arithmetics<'a>
    member this.X = x
    member this.Y = y
    
    override this.ToString() = "(" + x.ToString() + "; " + y.ToString() + ")"

    static member (+)(v1: Vector2D<'a>, v2: Vector2D<'a>) =
        let a = Vector2D(ar.(+)(v1.X, v2.X), (+) (v1.Y, v2.Y))
        // 1 + 1 |> ignore
        a

let a = Vector2D(1, 0)
let b = Vector2D(-5, -14)
printfn "%A + %A = " a b
printfn "%A" (a+b)

Still no typeclass constraint check is done at compile time, just syntactic sugar.

By LOST on 1/10/2011 4:44 AM (permalink)

Did you make changes to the compiler's code generation, or does it call into the reflection-based implementation that you posted at ntypeclasses.codeplex.com?

I think any useful type classes implementation needs to get around the problem of adding two numbers: that is, emitting the add opcode when adding two doubles or ints, and calling into the right op_Addition method everywhere else. This could work if you only referenced type classes implemented inside the same assembly (and let inline lets you go part of the way), but exposing enough information about type classes in the assembly metadata could be a lot of work.

By Tim Robinson on 11/29/2010 5:07 AM (permalink)

I've not made working changes to the compiler yet. And I'm not currently going to use add opcode or F#'s inline because it would break compatibility with other .NET languages.

I've not tested NTypeClasses's performance yet. In this particular case an adequate JIT optimization would be way better than manual replacing method calls with an add instruction in F# compiler. I hope it has already been done by CLR team. In case it hasn't, we can always vote for it on Microsoft Connect.

Since TypeClass<t>.Instance refers to static readonly field it is possible in theory to inline all calls to its methods. This is also very important because in this case it is possible to replace virtual method calls with ordinary ones.

By LOST on 11/29/2010 6:48 AM (permalink)

Topic tags

Built with WebSharper

Home

Answers

Events

Courses

Groups and Conferences

Blogs

Jobs

Developers

Current state

To be done, integrating to F#

Problems and things to discuss

Topic tags