Is short-circuiting logical operators mandated? And evaluation order?

Question

Does the ANSI standard mandate the logical operators to be short-circuited, in either C or C++?

I'm confused for I recall the K&R book saying your code shouldn't depend on these operations being short circuited, for they may not. Could someone please point out where in the standard it's said logic ops are always short-circuited? I'm mostly interested on C++, an answer also for C would be great.

I also remember reading (can't remember where) that evaluation order isn't strictly defined, so your code shouldn't depend or assume functions within an expression would be executed in a specific order: by the end of a statement all referenced functions will have been called, but the compiler has freedom in selecting the most efficient order.

Does the standard indicate the evaluation order of this expression?

if( functionA() && functionB() && functionC() ) {
    cout << "Hello world";
}

Spartacus

Carefull: It is true for POD types. But if you overload the operator && or operator || for a particular class these are NOT I repeat NOT shortcut. This is why it is advised that you do NOT define these operators for your own classes. – Crone

I redefined these operators a while ago, when I created a class that would do some basic boolean algebra operations. Probably should stick a warning comment "this destroys short circuiting and left-right evaluation!" in case I forget this. Also overloaded */+ and made them their synonyms :-) – Spartacus

Having function calls in an if-block is not a good programming practice. Always have a variable declared that holds the return value of the method and use it in the if-block. – Limitary

@SRChaitanya That is not correct. What you arbitrarily describe as poor practice is done all the time, especially with functions that return booleans, as here. – Charioteer

For those who need some assistance in untangling the meaning of the strange and unintuitive term "short circuit", check out this post: What is the meaning of "short circuit" operators? – Caughey

Answer 1

Yes, short-circuiting and evaluation order are required for operators || and && in both C and C++ standards.

C++ standard says (there should be an equivalent clause in the C standard):

1.9.18

In the evaluation of the following expressions

a && b
a || b
a ? b : c
a , b

using the built-in meaning of the operators in these expressions, there is a sequence point after the evaluation of the first expression (12).

In C++ there is an extra trap: short-circuiting does NOT apply to types that overload operators || and &&.

Footnote 12: The operators indicated in this paragraph are the built-in operators, as described in clause 5. When one of these operators is overloaded (clause 13) in a valid context, thus designating a user-defined operator function, the expression designates a function invocation, and the operands form an argument list, without an implied sequence point between them.

It is usually not recommended to overload these operators in C++ unless you have a very specific requirement. You can do it, but it may break expected behaviour in other people's code, especially if these operators are used indirectly via instantiating templates with the type overloading these operators.

Jeromejeromy

Didn't know short-circuiting wouldn't apply to overloaded logic ops, that's intesting. Can you please add a reference to the standard, or a source? I'm not distrusting you, just want to learn more about this. – Spartacus

yeah, that's logical. it's acting as arguments to operator&&(a, b) . it's the implementation of it that says what happens. – Kathlenekathlin

litb: It's just not possible to pass b to operator&&(a,b) without evaluating it. And there's no way undo evaluating b because the compiler cannot guarantee there aren't side effects. – Epineurium

joe, yeah indeed that's what i was trying to say. of course, the implementation cannot determine whether evaluation order matters again or not. sorry for being so blurry :) – Kathlenekathlin

I find this sad. I would've thought that, should I redefined operators && and || and they're still fully deterministic, the compiler would detect that and keep their evaluation short-circuited: after all, order is irrelevant, an they guarantee no side effects! – Spartacus

@Joe: but return value and arguments of the operator may change from boolean to something else. I used to implement "special" logic with THREE values ("true", "false" and "unknown"). Return value is deterministic, but short-circuiting behaviour is not appropriate. – Jeromejeromy

Gave it some thought, came to conclude short-circuited-ness depends on Boolean operators being idem-potent for some values, and having each a neuter element. It would be cool being able to let C++ know our redefined &&/|| are idem-potent for some operands, and which operand is the neuter. – Spartacus

But complexity of compilers would grow, so probably only math applications would benefit. Probably my dream of stating my overloaded operators are deterministic, idempotent, etc. is better left for LISP-like languages with their lazy evaluation, memoization, etc. – Spartacus

Can I assume that if I enable a high degree of optimizations in my compiler (say -O3 in gcc), that these semantics are still obeyed? – Pisces

@KenP yes, compiler must obey those to be compliant. With high optimisation level it may inline/reorder/speculatively execute code, but as long as observable behaviour is the same, it's OK. If you have, say, side effects like a volatile write, they will happen in correct order. – Jeromejeromy

The quoted part of the standard guarantees left-to-right evaluation, but not short-circuiting. That guarantee is found in the spec of the relevant operators. – Afflux

Answer 2

Short circuit evaluation, and order of evaluation, is a mandated semantic standard in both C and C++.

If it wasn't, code like this would not be a common idiom

   char* pChar = 0;
   // some actions which may or may not set pChar to something
   if ((pChar != 0) && (*pChar != '\0')) {
      // do something useful

   }

Section 6.5.13 Logical AND operator of the C99 specification (PDF link) says

(4). Unlike the bitwise binary & operator, the && operator guarantees left-to-right evaluation; there is a sequence point after the evaluation of the first operand. If the first operand compares equal to 0, the second operand is not evaluated.

Similarly, section 6.5.14 Logical OR operator says

(4) Unlike the bitwise | operator, the || operator guarantees left-to-right evaluation; there is a sequence point after the evaluation of the first operand. If the first operand compares unequal to 0, the second operand is not evaluated.

Similar wording can be found in the C++ standards, check section 5.14 in this draft copy. As checkers notes in another answer, if you override && or ||, then both operands must be evaluated as it becomes a regular function call.

Streamy

Ah, what I was looking for! OK, so both evaluation order and short-circuiting are mandated as per ANSI-C 99! I'd really love to see teh equivalent reference for ANSI-C++, though I'm almost 99% it must be the same. – Spartacus

Hard to find a good free link for the C++ standards, have linked to a draft copy I found with some googling. – Streamy

True for POD Types. But if you overload the operator && or the operator || these are not shortcut. – Crone

yeah it's interesting to note that for bool, you always will have guaranteed evaluation order & short circuit behavior. because you cannot overload operator&& for two built-in types. you need at least one user defined type in the operands to have it behave different. – Kathlenekathlin

I wish I could accept both Checkers and this answer. Since I'm mostly interested in C++, I'm accepting the other one, though have to admit this is superb, too! Thank you very much! – Spartacus

Answer 3

Yes, it mandates that (both evaluation order and short circuit). In your example if all functions return true, the order of the calls are strictly from functionA then functionB and then functionC. Used for this like

if(ptr && ptr->value) { 
    ...
}

Same for the comma operator:

// calls a, then b and evaluates to the value returned by b
// which is used to initialize c
int c = (a(), b()); 

One says between the left and right operand of &&, ||, , and between the first and second/third operand of ?: (conditional operator) is a "sequence point". Any side effects are evaluated completely before that point. So, this is safe:

int a = 0;
int b = (a++, a); // b initialized with 1, and a is 1

Note that the comma operator is not to be confused with the syntactical comma used to separate things:

// order of calls to a and b is unspecified!
function(a(), b());

The C++ Standard says in 5.14/1:

The && operator groups left-to-right. The operands are both implicitly converted to type bool (clause 4). The result is true if both operands are true and false otherwise. Unlike &, && guarantees left-to-right evaluation: the second operand is not evaluated if the first operand is false.

And in 5.15/1:

The || operator groups left-to-right. The operands are both implicitly converted to bool (clause 4). It returns true if either of its operands is true, and false otherwise. Unlike |, || guarantees left-to-right evaluation; moreover, the second operand is not evaluated if the first operand evaluates to true.

It says for both next to those:

The result is a bool. All side effects of the first expression except for destruction of temporaries (12.2) happen before the second expression is evaluated.

In addition to that, 1.9/18 says

In the evaluation of each of the expressions

• a && b
• a || b
• a ? b : C
• a , b

using the built-in meaning of the operators in these expressions (5.14, 5.15, 5.16, 5.18), there is a sequence point after the evaluation of the first expression.

Kathlenekathlin

Answer 4

Straight from good old K&R:

C guarantees that && and || are evaluated left to right — we shall soon see cases where this matters.

Skipper

K&R 2nd edition p40. "Expressions connected by && or || are evaluated left to right, and evaluation stops as soon as the truth or falsehood of the result is known. Most C programs rely on these properties." I can't find your quoted text anywhere in the book. Is this from the extremely obsolete 1st edition? Please clarify where you found this text. – Caughey

Ok turns out you are quoting this ancient tutorial. It is from 1974 and highly irrelevant. – Caughey

Answer 5

Be very very careful.

For fundamental types these are shortcut operators.

But if you define these operators for your own class or enumeration types they are not shortcut. Because of this semantic difference in their usage under these different circumstances it is recommended that you do not define these operators.

For the operator && and operator || for fundamental types the evaluation order is left to right (otherwise short cutting would be hard :-) But for overloaded operators that you define, these are basically syntactic sugar to defining a method and thus the order of evaluation of the parameters is undefined.

Crone

Operator overloading has nothing to do with the type being POD or not. To define an operator function, at least one of the arguments needs to be a class (or struct or union) or an enum, or a reference to one of those. Being POD means that you can use memcpy on it. – Oldline

And that is what I was saying. If you overload && for your class then it is really just a method call. Thus you can not rely on the order of evaluation of the parameters. Obviously you can not overload && for POD types. – Crone

You are using the term "POD types" incorrectly. You can overload && for any struct, class, union or enum, POD or not. You cannot overload && if both sides are numeric types or pointers. – Oldline

I was using POD as (char/int/float etc) not an aggrigate POD (which is what you are talking about) and is usually refered to seprately or more explicitly becuase it is not a built in type. – Crone

So you did mean "fundamental types" but wrote "POD types"? – Ileus

@ÖöTiib: See the comment above your comment. – Crone

Answer 6

If you trust Wikipedia:

[&& and ||] are semantically distinct from the bit-wise operators & and | because they will never evaluate the right operand if the result can be determined from the left alone

C (programming language)

Komsomol

Why trust wiki when we have a standard! – Crone

If you trust Wikipedia, 'Wikipedia is not a reliable resource'. – Charioteer

This is true as far as it goes, but incomplete, since overloaded operators in C++ are not short-circuited. – Fokos

Answer 7

Your question comes down to C++ operator precedence and associativity. Basically, in expressions with multiple operators and no parentheses, the compiler constructs the expression tree by following these rules.

For precedence, when you have something like A op1 B op2 C, you could group things as either (A op1 B) op2 C or A op1 (B op2 C). If op1 has higher precedence than op2, you'll get the first expression. Otherwise, you'll get the second one.

For associativity, when you have something like A op B op C, you could again group thins as (A op B) op C or A op (B op C). If op has left associativity, we end up with the first expression. If it has right associativity, we end up with the second one. This also works for operators at the same precedence level.

In this particular case, && has higher precedence than ||, so the expression will be evaluated as (a != "" && it == seqMap.end()) || isEven.

The order itself is "left-to-right" on the expression-tree form. So we'll first evaluate a != "" && it == seqMap.end(). If it's true the whole expression is true, otherwise we go to isEven. The procedure repeats itself recursively inside the left-subexpression of course.

---

Interesting tidbits, but the concept of precedence has its roots in mathematic notation. The same thing happens in a*b + c, where * has higher precedence than +.

Even more interesting/obscure, for a unparenthasiszed expression A1 op1 A2 op2 ... opn-1 An, where all operators have the same precedence, the number of binary expression trees we could form is given by the so called Catalan numbers. For large n, these grow extremely fast. d

Devon

All this is correct, but it is about operator precedence and associativity, not about evaluation order and short-curcuiting. Those are different things. – Fokos