Re: [GHC] #12235: Wrong compilation of bang patterns

27 Jun 2016

      #12235: Wrong compilation of bang patterns
-------------------------------------+-------------------------------------
        Reporter:  osa1              |                Owner:
            Type:  bug               |               Status:  closed
        Priority:  normal            |            Milestone:
       Component:  Compiler          |              Version:  8.1
      Resolution:  invalid           |             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 osa1):

 OK, I figured this out.

 Haskell2010 section 4.4.3.1 says this about translating equation-style
 definitions to case expressions:

     A function binding binds a variable to a function value. The general
 form
     of a function binding for variable `x` is:

         x p11 … p1k match1
         …
         x pn1 … pnk matchn

     where each `pij` is a pattern, and where each `matchi` is of the
 general
     form:

     <snip>

     Translation: The general binding form for functions is semantically
     equivalent to the equation (i.e. simple pattern binding):
         x = \ x1 … xk ->
                 case (x1, …, xk) of
                     (p11, …, p1k) match1
                     …
                     (pn1, …, pnk) matchn

     where the xi are new identifiers.

 GHC user manual 9.28.1 says `-XBangPatterns` adds a new production to the
 pattern syntax:

     pat ::= !pat

 So now let's say I have this:

 {{{
 fn5 :: Int -> [T] -> Int
 fn5 i  []       = i
 fn5 i  (A : ts) = fn5 (i + 1) ts
 fn5 !i (B : ts) = fn5 (i + 2) ts
 fn5 i  (C : ts) = fn5 0 ts
 }}}

 According to the report, this should become:

 {{{
 fn5 = \fresh_1 fresh_2 ->
         case (fresh_1, fresh_2) of
           (i,  [])       -> i
           (i,  (A : ts)) -> fn5 (i + 1) ts
           (!i, (B : ts)  -> fn5 (i + 2) ts
           (i,  (C : ts)  -> fn5 0 ts
 }}}

 The semantics is explained I think in this sentence (from the user
 manual):

     Matching an expression e against a pattern !p is done by first
 evaluating e
     (to WHNF) and then matching the result against p.

 in Haskell2010 "3.13 Case Expressions"

     A case expression is evaluated by pattern matching the expression e
 against
     the individual alternatives. The alternatives are tried sequentially,
 from
     top to bottom. ...

 So if we start matching these `i`s from top to bottom, for the third case
 we'd
 need to evaluate `i`. So when it finally came to matching `(i, (C : ts))`
 we've
 already evaluated `i` because we've tried the third pattern.

 Indeed, if I change the definition to

 {{{
 fn5 :: Int -> [T] -> Int
 fn5 i  []       = i
 fn5 i  (A : ts) = fn5 (i + 1) ts
 fn5 i  (C : ts) = fn5 0 ts
 fn5 !i (B : ts) = fn5 (i + 2) ts
 }}}

 It works as expected.

--
Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/12235#comment:6
GHC http://www.haskell.org/ghc/
The Glasgow Haskell Compiler