#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