[GHC] #14917: Allow levity polymorphism in binding position

[GHC]

#14917: Allow levity polymorphism in binding position
-------------------------------------+-------------------------------------
        Reporter:  andrewthad        |                Owner:  (none)
            Type:  feature request   |               Status:  new
        Priority:  normal            |            Milestone:
       Component:  Compiler          |              Version:  8.2.2
      Resolution:                    |             Keywords:
                                     |  LevityPolymorphism
Operating System:  Unknown/Multiple  |         Architecture:
                                     |  Unknown/Multiple
 Type of failure:  None/Unknown      |            Test Case:
      Blocked By:                    |             Blocking:
 Related Tickets:                    |  Differential Rev(s):
       Wiki Page:                    |
-------------------------------------+-------------------------------------

Comment (by simonpj):

 Richard says ''This means that, with your id definition, you couldn't
 have''
 {{{
 idList :: forall a. [a] -> [a]
 idList = id
 }}}
     Yes you could!  `idList` is parameterised over a normal always-boxed
 type variable, so all its calls will be at boxed types.  So `idList` can
 call the boxed-a version of `id`.  Easy!  Template polymorphism is not
 infectious.  On the contrary, you have to keep specifying it for each
 enclosing function.

 It's a bit tiresome to have to do this -- it'd be easier for the
 programmer to say that ''all'' polymorphism can be specialised in this
 way, as .NET does -- but I think that's out of reach for us.

 >  Generally, these schemes fail on polymorphic recursion, and I think we
 should do so here, too.

 I don't think so.  For `f :: V r. forall (a :: TYPE r). blah` we need one
 version of `f` per instantation of `r`.  And there are only a finite
 number of possiblities for `r` (boxed pointer, unboxed-32-bit,
 unboxed-64-bit, etc).

 If a function is template-polymorphic in N `RuntimeRep` parameters, then
 you could get a number of versions exponential in N, but that's very
 pathological.

 > Under your "no variables" rule, this List type would have to be
 specialized at every possible data parameter. I'm worried about bloat.

 I agree. I don't understand this no-variable business. Just one
 specialisation per variant of the `RuntimeRep` parameter(s).

 > In the end, I think we'd have to implement some deduplication algorithm
 during linking

 We already have this problem with specialisation. Suppose you say
 {{{
 module Lib where
   f = bah
   f :: Num a => a -> a
   {-# INLINABLE f #-}

 module A where { import Lib; foo = f :: Int -> Int }

 module B where { import Lib; bar = f :: Int -> Int }

 module C where { import Lib; import A; bax = f :: Int -> Int }
 }}}
 Then A and B will independently generate a duplicate version of `f`
 specialised for `Int -> Int`.  But C will not, because it can use the
 specialised version it "sees" from A.

 So far no one has reported unacceptable bloat.

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