# Changes between Version 4 and Version 5 of BangPatterns

Show
Ignore:
Timestamp:
02/06/06 07:42:52 (7 years ago)
Comment:

--

Unmodified
Added
Removed
Modified
• ## BangPatterns

v4 v5
11[[PageOutline]]
22= Bang patterns =
3
4== Tickets ==
5[[TicketQuery(description~=BangPatterns)]]
36
47== Goal ==

6366
6467
65 == Non-recursive let and where bindings ==
66
67 First, we deal with ''non-recursive'' bindings only.
68 In Haskell, let and where bindings can bind patterns.  Their semantics is given by translation to a case, with an implicit implicit tilde (~).
69 {{{
70 let [x,y] = e in b
68== Let and where bindings ==
69
70In Haskell, let and where bindings can bind patterns.  We propose to modify
71this by allowing an optional bang at the top level of the pattern.  Thus for example:
72{{{
73  let ![x,y] = e in b
74}}}
75The "`!`" should not be regarded as part of the pattern; after all,
76in a function argument `![x,y]` means the same as `[x,y]`.  Rather, the "`!`"
77is part of the syntax of `let` bindings.
78
79The semantics is simple; the above program is equivalent to:
80{{{
81  let p@[x,y] = e in p `seq` b
82}}}
83That is, for each bang pattern, invent a variable `p`, bind it to the
84banged pattern (removing the bang) with an as-pattern, and `seq` on it
85in the body of the `let`.  (Thanks to Ben Rudiak-Gould for suggesting
86this idea.)
87
88A useful special case is when the pattern is a variable:
89Similarly
90{{{
91  let !y = f x in b
7192}}}
7293means
7394{{{
74 case e of { ~[x,y] -> b }
75 }}}
76 In our proposal, if there is a bang right at the top of a let-bound pattern,
77 then the implicit tilde is replaced with an explicit bang:
78 {{{
79 let ![x,y] = e in b
80 }}}
81 means
82 {{{
83 case e of { ![x,y] -> b }
84 }}}
85 which is the same as
86 {{{
87 case e of { [x,y] -> b }
88 }}}
89 Similarly
90 {{{
91 let !y = f x in b
92 }}}
93 means
94 {{{
95 case f x of { !y -> b }
96 }}}
97 which evaluates the (f x), thereby giving a strict `let`.
98
99 == Examples ==
95  let y = f x in y `seq` b
96}}}
97which evaluates the `(f x)`, thereby giving a strict `let`.
98
99A useful law is this.  A ''non-recursive'' bang-pattern binding
100is equivalent to a `case` expression:
101{{{
102  let !p = <rhs> in <body>
103     is equivalent to (when the let is non-recursive)
104  case <rhs> of !p -> <body>
105}}}
106
107=== Example ===
100108Here is a more realistic example, a strict version of partition:
101109{{{

122130needed in this example but often useful).
123131
132== Recursive let and where bindings ==
133
134At first you might think that a recursive bang pattern
135don't make sense: how can you evaluate it strictly if it doesn't exist
136yet?  But consider
137{{{
138  let !xs = if funny then 1:xs else 2:xs in ...
139}}}
140Here the binding is recursive, but the translation still makes sense:
141{{{
142  let xs = if funny then 1:xs else 2:xs
143  in xs `seq` ...
144}}}
145
124146== Top-level bang-pattern bindings ==
125147

137159But it's not clear why it would be necessary or useful.  '''Conservative
138160conclusion''': no top-level bang-patterns.
139
140 == Recursive let and where bindings ==
141
142 It is just about possible to make sense of bang-patterns in
143 ''recursive'' let and where bindings.  At first you might think they
144 don't make sense: how can you evaluate it strictly if it doesn't exist
145 yet?  But consider
146 {{{
147   let !xs = if funny then 1:xs else 2:xs in ...
148 }}}
149 Here the binding is recursive, but makes sense to think of it
150 as equivalent to
151 {{{
152   let xs = if funny then 1:xs else 2:xs
153   in xs `seq` ...
154 }}}
155 But (a) it must be unusual, and (b) I have found it very hard to
156 come up with a plausible translation (that deals with all the tricky
157 points below).
158
159 '''Conservative conclusion''': bang-pattern bindings must be non-recursive.
160161
161162== Tricky point: syntax ==

183184what could {{{(+ 3, + 4)}}} mean apart from a tuple of two sections?
184185
185 == Tricky point: nested bangs ==
186== Tricky point: nested bangs (part 1) ==
187
188Consider this:
189{{{
190  let (x, Just !y) = <rhs> in <body>
191}}}
192Is `y` evaluted before `<body>` is begun?  No, it isn't.  That would be
193quite wrong.  Pattern matching in a `let` is lazy; if any of the variables bound
194by the pattern is evaluated, then the whole pattern is matched.  In this example,
195if `x` or `y` is evaluated, the whole pattern is matched, which in turn forces
196evaluation of `y`.  The binding is equivalent to
197{{{
198  let t = <rhs>
199      x = case t of { (x, Just !y) -> x }
200      y = case t of { (x, Just !y) -> y }
201  in <body>
202}}}
203
204== Tricky point: nested bangs (part 2) ==
186205
187206Consider this:

209228}}}
210229This won't work, because using `seq` on `t` won't force `y`.
211 You could build an intermediate tuple, thus:
230However, the semantics says that the original code is equivalent to
231{{{
232  let p@(x, Just !y) = <rhs> in p `seq` <body>
233}}}
234and we can desugar that in obvious way to
212235{{{
213236  let
214     t = case <rhs> of (x, Just !y) -> (x,y)
215     x = fst t
216     y = snd t
237    t = <rhs>
238    p = case t of p@(x, Just !y) -> p
239    x = case t of p@(x, Just !y) -> x
240    y = case t of p@(x, Just !y) -> y
241  in
242  p `seq` <body>
243}}}
244which is fine.
245
246You could also build an intermediate tuple, thus:
247{{{
248  let
249    t = case <rhs> of p@(x, Just !y) -> (p,x,y)
250    p = sel13 t
251    x = sel23 t
252    y = sel33 t
217253  in
218254  t `seq` <body>
219255}}}
220 But that seems a waste when the patttern is itself just a tuple;
221 and it needs adjustment when there is only one bound variable.
222
223 Bottom line: for non-recursive bindings, the straightforward translation
224 to a `case` is, well, straightforward.   Recursive bindings could probably
225 be handled, but it's more complicated.
256Indeed GHC does just this for complicated pattern bindings.
226257
227258== Tricky point: pattern-matching semantics ==

319350non-recursive bindings the order of the bindings shouldn't matter.
320351
321 == Tickets ==
322 [[TicketQuery(description~=BangPatterns)]]