Why isn't Orderless an Attribute of And?

Question

In standard logic And is a commutative operator. Still, in Mathematica, And doesn't have the Orderless attribute:

Attributes[And]
(* {Flat,HoldAll,OneIdentity,Protected} *)

This may have not been the case in the past. On page 190 of David Wagner's book "Power Programming with Mathematica" one finds a table with functions having different attributes. In that table And is listed as one of the functions that have the Orderless attribute. At the time of publication Mathematica version 3.0 had just released.

There are good reasons for And not to have Orderless among its attributes. One of them is efficiency. Since the argument order remains fixed, the programmer can sort the arguments so that the expected execution time will be minimized.

Another reason for eschewing Orderless is that, in Operator[x,y], the evaluation of x can have such side effects on y, and perhaps this may cause Operator[x,y] and Operator[y,x] have different values (I am not sure about this). However, this second argument for not including Orderless in the list of attributes of And also applies to functions like Max, Times, and Plus, and still all of these functions have the Orderless attribute.

One can see the consequences of these choices:

(x + y) == (y + x)
(* True *)
(x && y) == (y && x)
(* (x && y) == (y && x) *)

So was Orderless avoided in And just for efficiency reasons or is there any other specific feature of And that requires not including Orderless among its attributes?

Answer 1

As you mentioned, And is not Orderless just for efficiency; its arguments are evaluated one by one to prevent unnecessary computation. Orderless attribute would require sorting, which require more computation...

In a && b && c:

1. a is evaluated. If it is False, the evaluation ends, and the output is False. If not, the evaluation proceeds.
2. b is evaluated. If it is False, the evaluation ends, and the output is False. If not, the evaluation proceeds.
3. c is evaluated. If it is False, the output is False. If it is True, then the output is True.

This is very efficient.

Plus, as @Szabolcs mentions, not having Orderless attribute allows you to use short-circuit evaluation (a.k.a. McCarthy evaluation).

"You can safely use a && b even when b wouldn't correctly run unless a has evaluated to True. E.g. StringQ[s] && StringStartsQ[s, "x"]"

---

e.g. checking for perfect square using mod 256 (only 44 values occur for perfect squares mod 256 - more info):

mods = AssociationMap[True &, Array[Mod[#^2, 256] &, 256]];
perfectsquareq1 = 
  Lookup[mods, Mod[#, 256], False] && IntegerQ[Sqrt[#]] &;
perfectsquareq2 = 
  And @@ {Lookup[mods, Mod[#, 256], False], IntegerQ[Sqrt[#]]} &;

The first function uses And. The second function forces the evaluation and then uses And.

See the difference in speed:

Array[perfectsquareq1, 100000]; // AbsoluteTiming

{0.254216, Null}

Array[perfectsquareq2, 100000]; // AbsoluteTiming

{0.926911, Null}