[GHC] #9334: Implement "instance chains"

[GHC]

#9334: Implement "instance chains"
-------------------------------------+-------------------------------------
              Reporter:  diatchki    |             Owner:  diatchki
                  Type:  feature     |            Status:  new
  request                            |         Milestone:
              Priority:  normal      |           Version:  7.9
             Component:  Compiler    |          Keywords:
  (Type checker)                     |  Operating System:  Unknown/Multiple
            Resolution:              |   Type of failure:  None/Unknown
Differential Revisions:              |         Test Case:
          Architecture:              |          Blocking:
  Unknown/Multiple                   |
            Difficulty:  Unknown     |
            Blocked By:              |
       Related Tickets:              |
-------------------------------------+-------------------------------------

Comment (by diatchki):

 Replying to [comment:3 simonpj]:
 >  * The instance chains described in the instance-chain paper are much
 more elaborate than your proposal here; in particular they involve
 backtracking search and a "fails" possibility.  I imagine that is a
 deliberate narrowing of the specification on your part.

 Yeah, I thought that we should start simple :)   I'll try to meet with
 Mark to understand better how the full system should work.  For now, I
 just wrote up the part that I think fits easily with GHC.

 >  * The behaviour you specify for instance chains is, I think, precisely
 what GHC does for overlappping instances ''when they are all declared in
 the same module''.  See the bullets at the end of
 [http://www.haskell.org/ghc/docs/latest/html/users_guide/type-class-
 extensions.html#instance-overlap 7.6.3.5 in the user manual].  I grant
 that putting all the overlapping equations together in one place is
 clearer, just as with closed type families.  But you have the behaviour
 you want right now, I think.

 Interestingly, even in my simple version, instance chains are a bit more
 expressive, because of the explicit ordering of instances.  So we can
 write things like this:
 {{{
 instance C Int a    where ...
 else     C a   Int  where ...
 }}}
 I am not sure how common cases like these are, but it is worth noting.

 >  * I think you are arguing that we should ''replace'' overlapping
 instances with instance chains. That would render illegal any program that
 uses overlaping instnaces spread across modules.  I suspect that would
 make many people cry, so we'd end up with both.

 Ah, not yet!  I think the two can coexist for a while.  Once we have a
 working version of instance chains we can see if existing overlapping
 instances code can be replaced, and if not, why not.


 > If I have this right, its just a question of whether to support a
 chained syntax.

 For the simple implementation, I think I'll start by adding the syntax (in
 all passes of the front-end), and then modifying `InstEnv` to keep track
 of instance-chains rather than individual instances.

--
Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/9334#comment:4>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler