short circuiting and parenthesis

Question

Does it matter how I group subexpressions when dealing with a single short-circuiting operator?

a && b && c && d
a && (b && (c && d))
(a && b) && (c && d)
((a && b) && c) && d

Are the above expressions equivalent?

Sweetener

In my last comment I was in error and I apologize for that. I have deleted it, as it was incorrect. – Bledsoe

Answer 1

It is relatively easy to prove the equivalence for two simplified cases of three subexpressions:

a && (b && c)  -->  a && bc   // bc is a shorthand for b && c

Here, a will be evaluated first. If it is false, short circuiting will prevent the evaluation of bc. If it is true, bc will be evaluated, that is, b && c will be evaluated. If b is false, c won't be evaluated.

(a && b) && c  -->  ab && c   // ab is a shorthand for a && b

Here, ab will be evaluated first. (That is a && b is evaluated first. If a is false, short circuiting will prevent the evaluation of b. Otherwise, ab yields b.) If ab is false, c won't be evaluated.

---

Now, if you prefer evidence to proof, you can look at the assembly output of the following C code:

int a(), b(), c(), d();

void e()
{
    a() && b() && c() && d();
}

void f()
{
    a() && (b() && (c() && d()));
}

void g()
{
    (a() && b()) && (c() && d());
}

void h()
{
    ((a() && b()) && c()) && d();
}

(I used C code as opposed to C++ code to prevent name mangling.)

generated assembly for e:

_e:
    // ... enter ...
    call    _a
    testl   %eax, %eax
    je  L1
    call    _b
    testl   %eax, %eax
    je  L1
    call    _c
    testl   %eax, %eax
    je  L1
    call    _d
    testl   %eax, %eax
    nop
L1:
    // ... leave ...

generated assembly for f:

_f:
    // ... enter ...
    call    _a
    testl   %eax, %eax
    je  L4
    call    _b
    testl   %eax, %eax
    je  L4
    call    _c
    testl   %eax, %eax
    je  L4
    call    _d
    testl   %eax, %eax
    nop
L4:
    // ... leave ...

generated assembly for g:

_g:
    // ... enter ...
    call    _a
    testl   %eax, %eax
    je  L7
    call    _b
    testl   %eax, %eax
    je  L7
    call    _c
    testl   %eax, %eax
    je  L7
    call    _d
    testl   %eax, %eax
    nop
L7:
    // ... leave ...

generated assembly for h:

_h:
    // ... enter ...
    call    _a
    testl   %eax, %eax
    je  L10
    call    _b
    testl   %eax, %eax
    je  L10
    call    _c
    testl   %eax, %eax
    je  L10
    call    _d
    testl   %eax, %eax
    nop
L10:
    // ... leave ...

As you can see, apart from labels, the generated assembly code is completely identical.

Histolysis

Answer 2

Yes, those expressions are all equivalent, including their short-circuiting behaviour.

The parentheses change the order in which the individual &&s are evaluated. However, as && is always left-associative, the terms are always evaluated in a left-to-right order. So as soon as a term is found to be false, the rest can be skipped.

Activator

Answer 3

In your example, the parenthesis don't matter. But that's just becuase of the nature of && where all the terms need to be checked (if true, or if either one is false it is false).

In this example, the parenthesis do make a big difference:

(a && b) || (c && d) // either a & b are true, or c & d

a && (b || c && d) // a must be true, and either b or c & d

(a && b || c) && d // d must be true, and either c or a & b

And of course because the logic is different, the short-circuiting works differently.
In the first line if a is false, it will continue to the second term (c && d).
In the second line if a is false, it will just return false.

Elianore

Answer 4

This property is called Associativity. From the Wikipedia Article:

In mathematics, associativity is a property of some binary operations. It means that, within an expression containing two or more occurrences in a row of the same associative operator, the order in which the operations are performed does not matter as long as the sequence of the operands is not changed. That is, rearranging the parentheses in such an expression will not change its value.

The built-in operator&& is fully associative, and thus the above applies.

This is not always the case, for example:

• operator- is generally left-associative, that is a - b - c == (a - b) - c != a - (b - c)
• exponentiation is right-associative, that is a ** b ** c == a ** (b ** c) != (a ** b) ** c
• cross-product is non-associative, that is (a x b) x c != a x (b x c) (and without parentheses, the expression does not even makes sense)

Note that this only applies to the case of a single operator being used consistently, as soon as another operator (like ||) is introduced in the mix, then you have to take into account the operator precedence, which is another topic.

Berkman

This addresses the associativity of the mathematical definition of &&, but it doesn't address the issue of short-circuiting (not part of the mathematical definition). – Activator

@Oli: The quote does not address it, however when I qualify the operator&& as being fully associative, I do. If the short-circuit behavior was not maintained, then we could not qualify the operator as associative. – Berkman

According to most descriptions of the C operators, && is left-associative. To be fair, I don't really know what that means, because no other operator has the same precedence as it. – Activator

@Oli: left-associative can mean that a && b && c == (a && b) && c != a && (b && c), I would say that this is erroneous, or it can mean a && b && c == (a && b) && c and forget about right-associativity. When evaluating a && (b && c), if a is false, then it stops, else it evaluates b && c which does short-circuit if b is false and else evaluates c. Thus && is fully-associative, and you might say it's left-associative (though not strictly). – Berkman

I interpret "left-associative" to imply a && b && c == (a && b) && c. It doesn't necessarily imply the != a && (b && c). – Activator