Changes between Version 5 and Version 6 of BangPatterns


Ignore:
Timestamp:
Feb 8, 2006 10:26:59 AM (10 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