Changes between Version 3 and Version 4 of Ticket #76


Ignore:
Timestamp:
Jan 26, 2006 8:56:54 PM (10 years ago)
Author:
ross@…
Comment:

Legend:

Unmodified
Added
Removed
Modified
  • Ticket #76 – Description

    v3 v4  
    1 == Goal ==
    2 Our goal is to make it easier to write strict programs in
    3 Haskell.  Programs that use 'seq' extensively are possible but clumsy,
    4 and it's often quite awkward or inconvenient to increase the strictness
    5 of a Haskell program.  This proposal changes nothing fundamental;
    6 but it makes strictness more convenient.
    7 
    8 == The basic idea ==
    9 
    10 The main idea is to add a single new production to the syntax of
    11 patterns
    12 {{{
    13         pat ::= !pat
    14 }}}
    15 Matching an expression e against a pattern !p is done by first
    16 evaluating e (to WHNF) and then matching the result against p.
    17 
    18 Example:
    19 {{{
    20   f1 !x = True
    21 }}}
    22 f1 is strict in x.  In this case, it's not so bad to write
    23 {{{
    24   f1 x = x `seq` True
    25 }}}
    26 but when guards are involved the {{{seq}}} version becomes horrible:
    27 {{{
    28   -- Duplicate the seq on y
    29   f2 x y | g x = y `seq` rhs1
    30          | otherwise = y `seq` rhs2
    31 
    32   -- Have a weird guard
    33   f2 x y | y `seq` False = undefined
    34         | g x = rhs1
    35         | otherwise = rhs2
    36 
    37   -- Use bang patterns
    38   f2 !x !y | g x = rhs1
    39            | otherwise = rhs2
    40 }}}
    41 Bang patterns can be nested of course:
    42 {{{
    43   f2 (!x, y) = [x,y]
    44 }}}
    45 f2 is strict in x but not in y.  A bang only really has an effect
    46 if it precedes a variable or wild-card pattern:
    47 {{{
    48   f3 !(x,y) = [x,y]
    49   f4 (x,y)  = [x,y]
    50 }}}
    51 f3 and f4 are identical; putting a bang before a pattern that
    52 forces evaluation anyway does nothing.
    53 {{{
    54   g5 x = let y = f x in body
    55   g6 x = case f x of { y -> body }
    56   g7 x = case f x of { !y -> body }
    57 }}}
    58 g5 and g6 mean exactly the same thing.  But g7 evalutes (f x), binds y to the
    59 result, and then evaluates body.
    60  
    61 
    62 == Non-recursive let and where bindings ==
    63 
    64 In Haskell, let and where bindings can bind patterns.  Their semantics is given by translation to a case, with an implicit implicit tilde (~).
    65 {{{
    66         let [x,y] = e in b
    67 }}}
    68 means
    69 {{{
    70         case e of { ~[x,y] -> b }
    71 }}}
    72 In our proposal, if there is a bang right at the top of a let-bound pattern,
    73 then the implicit tilde is replaced with an explicit bang:
    74 {{{
    75         let ![x,y] = e in b
    76 }}}
    77 means
    78 {{{
    79         case e of { ![x,y] -> b }
    80 }}}
    81 which is the same as
    82 {{{
    83         case e of { [x,y] -> b }
    84 }}}
    85 Similarly
    86 {{{
    87         let !y = f x in b
    88 }}}
    89 means
    90 {{{
    91         case f x of { !y -> b }
    92 }}}
    93 which evaluates the (f x), thereby giving a strict `let`.
    94 
    95 Here is a more realistic example, a strict version of partition:
    96 {{{
    97         partitionS p [] = ([], [])
    98         partitionS p (x:xs)
    99           | p x       = (x:ys, zs)
    100           | otherwise = (ys, x:zs)
    101           where
    102             !(ys,zs) = partitionS p xs
    103 }}}
    104 The bang in the where clause ensures that the recursive
    105 call is evaluated eagerly.  In Haskell today we are forced to
    106 write
    107 {{{
    108         partitionS p [] = ([], [])
    109         partitionS p (x:xs)
    110           = case partitionS p xs of
    111                 (ys,zs) | p x       = (x:ys, zs)
    112                         | otherwise = (ys, x:zs)
    113 }}}
    114 which is clumsier (especially if there are a bunch of where-clause
    115 bindings, all of which should be evaluated strictly), and doesn't
    116 provide the opportunity to fall through to the next equation (not
    117 needed in this example but often useful).
    118 
    119 The
    120 
    121 == Changes to the Report ==
    122 
    123 The changes to the Report would be these
    124 
    125  * Section 3.17, add pat ::= !pat to the syntax of patterns.
    126    We would need to take care to make clear whether
    127 {{{
    128    f !x = 3
    129 }}}
    130    was a definition of the function "!", or of "f".  (There is
    131    a somewhat similar complication with n+k patterns; see the
    132    end of 4.3.3.2 in the Report.  However we probably do not
    133    want to require parens thus
    134 {{{
    135    f (!x) = 3
    136 }}}
    137    which are required in n+k patterns.
    138 
    139  * Section 3.17.2: add new bullet 10, saying "Matching
    140    the pattern "!pat" against a value "v" behaves as follows:
    141    * if v is bottom, the match diverges
    142    * otherwise, "pat" is matched against "v".
    143 
    144  * Fig 3.1, 3.2, add a new case (t):
    145 {{{
    146    case v of { !pat -> e; _ -> e' }
    147    = v `seq` case v of { pat -> e; _ -> e' }
    148 }}}
    149 
    150  * Section 3.12 (let expressions).  In the translation box, wherever
    151    there is a bang right at the top of a pattern on the LHS of the
    152    translation rule, omit the implicit tilde that occurs at the top
    153    of the pattern on the RHS of the rule.
    154 
    155 The last point is the only delicate one. If we adopt this proposal
    156 we'd need to be careful about the semantics.  For example, are
    157 bangs ok in recursive bindings? (Yes.) And for
    158 non-recursive bindings the order of the bindings shouldn't matter.
     1See BangPatterns.