Logical And

[sam]

Please look at the code below


#include <stdio.h>

int expr(char str[], int i){
printf("%s \n",str);
return i;
}

int main()
{
if(expr("1st",1) || expr("2nd",0) && expr("3rd",1));
return 0;
}

output
-------
1st

As && has an higher precedence over ||
then it should call expr("2nd",0) or expr("3rd",0)
first then why it calls (expr("1st",1) first

Regards
Shiju

 

[Mark A. Odell]

(e-mail address removed) (sam) wrote in

Please look at the code below


#include <stdio.h>

int expr(char str[], int i){
printf("%s \n",str);
return i;
}

int main()
{
if(expr("1st",1) || expr("2nd",0) && expr("3rd",1));
return 0;
}

output
-------
1st

As && has an higher precedence over ||
then it should call expr("2nd",0) or expr("3rd",0)
first then why it calls (expr("1st",1) first

It's called a short-circuit. If expr("1st",1) is true, then there is no
need to bother evaluting expr("3rd",0) and then expr("2nd",0), so it does
not. What you have seen is correct.

 

[Christopher Benson-Manica]

int main()
{
if(expr("1st",1) || expr("2nd",0) && expr("3rd",1));
return 0;
}

As && has an higher precedence over ||
then it should call expr("2nd",0) or expr("3rd",0)
first then why it calls (expr("1st",1) first

Does this make sense?

* > +
A + B * C equals A + (B * C)

&& > ||
A || B && C equals A || (B && C)

As Mark stated, the last expression is subject to short-circuit
evaluation, and thus there is no need to evaluate B && C (since A is
true in this case). Notice that

B && C || A

in this case calls #2 and #1, but not #3, again because of
short-circuit evaluation.

 

[Eric Sosman]

Please look at the code below

#include <stdio.h>

int expr(char str[], int i){
printf("%s \n",str);
return i;
}

int main()
{
if(expr("1st",1) || expr("2nd",0) && expr("3rd",1));
return 0;
}

output
-------
1st

As && has an higher precedence over ||
then it should call expr("2nd",0) or expr("3rd",0)
first then why it calls (expr("1st",1) first

"Operator precedence" and "order of evaluation" are
two different things. Precedence dictates that the
expression means

expr("1st",1) || ( expr("2nd",0) && expr("3rd",0) )

rather than

( expr("1st",1) || expr("2nd",0) ) && expr("3rd",0)

.... but precedence alone doesn't determine the order in
which the three expr() calls are made.

The evaluation order is determined not by the precedence,
but by the definitions of the || and && operators. In this
case, the rule for || says that if expr("1st",1) produces a
non-zero value, the second sub-expression is not evaluated
at all. If the expr("1st",1) yields zero, the second sub-
expression *is* evaluated -- and in that evaluation, there
is a similar rule for && that governs the order in which
expr("2nd",0) and expr("3rd",0) are evaluated.

Summary: Operator precedence governs the meaning of an
expression with multiple operators, but does not control
the order in which the operands are evaluated.

 

[Mark A. Odell]

This is nasty stuff!

Nasty nothing. It's dog simple.

if (a || b)

Why on earth would you ever evaluate b if a is true? Very simple. I
believe we need to think about sequence points here.

 

[Eric Sosman]

This is nasty stuff! Once prompted, I remember the short circuit rule and
how I once wanted such a rule in Pascal. But digging this rule out of the
BNF for C seems like a real challenge.

A challenge, indeed, because the short-circuit rule is
not present in the BNF in the first place.

However I would expect it to be
noticeable in syntax charts.

Why? The syntax will tell you what arrangements of
symbols are valid C utterances, but will say nothing about
what those utterances mean (if, indeed, they mean anything
at all).

 

[osmium]

Mark A. Odell writes:

Please look at the code below


#include <stdio.h>

int expr(char str[], int i){
printf("%s \n",str);
return i;
}

int main()
{
if(expr("1st",1) || expr("2nd",0) && expr("3rd",1));
return 0;
}

output
-------
1st

As && has an higher precedence over ||
then it should call expr("2nd",0) or expr("3rd",0)
first then why it calls (expr("1st",1) first

It's called a short-circuit. If expr("1st",1) is true, then there is no
need to bother evaluting expr("3rd",0) and then expr("2nd",0), so it does
not. What you have seen is correct.

This is nasty stuff! Once prompted, I remember the short circuit rule and
how I once wanted such a rule in Pascal. But digging this rule out of the
BNF for C seems like a real challenge. However I would expect it to be
noticeable in syntax charts. Does any one know of a site containing syntax
charts for C? I looked and failed to find one. I know there is a book, I
saw one several years ago, but I didn't like it.

 

[Sidney Cadot]

[...snip...]
Nasty nothing. It's dog simple.

if (a || b)

Why on earth would you ever evaluate b if a is true?

If this wasn't a rhetorical question, I /could/ think of an answer. For
example: short-circuit evaluation may, under some circumstances,
negatively impact the size and/or speed of generated assembly code
(e.g., by introducing pipeline stalls).

Best regards, Sidney

 

[Eric Sosman]

"osmium" <[email protected]> wrote in

[...snip...]
Nasty nothing. It's dog simple.

if (a || b)

Why on earth would you ever evaluate b if a is true?

If this wasn't a rhetorical question, I /could/ think of an answer. For
example: short-circuit evaluation may, under some circumstances,
negatively impact the size and/or speed of generated assembly code
(e.g., by introducing pipeline stalls).

You're missing the point, I think. Short-circuit
evaluation isn't about efficiency, but about correctness.
The || and && operators are *defined* to work this way;
an implementation that evaluated `b' when `a' was true
would not be an implementation of C.

 

[glen herrmannsfeldt]

Eric Sosman wrote:

(snip)

(snip)

... but precedence alone doesn't determine the order in
which the three expr() calls are made.

The evaluation order is determined not by the precedence,
but by the definitions of the || and && operators. In this
case, the rule for || says that if expr("1st",1) produces a
non-zero value, the second sub-expression is not evaluated
at all. If the expr("1st",1) yields zero, the second sub-
expression *is* evaluated -- and in that evaluation, there
is a similar rule for && that governs the order in which
expr("2nd",0) and expr("3rd",0) are evaluated.

Summary: Operator precedence governs the meaning of an
expression with multiple operators, but does not control
the order in which the operands are evaluated.

Funny. There is a very similar discussion in comp.lang.fortran,
except that Fortran does not guarantee short circuit evaluation.

The discussion of precedence and evaluation order is there, though.

-- glen

 

[Keith Thompson]

Nasty nothing. It's dog simple.

if (a || b)

Why on earth would you ever evaluate b if a is true? Very simple. I
believe we need to think about sequence points here.

The && and || operators short-circuit because the standard says so.
It's not at all obvious that they need to. There are at least four
possible ways this could have been defined, and I think there are
languages that implement each of them:

1. The logical "and" and "or" operators (however they're spelled)
always short-circuit (C, C++, Perl, etc.).

2. The "and" and "or" operators never short-circuit (Pascal, I think).

3. It's unspecified or implementation-defined whether they
short-circuit; code that assumes either that they do or that they
don't is potentially non-portable (I don't know of an example of
this).

4. The language provides variant forms, letting the programmer decide
whether short-circuiting is desired (Ada has "and" and "or", which
don't short-circuit, and "and then" and "or else", which do).

On modern CPUs, a non-short-circuiting form can actually improve
performance in some cases by avoiding pipeline stalls. The fact that
C doesn't provide an easy way to do this is partly a result of the
fact that the language was defined before pipeline stalls were much of
an issue.

I would geuss that some optimizing C compilers can transform "&&" and
"||" to non-short-circuiting forms if they can prove the RHS has no
side effects and doesn't depend on the LHS.

Of course short-circuiting is extremely useful for things like:

if (ptr != NULL && *ptr != 0) { ... }

 

[Sidney Cadot]

You're missing the point, I think.

Umm no, I don't think so. I was merely following my instincts, which
invariably make me answer seemingly rhetorical questions.

Short-circuit evaluation isn't about efficiency, but about correctness.
The || and && operators are *defined* to work this way;
an implementation that evaluated `b' when `a' was true
would not be an implementation of C.

According to the "as if" principle, a compiler is perfectly free to do
this given the right circumstances. And, in fact, it may just be the
clever thing to do. Consider:

int proof_of_concept(void)
{
int a,b,c,d;

a = function_returning_int()!=0;
b = function_returning_int()!=0;
c = function_returning_int()!=0;
d = function_returning_int()!=0;

return a||b||c||d;
}

The best (fastest & shortest) translation of the return expression
evaluation for most architectures would be to just use the binary-or
operator on a, b, c, and d.

The alternative would involve a lot of branching, which is really
significantly slower on many architectures.

Whether any compiler is actually smart enough to do this: I doubt it!

Best regards, Sidney

 

[Eric Sosman]

[...]
On modern CPUs, a non-short-circuiting form can actually improve
performance in some cases by avoiding pipeline stalls. The fact that
C doesn't provide an easy way to do this is partly a result of the
fact that the language was defined before pipeline stalls were much of
an issue.

"C doesn't provide?" Perhaps you've forgotten

if (a || b) vs. if (a | b)
if (a && b) vs. if (a & b)

.... except that in some circumstances you might need to
write the last of these as `if (!!a & !!b)'. At any rate,
C does in fact provide non-short-circuited forms if you
want them.

 

[Eric Sosman]

You're missing the point, I think.

Umm no, I don't think so. I was merely following my instincts, which
invariably make me answer seemingly rhetorical questions.

Short-circuit evaluation isn't about efficiency, but about correctness.
The || and && operators are *defined* to work this way;
an implementation that evaluated `b' when `a' was true
would not be an implementation of C.

According to the "as if" principle, [...]

Ah, well, yes, of course. Perhaps I should have written
"An implementation that permitted the program to observe that
`b' had been evaluated ..." Schrödinger was a compiler writer
(at least, that's what Heisenberg may have said).

 

[Sidney Cadot]

[...]
On modern CPUs, a non-short-circuiting form can actually improve
performance in some cases by avoiding pipeline stalls. The fact that
C doesn't provide an easy way to do this is partly a result of the
fact that the language was defined before pipeline stalls were much of
an issue.

"C doesn't provide?" Perhaps you've forgotten

if (a || b) vs. if (a | b)
if (a && b) vs. if (a & b)

....And next time someone has the temerity to suggest that Pascal doesn't
provide short-circuit evaluation, I will be sure to point out the error
of their thinking by showing how it can be simulated in Pascal

Personally, I wouldn't consider using bit-ops an easy way to emulate
non-short-circuit evaluation, given the interpretation of true as
"anything un-equal to zero". As you rightly point out, this can be
overcome by using !!x or (x!=0) for any boolean operand, but it's still
a bit clumsy, and quite error-prone. Proper operators for this would be
nice-to-have.

Best regards,

Sidney

 

[Keith Thompson]

[...]
On modern CPUs, a non-short-circuiting form can actually improve
performance in some cases by avoiding pipeline stalls. The fact that
C doesn't provide an easy way to do this is partly a result of the
fact that the language was defined before pipeline stalls were much of
an issue.

"C doesn't provide?" Perhaps you've forgotten

if (a || b) vs. if (a | b)
if (a && b) vs. if (a & b)

... except that in some circumstances you might need to
write the last of these as `if (!!a & !!b)'. At any rate,
C does in fact provide non-short-circuited forms if you
want them.

If by "some circumstances" you mean "nearly all circumstances",
perhaps.

If I saw code that used "if (a & b)", my first assumption would be
that it was a typo for "if (a && b)", and my second would be that the
author really intended to test the bitwise "and" of a and b. If there
were a comment explaining that it's really a logical "and", using "&"
rather than "&&" to avoid pipeline stalls, I'd spend a long time
trying to figure out (1) how it's known that the values of a and b
cannot be anything other 0 or 1, and (2) why the author thought this
micro-optimization was worth the time I'm spending thinking about it.

 

[Jack Klein]

[...]
On modern CPUs, a non-short-circuiting form can actually improve
performance in some cases by avoiding pipeline stalls. The fact that
C doesn't provide an easy way to do this is partly a result of the
fact that the language was defined before pipeline stalls were much of
an issue.

"C doesn't provide?" Perhaps you've forgotten

if (a || b) vs. if (a | b)
if (a && b) vs. if (a & b)

... except that in some circumstances you might need to
write the last of these as `if (!!a & !!b)'. At any rate,
C does in fact provide non-short-circuited forms if you
want them.

Yes, "!!" in C is the "Booleanization" operator for scalar types.

In C99:

if (_Bool(a) | _Bool(b))

....of course, bool may be substituted for _Bool if <stdbool.h> is
included.

 

[Jeremy Yallop]

In C99:

if (_Bool(a) | _Bool(b))

ITYM

if ((_Bool)a | (_Bool)b)

(assuming you got mixed up with C++ constructor syntax).

Jeremy.

 

[CBFalconer]

Please look at the code below

#include <stdio.h>

int expr(char str[], int i){
printf("%s \n",str);
return i;
}

int main()
{
if(expr("1st",1) || expr("2nd",0) && expr("3rd",1));
return 0;
}

output
-------
1st

As && has an higher precedence over ||
then it should call expr("2nd",0) or expr("3rd",0)
first then why it calls (expr("1st",1) first

"Operator precedence" and "order of evaluation" are
two different things. Precedence dictates that the
expression means

expr("1st",1) || ( expr("2nd",0) && expr("3rd",0) )

rather than

( expr("1st",1) || expr("2nd",0) ) && expr("3rd",0)

... but precedence alone doesn't determine the order in
which the three expr() calls are made.

The evaluation order is determined not by the precedence,
but by the definitions of the || and && operators. In this
case, the rule for || says that if expr("1st",1) produces a
non-zero value, the second sub-expression is not evaluated
at all. If the expr("1st",1) yields zero, the second sub-
expression *is* evaluated -- and in that evaluation, there
is a similar rule for && that governs the order in which
expr("2nd",0) and expr("3rd",0) are evaluated.

Summary: Operator precedence governs the meaning of an
expression with multiple operators, but does not control
the order in which the operands are evaluated.

Finally a sensible answer in this thread. A corollary is: If you
want to use complex logical expressions, parenthise them so there
is NO DOUBT, NO DOUBT WHATSOEVER, what they mean. You will save a
lot of headaches, both your own and others.

 

[Jack Klein]

ITYM

if ((_Bool)a | (_Bool)b)

(assuming you got mixed up with C++ constructor syntax).

Jeremy.

Do you think in the next upgrade to the C++ standard they should add a
<stdbool> header that defines the macro _Bool to bool?

Thanks for correcting brain fart.