Changes between Version 5 and Version 6 of BangPatterns


Ignore:
Timestamp:
Feb 8, 2006 10:26:59 AM (9 years ago)
Author:
simonpj@…
Comment:

--

Legend:

Unmodified
Added
Removed
Modified
  • BangPatterns

    v5 v6  
    105105}}} 
    106106 
    107 === Example === 
    108107Here is a more realistic example, a strict version of partition: 
    109108{{{ 
     
    129128provide the opportunity to fall through to the next equation (not 
    130129needed in this example but often useful). 
     130 
     131---- 
     132= Changes to the Report = 
     133 
     134The changes to the Report would be these.  (Incomplete.) 
     135 
     136 * Section 3.17, add pat ::= !pat to the syntax of patterns. 
     137   We would need to take care to make clear whether 
     138   {{{ 
     139f !x = 3 
     140}}} 
     141   was a definition of the function "!", or of "f".  (There is 
     142   a somewhat similar complication with n+k patterns; see the 
     143   end of 4.3.3.2 in the Report.  However we probably do not  
     144   want to require parens thus 
     145   {{{ 
     146f (!x) = 3 
     147}}} 
     148   which are required in n+k patterns. 
     149 
     150 * Section 3.17.2: add new bullet 10, saying "Matching 
     151   the pattern "!pat" against a value "v" behaves as follows: 
     152   * if v is bottom, the match diverges 
     153   * otherwise, "pat" is matched against "v". 
     154 
     155 * Fig 3.1, 3.2, add a new case (t): 
     156   {{{ 
     157case v of { !pat -> e; _ -> e' } 
     158   = v `seq` case v of { pat -> e; _ -> e' } 
     159}}} 
     160 
     161 * Section 3.12 (let expressions).  In the translation box, first apply  
     162   the following transformation:  for each pattern pi that is of  
     163   form `!qi = ei`, transform it to `xi@qi = ei`, and and replace `e0`  
     164   by {{{(xi `seq` e0)}}}.  Then, when none of the left-hand-side patterns 
     165   have a bang at the top, apply the rules in the existing box. 
     166 
     167---- 
     168= Discussion = 
    131169 
    132170== Recursive let and where bindings == 
     
    184222what could {{{(+ 3, + 4)}}} mean apart from a tuple of two sections? 
    185223 
     224== Tricky point: pattern-matching semantics == 
     225 
     226A bang is part of a ''pattern''; matching a bang forces evaluation.  
     227So the exact placement of bangs in equations matters. For example, 
     228there is a difference between these two functions: 
     229{{{ 
     230  f1 x  True  = True 
     231  f1 !x False = False 
     232 
     233  f2 !x True  = True 
     234  f2  x False = False 
     235}}} 
     236Since pattern matching goes top-to-bottom, left-to-right,  
     237{{{(f1 bottom True)}}} is {{{True}}}, whereas {{{(f2 bottom True)}}}  
     238is {{{bottom}}}. 
     239 
     240== Tricky point: binding transformations == 
     241 
     242In Haskell 98, these two bindings are equivalent: 
     243{{{ 
     244    { p1=e1; p2=e2 }    and     { (~p1,~p2) = (e1,e2) } 
     245}}} 
     246But with bang patterns this transformation only holds if `p1`, `p2` are 
     247not bang-patterns.   Remember, the bang is part of the binding, not the pattern, 
     248 
    186249== Tricky point: nested bangs (part 1) == 
    187250 
     
    256319Indeed GHC does just this for complicated pattern bindings. 
    257320 
    258 == Tricky point: pattern-matching semantics == 
    259  
    260 A bang is part of a ''pattern''; matching a bang forces evaluation.  
    261 So the exact placement of bangs in equations matters. For example, 
    262 there is a difference between these two functions: 
    263 {{{ 
    264   f1 x  True  = True 
    265   f1 !x False = False 
    266  
    267   f2 !x True  = True 
    268   f2  x False = False 
    269 }}} 
    270 Since pattern matching goes top-to-bottom, left-to-right,  
    271 {{{(f1 bottom True)}}} is {{{True}}}, whereas {{{(f2 bottom True)}}}  
    272 is {{{bottom}}}. 
    273  
    274321== Tricky point: polymorphism == 
    275322 
     
    311358for bang-pattern bindings. 
    312359 
    313 == Changes to the Report == 
    314  
    315 The changes to the Report would be these.  (Incomplete.) 
    316  
    317  * Section 3.17, add pat ::= !pat to the syntax of patterns. 
    318    We would need to take care to make clear whether 
    319    {{{ 
    320 f !x = 3 
    321 }}} 
    322    was a definition of the function "!", or of "f".  (There is 
    323    a somewhat similar complication with n+k patterns; see the 
    324    end of 4.3.3.2 in the Report.  However we probably do not  
    325    want to require parens thus 
    326    {{{ 
    327 f (!x) = 3 
    328 }}} 
    329    which are required in n+k patterns. 
    330  
    331  * Section 3.17.2: add new bullet 10, saying "Matching 
    332    the pattern "!pat" against a value "v" behaves as follows: 
    333    * if v is bottom, the match diverges 
    334    * otherwise, "pat" is matched against "v". 
    335  
    336  * Fig 3.1, 3.2, add a new case (t): 
    337    {{{ 
    338 case v of { !pat -> e; _ -> e' } 
    339    = v `seq` case v of { pat -> e; _ -> e' } 
    340 }}} 
    341  
    342  * Section 3.12 (let expressions).  In the translation box, wherever 
    343    there is a bang right at the top of a pattern on the LHS of the 
    344    translation rule, omit the implicit tilde that occurs at the top  
    345    of the pattern on the RHS of the rule. 
    346  
    347 The last point is the only delicate one. If we adopt this proposal 
    348 we'd need to be careful about the semantics.  For example, are 
    349 bangs ok in recursive bindings? (Yes.) And for  
    350 non-recursive bindings the order of the bindings shouldn't matter. 
    351  
     360== Existentials == 
     361 
     362A strict pattern match could perhaps support existentials (which GHC currently 
     363rejects in pattern bindings): 
     364{{{ 
     365  data T where 
     366    T :: a -> (a->Int) -> T 
     367 
     368  f x = let !(T y f) = x in ... 
     369}}} 
     370 
     371 
     372---- 
     373= A more radical proposal = 
     374 
     375A more radical proposal (from John Hughes) is to make pattern matching 
     376in `let` strict.  Thus 
     377{{{ 
     378  let (x,y) = e in b 
     379}}} 
     380would be equivalent to 
     381{{{ 
     382  case e of (x,y) -> b 
     383}}} 
     384(in the non-recursive case) and to 
     385{{{ 
     386  let t = let { x = fst t; y = snd t } in e 
     387  in case t of (x,y) -> b 
     388}}} 
     389(in the recursive case).   
     390 
     391To recover Haskell 98 semantics for a pattern binding, use a tilde: 
     392{{{ 
     393  let ~(x,y) = e in b 
     394}}} 
     395 
     396More precisely, the rules for desugaring binding are these: 
     397 1. Sort into strongly-connected components. 
     398 2. Apply the following rules: 
     399{{{ 
     400let p1=e1 ; ... ; pn = en in e    ==>    let (p1,...,pn) = (e1,...,en) in e 
     401 
     402let p = e1 in e0                  ==>   case e1 of p -> e0 
     403                                  where no variable in p occurs free in e1 
     404 
     405let p = e1 in e0                  ==> let p = fix (\ ~p -> e1) in e0 
     406                                  otherwise 
     407}}} 
     408== Why the strongly-connected component? == 
     409 
     410Consider this 
     411{{{ 
     412  let (y:ys) = xs 
     413      (z:zs) = ys 
     414  in ... 
     415}}} 
     416There is no real recursion here, but considered all together the  
     417second binding does refer to the first. So the desugaring above would use 
     418fix, and if you work it out you'll find that all the variables get bound to bottom. 
     419 
     420Note that the ''static'' semantics already requires a strongly-conneted component 
     421analysis. 
     422 
     423