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?

Improve this question
$\endgroup$
2
  • 9
    $\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$ Commented Oct 23, 2016 at 3:20
  • 4
    $\begingroup$ To preserve short circuiting. $\endgroup$ Commented Oct 23, 2016 at 3:38

1 Answer 1

Reset to default
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}

Improve this answer
$\endgroup$
2
  • 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$ Commented Oct 23, 2016 at 3:27
  • $\begingroup$ @Szabolcs Hm, forgot about that. Thanks for telling me. $\endgroup$ Commented Oct 23, 2016 at 3:32

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.