Changes between Version 3 and Version 4 of Ticket #76


Ignore:
Timestamp:
Jan 26, 2006 8:56:54 PM (8 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.