Partial type class support

[bergmark]

https://github.com/faylang/fay/wiki/Fay-Status-Update-September-2013%3A-ZuriHac%2C-typeclasses%2C-haskell-suite%2C-and-strictness-wrappers#type-classes-and-typechecking

Also see #269

[joelburget]

Is anybody working on this at the moment? I'd like to help if possible but don't think I have a deep enough understanding of typing Haskell or Fay internals to tackle this alone.

[bergmark]

Hi @joelburget,

I started working on this a while ago but got too occupied with other things before I got that far. If you'd like to continue that'd be awesome! I'll help you out.

There are some commits on the typeclasses branch. I just pushed some more that never made it to github but i don't remember exactly what state I left it in so it may or may not be useful to look at it. The first commit 58b606f5f66fa48a85a43e01e6a11cfeb2431c8a can probably be reused, it calculates a dictionary Map (ModuleName, Name) Int where where the key is the location and name of an instance method. The Int is the position for the first contravariant argument of the type the method belongs to (I'll explain what this means further down). Putting that commit on top of master and getting the tests to pass sounds like a good way to get a bit of a feel for the code base.

What's left is essentially just additions to code generation, when we come across an instance declaration such as

instance Show Foo where
  show t = magic t

we want to generate something like (thunking and forcing excluded)

_Foo.prototype.show = function (t) { return magic(t); };

And for each occurrence of an identifier such as in bar = show Foo we need to check if the identifiers are instance methods. Normally we just replace the identifier with the name of the function (id -> Prelude.id) but for methods it needs to be replaced with a call to the prototype such as (show Foo -> Foo.show(Foo)).

If the instance method has multiple arguments, e.g if we have showWeird :: ShowWeird a => Int -> a -> String we cannot just pick the first argument as the root, we need to pick the first occurrence of a to find where the method is defined, so here showWeird 1 Foo -> Foo.showWeird(1, Foo). The contravariance commit figures out which position the value you should use as the root is.

This gives us a subset of Haskell98 type classes. We can implement Show since it's Show a => a -> String, Functor since it's fmap :: Functor f => (a -> b) -> f a -> f b, and others, but not Read since read :: Read a => String -> a has a in a covariant position. Intuitively you can see the covariance in read in that we cannot dispatch on a here it since we'd need to call the correct read function in order to get the a!

So this is not writing a type checker, we don't care about types at all and instead just figure out which instance methods can use dynamic dispatch. We also don't need to pass type class dictionaries around.

Don't hesitate to ask if you have more questions!

[joelburget]

I made a bit of progress on this today, but I have a couple questions.

Code generation

We're in compileApp and we would like to know whether the Var we're applying is a class method. How do we do that? stateClass :: Map (N.QName, N.Name) Int doesn't seem to be quite what we want since in compileApp we just have an S.QName. As far as I can tell that gives us no way to produce the class name. All the different types of names are a bit confusing (N.QName, N.Name, S.Quame, others?) but I think we should have an additional mapping from method to class name stateClasses :: Map S.Qname (Set N.QName). I don't know - that's probably wrong in multiple ways. I assume there can be multiple classes in scope defining the same class method, but I haven't found the relevant part of the Haskell report yet. Also not sure if I got those name types right...

prototype

Assigning the class method to the prototype is a cute trick, but I'm not convinced it's the best way to proceed. As far as I understand, the instance (the first Foo in Foo.showWeird(1, Foo)) doesn't "bring anything to the table". In the implementation it's disregarded since only the normal parameters are considered.

Why not generate a unique name and object for each instance - essentially the same thing GHC would do behind the scenes?

instance Show Foo where
    show t = magic t

...

show Foo

translates to

var instance2983429 = { show: someFayFunc };

...

instance2983429.show(Foo)

This seems slightly less confusing to me and provides a clearer way forward if someone wants to add more capable type class support in the future.

[chrisdone]

Why not generate a unique name and object for each instance - essentially the same thing GHC would do behind the scenes?

instance2983429.show(Foo)

@joelburget Please read this page.

[bergmark]

Thanks for looking into this!

I'll try to answer.

The AST can be in three different states:

• F.* is what we get after parsing with haskell-src-exts, here the annotation is SrcSpanInfo, just the source location, this is aliased in Fay.Exts
• S.*: After that we perform name resolution which changes the annotation to Scoped SrcSpanInfo which contains haskell-names name information. Fay.Exts.Scoped
• N.*: Is unannotated values (()), we use these as much as possible to signal when we don't care about the annotation. If we store a N.QName in CompileState it should always be fully resolved. Fay.Exts.NoAnnotation. My reasoning is that storing an S.QName might be error prone. We generally don't care about what the local qualification of a name is, we only need the fully resolved qualified name.

Name vs QName is both in haskell-src-exts:

λ> import Language.Haskell.Exts.Annotated.Syntax
λ> :i QName
data QName l
  = Qual l (ModuleName l) (Name l)
  | UnQual l (Name l)
  | Special l (SpecialCon l)
λ> :i Name
data Name l
  = Ident l String
  | Symbol l String

Everytime a name may have a qualification it's wrapped in a QName in the AST.

(ModuleName, Name) contains the same information as QName, but without the occurence of Special. You can't name a class method any of the Special names so there's no need to have that extra case in there. I'm not sure if I thought of this when first adding it, but it seems better this way :-)

You are correct in that there might be several classes with the same method names, good catch! I went back and forward on this for a few minutes. I don't think we need the name of the class, only its originating module. We already have this information after calling tryResolveName! From this we can generate a unique name on the prototype such as X.prototype.Foo$Bar$show.

As chris pointed out we can't generate a unique name because when we see a class method in the AST we can't make any assumptions about what type it has. If we could do this we would need all type information, and as a result have full Haskell98 type classes!

The first Foo in Foo.showWeird(1, Foo) does the dynamic dispatch to the right implementation, we can't just call some global show since each type can have its own implementation.

Please let me know if you'd like me to clarify this further!

[bergmark]

Spring cleaning. Lack of activity, it's unlikely that this will happen.