Skip to content

HTTPS clone URL

Subversion checkout URL

You can clone with HTTPS or Subversion.

Download ZIP
Newer
Older
100644 802 lines (592 sloc) 24.96 kb
6a5224b RaimoNiskanen Cleanup and convert to Markdown
RaimoNiskanen authored
1 Author: Richard A. O'Keefe <ok(at)cs(dot)otago(dot)ac(dot)nz>
2 Status: Draft
3 Type: Standards Track
4 Erlang-Version: R12B-5
5 Created: 25-Feb-2009
6 Post-History:
7 ****
8 EEP 29: Abstract Patterns, Stage 1
9 ----
3ab7f88 RaimoNiskanen Added EEP 29: Abstract Patterns, Stage 1
RaimoNiskanen authored
10
11
12
13 Abstract
6a5224b RaimoNiskanen Cleanup and convert to Markdown
RaimoNiskanen authored
14 ========
15
16 Abstract Patterns are named pattern/guard combinations
17 which can be used
18
19 - in patterns, to support abstract data types
20 - as user-defined guards, guaranteed safe-for-guards
21 - as ordinary functions
22 - to replace many but not all uses of macros.
3ab7f88 RaimoNiskanen Added EEP 29: Abstract Patterns, Stage 1
RaimoNiskanen authored
23
6a5224b RaimoNiskanen Cleanup and convert to Markdown
RaimoNiskanen authored
24 The full proposal has six stages, of which this is stage 1.
25 This stage allows only simple abstract patterns which can be
26 handled by in-line substitution, so requiring no change to the
27 Erlang Virtual Machine.
3ab7f88 RaimoNiskanen Added EEP 29: Abstract Patterns, Stage 1
RaimoNiskanen authored
28
29
30
31 Specification
6a5224b RaimoNiskanen Cleanup and convert to Markdown
RaimoNiskanen authored
32 =============
3ab7f88 RaimoNiskanen Added EEP 29: Abstract Patterns, Stage 1
RaimoNiskanen authored
33
6a5224b RaimoNiskanen Cleanup and convert to Markdown
RaimoNiskanen authored
34 We introduce abstract pattern declarations and calls.
35 The syntax is given as an adaptation of that in parse.yrl.
3ab7f88 RaimoNiskanen Added EEP 29: Abstract Patterns, Stage 1
RaimoNiskanen authored
36
37 form -> abstract_pattern dot.
38
39 abstract_pattern -> '#' atom clause_args clause_guard
40 '->' expr.
41
6a5224b RaimoNiskanen Cleanup and convert to Markdown
RaimoNiskanen authored
42 For future reference, we'll use the schematic rule
43
44 #A(H1, ..., Hn) when G -> B.
45
46 where an empty clause_guard is taken to mean that `G` is 'true'.
47 `H1, ..., Hn` and `B` must all be patterns.
48
49 Abstract patterns may not be directly or indirectly recursive.
3ab7f88 RaimoNiskanen Added EEP 29: Abstract Patterns, Stage 1
RaimoNiskanen authored
50
51 expr_700 -> pattern_call.
52
53 pattern_call -> '#' atom argument_list
54
6a5224b RaimoNiskanen Cleanup and convert to Markdown
RaimoNiskanen authored
55 The expressions in the argument_list of a pattern_call must be
3ab7f88 RaimoNiskanen Added EEP 29: Abstract Patterns, Stage 1
RaimoNiskanen authored
56
6a5224b RaimoNiskanen Cleanup and convert to Markdown
RaimoNiskanen authored
57 - patterns in a pattern
58 - guard expressions elsewhere in a guard
59 - any expression elsewhere in an ordinary expression.
3ab7f88 RaimoNiskanen Added EEP 29: Abstract Patterns, Stage 1
RaimoNiskanen authored
60
6a5224b RaimoNiskanen Cleanup and convert to Markdown
RaimoNiskanen authored
61 There are two ways to understand the semantics of abstract
62 patterns: as function calls and as inline substitution.
3ab7f88 RaimoNiskanen Added EEP 29: Abstract Patterns, Stage 1
RaimoNiskanen authored
63
6a5224b RaimoNiskanen Cleanup and convert to Markdown
RaimoNiskanen authored
64 Considered as functions, stage 1 abstract patterns correspond
65 to two functions. Given our schematic rule, we get
3ab7f88 RaimoNiskanen Added EEP 29: Abstract Patterns, Stage 1
RaimoNiskanen authored
66
6a5224b RaimoNiskanen Cleanup and convert to Markdown
RaimoNiskanen authored
67 '#A->'(H1, ..., Hn) when G -> B.
3ab7f88 RaimoNiskanen Added EEP 29: Abstract Patterns, Stage 1
RaimoNiskanen authored
68
6a5224b RaimoNiskanen Cleanup and convert to Markdown
RaimoNiskanen authored
69 That is, part of the meaning of an abstract pattern is a
70 function that works just the way it looks as if it works.
71 (The name '#A->' is for expository purposes and should not
72 be taken literally. In particular, it is NOT part of this
73 specification that such a function should be directly
74 accessible at all, still less that it should be accessible
75 by a name of that form.) So
3ab7f88 RaimoNiskanen Added EEP 29: Abstract Patterns, Stage 1
RaimoNiskanen authored
76
6a5224b RaimoNiskanen Cleanup and convert to Markdown
RaimoNiskanen authored
77 #permute([R,A,T]) when is_atom(A) -> [T,A,R].
3ab7f88 RaimoNiskanen Added EEP 29: Abstract Patterns, Stage 1
RaimoNiskanen authored
78
6a5224b RaimoNiskanen Cleanup and convert to Markdown
RaimoNiskanen authored
79 acts in one direction just like
3ab7f88 RaimoNiskanen Added EEP 29: Abstract Patterns, Stage 1
RaimoNiskanen authored
80
6a5224b RaimoNiskanen Cleanup and convert to Markdown
RaimoNiskanen authored
81 '#permute->'([R,A,T]) when is_atom(A) -> [T,A,R].
3ab7f88 RaimoNiskanen Added EEP 29: Abstract Patterns, Stage 1
RaimoNiskanen authored
82
6a5224b RaimoNiskanen Cleanup and convert to Markdown
RaimoNiskanen authored
83 would. Because abstract patterns are not allowed to be
84 recursive and cannot have any side effects, it is safe
85 to call them in guards. As a guard test, `#A(E1,...,En)`
86 is equivalent to `(true = '#A->'(E1,...,En))`.
3ab7f88 RaimoNiskanen Added EEP 29: Abstract Patterns, Stage 1
RaimoNiskanen authored
87
6a5224b RaimoNiskanen Cleanup and convert to Markdown
RaimoNiskanen authored
88 In the other direction, we get
3ab7f88 RaimoNiskanen Added EEP 29: Abstract Patterns, Stage 1
RaimoNiskanen authored
89
6a5224b RaimoNiskanen Cleanup and convert to Markdown
RaimoNiskanen authored
90 '#A='(B) when G -> {H1, ..., Hn}.
3ab7f88 RaimoNiskanen Added EEP 29: Abstract Patterns, Stage 1
RaimoNiskanen authored
91
6a5224b RaimoNiskanen Cleanup and convert to Markdown
RaimoNiskanen authored
92 A pattern match
3ab7f88 RaimoNiskanen Added EEP 29: Abstract Patterns, Stage 1
RaimoNiskanen authored
93
6a5224b RaimoNiskanen Cleanup and convert to Markdown
RaimoNiskanen authored
94 #A(P1, ..., Pn) = E
3ab7f88 RaimoNiskanen Added EEP 29: Abstract Patterns, Stage 1
RaimoNiskanen authored
95
6a5224b RaimoNiskanen Cleanup and convert to Markdown
RaimoNiskanen authored
96 is equivalent to
3ab7f88 RaimoNiskanen Added EEP 29: Abstract Patterns, Stage 1
RaimoNiskanen authored
97
6a5224b RaimoNiskanen Cleanup and convert to Markdown
RaimoNiskanen authored
98 {P1, ..., Pn} = '#A='(E)
3ab7f88 RaimoNiskanen Added EEP 29: Abstract Patterns, Stage 1
RaimoNiskanen authored
99
6a5224b RaimoNiskanen Cleanup and convert to Markdown
RaimoNiskanen authored
100 When some of the patterns Hi, B use '=', the definition is
101 a little trickier. Suppose, for example, we have
3ab7f88 RaimoNiskanen Added EEP 29: Abstract Patterns, Stage 1
RaimoNiskanen authored
102
6a5224b RaimoNiskanen Cleanup and convert to Markdown
RaimoNiskanen authored
103 #foo([H|T] = X) -> {H,T}.
3ab7f88 RaimoNiskanen Added EEP 29: Abstract Patterns, Stage 1
RaimoNiskanen authored
104
6a5224b RaimoNiskanen Cleanup and convert to Markdown
RaimoNiskanen authored
105 A naive translation would be
3ab7f88 RaimoNiskanen Added EEP 29: Abstract Patterns, Stage 1
RaimoNiskanen authored
106
6a5224b RaimoNiskanen Cleanup and convert to Markdown
RaimoNiskanen authored
107 '#foo='({H,T}) -> [H|T] = X.
3ab7f88 RaimoNiskanen Added EEP 29: Abstract Patterns, Stage 1
RaimoNiskanen authored
108
6a5224b RaimoNiskanen Cleanup and convert to Markdown
RaimoNiskanen authored
109 which would not work, because X would be undefined. The
110 basic problem here is that '=' in patterns is symmetric,
111 while '=' in expressions is not. The real translation
112 has to be that
3ab7f88 RaimoNiskanen Added EEP 29: Abstract Patterns, Stage 1
RaimoNiskanen authored
113
6a5224b RaimoNiskanen Cleanup and convert to Markdown
RaimoNiskanen authored
114 #A(H11=H12=.., ..., Hn1=Hn2=..) when G -> B
3ab7f88 RaimoNiskanen Added EEP 29: Abstract Patterns, Stage 1
RaimoNiskanen authored
115
6a5224b RaimoNiskanen Cleanup and convert to Markdown
RaimoNiskanen authored
116 is equivalent to
3ab7f88 RaimoNiskanen Added EEP 29: Abstract Patterns, Stage 1
RaimoNiskanen authored
117
6a5224b RaimoNiskanen Cleanup and convert to Markdown
RaimoNiskanen authored
118 '#A='(B)
119 when G, X1=H11, X1=H12, ..., Xn=Hn1, Xn=Hn2, ...
120 -> {X1, ..., Xn}
3ab7f88 RaimoNiskanen Added EEP 29: Abstract Patterns, Stage 1
RaimoNiskanen authored
121
6a5224b RaimoNiskanen Cleanup and convert to Markdown
RaimoNiskanen authored
122 where the bindings `Xi=Hij` are both sorted and re-ordered
123 (that is, switched from `Xi=Hij` to `Hij=Xi`) according to
124 data flow. In the case of the `#foo/1` example, we'd get
3ab7f88 RaimoNiskanen Added EEP 29: Abstract Patterns, Stage 1
RaimoNiskanen authored
125
6a5224b RaimoNiskanen Cleanup and convert to Markdown
RaimoNiskanen authored
126 '#foo='({H,T}) when X1 = [H|T], X = X1 -> {X1}.
3ab7f88 RaimoNiskanen Added EEP 29: Abstract Patterns, Stage 1
RaimoNiskanen authored
127
6a5224b RaimoNiskanen Cleanup and convert to Markdown
RaimoNiskanen authored
128 The sorting and reordering process is easier than it sounds.
129 While there is an equation `Xi=Hij` such that either every
130 variable in `Hij` is known or `Xi` is known, add `Xi=Hij` if
131 `Hij` is all known, or `Hij = Xi` if `Xi` is known.
3ab7f88 RaimoNiskanen Added EEP 29: Abstract Patterns, Stage 1
RaimoNiskanen authored
132
6a5224b RaimoNiskanen Cleanup and convert to Markdown
RaimoNiskanen authored
133 This sorting-and-reordering-by-dataflow is also recommended
134 in the forward direction when B contains '='.
3ab7f88 RaimoNiskanen Added EEP 29: Abstract Patterns, Stage 1
RaimoNiskanen authored
135
6a5224b RaimoNiskanen Cleanup and convert to Markdown
RaimoNiskanen authored
136 Sometimes one or the other direction of an abstract pattern
137 cannot be constructed, even with sorting and reordering by
138 dataflow. This is typically because one side contains a
139 variable that doesn't occur on the other. For example,
3ab7f88 RaimoNiskanen Added EEP 29: Abstract Patterns, Stage 1
RaimoNiskanen authored
140
6a5224b RaimoNiskanen Cleanup and convert to Markdown
RaimoNiskanen authored
141 #first(X) -> {X,_}.
142 #second(Y) -> {_,Y}.
3ab7f88 RaimoNiskanen Added EEP 29: Abstract Patterns, Stage 1
RaimoNiskanen authored
143
6a5224b RaimoNiskanen Cleanup and convert to Markdown
RaimoNiskanen authored
144 are usable as patterns, but not as functions. The compiler
145 should issue a warning for such abstract patterns but allow
146 them. It should be a run-time error to call such a pattern
147 as a function as well. It should be possible to suppress
148 the warning, perhaps by
3ab7f88 RaimoNiskanen Added EEP 29: Abstract Patterns, Stage 1
RaimoNiskanen authored
149
6a5224b RaimoNiskanen Cleanup and convert to Markdown
RaimoNiskanen authored
150 -compile({pattern_only,[{first,1,second,1}]}).
3ab7f88 RaimoNiskanen Added EEP 29: Abstract Patterns, Stage 1
RaimoNiskanen authored
151
6a5224b RaimoNiskanen Cleanup and convert to Markdown
RaimoNiskanen authored
152 (That's within the current syntax. Ideally that should be
153 ` #first/1` and `#second/1`.)
3ab7f88 RaimoNiskanen Added EEP 29: Abstract Patterns, Stage 1
RaimoNiskanen authored
154
6a5224b RaimoNiskanen Cleanup and convert to Markdown
RaimoNiskanen authored
155 For another example,
3ab7f88 RaimoNiskanen Added EEP 29: Abstract Patterns, Stage 1
RaimoNiskanen authored
156
6a5224b RaimoNiskanen Cleanup and convert to Markdown
RaimoNiskanen authored
157 #is_date(#date(_,_,_)) -> true.
3ab7f88 RaimoNiskanen Added EEP 29: Abstract Patterns, Stage 1
RaimoNiskanen authored
158
6a5224b RaimoNiskanen Cleanup and convert to Markdown
RaimoNiskanen authored
159 is usable as a function, even/especially in a guard, but is
160 not usable as a pattern. The compiler should issue a
161 warning for such abstract patterns but allow them. It
162 should be a run-time error to call such a pattern as well.
163 It should be possible to suppress the warning, perhaps by
3ab7f88 RaimoNiskanen Added EEP 29: Abstract Patterns, Stage 1
RaimoNiskanen authored
164
6a5224b RaimoNiskanen Cleanup and convert to Markdown
RaimoNiskanen authored
165 -compile({function_only,[{is_date,1}]}).
3ab7f88 RaimoNiskanen Added EEP 29: Abstract Patterns, Stage 1
RaimoNiskanen authored
166
6a5224b RaimoNiskanen Cleanup and convert to Markdown
RaimoNiskanen authored
167 Definition via in-line substituion is straightforward.
168 All of the following rewrites assume a standard renaming
169 of variables.
3ab7f88 RaimoNiskanen Added EEP 29: Abstract Patterns, Stage 1
RaimoNiskanen authored
170
6a5224b RaimoNiskanen Cleanup and convert to Markdown
RaimoNiskanen authored
171 f(... #A(P1,...,Pn) ...) when Gf -> Bf
3ab7f88 RaimoNiskanen Added EEP 29: Abstract Patterns, Stage 1
RaimoNiskanen authored
172
6a5224b RaimoNiskanen Cleanup and convert to Markdown
RaimoNiskanen authored
173 rewrites to
3ab7f88 RaimoNiskanen Added EEP 29: Abstract Patterns, Stage 1
RaimoNiskanen authored
174
6a5224b RaimoNiskanen Cleanup and convert to Markdown
RaimoNiskanen authored
175 f(... B ...)
176 when G, Xi=Hij..., {P1,...,Pn} = {X1,...,Xn}, Gf -> Bf
3ab7f88 RaimoNiskanen Added EEP 29: Abstract Patterns, Stage 1
RaimoNiskanen authored
177
6a5224b RaimoNiskanen Cleanup and convert to Markdown
RaimoNiskanen authored
178 case ... of ... #(P1,...,Pn) ... when Gc -> Bc
3ab7f88 RaimoNiskanen Added EEP 29: Abstract Patterns, Stage 1
RaimoNiskanen authored
179
6a5224b RaimoNiskanen Cleanup and convert to Markdown
RaimoNiskanen authored
180 rewrites to
3ab7f88 RaimoNiskanen Added EEP 29: Abstract Patterns, Stage 1
RaimoNiskanen authored
181
6a5224b RaimoNiskanen Cleanup and convert to Markdown
RaimoNiskanen authored
182 case ... of ... B ...
183 when G, Xi=Hij..., {P1,...,Pn} = {X1,...,Xn}, Gc -> Bc
3ab7f88 RaimoNiskanen Added EEP 29: Abstract Patterns, Stage 1
RaimoNiskanen authored
184
6a5224b RaimoNiskanen Cleanup and convert to Markdown
RaimoNiskanen authored
185 P = E
3ab7f88 RaimoNiskanen Added EEP 29: Abstract Patterns, Stage 1
RaimoNiskanen authored
186
6a5224b RaimoNiskanen Cleanup and convert to Markdown
RaimoNiskanen authored
187 rewrites to
3ab7f88 RaimoNiskanen Added EEP 29: Abstract Patterns, Stage 1
RaimoNiskanen authored
188
6a5224b RaimoNiskanen Cleanup and convert to Markdown
RaimoNiskanen authored
189 case E of P -> ok end
3ab7f88 RaimoNiskanen Added EEP 29: Abstract Patterns, Stage 1
RaimoNiskanen authored
190
6a5224b RaimoNiskanen Cleanup and convert to Markdown
RaimoNiskanen authored
191 In a guard expression,
3ab7f88 RaimoNiskanen Added EEP 29: Abstract Patterns, Stage 1
RaimoNiskanen authored
192
6a5224b RaimoNiskanen Cleanup and convert to Markdown
RaimoNiskanen authored
193 (... #A(E1, ..., En) ...)
3ab7f88 RaimoNiskanen Added EEP 29: Abstract Patterns, Stage 1
RaimoNiskanen authored
194
6a5224b RaimoNiskanen Cleanup and convert to Markdown
RaimoNiskanen authored
195 rewrites to
196
197 {H1,...,Hn} = {E1,...,En}, G, (... B ...)
198
199 As a guard test,
200
201 #A(E1, ..., En)
202
203 rewrites to
204
205 {H1,...,Hn} = {E1,...,En}, G, true = B
206
207 As an ordinary expression,
208
209 #A(E1, ..., En)
210
211 rewrites to
3ab7f88 RaimoNiskanen Added EEP 29: Abstract Patterns, Stage 1
RaimoNiskanen authored
212
6a5224b RaimoNiskanen Cleanup and convert to Markdown
RaimoNiskanen authored
213 case {E1,...,En} of {H1,...,Hn} when G -> B end
3ab7f88 RaimoNiskanen Added EEP 29: Abstract Patterns, Stage 1
RaimoNiskanen authored
214
215
6a5224b RaimoNiskanen Cleanup and convert to Markdown
RaimoNiskanen authored
216
217 Motivation
218 ==========
219
220 Even in this restricted form, abstract patterns solve a lot
221 of problems that keep coming up on the Erlang mailing list.
222 They were invented to serve two main purposes: to greatly
223 reduce the need for the preprocessor, and to support the
224 use of abstract data types. It turns out that they can also
225 reduce the amount of keyboard work a programmer has to do,
226 and increase the amount of type information available to the
227 compiler.
228
229 Macros are often used to provide named constants.
230 For example,
231
232 -define(unknown, "UNKNOWN").
233 f(?unknown, Actors) -> Actors;
234 f(N, Actors) -> lists:keydelete(N, #actor.name, Actors).
235
236 A function is not used here because function calls may not
237 appear in patterns. Abstract patterns are functions that
238 are sufficiently restricted that they _may_ appear in patterns:
239
240 #unknown() -> "UNKNOWN".
241 f(#unknown(), Actors) -> Actors;
242 f(N, Actors) -> lists:keydelete(n, #actor.name, Actors).
243
244 Sometimes these constants must be computed.
245 For example,
246
247 -define(START_TIMEOUT, 1000 * 30).
248
249 Thanks to variable binding in guards, we can do that too:
250
251 #start_timeout() when N = 1000*30 -> N.
252
253 There are things that macros cannot do, because there needs
254 to be a guard test as well as a pattern. Macros can't bilocate.
255
256 #date(D, M, Y)
257 when is_integer(Y), Y >= 1600, Y =< 2500,
258 is_integer(M), M >= 1, M =< 12,
259 is_integer(D), D >= 1, D =< 31
260 -> {Y, M, D}.
261
262 #vector3(X, Y, Z)
263 when is_float(X), is_float(Y), is_float(Z)
264 -> {X, Y, Z}.
265
266 #mod_func(M, F) when is_atom(M), is_atom(F) -> {M, F}.
267
268 #mod_func_arity(M, F, A)
269 when is_atom(M), is_atom(F), is_integer(A), A >= 0
270 -> {M, F, A}.
271
272 Some macros cannot be replaced by abstract patterns.
273
274 -define(DBG(DbgLvl, Format, Data),
275 dbg(DbgLvl, Format, Data)).
276
277 cannot be an abstract pattern because the right hand side
278 involves a call to an ordinary function.
279
280 Some macros define guard tests. For example,
281
282 -define(tab, 9).
283 -define(space, 32).
284 -define(is_tab(X), X == ?tab).
285 -define(is_space(X), X == ?space).
286 -define(is_underline(X), X == $_).
287 -define(is_number(X), X >= $0, X =< $9).
288 -define(is_upper(X), X >= $A, X =< $Z).
289 -define(is_lower(X), X >= $a, X =< $z).
290
291 token([X|File], L, Result, Gen, BsNl)
292 when ?is_upper(X) ->
293 GenNew = case Gen of not_set -> var; _ -> Gen end,
294 {Rem, Var} = tok_var(File, [X]),
295 token(Rem, L, [{var,Var}|Result], GenNew, BsNl);
296 token([X|File], L, Result, Gen, BsNl)
297 when ?is_lower(X) ->
298 GenNew = case Gen of not_set -> var; _ -> Gen end,
299 {Rem, Var} = tok_var(File, [X]),
300 token(Rem, L, [{var,Var}|Result], GenNew, BsNl);
301 token([X|File], L, Result, Gen, BsNl)
302 when ?is_underline(X) ->
303 GenNew = case Gen of not_set -> var; _ -> Gen end,
304 {Rem, Var} = tok_var(File, [X]),
305 token(Rem, L, [{var,Var}|Result], GenNew, BsNl);
306
307 These can be converted to abstract patterns that are usable
308 as guard tests,
309
310 #tab() -> 9.
311 #space() -> 32.
312 #is_tab(#tab()) -> true.
313 #is_space(#space()) -> true.
314 #is_underline($_)) -> true.
315 #is_number(X) when X >= $0, X =< $9 -> true.
316 #is_upper(X) when X >= $A, X =< $Z -> true.
317 #is_lower(X) when X >= $a, X =< $z -> true.
318
319 token([X|File], L, Result, Gen, BsNl)
320 when #is_upper(X) ->
321 GenNew = case Gen of not_set -> var; _ -> Gen end,
322 {Rem, Var} = tok_var(File, [X]),
323 token(Rem, L, [{var,Var}|Result], GenNew, BsNl);
324 token([X|File], L, Result, Gen, BsNl)
325 when #is_lower(X) ->
326 GenNew = case Gen of not_set -> var; _ -> Gen end,
327 {Rem, Var} = tok_var(File, [X]),
328 token(Rem, L, [{var,Var}|Result], GenNew, BsNl);
329 token([X|File], L, Result, Gen, BsNl)
330 when #is_underline(X) ->
331 GenNew = case Gen of not_set -> var; _ -> Gen end,
332 {Rem, Var} = tok_var(File, [X]),
333 token(Rem, L, [{var,Var}|Result], GenNew, BsNl);
334
335 or to abstract patterns that can be used as patterns,
336
337 #tab() -> 9.
338 #space() -> 32.
339 #underline(X) when X == $_ -> X.
340 #number(X) when X >= $0, X =< $9 -> X.
341 #upper(X) when X >= $A, X =< $Z -> X.
342 #lower(X) when X >= $a, X =< $z -> X.
3ab7f88 RaimoNiskanen Added EEP 29: Abstract Patterns, Stage 1
RaimoNiskanen authored
343
6a5224b RaimoNiskanen Cleanup and convert to Markdown
RaimoNiskanen authored
344 token([#upper(X)|File], L, Result, Gen, BsNl) ->
345 GenNew = case Gen of not_set -> var; _ -> Gen end,
346 {Rem, Var} = tok_var(File, [X]),
347 token(Rem, L, [{var,Var}|Result], GenNew, BsNl);
348 token([#lower(X)|File], L, Result, Gen, BsNl) ->
349 GenNew = case Gen of not_set -> var; _ -> Gen end,
350 {Rem, Var} = tok_var(File, [X]),
351 token(Rem, L, [{var,Var}|Result], GenNew, BsNl);
352 token([#underline(X)|File], L, Result, Gen, BsNl) ->
353 GenNew = case Gen of not_set -> var; _ -> Gen end,
354 {Rem, Var} = tok_var(File, [X]),
355 token(Rem, L, [{var,Var}|Result], GenNew, BsNl);
356
357 Of course we can use disjunction in the guard of an
358 abstract pattern.
359
360 #id_start(X) when X >= $A, X =< $Z
361 ; X >= $a, X =< $z
362 ; X == $_ -> X.
363
364 token([#is_start(X)|File], L, Result, Gen, BsNl) ->
365 GenNew = case Gen of not_set -> var; _ -> Gen end,
366 {Rem, Var} = tok_var(File, [X]),
367 token(Rem, L, [{var,Var}|Result], GenNew, BsNl);
368
369 Yes, the original macro-based version could have done the same.
370 It's from the OTP sources; don't blame me.
371
372 Aside from replacing a pattern AND a guard, which macros cannot
373 do, the great advantages over patterns over macros are that
374
375 - they can be syntax-checked at the point of definition,
376 while macros can only be syntax-checked at the point of use;
377 - there is no problem, indeed no possibility, of variable name
378 capture;
379 - abstract patterns are value based, not token-list based, so
380 there are no problems with operators.
381
382 Consider the following OTP macro:
383
384 -define(IC_FLAG_TEST(_F1, _I1), ((_F1 band _I1) == _I1)).
385
386 First, the author was evidently scared of accidental collisions
387 with other variable names. Second, the parentheses look as
388 though they are there in case of operator precedence bugs.
389
390 There's at least one other like it,
391
392 -define(is_set(F, Bits), ((F) band (Bits)) == (F)).
393
394 which (correctly) suggests that the first macro doesn't have enough
395 parentheses. The abstract pattern equivalent,
396
397 #ic_flag_test(Flags, Mask) when Flags band Mask == Mask -> true.
398
399 has neither problem.
400
401 Once again, there are things that abstract patterns cannot do.
402 For example,
403
404 -define(get_max(_X, _Y), if _X > _Y -> _X; true -> _Y end).
405 -define(get_min(_X, _Y), if _X > _Y -> _Y; true -> _X end).
406
407 These cannot be abstract patterns because an abstract pattern
408 cannot contain an 'if' or a 'case' or any other control structure.
409 But they can, and should, be ordinary inline functions:
410
411 -compile({inline,[{max,2},{min,2}]}).
412 max(X, Y) -> if X > Y -> X; true -> Y end.
413 min(X, Y) -> if X > Y -> Y; true -> X end.
414
415 Abstract patterns don't need to do what ordinary functions can.
416 Here's another example from the OTP sources.
417
418 -define(LOWER(Char),
419 if
420 Char >= $A, Char =< $Z ->
421 Char - ($A - $a);
422 true ->
423 Char
424 end).
425 tolower(Chars) ->
426 [?LOWER(Char) || Char <- Chars].
427
428 This could, and should, have been an ordinary inlined function.
429 Abstract patterns don't need to do what ordinary functions can.
430 Let's examine it a little closer. Suppose we had a pattern
431
432 Cl = #lower(Cx)
433
434 which when used as an ordinary function converted both `$x` and `$X`
435 to `$x`. Then when used as a pattern `#lower(Cx) = $x`, there would
436 be two correct answers for `Cx`. There are no other cases where
437 a pattern may match more than one way. The fact that abstract
438 patterns cannot do conditionals is one of the things that makes
439 them usable as patterns.
440
441 Macros are sometimes used for module names.
442
443 -define(SERVER,{rmod_random_impl,
444 list_to_atom("babbis@" ++
445 hd(tl(string:tokens(atom_to_list(node()),"@"))))}).
446
447 -define(CLIENTMOD,'rmod_random').
448
449 produce() -> ?CLIENTMOD:produce(?SERVER).
450
451 Abstract patterns can be used for this too, but there is an
452 error waiting to happen.
453
454 server() -> {rmod_random_impl,
455 list_to_atom("babbis@" ++
456 hd(tl(string:tokens(atom_to_list(node()),"@"))))}.
457
458 #client_mod() -> 'rmod_random'.
3ab7f88 RaimoNiskanen Added EEP 29: Abstract Patterns, Stage 1
RaimoNiskanen authored
459
6a5224b RaimoNiskanen Cleanup and convert to Markdown
RaimoNiskanen authored
460 produce -> #client_mod():produce(server()).
461
462 The risk is that of writing `#client_mod:produce(server())`,
463 which is the syntax we'll want in stage 2 for calling an
464 abstract pattern defined in another module.
465 There is one thing that macros are used for that abstract
466 patterns can be used for, but you'd probably rather not.
467
468 Abstract patterns were also invented with the aim of
469 replacing at least some uses of records. Frames (or Joe
470 Armstrong's structs, which are essentially the same thing)
471 are a superior way to do that. Let's see a simple case.
472
473 -record(mark_params, {cell_id,
474 virtual_col,
475 virtual_row
476 }).
477 ...
478 MarkP = mark_params(),
479 ...
480 NewMarkP = MarkP#mark_params{cell_id = undefined,
481 virtual_col = undefined,
482 virtual_row = VirtualRow
483 },
484
485 This becomes
486
487 % General
488 #mark_params(Cell, Row, Col) -> {mark_params, Cell, Row, Col}.
489 % Initial value
490 #mark_params() -> #mark_params(undefined, undefined, undefined).
491 % Recogniser
492 #is_mark_params({mark_params,_,_,_}) -> true.
493 % Cell extractor
494 #mark_params__cell(#mark_params(Cell,_,_)) -> Cell.
495 % Cell updater
496 #mark_params__cell(Cell, #mark_params(_,R,C)) ->
497 #mark_params(Cell, R, C).
498 % Row extractor
499 #mark_params__row(#mark_params(_,Row,_)) -> Row.
500 % Row updater
501 #mark_params__row(Row, #mark_params(K,_,C)) ->
502 #mark_params(K, Row, C).
503 % Col extractor
504 #mark_params__col(#mark_params(_,_,Col)) -> Col.
505 % Col updater
506 #mark_params__col(Col, #mark_params(K,R,_)) ->
507 #mark_params(K, R, Col).
508 ...
509 MarkP = #mark_params(),
510 ...
511 NewMarkP = #mark_params__row(VirtualRow,
512 #mark_params__col(undefined,
513 #mark_params__cell(undefined, MarkP)))
514
515 The extractor and updater patterns can be derived automatically,
516 which comes in stage 4. With frames/structs, we may never bother.
517
518 There is a feature of Haskell that I have long loved.
519 That is so-called "n+k patterns", where a pattern may be N+K
520 for N a variable and K a positive integer. This matches V
521 if V is an integer greater than or equal to K, and binds N
522 to V - K. For example,
523
524 fib 0 = 1
525 fib 1 = 1
526 fib (n+2) = fib n + fib (n+1)
527
528 Not that that's a good way to implement the Fibonacci function,
529 of course. (It takes O(phi^N) when O(log N) is attainable.)
530 There's no such thing in Erlang. But with abstract patterns,
531 we could program it:
532
533 #succ(M) when is_integer(N), N >= 1, M = N - 1 -> N.
534
535 fib(0) -> 1;
536 fib(1) -> 1;
537 fib(#succ(#succ(N)) -> fib(N) + fib(N+1).
538
539 Sometimes we want a three-way split:
540
541 N = 1
542 N = 2k+0 (k >= 1)
543 N = 2k+1 (k >= 1)
544
545 We can program that too:
546
547 #one() -> 1.
548 #even(K)
549 when is_integer(N), (N band 1) == 0, N >= 2, K = N div 2
550 -> N.
551 #odd(K)
552 when is_integer(N), (N band 1) == 1, N >= 3, K = N div 2
553 -> N.
554
555 ruler(#one()) -> 0 ;
556 ruler(#even(K)) -> 1 + ruler(K);
557 ruler(#odd(K)) -> 1.
558
559 Let's turn to abstract data types.
560 There are three obvious ways to implement association lists
561 as single data structures:
562
563 [{K1,V1}, ..., {Kn,Vn}] % pairs
564 [K1,V1, ..., Kn,Vn] % alternating
565 {K1,V1, ..., {Kn,Vn,[]}} % triples
566
567 Suppose you cannot make up your mind which is better.
568
569 #empty_alist() -> [].
570 -ifdef(PAIRS).
571 #non_empty_alist(K,V,R) -> [{K,V}|R].
572 -else.
573 -ifdef(TRIPLES).
574 #non_empty_alist(K,V,R) -> {K,V,R}.
575 -else.
576 #non_empty_alist(K,V,R) -> [K,V|R].
577 -endif.
578 -endif.
579
580 zip([K|Ks], [V|Vs]) ->
581 #non_empty_alist(K, V, zip(Ks, Vs));
582 zip([], []) ->
583 #empty_alist().
584
585 lookup(K, #non_empty_alist(K,V,_), _) ->
586 V;
587 lookup(K, #non_empty_alist(_,_,R), D) ->
588 lookup(K, R, D);
589 lookup(K, #empty_alist(), D) ->
590 D.
591
592 Now you can switch between the three implementations, for
593 testing and benchmarking, by flicking a single preprocessor
594 switch.
595
596 Sometimes there is something that would have been an algebraic
597 data type in Haskell or Clean or SML or CAML, but in Erlang we
598 just have to use a variety of tuples. The parsed form of
599 Erlang source code is a good example.
600
601 lform({attribute,Line,Name,Arg}, Hook) ->
602 lattribute({attribute,Line,Name,Arg}, Hook);
603 lform({function,Line,Name,Arity,Clauses}, Hook) ->
604 lfunction({function,Line,Name,Arity,Clauses}, Hook);
605 lform({rule,Line,Name,Arity,Clauses}, Hook) ->
606 lrule({rule,Line,Name,Arity,Clauses}, Hook);
607 %% These are specials to make it easier for the compiler.
608 lform({error,E}, _Hook) ->
609 leaf(format("~p\n", [{error,E}]));
610 lform({warning,W}, _Hook) ->
611 leaf(format("~p\n", [{warning,W}]));
612 lform({eof,_Line}, _Hook) ->
613 $\n.
614
615 We can define abstract patterns for these.
616
617 #attribute(L, N, A) -> {attribute, L, N, A}.
618 #function( L, N, A, C) -> {function, L, N, A, C}.
619 #rule( L, N, A, C) -> {rule, L, N, A, C}.
620 #eof( L) -> {eof, L}.
621 #error( E_ -> {error, E}.
622 #warning( W) -> {warning, W}.
623
624 #attribute() -> #attribute(_,_,_).
625 #function() -> #function(_,_,_,_).
626 #rule() -> #rule(_,_,_,_).
627
628 lform(Form, Hook) ->
629 case Form
630 of #attribute() -> lattribute(Form, Hook)
631 ; #function() -> lfunction( Form, Hook)
632 ; #rule() -> lrule( Form, Hook)
633 ; #error(E) -> leaf(format("~p\n", [{error,E}]))
634 ; #warning(W) -> leaf(format("~p\n", [{warning,W}]))
635 ; #eof(_) -> $\n
636 end.
637
638 It would almost be worth defining these patterns even if these
639 were their only occurrences, simply for the clarity they permit.
640 But these patterns would be used over and over again. Using
641 the patterns not only makes the code shorter and clearer, it
642 gives us two kinds of protection against changes to the data
643 representation. For example, suppose we decided to hold
644 Name/Arity information in 'function' and 'rule' tuples as
645 pairs, not as separate fields. Then we could do
646
647 -ifdef(OLD_DATA).
648 #function( L, N, A, C) -> {function, L, N, A, C}.
649 #rule( L, N, A, C) -> {rule, L, N, A, C}.
650 #function( L, {N,A}, C) -> {function, L, N, A, C}.
651 #rule( L, {N,A}, C) -> {rule, L, N, A, C}.
652 -else.
653 #function( L, N, A, C) -> {function, L, {N,A}, C}.
654 #rule( L, N, A, C) -> {rule, L, {N,A}, C}.
655 #function( L, NA, C) -> {function, L, NA, C}.
656 #rule( L, NA, C) -> {rule, L, NA, C}.
657 -endif.
658
659 The rest of the code would remain unchanged. That's one kind of
660 protection. It doesn't help us when we need to add new cases.
661 That's when the second kind of protection comes up. Looking
662 for `#function` is a much safer guide to finding relevant places
663 than looking for `function`.
3ab7f88 RaimoNiskanen Added EEP 29: Abstract Patterns, Stage 1
RaimoNiskanen authored
664
665
666
667 Rationale
6a5224b RaimoNiskanen Cleanup and convert to Markdown
RaimoNiskanen authored
668 =========
669
670 There is more to the idea of abstract patterns than this
671 specification describes. Here's a "road map".
672
673 * Stage 0:
674 Allow pattern matching in guards.
675 This is the subject of another EEP, as it is
676 desirable in itself. This MUST be implemented
677 first before implementing Stage 1, because that's
678 what we want inlinable pattern calls to expand to.
679
680 * Stage 1:
681 Simple abstract patterns restricted so that they
682 can be implemented exclusively by inline expansion.
683 This requires no change to the VM other than the
684 changes required for Stage 0.
685
686 Import/export of patterns can be faked using the
687 preprocessor to -include definitions; this is not
688 ideal, but it's an acceptable stopgap.
689
690 * Stage 2:
691 Abstract functions are (pairs of) real functions,
692 they may be -exported and -imported, may be called
693 with module prefixes, can be replaced by hot loading,
694 should be traceable, debuggable, profilable, and so
695 on, just like other functions. In Stage 2, exported
696 abstract patterns would need inline declarations if
697 they are to be inlined; other patterns would continue
698 to be inlined except when compiled in debugging mode.
699
700 This requires fairly substantial changes to the
701 run time system. The big payoff here is that
702 imported abstract patterns can be replaced by hot
703 loading, unlike macros.
3ab7f88 RaimoNiskanen Added EEP 29: Abstract Patterns, Stage 1
RaimoNiskanen authored
704
6a5224b RaimoNiskanen Cleanup and convert to Markdown
RaimoNiskanen authored
705 * Stage 3:
3ab7f88 RaimoNiskanen Added EEP 29: Abstract Patterns, Stage 1
RaimoNiskanen authored
706
6a5224b RaimoNiskanen Cleanup and convert to Markdown
RaimoNiskanen authored
707 #fun [Module:]Name/Arity and
708 #fun (P1, ..., Pn) when G -> B end
3ab7f88 RaimoNiskanen Added EEP 29: Abstract Patterns, Stage 1
RaimoNiskanen authored
709
6a5224b RaimoNiskanen Cleanup and convert to Markdown
RaimoNiskanen authored
710 forms are introduced, and a metacall
3ab7f88 RaimoNiskanen Added EEP 29: Abstract Patterns, Stage 1
RaimoNiskanen authored
711
6a5224b RaimoNiskanen Cleanup and convert to Markdown
RaimoNiskanen authored
712 #Var(E1,...,En) is added.
713
714 This requires extensions to the Erlang term
715 representation and the VM. The gain here is that
716 the FAQ "how do I pass a pattern as a parameter"
717 finally gets a safe answer. For example,
718
719 collect_messages(P) ->
720 lists:reverse(collect_messages_loop(P, [])).
721
722 collect_messages_loop(P, Ms) ->
723 receive M = #P() -> collect_messages_loop([M|Ms])
724 after 0 -> Ms
725 end.
726
727 gathers all the messages currently in the mailbox
728 that match a pattern passed as a parameter.
3ab7f88 RaimoNiskanen Added EEP 29: Abstract Patterns, Stage 1
RaimoNiskanen authored
729
6a5224b RaimoNiskanen Cleanup and convert to Markdown
RaimoNiskanen authored
730 * Stage 4:
731 `<expression>#<pattern call>` field update,
732 as described in the original proposal.
3ab7f88 RaimoNiskanen Added EEP 29: Abstract Patterns, Stage 1
RaimoNiskanen authored
733
6a5224b RaimoNiskanen Cleanup and convert to Markdown
RaimoNiskanen authored
734 * Stage 5:
735 Multi-clause abstract patterns,
736 as described in the original proposal.
737 Multi-clause abstract patterns CAN handle
738 examples like `?get_max` and `?LOWER`, which makes
739 them even more useful in guards, but more than
740 a little dubious as patterns.
3ab7f88 RaimoNiskanen Added EEP 29: Abstract Patterns, Stage 1
RaimoNiskanen authored
741
6a5224b RaimoNiskanen Cleanup and convert to Markdown
RaimoNiskanen authored
742 * Stage 6:
743 "Hybrid" abstract patterns, where in `#A/M+N` the
744 first `M` arguments are always inputs, and only
745 the last `N` are outputs. This one isn't actually
746 my idea. The example
3ab7f88 RaimoNiskanen Added EEP 29: Abstract Patterns, Stage 1
RaimoNiskanen authored
747
6a5224b RaimoNiskanen Cleanup and convert to Markdown
RaimoNiskanen authored
748 #range(L, U, N)
749 when is_integer(N), L =< N, N =< U
750 -> N.
3ab7f88 RaimoNiskanen Added EEP 29: Abstract Patterns, Stage 1
RaimoNiskanen authored
751
6a5224b RaimoNiskanen Cleanup and convert to Markdown
RaimoNiskanen authored
752 comes from the mailing list. I don't like this very
753 much, and note that for some purposes,
3ab7f88 RaimoNiskanen Added EEP 29: Abstract Patterns, Stage 1
RaimoNiskanen authored
754
6a5224b RaimoNiskanen Cleanup and convert to Markdown
RaimoNiskanen authored
755 range(L, U) ->
756 #fun(N) when is_integer(N), L =< N, N =< U
757 -> N end.
3ab7f88 RaimoNiskanen Added EEP 29: Abstract Patterns, Stage 1
RaimoNiskanen authored
758
6a5224b RaimoNiskanen Cleanup and convert to Markdown
RaimoNiskanen authored
759 can do the same job.
3ab7f88 RaimoNiskanen Added EEP 29: Abstract Patterns, Stage 1
RaimoNiskanen authored
760
6a5224b RaimoNiskanen Cleanup and convert to Markdown
RaimoNiskanen authored
761 What I've done for this proposal is to strip away everything
762 that isn't essential. We get data abstraction, user defined
763 guard tests and functions, and a replacement for many uses
764 of macros, without run time overheads and without changes to
765 anything except the compiler front end, assuming that Stage 0
766 is done first.
3ab7f88 RaimoNiskanen Added EEP 29: Abstract Patterns, Stage 1
RaimoNiskanen authored
767
768
769
6a5224b RaimoNiskanen Cleanup and convert to Markdown
RaimoNiskanen authored
770 Backwards Compatibility
771 =======================
772
773 Erlang currently uses the sharp sign for record syntax.
774 Since record syntax uses curly braces, and abstract patterns
775 use round parentheses, no existing code should be affected.
776
777
3ab7f88 RaimoNiskanen Added EEP 29: Abstract Patterns, Stage 1
RaimoNiskanen authored
778
6a5224b RaimoNiskanen Cleanup and convert to Markdown
RaimoNiskanen authored
779 Reference Implementation
780 ========================
781
782 Sketched above. Given stage 0, this stage 1 is within my
783 knowledge and abilities, but I don't understand the Erlang
784 VM well enough to do stage 0.
3ab7f88 RaimoNiskanen Added EEP 29: Abstract Patterns, Stage 1
RaimoNiskanen authored
785
786
787
6a5224b RaimoNiskanen Cleanup and convert to Markdown
RaimoNiskanen authored
788 Copyright
789 =========
790
791 This document has been placed in the public domain.
3ab7f88 RaimoNiskanen Added EEP 29: Abstract Patterns, Stage 1
RaimoNiskanen authored
792
793
794
6a5224b RaimoNiskanen Cleanup and convert to Markdown
RaimoNiskanen authored
795 [EmacsVar]: <> "Local Variables:"
796 [EmacsVar]: <> "mode: indented-text"
797 [EmacsVar]: <> "indent-tabs-mode: nil"
798 [EmacsVar]: <> "sentence-end-double-space: t"
799 [EmacsVar]: <> "fill-column: 70"
800 [EmacsVar]: <> "coding: utf-8"
801 [EmacsVar]: <> "End:"
Something went wrong with that request. Please try again.