[GHC] #12364: Demand analysis for sum types

[GHC]

#12364: Demand analysis for sum types
-------------------------------------+-------------------------------------
        Reporter:  nomeata           |                Owner:
            Type:  task              |               Status:  new
        Priority:  normal            |            Milestone:
       Component:  Compiler          |              Version:  8.0.1
      Resolution:                    |             Keywords:
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 jmct):

 Hey everyone, I hope it's okay if I chime in for a second. I was also
 originally writting this comment on #12368 but I think it's a bit more
 relevant here.

 Because of what Simon says on ticket:12368#comment:1, fixpoint convergence
 should not be used to perform strictness analysis on recursive sum types.
 I could probably dig up some examples of where it produces incorrect
 results if you'd like.

 The standard way of handling recursive types is to ensure they're regular
 types, which allows you to assume a 'uniform' demand on the type. The
 frustrating thing when trying to apply this to Haskell is polymorphic
 recursion which would allow for non-uniform demands on a recursive type.

 For the unboxing of sum-types we wanted to get around this by checking
 whether we were analysing a recursive sum type, but that turns out to be
 difficult in GHC at the moment: https://mail.haskell.org/pipermail/ghc-
 devs/2016-March/011526.html
 However, that only works for us because we only want to unbox non-
 recursive things anyway.

 If you definitely want to analyse recursive types then some new theory is
 going to have to be worked out. The unexplored parts are strictness on
 nested types and the higher-kinded polymorphism possibly allowing for
 introduction of loops. I've thought a bit about how to do it but haven't
 had a serious go at it.

 During my thesis defense Prof. Mycoft suggested the problem might be
 solvable using a PER-based analysis, which has been shown to generalize
 projection-based analyses. I haven't looked at that approach yet, but I
 did scribble down a particular thesis he told me to read.

 For some background, Hinze's thesis is (IMO) the best this topic. I've
 read and re-read his thesis several times in the past few years and I
 still get new insight from it each time. You can find it on his site here:
 http://www.cs.ox.ac.uk/ralf.hinze/publications/#D2

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