Changes between Version 4 and Version 5 of BangPatterns


Ignore:
Timestamp:
Feb 6, 2006 3:42:52 PM (8 years ago)
Author:
simonpj@…
Comment:

--

Legend:

Unmodified
Added
Removed
Modified
  • BangPatterns

    v4 v5  
    11[[PageOutline]] 
    22= Bang patterns = 
     3 
     4== Tickets == 
     5[[TicketQuery(description~=BangPatterns)]] 
    36 
    47== Goal == 
     
    6366  
    6467 
    65 == Non-recursive let and where bindings == 
    66  
    67 First, we deal with ''non-recursive'' bindings only. 
    68 In Haskell, let and where bindings can bind patterns.  Their semantics is given by translation to a case, with an implicit implicit tilde (~). 
    69 {{{ 
    70 let [x,y] = e in b 
     68== Let and where bindings == 
     69 
     70In Haskell, let and where bindings can bind patterns.  We propose to modify  
     71this by allowing an optional bang at the top level of the pattern.  Thus for example: 
     72{{{ 
     73  let ![x,y] = e in b 
     74}}} 
     75The "`!`" should not be regarded as part of the pattern; after all, 
     76in a function argument `![x,y]` means the same as `[x,y]`.  Rather, the "`!`"  
     77is part of the syntax of `let` bindings. 
     78 
     79The semantics is simple; the above program is equivalent to: 
     80{{{ 
     81  let p@[x,y] = e in p `seq` b 
     82}}} 
     83That is, for each bang pattern, invent a variable `p`, bind it to the  
     84banged pattern (removing the bang) with an as-pattern, and `seq` on it 
     85in the body of the `let`.  (Thanks to Ben Rudiak-Gould for suggesting 
     86this idea.) 
     87 
     88A useful special case is when the pattern is a variable: 
     89Similarly 
     90{{{ 
     91  let !y = f x in b 
    7192}}} 
    7293means 
    7394{{{ 
    74 case e of { ~[x,y] -> b } 
    75 }}} 
    76 In our proposal, if there is a bang right at the top of a let-bound pattern, 
    77 then the implicit tilde is replaced with an explicit bang: 
    78 {{{ 
    79 let ![x,y] = e in b 
    80 }}} 
    81 means 
    82 {{{ 
    83 case e of { ![x,y] -> b } 
    84 }}} 
    85 which is the same as  
    86 {{{ 
    87 case e of { [x,y] -> b } 
    88 }}} 
    89 Similarly 
    90 {{{ 
    91 let !y = f x in b 
    92 }}} 
    93 means 
    94 {{{ 
    95 case f x of { !y -> b } 
    96 }}} 
    97 which evaluates the (f x), thereby giving a strict `let`. 
    98  
    99 == Examples == 
     95  let y = f x in y `seq` b 
     96}}} 
     97which evaluates the `(f x)`, thereby giving a strict `let`. 
     98 
     99A useful law is this.  A ''non-recursive'' bang-pattern binding 
     100is equivalent to a `case` expression: 
     101{{{ 
     102  let !p = <rhs> in <body> 
     103     is equivalent to (when the let is non-recursive) 
     104  case <rhs> of !p -> <body> 
     105}}} 
     106 
     107=== Example === 
    100108Here is a more realistic example, a strict version of partition: 
    101109{{{ 
     
    122130needed in this example but often useful). 
    123131 
     132== Recursive let and where bindings == 
     133 
     134At first you might think that a recursive bang pattern 
     135don't make sense: how can you evaluate it strictly if it doesn't exist 
     136yet?  But consider 
     137{{{ 
     138  let !xs = if funny then 1:xs else 2:xs in ... 
     139}}} 
     140Here the binding is recursive, but the translation still makes sense: 
     141{{{ 
     142  let xs = if funny then 1:xs else 2:xs  
     143  in xs `seq` ... 
     144}}} 
     145 
    124146== Top-level bang-pattern bindings == 
    125147 
     
    137159But it's not clear why it would be necessary or useful.  '''Conservative 
    138160conclusion''': no top-level bang-patterns. 
    139  
    140 == Recursive let and where bindings == 
    141  
    142 It is just about possible to make sense of bang-patterns in  
    143 ''recursive'' let and where bindings.  At first you might think they 
    144 don't make sense: how can you evaluate it strictly if it doesn't exist 
    145 yet?  But consider 
    146 {{{ 
    147   let !xs = if funny then 1:xs else 2:xs in ... 
    148 }}} 
    149 Here the binding is recursive, but makes sense to think of it 
    150 as equivalent to 
    151 {{{ 
    152   let xs = if funny then 1:xs else 2:xs  
    153   in xs `seq` ... 
    154 }}} 
    155 But (a) it must be unusual, and (b) I have found it very hard to 
    156 come up with a plausible translation (that deals with all the tricky  
    157 points below).   
    158  
    159 '''Conservative conclusion''': bang-pattern bindings must be non-recursive. 
    160161 
    161162== Tricky point: syntax == 
     
    183184what could {{{(+ 3, + 4)}}} mean apart from a tuple of two sections? 
    184185 
    185 == Tricky point: nested bangs == 
     186== Tricky point: nested bangs (part 1) == 
     187 
     188Consider this: 
     189{{{ 
     190  let (x, Just !y) = <rhs> in <body> 
     191}}} 
     192Is `y` evaluted before `<body>` is begun?  No, it isn't.  That would be 
     193quite wrong.  Pattern matching in a `let` is lazy; if any of the variables bound 
     194by the pattern is evaluated, then the whole pattern is matched.  In this example, 
     195if `x` or `y` is evaluated, the whole pattern is matched, which in turn forces  
     196evaluation of `y`.  The binding is equivalent to 
     197{{{ 
     198  let t = <rhs> 
     199      x = case t of { (x, Just !y) -> x } 
     200      y = case t of { (x, Just !y) -> y } 
     201  in <body> 
     202}}} 
     203 
     204== Tricky point: nested bangs (part 2) == 
    186205 
    187206Consider this: 
     
    209228}}} 
    210229This won't work, because using `seq` on `t` won't force `y`. 
    211 You could build an intermediate tuple, thus: 
     230However, the semantics says that the original code is equivalent to 
     231{{{ 
     232  let p@(x, Just !y) = <rhs> in p `seq` <body> 
     233}}} 
     234and we can desugar that in obvious way to 
    212235{{{ 
    213236  let  
    214     t = case <rhs> of (x, Just !y) -> (x,y) 
    215     x = fst t 
    216     y = snd t 
     237    t = <rhs> 
     238    p = case t of p@(x, Just !y) -> p 
     239    x = case t of p@(x, Just !y) -> x 
     240    y = case t of p@(x, Just !y) -> y 
     241  in 
     242  p `seq` <body> 
     243}}} 
     244which is fine. 
     245 
     246You could also build an intermediate tuple, thus: 
     247{{{ 
     248  let  
     249    t = case <rhs> of p@(x, Just !y) -> (p,x,y) 
     250    p = sel13 t 
     251    x = sel23 t 
     252    y = sel33 t 
    217253  in 
    218254  t `seq` <body> 
    219255}}} 
    220 But that seems a waste when the patttern is itself just a tuple; 
    221 and it needs adjustment when there is only one bound variable. 
    222  
    223 Bottom line: for non-recursive bindings, the straightforward translation 
    224 to a `case` is, well, straightforward.   Recursive bindings could probably 
    225 be handled, but it's more complicated. 
     256Indeed GHC does just this for complicated pattern bindings. 
    226257 
    227258== Tricky point: pattern-matching semantics == 
     
    319350non-recursive bindings the order of the bindings shouldn't matter. 
    320351 
    321 == Tickets == 
    322 [[TicketQuery(description~=BangPatterns)]]