Discrepancy between instance declarations: type families vs. type classes

There is a discrepancy between the way instances of type families and type classes are represented in HSE.

data Decl l
    ...

So far so good.

    ...
    | TypeInsDecl  l     (Type l) ...
    | DataInsDecl  l ... (Type l) ...
    | GDataInsDecl l ... (Type l) ...
    ...

This is a very broad type, which is not too type-safe, but it might be handy for some applications to have an instance head to be presented like this.

    ...
    | InstDecl     l (Maybe (Context l)) (InstHead l) ...
    | DerivDecl    l (Maybe (Context l)) (InstHead l)
    ...

This is a much narrower type, but at least we can be sure that the type will be like C t1 .. tn, which is helpful in certain situations. However, it's currently too narrow and it causes problems (see #9), so it should perhaps include (Maybe [TyVarBind l]). It might even be useful to absorb these two fields into the InstHead data type.

For Language.Haskell.Exts.Syntax it's worse.

data Decl
    ...
    | TypeInsDecl  SrcLoc     Type ...
    | DataInsDecl  SrcLoc ... Type ...
    | GDataInsDecl SrcLoc ... Type ...
    ...

For type families, nothing really changes.

    ...
    | InstDecl     SrcLoc Context QName [Type] ...
    | DerivDecl    SrcLoc Context QName [Type]
    ...

For type classes, there isn't even an InstHead data type.

I suggest that all these cases should be turned into one encoding, be it Types or InstHeads. In my opinion, InstHead is the most HSE-ish approach here.

[niklasbroberg]

Agreed.

I suppose the following is correct for classes and class instances:

data InstHead l
    = InstHead l (Maybe [TyVarBind l]) (Maybe (Context l)) (Asst l)
    | IHParen l (InstHead l)
data DeclHead l
    = DeclHead l                       (Maybe (Context l)) (Asst l)
    | DHParen l (DeclHead l)
data Asst l
    = AsApp l (Asst l) (Type l)
    | AsCon l (QName l)
    | AsParen l (Asst l)
    | AsInfix l (Type l) (QName l) (Type l)

(I'm reusing the Asst name here, because I expect a resolution of #107 would cause Asst to be replaced by Type, and equality constraints might become elements of Type to resolve #8.)

I haven't experimented with applicability to type families yet.

Any thoughts?

[pjonsson]

Commit 1f20159 moves towards the suggested representation, but App resides in InstHead and DeclHead rather than Asst. That allows us to faithfully represent programs like the example in #3.

[pjonsson]

I have a partial implementation of the suggested refactoring for InstHead, with a broken out Asst that I call DeclOrInstHead. Pushing down the context into InstHead would improve things everywhere except for data Deriving l = Deriving l [InstHead l] which would admit more things.

DeclHead is less clear cut though. TypeDecl, TypeFamDecl and ClsTyFam would all admit more things. From pure counting it would improve the state of things for more things. In total we could reduce some redundancy in our code by sharing the suggested DeclOrInstHead between DeclHead and InstHead.

Any opinions?

[pjonsson]

I pushed the first half of the change in d4f3cc8 since that fixes #7. The change is low risk despite admitting more things for Deriving--there's only one place where Deriving is created in the parser and we immediately put Nothing for the InstHead context.

[niklasbroberg]

First, the bikeshed. We should be careful what we name things: 'head' is a term from logic with an exact meaning (the goal of a proof rule). The 'head' of the declaration instance Foo a => Bar a is Bar a, i.e. the thing that was previously called InstHead. It makes sense representation-wise to push the Context into it, but then it needs a different name. See here.

Now for the more semantic question of whether to reuse what's currently called DeclOrInstHead for both instances (w family) and class/type declarations (w family). The drawback of that is that the latter declare new names, and hence only Name and TyVarBind make sense, whereas the former use existing names and thus need QName and Type. I think this distinction is quite important to make, so I would be quite hesitant to merge the two.

We could of course make a similar trick to what @feuerbach tried for types in #11, and make a recursive parameterised structural type that gets instantiated with the two different versions. For this case, I don't think the duplication is so bad that it would be worth it.

data InstSomething l
    = InstSomething l (Maybe [TyVarBind l]) (Maybe (Context l)) (InstHead l)
    | IHParen l (InstSomething l)
data InstHead l
    = IHead l (QName l)
    | IHInfix l (Type l) (QName l)
    | IHParen l (InstHead l)
    | IHApp   l (InstHead l) (Type l)

data DeclSomething l
    = DeclSomething l                       (Maybe (Context l)) (DeclHead l)
    | DHParen l (DeclSomething l)
data DeclHead l
    = DHead l (Name l)
    | DHInfix l (TyVarBind l) (Name l)
    | DHParen l (DeclHead l)
    | DHApp   l (DeclHead l) (TyVarBind l)

This - with something sensible in place of "Something" - would be my suggestion.

[pjonsson]

I agree about the name. Do you have a suggestion for the new name?

The reason Decl isn't merged yet is that it doesn't work as far as I can tell, and you give a good argument for the reasoning behind "it doesn't work".

[niklasbroberg]

Hmm. Going with the logic connection, would InstRule make sense, or is that too theory-nerdy? Go the ugly route and call them InstCtxtHead to denote that it's both the context and the head in one? InstHeadline? InstDeclHeader? I'm not entirely sold on any of them, so input is more than welcome.

[pjonsson]

I think our average user has or are working on a PhD in programming languages. We're much too down to earth to scare them off with pieces of theory since we actually run our programs. I'll put the rename on my queue.

Since you're obviously here now.. ;-)

I sent a mail to your Chalmers adress about haskell-src-exts a couple of weeks ago. Did you change adress or is it in your backlog?

[niklasbroberg]

It reached me, and indeed ended up in the backlog. I thought there would be a better place than this thread to discuss it though, but I can't seem to find a thread on fault-tolerance. Could you perchance point me to it?

(I also can't find a search function on github for issues, am I just blind?)

[pjonsson]

I just opened #145 for that discussion. My mail was mainly a probe to see what your thoughts were.

There is a search box at the top of the page, but the results I get are on average useless.