| 130 | |
| 131 | ---- |
| 132 | = Changes to the Report = |
| 133 | |
| 134 | The 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 | {{{ |
| 139 | f !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 | {{{ |
| 146 | f (!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 | {{{ |
| 157 | case 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 = |
| 224 | == Tricky point: pattern-matching semantics == |
| 225 | |
| 226 | A bang is part of a ''pattern''; matching a bang forces evaluation. |
| 227 | So the exact placement of bangs in equations matters. For example, |
| 228 | there 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 | }}} |
| 236 | Since pattern matching goes top-to-bottom, left-to-right, |
| 237 | {{{(f1 bottom True)}}} is {{{True}}}, whereas {{{(f2 bottom True)}}} |
| 238 | is {{{bottom}}}. |
| 239 | |
| 240 | == Tricky point: binding transformations == |
| 241 | |
| 242 | In Haskell 98, these two bindings are equivalent: |
| 243 | {{{ |
| 244 | { p1=e1; p2=e2 } and { (~p1,~p2) = (e1,e2) } |
| 245 | }}} |
| 246 | But with bang patterns this transformation only holds if `p1`, `p2` are |
| 247 | not bang-patterns. Remember, the bang is part of the binding, not the pattern, |
| 248 | |
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 | |
| 362 | A strict pattern match could perhaps support existentials (which GHC currently |
| 363 | rejects 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 | |
| 375 | A more radical proposal (from John Hughes) is to make pattern matching |
| 376 | in `let` strict. Thus |
| 377 | {{{ |
| 378 | let (x,y) = e in b |
| 379 | }}} |
| 380 | would 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 | |
| 391 | To recover Haskell 98 semantics for a pattern binding, use a tilde: |
| 392 | {{{ |
| 393 | let ~(x,y) = e in b |
| 394 | }}} |
| 395 | |
| 396 | More precisely, the rules for desugaring binding are these: |
| 397 | 1. Sort into strongly-connected components. |
| 398 | 2. Apply the following rules: |
| 399 | {{{ |
| 400 | let p1=e1 ; ... ; pn = en in e ==> let (p1,...,pn) = (e1,...,en) in e |
| 401 | |
| 402 | let p = e1 in e0 ==> case e1 of p -> e0 |
| 403 | where no variable in p occurs free in e1 |
| 404 | |
| 405 | let p = e1 in e0 ==> let p = fix (\ ~p -> e1) in e0 |
| 406 | otherwise |
| 407 | }}} |
| 408 | == Why the strongly-connected component? == |
| 409 | |
| 410 | Consider this |
| 411 | {{{ |
| 412 | let (y:ys) = xs |
| 413 | (z:zs) = ys |
| 414 | in ... |
| 415 | }}} |
| 416 | There is no real recursion here, but considered all together the |
| 417 | second binding does refer to the first. So the desugaring above would use |
| 418 | fix, and if you work it out you'll find that all the variables get bound to bottom. |
| 419 | |
| 420 | Note that the ''static'' semantics already requires a strongly-conneted component |
| 421 | analysis. |
| 422 | |
| 423 | |