12
$\begingroup$

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?

$\endgroup$
  • 8
    $\begingroup$ You already answered your own question. And is not Orderless so it can be short circuiting. This is not only about efficiency. You can also do stuff like FooQ[x] && FunnyFooQ[x] where FunnyFooQ won't even run without errors for something that is not a "Foo". Short circuiting makes it possible to write more concise and therefore clearer code without too many Ifs. $\endgroup$ – Szabolcs Oct 23 '16 at 3:20
  • 4
    $\begingroup$ To preserve short circuiting. $\endgroup$ – Chip Hurst Oct 23 '16 at 3:38
11
$\begingroup$

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}

$\endgroup$
  • 8
    $\begingroup$ This property is called short circuiting and it's not only about efficiency. 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"] $\endgroup$ – Szabolcs Oct 23 '16 at 3:27
  • $\begingroup$ @Szabolcs Hm, forgot about that. Thanks for telling me. $\endgroup$ – JungHwan Min Oct 23 '16 at 3:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.