EEP 26: Make andalso and orelse tail-recursive #

Abstract #

Erlang 5.1 added the ability to use ‘andalso’, ‘orelse’, ‘and’, and ‘or’ in guards. However, the semantics for ‘andalso’ and ‘orelse’ differs from that in other related languages, causing confusion and inefficiency.

I propose making ‘andalso’ and ‘orelse’ tail-recursive.

This EEP is partly based on Richard O’Keefe’s EEP 17, but has a narrower scope.

Specification #

Currently, (E1 andalso E2) as an expression acts like

case E1 of
    false -> false;
    true  -> case E2 of
                 false -> false;
                 true  -> true
             end
end

except that the former raises {badarg,NonBool} exceptions and the latter raises {case_clause,NonBool} ones.

This should be changed to

case E1 of
    false -> false;
    true  -> E2
end.

Currently, (E1 orelse E2) as an expression acts like

case E1 of
    true -> true
    false -> case E2 of
        true  -> true
        false -> false
    end
end

except that the former raises {badarg,NonBool} exceptions and the latter raises {case_clause,NonBool} ones.

This should be changed to

case E1 of
    true  -> true;
    false -> E2
end

Motivation #

To unlock the full potential of ‘andalso’/’orelse’ in Erlang.

Given the current implementation, you either have to make rewrite code that is naturally written using AND and OR operators using ‘case’, or only use ‘andalso’/’orelse’ when you know that your lists are relatively short.

For instance, the function all/2 that returns ‘true’ if all elements of a list satisfies a predicate and ‘false’ otherwise, can be written like this:

all(Pred, [Hd|Tail]) ->
    Pred(Hd) and all(Pred, Tail);
all(_, []) ->
    true.

In each recursion, we test that the current element Hd satisfies the predicate AND that the rest of the list also matches the predicate. The code reads almost like English.

Of course, ‘and’ evaluates both of its operand, so the entire list will be traversed even if the first element of the list fails to satisfy the predicate. Furthermore, ‘and’ is not tail-recursive, so the function will use stack space proportional to the length of the list.

To avoid the traversing the rest of the list if one element fails to satisfy the predicate, we can use ‘andalso’:

all(Pred, [Hd|Tail]) ->
    Pred(Hd) andalso all(Pred, Tail);
all(_, []) ->
    true.

As soon as Pred(Hd) returns false, the recursion will stop and the rest of the list need not be traversed. Since ‘andalso’ is not tail-recursive, however, the function will need stack space proportional to the number of list elements that are traversed.

To see more clearly that ‘andalso’ is not tail-recursive, here is all/1 with ‘andalso’ expanded out to a nested ‘case’ expression (as it would be in R12B-5):

all(Pred, [Hd|Tail]) ->
    case Pred(Hd) of
        false -> false;
        true  -> case all(Pred, Tail) of
        false -> false;
        true  -> true
        end
    end;
all(_, []) ->
    true.

To make all/1 tail-recursive in R12B-5, you would have to write a ‘case’ expression yourself:

all(Pred, [Hd|Tail]) ->
    case Pred(Hd) of
        false -> false;
        true  -> all(Pred, Tail)
    end;
all(_, []) ->
    true.

If this EEP is accepted, in R13B we could write like this

all(Pred, [Hd|Tail]) ->
    Pred(Hd) andalso all(Pred, Tail);
all(_, []) ->
    true.

and the all/1 function would be tail-recursive.

In my opinion, the latter is easier to read and write. The ‘case’ expression is mostly boiler-plate code where ‘true’ and ‘false’ must be correctly spelled several times. (Misspellings like ‘ture’ and ‘flase’ are quite common, but are in most cases found the first time the program is tested.)

It could be argued that because Erlang has clearly defined truth values (unlike some other languages where 0 is false and everything else true), all operators that operate on booleans should make sure that their arguments are booleans.

Testing both arguments of ‘and’ and ‘or’ makes sense, because the code executed for those operators always GETS the values of both operands. But ‘andalso’ and ‘orelse’ only test their second operand SOME of the time.

X = 1, X >= 0 andalso X    % checked error
X = 1, X < 0 andalso X     % unchecked error

There doesn’t seem to be much point in checking SOME of the time, especially when it does something as dramatic as blocking tail recursion.

Richard O’Keefe’s motivation in EEP 17 is “Cultural consistency” with other languages. See EEP 17.

Rationale #

Surprisingly (for me), the subject of this EEP turned out to be controversial.

I will start this rationale by listing some of the more serious arguments against this proposal and my counter-arguments, and finish with the arguments for this proposal.

One argument against is to be that the new construct will be confusing for users. ‘andalso’/’orelse’ can no longer be described as a “boolean operator”, but is now a “control structure”.

Yes, ‘andalso’/’orelse’ is no longer a boolean operator in the sense that it no longer GUARANTEES that it returns a boolean. However, using ‘andalso’/’orelse’ as a ‘case’ expression

case E1 orelse E2 of
    true -> ....;
    false -> ...
end

works in the same way as before. Most users certainly will not notice any difference. And if an operator is not allowed to not evaluate both of its arguments, it certainly wasn’t an operator before either.

Another argument against is that ‘andalso’/’orelse’ can be used in one-liners to write “ugly code”, such as

Debug andalso io:format("...", [...])

instead of

if
    Debug -> io:format("...", [...]);
    true -> ok
end

The code might be “ugly” (according to someone’s taste or some definition of “ugly”), but the one-liner is not hard to understand and I don’t see how it could turn into a code-maintenance problem.

The main argument for making ‘andalso’/’orelse’ tail-recursive: The current implementation is dangerous. You could very easily write non-tail-recursive code, for instance

all(Pred, [Hd|Tail]) ->
    Pred(Hd) andalso all(Pred, Tail);
all(_, []) ->
    true.

without realizing it and introduce serious performance problems. (Which has happened in practice).

If you cannot use ‘andalso’/’orelse’ in this way, these operators become pretty useless. (Some would say “utterly useless”.) You have to rewrite beautiful code (in my opinion) to uglier code (in comparison, in my opinion) and more error-prone code (misspelling of ‘true’/’false’ in the boiler-plate code):

all(Pred, [Hd|Tail]) ->
    case Pred(Hd) of
        false -> false;
        true  -> all(Pred, Tail)
    end;
all(_, []) ->
   true.

Backwards Compatibility #

Any code that ran without raising exceptions will continue to produce the same results, except for running faster.

Code that did raise exceptions may raise different exceptions elsewhere later, or may quietly complete in unexpected ways. I believe it to be unlikely that anyone deliberately relied on (E1 andalso 0) raising an exception.

Code that was previously broken because these operators have such surprising behavior will now work in more cases.

Reference Implementation #

The proposed change has been implemented and run in our daily builds without finding any code in Erlang/OTP that needed to be updated. One test case in the compiler test suite that that test ‘andalso’/’orelse’ needed to be updated.

Copyright #

This document has been placed in the public domain.