[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):

 Some notes on exceptions so far:

 Given code like:

 {{{

 data T = A | B | C | D

 f :: T -> T -> Int
 f A A = 1
 f B A = 2
 f C A = 3

 f2 :: T -> T -> Int
 f2 A A = 1
 f2 A B = 2
 f2 A C = 3

 }}}

 Ideally I would like to generate the same code for both variants.
 Check the A column first and then switch on the ABC column reducing the
 number of case statements.

 == The theory works out so far.

 For `f x A` with x = [ABC] we get a number out either way so that is fine.

 For `f (raisesException1) (raisesException2)` we get different exceptions
 depending on order of matching.
 If we break down the matching into case statements as defined in the
 Haskell Report and apply imprecise exceptions the implementation can
 choose either exception so this is somewhat ok too.

 For `f D (raisesException2)` the result is the Exception Set for (error
 "No Match") currently, changing to the union of (raisesException + error
 "No Match") if we change the order of evaluation.

 In theory that is ok. `error x` and undefined are both ⊥ according to the
 Haskell Report. So the result is the set of all exceptions either way.
 If we start with the first argument that is because error is equal to the
 set of all exceptions.
 If we check the second first we do the "execute all alternatives in
 exception mode" thing giving the same result as it comes across `error "No
 Match"`

 == Are there practical Problems with this approach?

 The theory only works for all cases if we treat `error` as non
 termination. With `PatternMatchFail` and `ErrorCall` one can easily
 distinguish these in practice.

 Catching failing pattern matches by default seems insane to me so I don't
 think returning another exception instead of MatchFail should break much
 that wasn't broken to begin with. Especially given that it only matters if
 another strict argument raises an exception first.

 While I can come up with a theoretical scenario where someone ends up with
 `f (raisesLaterCatchedException) (causesMatchFailure)` where changing the
 order would break the code personally I don't think that edge case is
 worth keeping. It depended on an implementation detail in the first place.
 Is unlikely to occur and when it happens easy to fix.

 But still I would like some feedback to judge if I underestimate the
 implications.

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