Do the binary boolean operators have associativity?

Question

Is a && b && c defined by the language to mean (a && b) && c or a && (b && c)?

Wow, Jerry was quick. To beef up the question: does it actually matter? Would there be an observable difference between a && b && c being interpreted as (a && b) && c or a && (b && c)?

Adiabatic

Yes, it matters. Short-circuting would prevent some of your operands from being evaluated. – Zweig

@meagar How would (a && b) && c differ from a && (b && c) with respect to short-circuiting? For example, how would (false && b) && c differ from false && (b && c)? Both expressions evaluate neither b nor c... – Adiabatic

@FredOverflow if a is false, you are correct. if b is false, c never gets evaluated. Basically, if there is some false to the left of some AND'd conditions, the tests stop with it. – Nomadic

@ZacHowland: If a is true, and b is false, c doesn't get evaluated, regardless of whether you use (a && b) && c or a && (b && c) – Cocker

@BenjaminLindley Isn't that what I just said? – Nomadic

@ZacHowland: Did you? I assumed you were stating that for only one of the two expressions, because your answer seems to indicate that you are of the opinion that associativity matters because of short-circuiting. But if what I said in my comment is true, it does not. – Cocker

@BenjaminLindley I've updated my answer to be more clear. What I was stating in the previous comment was simply that if you operate from left to right, the first false stops anything further right from being tested/executed. With that in mind, it doesn't matter if you write (a && b) && c or a && (b && c) or a && b && c as they are all equivalent. The only thing that does matter is the order of the operands. – Nomadic

Answer 1

§5.14/1: "The && operator groups left-to-right. [...] Unlike &, && guarantees left-to-right evaluation: the second operand is not evaluated if the first operand is false."

As to when or how it matters: I'm not sure it really does for built-in types. It's possible, however, to overload it in a way that would make it matter. For example:

#include <iostream>

class A;

class M {
    int x;
public:
    M(int x) : x(x) {}
    M &operator&&(M const &r); 
    M &operator&&(A const &r); 
    friend class A;
};

class A {
    int x;
    public:
    A(int x) : x(x) {}
    A &operator&&(M const &r); 
    A &operator&&(A const &r);
    operator int() { return x;}
    friend class M;
};

M & M::operator&&(M const &r) {
    x *= r.x;
    return *this;
}

M & M::operator&&(A const &r) {
    x *= r.x;
    return *this;
}

A &A::operator&&(M const &r) {
    x += r.x;
    return *this;
}

A &A::operator&&(A const &r) {
    x += r.x;
    return *this;
}

int main() {
    A a(2), b(3);
    M c(4);

    std::cout << ((a && b) && c) << "\n";
    std::cout << (a && (b && c)) << "\n";
}

Result:

9
16

Caveat: this only shows how it can be made to matter. I'm not particularly recommending that anybody do so, only showing that if you want to badly enough, you can create a situation in which it makes a difference.

Borreri

I believe all binary operators of equivalent priority follow this convention. – Nomadic

Just to be clear, that means (a && b) && c and not a && (b && c), right? – Adiabatic

@ZacHowland: conditional operators and assignment (to name just two I can think of immediately) group right to left, so a=b=c is equivalent to a=(b=c). – Borreri

@JerryCoffin Ah, good point. I haven't chained assignments in so long that I didn't even think of it. – Nomadic

Answer 2

In fact it is very important that the expression is computed from left to right. This is used to have short-circuit in some expressions. Here is a case where it does matter:

vector<vector<int> > a;
if (!a.empty()  && !a[0].empty() && a[0].back() == 3) 

I bet you write similar statements few times a day. And if associativity was not defined you would be in huge trouble.

Chromatograph

@FredOverflow right you are.I have added a way more practical and in fact common case. – Chromatograph

If you add explicit parentheses to change the associativity of the expression, i.e. if (!a.empty() && (!a[0].empty() && a[0].back() == 3)) -- does it make a difference? I don't think it does. – Cocker

@BenjaminLindley no it does not. I believe my answer addresses an earlier version of the question where if the expression is evaluated left to right or right to left was included – Chromatograph

Answer 3

The && and || operators short-circuit: if the operand on the left determines the result of the overall expression, the operand on the right will not even be evaluated.

Therefore, a mathematician would describe them as left-associative, e.g.
a && b && c ⇔ (a && b) && c, because to a mathematician that means a and b are considered first. For pedagogical purposes, though, it might be useful to write a && (b && c) instead, to emphasize that neither b nor c will be evaluated if a is false.

Parentheses in C only change evaluation order when they override precedence. Both a && (b && c)
and (a && b) && c will be evaluated as a first, then b, then c. Similarly, the evaluation order of both
a + (b + c) and (a + b) + c is unspecified. Contrast a + (b * c) versus (a + b) * c, where the compiler is still free to evaluate a, b, and c in any order, but the parentheses determine whether the multiplication or the addition happens first. Also contrast FORTRAN, where in at least some cases parenthesized expressions must be evaluated first.

Koy

Er, if by "it does not matter" you mean "a && b && c is evaluated strictly left to right regardless of parenthesization", then yes. See edit. – Koy

Interestingly, in Haskell, for example, (&&) and (||) are right-associative, which seems to make more sense. I don't understand why in JavaScript and Python they are left-associative. – Christmas

Answer 4

If a && b is false, then the && c portion is never tested. So yes, it does matter (at least in that you need to have your operations ordered from left to right). && is an associative operation by nature.

Associative Property

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.

So it doesn't matter (logically) if you write it as a && (b && c) or (a && b) && c. Both are equivalent. But you cannot change the order of the operations (e.g a && c && b is not equivalent to a && b && c).

Nomadic

How would (false && b) && c differ from false && (b && c)? Both expressions evaluate neither b nor c... – Adiabatic

In that case, you are correct. The logical flow is simply from left to right, so when you reach your first false condition in a chain of conditions, it stops there. Since && is associative by nature, as long as you don't throw an || in there, it won't make much of a difference. As soon as you have an || condition, the parentheses start to matter. – Nomadic