Changes between Version 4 and Version 5 of BangPatterns


Ignore:
Timestamp:
Feb 6, 2006 3:42:52 PM (10 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)]]