wiki:BangPatterns

Version 2 (modified by ross@…, 8 years ago) (diff)

--

Bang patterns

Goal

Our goal is to make it easier to write strict programs in Haskell. Programs that use 'seq' extensively are possible but clumsy, and it's often quite awkward or inconvenient to increase the strictness of a Haskell program. This proposal changes nothing fundamental; but it makes strictness more convenient.

The basic idea

The main idea is to add a single new production to the syntax of patterns

	pat ::= !pat

Matching an expression e against a pattern !p is done by first evaluating e (to WHNF) and then matching the result against p.

Example:

f1 !x = True

f1 is strict in x. In this case, it's not so bad to write

f1 x = x `seq` True

but when guards are involved the seq version becomes horrible:

-- Duplicate the seq on y
f2 x y | g x = y `seq` rhs1
       | otherwise = y `seq` rhs2

-- Have a weird guard
f2 x y | y `seq` False = undefined
       | g x = rhs1
       | otherwise = rhs2

-- Use bang patterns
f2 !x !y | g x = rhs1
         | otherwise = rhs2

Bang patterns can be nested of course:

f2 (!x, y) = [x,y]

f2 is strict in x but not in y. A bang only really has an effect if it precedes a variable or wild-card pattern:

f3 !(x,y) = [x,y]
f4 (x,y)  = [x,y]

f3 and f4 are identical; putting a bang before a pattern that forces evaluation anyway does nothing.

g5 x = let y = f x in body
g6 x = case f x of { y -> body }
g7 x = case f x of { !y -> body }

g5 and g6 mean exactly the same thing. But g7 evalutes (f x), binds y to the result, and then evaluates body.

Non-recursive let and where bindings

In Haskell, let and where bindings can bind patterns. Their semantics is given by translation to a case, with an implicit implicit tilde (~).

let [x,y] = e in b

means

case e of { ~[x,y] -> b }

In our proposal, if there is a bang right at the top of a let-bound pattern, then the implicit tilde is replaced with an explicit bang:

let ![x,y] = e in b

means

case e of { ![x,y] -> b }

which is the same as

case e of { [x,y] -> b }

Similarly

let !y = f x in b

means

case f x of { !y -> b }

which evaluates the (f x), thereby giving a strict let.

Here is a more realistic example, a strict version of partition:

partitionS p [] = ([], [])
partitionS p (x:xs) 
  | p x       = (x:ys, zs)
  | otherwise = (ys, x:zs)
  where
    !(ys,zs) = partitionS p xs

The bang in the where clause ensures that the recursive call is evaluated eagerly. In Haskell today we are forced to write

partitionS p [] = ([], [])
partitionS p (x:xs) 
  = case partitionS p xs of
	(ys,zs) | p x       = (x:ys, zs)
		| otherwise = (ys, x:zs)

which is clumsier (especially if there are a bunch of where-clause bindings, all of which should be evaluated strictly), and doesn't provide the opportunity to fall through to the next equation (not needed in this example but often useful).

Changes to the Report

The changes to the Report would be these

  • Section 3.17, add pat ::= !pat to the syntax of patterns. We would need to take care to make clear whether
    f !x = 3
    
    was a definition of the function "!", or of "f". (There is a somewhat similar complication with n+k patterns; see the end of 4.3.3.2 in the Report. However we probably do not want to require parens thus
    f (!x) = 3
    
    which are required in n+k patterns.
  • Section 3.17.2: add new bullet 10, saying "Matching the pattern "!pat" against a value "v" behaves as follows:
    • if v is bottom, the match diverges
    • otherwise, "pat" is matched against "v".
  • Fig 3.1, 3.2, add a new case (t):
    case v of { !pat -> e; _ -> e' }
       = v `seq` case v of { pat -> e; _ -> e' }
    
  • Section 3.12 (let expressions). In the translation box, wherever there is a bang right at the top of a pattern on the LHS of the translation rule, omit the implicit tilde that occurs at the top of the pattern on the RHS of the rule.

The last point is the only delicate one. If we adopt this proposal we'd need to be careful about the semantics. For example, are bangs ok in recursive bindings? (Yes.) And for non-recursive bindings the order of the bindings shouldn't matter.

Tickets

#76
Bang patterns