Changes between Version 3 and Version 4 of BangPatterns


Ignore:
Timestamp:
Feb 6, 2006 11:03:52 AM (10 years ago)
Author:
simonpj@…
Comment:

--

Legend:

Unmodified
Added
Removed
Modified
  • BangPatterns

    v3 v4  
    135135the module initialisation is performed.
    136136
    137 But it's not clear why it would be necessary or useful.  Conservative
    138 conclusion: no top-level bang-patterns.
     137But it's not clear why it would be necessary or useful.  '''Conservative
     138conclusion''': no top-level bang-patterns.
    139139
    140140== Recursive let and where bindings ==
     
    155155But (a) it must be unusual, and (b) I have found it very hard to
    156156come up with a plausible translation (that deals with all the tricky
    157 points). 
    158 
    159 Conservative conclusion: bang-pattern bindings must be non-recursive.
    160 
    161 === Tricky point: syntax ===
     157points below). 
     158
     159'''Conservative conclusion''': bang-pattern bindings must be non-recursive.
     160
     161== Tricky point: syntax ==
    162162
    163163What does this mean?
     
    174174}}}
    175175
    176 === Tricky point: nested bangs ===
     176Another point that came up in implementation is this.  In GHC, at least,
     177''patterns'' are initially parsed as ''expressions'', because Haskell's syntax
     178doesn't let you tell the two apart until quite late in the day. 
     179In expressions, the form {{{(! x)}}} is a right section, and parses fine.
     180But the form {{{(!x, !y)}}} is simply illegal.  Solution:
     181in the syntax of expressions, allow sections without the wrapping parens
     182in explicit lists and tuples.  Actually this would make sense generally:
     183what could {{{(+ 3, + 4)}}} mean apart from a tuple of two sections?
     184
     185== Tricky point: nested bangs ==
    177186
    178187Consider this:
     
    188197not evaluated; but `y` '''is''' evaluated.
    189198
     199This means that you can't give the obvious alternative translation that uses
     200just let-bindings and {{{seq}}.  For example, we could attempt to translate
     201the example to:
     202{{{
     203  let
     204    t = <rhs>
     205    x = case t of (x, Just !y) -> x
     206    y = case t of (x, Just !y) -> y
     207  in
     208  t `seq` <body>
     209}}}
     210This won't work, because using `seq` on `t` won't force `y`.
     211You could build an intermediate tuple, thus:
     212{{{
     213  let
     214    t = case <rhs> of (x, Just !y) -> (x,y)
     215    x = fst t
     216    y = snd t
     217  in
     218  t `seq` <body>
     219}}}
     220But that seems a waste when the patttern is itself just a tuple;
     221and it needs adjustment when there is only one bound variable.
     222
     223Bottom line: for non-recursive bindings, the straightforward translation
     224to a `case` is, well, straightforward.   Recursive bindings could probably
     225be handled, but it's more complicated.
     226
     227== Tricky point: pattern-matching semantics ==
     228
     229A bang is part of a ''pattern''; matching a bang forces evaluation.
     230So the exact placement of bangs in equations matters. For example,
     231there is a difference between these two functions:
     232{{{
     233  f1 x  True  = True
     234  f1 !x False = False
     235
     236  f2 !x True  = True
     237  f2  x False = False
     238}}}
     239Since pattern matching goes top-to-bottom, left-to-right,
     240{{{(f1 bottom True)}}} is {{{True}}}, whereas {{{(f2 bottom True)}}}
     241is {{{bottom}}}.
     242
    190243== Tricky point: polymorphism ==
    191244
     
    204257But if this is Haskell source, then `f` won't be polymorphic.
    205258
     259One could say that the translation isn't required to preserve the static
     260semantics, but GHC, at least, translates into System F, and being able
     261to do so is a good sanity check.  If we were to do that, then we would
     262need
     263{{{
     264    <rhs> :: Maybe (forall a. Num a => a -> a)
     265}}}
     266so that the case expression works out in System F:
     267{{{
     268   case <rhs> of {
     269     Just (f :: forall a. Num a -> a -> a)
     270        -> (f Int dNumInt (1::Int), f Integer dNumInteger (2::Integer) }
     271}}}
     272The trouble is that `<rhs>` probably has a type more like
     273{{{
     274    <rhs> :: forall a. Num a => Maybe (a -> a)
     275}}}     
     276...and now the dictionary lambda may get in the way
     277of forcing the pattern.
     278
     279This is a swamp.  '''Conservative conclusion''': no generalisation (at all)
     280for bang-pattern bindings.
    206281
    207282== Changes to the Report ==
    208283
    209 The changes to the Report would be these
     284The changes to the Report would be these.  (Incomplete.)
    210285
    211286 * Section 3.17, add pat ::= !pat to the syntax of patterns.