[GHC] #14201: Implement ideas from "Compiling Pattern Matching to Good Decision Trees"

[GHC]

#14201: Implement ideas from "Compiling Pattern Matching to Good Decision Trees"
-------------------------------------+-------------------------------------
        Reporter:  AndreasK          |                Owner:  AndreasK
            Type:  feature request   |               Status:  new
        Priority:  normal            |            Milestone:
       Component:  Compiler          |              Version:  8.2.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 AndreasK):

 Replying to [comment:9 simonpj]:
 > Sounds complicated enough to be worth a Haskell Symposium paper!
 Seriously, writing a paper is often a good way to refine an idea.

 Having that opportunity would be wonderful. I have to write it up with
 rigor for my undergrad thesis anyway.

 For a update on the progress:

 * I've put instrumentation code into GHC to extract patterns.
 * I've coded up a simplified version of the current algorithm outside of
 GHC. Simplifications are:
   * It only covers Constructor/Wildcard/Variable patterns.
   * It only selects a rhs but does no binding/the associated bookkeeping.
   * Record patterns with a different order then their definition are
 treated like a different constructor.
   * It treats all patterns as non-exhaustive.
 * I fully formulated my approach for matching the strictness of the
 current algorithm.

 The next steps are:

 * Implement my approach.
 * Get some statistics of their differences.
 * If it seems worthwhile try to measure the impact of the simplifier. (As
 the output of the desugar stage can be a lot worse and yet still result in
 perfect code).
 * Document the results in a presentable form.
 * Depending on how promising the results are hopefully implement the new
 approach in GHC.

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