Skip to content

HTTPS clone URL

Subversion checkout URL

You can clone with HTTPS or Subversion.

Download ZIP
Newer
Older
100644 300 lines (220 sloc) 8.498 kb
6a5224b @RaimoNiskanen Cleanup and convert to Markdown
RaimoNiskanen authored
1 Author: Björn Gustavsson <bjorn(at)erlang(dot)org>
2 Status: Accepted/R13A Proposal is to be implemented in OTP release R13A
3 Type: Standards Track
4 Erlang-Version: R12B-5
5 Created: 28-Jan-2009
6 Post-History:
7 ****
8 EEP 26: Make andalso and orelse tail-recursive
9 ----
6622778 @RaimoNiskanen Added EEP 26
RaimoNiskanen authored
10
11
12
13 Abstract
6a5224b @RaimoNiskanen Cleanup and convert to Markdown
RaimoNiskanen authored
14 ========
6622778 @RaimoNiskanen Added EEP 26
RaimoNiskanen authored
15
6a5224b @RaimoNiskanen Cleanup and convert to Markdown
RaimoNiskanen authored
16 Erlang 5.1 added the ability to use 'andalso', 'orelse',
17 'and', and 'or' in guards. However, the semantics for
18 'andalso' and 'orelse' differs from that in other related
19 languages, causing confusion and inefficiency.
20
21 I propose making 'andalso' and 'orelse' tail-recursive.
22
23 This EEP is partly based on Richard O'Keefe's [EEP 17][],
24 but has a narrower scope.
6622778 @RaimoNiskanen Added EEP 26
RaimoNiskanen authored
25
26
27
28 Specification
6a5224b @RaimoNiskanen Cleanup and convert to Markdown
RaimoNiskanen authored
29 =============
6622778 @RaimoNiskanen Added EEP 26
RaimoNiskanen authored
30
6a5224b @RaimoNiskanen Cleanup and convert to Markdown
RaimoNiskanen authored
31 Currently, `(E1 andalso E2)` as an expression acts like
6622778 @RaimoNiskanen Added EEP 26
RaimoNiskanen authored
32
6a5224b @RaimoNiskanen Cleanup and convert to Markdown
RaimoNiskanen authored
33 case E1 of
34 false -> false;
35 true -> case E2 of
36 false -> false;
37 true -> true
38 end
39 end
6622778 @RaimoNiskanen Added EEP 26
RaimoNiskanen authored
40
6a5224b @RaimoNiskanen Cleanup and convert to Markdown
RaimoNiskanen authored
41 except that the former raises `{badarg,NonBool}` exceptions and the
42 latter raises `{case_clause,NonBool}` ones.
6622778 @RaimoNiskanen Added EEP 26
RaimoNiskanen authored
43
6a5224b @RaimoNiskanen Cleanup and convert to Markdown
RaimoNiskanen authored
44 This should be changed to
6622778 @RaimoNiskanen Added EEP 26
RaimoNiskanen authored
45
6a5224b @RaimoNiskanen Cleanup and convert to Markdown
RaimoNiskanen authored
46 case E1 of
47 false -> false;
48 true -> E2
49 end.
6622778 @RaimoNiskanen Added EEP 26
RaimoNiskanen authored
50
6a5224b @RaimoNiskanen Cleanup and convert to Markdown
RaimoNiskanen authored
51 Currently, `(E1 orelse E2)` as an expression acts like
6622778 @RaimoNiskanen Added EEP 26
RaimoNiskanen authored
52
6a5224b @RaimoNiskanen Cleanup and convert to Markdown
RaimoNiskanen authored
53 case E1 of
54 true -> true
55 false -> case E2 of
56 true -> true
57 false -> false
6622778 @RaimoNiskanen Added EEP 26
RaimoNiskanen authored
58 end
6a5224b @RaimoNiskanen Cleanup and convert to Markdown
RaimoNiskanen authored
59 end
6622778 @RaimoNiskanen Added EEP 26
RaimoNiskanen authored
60
6a5224b @RaimoNiskanen Cleanup and convert to Markdown
RaimoNiskanen authored
61 except that the former raises `{badarg,NonBool}` exceptions and the
62 latter raises `{case_clause,NonBool}` ones.
6622778 @RaimoNiskanen Added EEP 26
RaimoNiskanen authored
63
6a5224b @RaimoNiskanen Cleanup and convert to Markdown
RaimoNiskanen authored
64 This should be changed to
6622778 @RaimoNiskanen Added EEP 26
RaimoNiskanen authored
65
6a5224b @RaimoNiskanen Cleanup and convert to Markdown
RaimoNiskanen authored
66 case E1 of
67 true -> true;
68 false -> E2
69 end
6622778 @RaimoNiskanen Added EEP 26
RaimoNiskanen authored
70
71 Motivation
6a5224b @RaimoNiskanen Cleanup and convert to Markdown
RaimoNiskanen authored
72 ==========
73
74 To unlock the full potential of 'andalso'/'orelse' in Erlang.
75
76 Given the current implementation, you either have to make
77 rewrite code that is naturally written using AND and OR
78 operators using 'case', or only use 'andalso'/'orelse' when
79 you know that your lists are relatively short.
80
81 For instance, the function `all/2` that returns 'true' if
82 all elements of a list satisfies a predicate and 'false'
83 otherwise, can be written like this:
84
85 all(Pred, [Hd|Tail]) ->
86 Pred(Hd) and all(Pred, Tail);
87 all(_, []) ->
88 true.
89
90 In each recursion, we test that the current element Hd
91 satisfies the predicate AND that the rest of the list also
92 matches the predicate. The code reads almost like English.
93
94 Of course, 'and' evaluates both of its operand, so the entire
95 list will be traversed even if the first element of the list
96 fails to satisfy the predicate. Furthermore, 'and' is not
97 tail-recursive, so the function will use stack space
98 proportional to the length of the list.
99
100 To avoid the traversing the rest of the list if one element
101 fails to satisfy the predicate, we can use 'andalso':
102
103 all(Pred, [Hd|Tail]) ->
104 Pred(Hd) andalso all(Pred, Tail);
105 all(_, []) ->
106 true.
107
108 As soon as `Pred(Hd)` returns false, the recursion will
109 stop and the rest of the list need not be traversed.
110 Since 'andalso' is not tail-recursive, however, the
111 function will need stack space proportional to the number
112 of list elements that are traversed.
113
114 To see more clearly that 'andalso' is not tail-recursive,
115 here is `all/1` with 'andalso' expanded out to a nested
116 'case' expression (as it would be in R12B-5):
117
118 all(Pred, [Hd|Tail]) ->
119 case Pred(Hd) of
120 false -> false;
121 true -> case all(Pred, Tail) of
122 false -> false;
123 true -> true
124 end
125 end;
126 all(_, []) ->
127 true.
128
129 To make `all/1` tail-recursive in R12B-5, you would have
130 to write a 'case' expression yourself:
131
132 all(Pred, [Hd|Tail]) ->
133 case Pred(Hd) of
134 false -> false;
135 true -> all(Pred, Tail)
136 end;
137 all(_, []) ->
138 true.
139
140 If this EEP is accepted, in R13B we could write like
141 this
142
143 all(Pred, [Hd|Tail]) ->
144 Pred(Hd) andalso all(Pred, Tail);
145 all(_, []) ->
146 true.
147
148 and the `all/1` function would be tail-recursive.
149
150 In my opinion, the latter is easier to read and write.
151 The 'case' expression is mostly boiler-plate code
152 where 'true' and 'false' must be correctly spelled
153 several times. (Misspellings like 'ture' and 'flase'
154 are quite common, but are in most cases found the
155 first time the program is tested.)
156
157 It could be argued that because Erlang has clearly defined truth
158 values (unlike some other languages where 0 is false and
159 everything else true), all operators that operate on booleans
160 should make sure that their arguments are booleans.
161
162 Testing both arguments of 'and' and 'or' makes
163 sense, because the code executed for those operators always GETS
164 the values of both operands. But 'andalso' and 'orelse' only test
165 their second operand SOME of the time.
166
167 X = 1, X >= 0 andalso X % checked error
168 X = 1, X < 0 andalso X % unchecked error
169
170 There doesn't seem to be much point in checking SOME of the time,
171 especially when it does something as dramatic as blocking tail
172 recursion.
173
174 Richard O'Keefe's motivation in [EEP 17][] is "Cultural consistency"
175 with other languages. See [EEP 17][].
6622778 @RaimoNiskanen Added EEP 26
RaimoNiskanen authored
176
177
178
6a5224b @RaimoNiskanen Cleanup and convert to Markdown
RaimoNiskanen authored
179 Rationale
180 =========
6622778 @RaimoNiskanen Added EEP 26
RaimoNiskanen authored
181
6a5224b @RaimoNiskanen Cleanup and convert to Markdown
RaimoNiskanen authored
182 Surprisingly (for me), the subject of this EEP turned out to
183 be controversial.
6622778 @RaimoNiskanen Added EEP 26
RaimoNiskanen authored
184
6a5224b @RaimoNiskanen Cleanup and convert to Markdown
RaimoNiskanen authored
185 I will start this rationale by listing some of the more serious
186 arguments against this proposal and my counter-arguments, and
187 finish with the arguments for this proposal.
6622778 @RaimoNiskanen Added EEP 26
RaimoNiskanen authored
188
6a5224b @RaimoNiskanen Cleanup and convert to Markdown
RaimoNiskanen authored
189 One argument against is to be that the new construct
190 will be confusing for users. 'andalso'/'orelse' can no longer
191 be described as a "boolean operator", but is now a "control
192 structure".
6622778 @RaimoNiskanen Added EEP 26
RaimoNiskanen authored
193
6a5224b @RaimoNiskanen Cleanup and convert to Markdown
RaimoNiskanen authored
194 Yes, 'andalso'/'orelse' is no longer a boolean operator in the
195 sense that it no longer GUARANTEES that it returns a boolean.
196 However, using 'andalso'/'orelse' as a 'case' expression
6622778 @RaimoNiskanen Added EEP 26
RaimoNiskanen authored
197
6a5224b @RaimoNiskanen Cleanup and convert to Markdown
RaimoNiskanen authored
198 case E1 orelse E2 of
199 true -> ....;
200 false -> ...
201 end
6622778 @RaimoNiskanen Added EEP 26
RaimoNiskanen authored
202
6a5224b @RaimoNiskanen Cleanup and convert to Markdown
RaimoNiskanen authored
203 works in the same way as before. Most users certainly will not
204 notice any difference. And if an operator is not allowed to not
205 evaluate both of its arguments, it certainly wasn't an operator
206 before either.
6622778 @RaimoNiskanen Added EEP 26
RaimoNiskanen authored
207
6a5224b @RaimoNiskanen Cleanup and convert to Markdown
RaimoNiskanen authored
208 Another argument against is that 'andalso'/'orelse' can be
209 used in one-liners to write "ugly code", such as
6622778 @RaimoNiskanen Added EEP 26
RaimoNiskanen authored
210
6a5224b @RaimoNiskanen Cleanup and convert to Markdown
RaimoNiskanen authored
211 Debug andalso io:format("...", [...])
6622778 @RaimoNiskanen Added EEP 26
RaimoNiskanen authored
212
6a5224b @RaimoNiskanen Cleanup and convert to Markdown
RaimoNiskanen authored
213 instead of
6622778 @RaimoNiskanen Added EEP 26
RaimoNiskanen authored
214
6a5224b @RaimoNiskanen Cleanup and convert to Markdown
RaimoNiskanen authored
215 if
216 Debug -> io:format("...", [...]);
217 true -> ok
218 end
219
220 The code might be "ugly" (according to someone's taste or
221 some definition of "ugly"), but the one-liner is not hard
222 to understand and I don't see how it could turn into a
223 code-maintenance problem.
6622778 @RaimoNiskanen Added EEP 26
RaimoNiskanen authored
224
6a5224b @RaimoNiskanen Cleanup and convert to Markdown
RaimoNiskanen authored
225 The main argument for making 'andalso'/'orelse' tail-recursive:
226 The current implementation is dangerous. You could very easily
227 write non-tail-recursive code, for instance
6622778 @RaimoNiskanen Added EEP 26
RaimoNiskanen authored
228
6a5224b @RaimoNiskanen Cleanup and convert to Markdown
RaimoNiskanen authored
229 all(Pred, [Hd|Tail]) ->
230 Pred(Hd) andalso all(Pred, Tail);
231 all(_, []) ->
232 true.
6622778 @RaimoNiskanen Added EEP 26
RaimoNiskanen authored
233
6a5224b @RaimoNiskanen Cleanup and convert to Markdown
RaimoNiskanen authored
234 without realizing it and introduce serious performance
235 problems. (Which has happened in [practice][2]).
6622778 @RaimoNiskanen Added EEP 26
RaimoNiskanen authored
236
6a5224b @RaimoNiskanen Cleanup and convert to Markdown
RaimoNiskanen authored
237 If you cannot use 'andalso'/'orelse' in this way, these
238 operators become pretty useless. (Some would say
239 ["utterly useless"][2].) You have to rewrite
240 beautiful code (in my opinion) to uglier code (in
241 comparison, in my opinion) and more error-prone
242 code (misspelling of 'true'/'false' in the boiler-plate
243 code):
6622778 @RaimoNiskanen Added EEP 26
RaimoNiskanen authored
244
6a5224b @RaimoNiskanen Cleanup and convert to Markdown
RaimoNiskanen authored
245 all(Pred, [Hd|Tail]) ->
246 case Pred(Hd) of
247 false -> false;
248 true -> all(Pred, Tail)
249 end;
250 all(_, []) ->
251 true.
6622778 @RaimoNiskanen Added EEP 26
RaimoNiskanen authored
252
253
254
6a5224b @RaimoNiskanen Cleanup and convert to Markdown
RaimoNiskanen authored
255 Backwards Compatibility
256 =======================
6622778 @RaimoNiskanen Added EEP 26
RaimoNiskanen authored
257
6a5224b @RaimoNiskanen Cleanup and convert to Markdown
RaimoNiskanen authored
258 Any code that ran without raising exceptions will continue
259 to produce the same results, except for running faster.
6622778 @RaimoNiskanen Added EEP 26
RaimoNiskanen authored
260
6a5224b @RaimoNiskanen Cleanup and convert to Markdown
RaimoNiskanen authored
261 Code that did raise exceptions may raise different exceptions
262 elsewhere later, or may quietly complete in unexpected ways.
263 I believe it to be unlikely that anyone deliberately relied
264 on `(E1 andalso 0)` raising an exception.
6622778 @RaimoNiskanen Added EEP 26
RaimoNiskanen authored
265
6a5224b @RaimoNiskanen Cleanup and convert to Markdown
RaimoNiskanen authored
266 Code that was previously broken because these operators have
267 such surprising behavior will now work in more cases.
6622778 @RaimoNiskanen Added EEP 26
RaimoNiskanen authored
268
269
270
6a5224b @RaimoNiskanen Cleanup and convert to Markdown
RaimoNiskanen authored
271 Reference Implementation
272 ========================
6622778 @RaimoNiskanen Added EEP 26
RaimoNiskanen authored
273
6a5224b @RaimoNiskanen Cleanup and convert to Markdown
RaimoNiskanen authored
274 The proposed change has been implemented and run in our
275 daily builds without finding any code in Erlang/OTP that
276 needed to be updated. One test case in the compiler test
277 suite that that test 'andalso'/'orelse' needed to be updated.
6622778 @RaimoNiskanen Added EEP 26
RaimoNiskanen authored
278
279
6a5224b @RaimoNiskanen Cleanup and convert to Markdown
RaimoNiskanen authored
280
281 [EEP 17]: eep-0017.md
282 "Richard O'Keefe: EEP 17 - Fix andalso and orelse"
6622778 @RaimoNiskanen Added EEP 26
RaimoNiskanen authored
283
6a5224b @RaimoNiskanen Cleanup and convert to Markdown
RaimoNiskanen authored
284 [2]: http://www.erlang.org/pipermail/erlang-questions/2008-November/039935.html
285 "Mikael Pettersson: e-mail to erlang-questions"
6622778 @RaimoNiskanen Added EEP 26
RaimoNiskanen authored
286
287
288
6a5224b @RaimoNiskanen Cleanup and convert to Markdown
RaimoNiskanen authored
289 Copyright
290 =========
291
292 This document has been placed in the public domain.
293 [EmacsVar]: <> "Local Variables:"
294 [EmacsVar]: <> "mode: indented-text"
295 [EmacsVar]: <> "indent-tabs-mode: nil"
296 [EmacsVar]: <> "sentence-end-double-space: t"
297 [EmacsVar]: <> "fill-column: 70"
298 [EmacsVar]: <> "coding: utf-8"
299 [EmacsVar]: <> "End:"
Something went wrong with that request. Please try again.