[GHC] #15151: Better Interaction Specialization and GND

[GHC]

#15151: Better Interaction Specialization and GND
-------------------------------------+-------------------------------------
           Reporter:  andrewthad     |             Owner:  (none)
               Type:  feature        |            Status:  new
  request                            |
           Priority:  normal         |         Milestone:  8.6.1
          Component:  Compiler       |           Version:  8.4.2
           Keywords:                 |  Operating System:  Unknown/Multiple
       Architecture:                 |   Type of failure:  None/Unknown
  Unknown/Multiple                   |
          Test Case:                 |        Blocked By:
           Blocking:                 |   Related Tickets:
Differential Rev(s):                 |         Wiki Page:
-------------------------------------+-------------------------------------
 Let us consider the following code:

 {{{
 -- Sort.hs
 sort :: (Prim a, Ord a) => MutablePrimArray s a -> ST s ()
 sort mutArr = ...
 {-# SPECIALIZE sort :: MutablePrimArray s Int -> ST s () -#}
 {-# SPECIALIZE sort :: MutablePrimArray s Int8 -> ST s () -#}
 {-# SPECIALIZE sort :: MutablePrimArray s Word8 -> ST s () -#}
 ...
 }}}

 For reference, a `MutablePrimArray` is a `MutableByteArray` with a phantom
 type variable to tag the element type. This sorting algorithm may be
 implemented in any number of ways, and the implementation is unimportant
 here. The specialize pragmas are intended to capture a number of common
 use cases. Here's where a problem arises:

 {{{
 -- Example.hs
 newtype PersonId = PersonId Int
   deriving (Eq,Ord,Prim)
 sortPeople :: MutablePrimArray s PersonId -> MutablePrimArray s PersonId
 sortPeople x = sort x
 }}}

 There isn't a rewrite rule that specializes the `sort` function when we
 are dealing with `PersonId`. So, we end up with a slower version of the
 code that explicitly passes all the dictionaries. One solution would be to
 just use `INLINABLE` instead. Then we don't have to try to list every
 type, and we just let the specialization be generate at the call site. But
 this isn't totally satisfying. There are a lot of types that are just
 newtype wrappers around `Int`. Why should we have an extra copy of the
 same code for each of them? (Even without newtypes, `INLINABLE` can still
 result in duplication if neither of the modules that needs a
 specialization transitively imports the other).

 What I'm suggesting is that rewrite rules (like those generated by
 `SPECIALIZE`) could target not just the given type but also any newtype
 around it, provided that all typeclass instances required by the function
 were the result of GND. The only situations where this is unsound are
 situations where the user was already doing something unsound with rewrite
 rules. There are several implementation difficulties:

 * In core, there is no good way to tell that a typeclass instance
 dictionary was the result of GND. I'm not sure how to work around this.
 * `Eq` and `Ord` usually aren't handled by the `newtype` deriving
 strategy. They are handled by the `stock` strategy, which produces code
 with equivalent behavior but is nevertheless different code.
 * The rewrite rule would need to look at additional arguments beyond the
 type arguments.

 I suspect that these difficulties would make such this feature difficult
 to implement, but this feature would help me with some of my libraries and
 applications.

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