Lazy evaluation question

[Richard Harter]

Boltar said:


That's the kind of thing a good optimising compiler will already do.

Even though the RHS might have side effects?

 

[Richard Harter]

No, they are not.

An important goal of C was to generate efficient code. The operands of the
logical operators &&, ||, !, and ? must usually be tested at run time for a
true or false value, normally by a conditional branch. There is no extra
cost to short circuit evaluation and it is a short-hand convenience to
programming.

This isn't really right. The point of short circuit evaluation
of && and || is to suppress evaluation of the RHS when the LHS
establishes the truth of falsity of the boolean expression. This
is a programming convenience in code patterns like

if (ptr && foo(ptr)) {...}

IF we don't want to call foo when ptr is null. However if we do
want to call foo regardless of whether ptr is null, then short
circuit evaluation forces us to do something like

tmp = foo(ptr);
if (ptr && tmp) {...}

It turns out that short circuit evaluation is more convenient
(IMHO) and that C made the right choice.

 

[Tor Rustad]

Boltar said:


That's the kind of thing a good optimising compiler will already do.

Really?

Methinks, & operator always evaluate both operands, just like the |
operator.

 

[Syren Baran]

Yes , if the LHS value is 0xFFFFFFF or whatever theres no point
evaluating the RHS of a bitwise OR.

Right. But theres no point in checking the LHS side first for a 2 in
2^32 chance of not having to do the operation.
In x86 assembly this relates to 2 instructions, a CMP ..,0 + a JE ..
or a CMP ..,0xFFFFFFFF + a JE .. just to save an AND or OR?
A preprocessor can replace such an instruction in case of a constant,
but with vars such a check is complete bullshit.

 

[christian.bau]

Consider the loops

for (i = 0; i < n; ++i)
*p++ = *q++ & *r++;

and

for (i = 0; i < n; ++i)
*p++ = *r++ & *q++;

Would you want both loops to have the same or different behaviour?

 

[Tor Rustad]

Why does C do lazy evaluation for logical boolean operations but not
bitwise ones?

Ie: the following program prints "1 2" , not "1 1" under gcc

main()
{
int a = 1;
int b = 1;
0 && ++a;
0 & ++b;
printf("%d %d\n",a,b);
}

Surely the bitwise boolean ops are just as appropriate for doing lazy
evaluation with?

In C, 32 out of 34 binary operators always evaluate both their operands.

Many C coding standards prohibits side-effects on the second operand of
the && and the || operators, because there are some clueless
programmers, not aware of the conditional evaluation of the second operand.

 

[Richard Heathfield]

Richard Harter said:

Even though the RHS might have side effects?

Oh dear, this isn't turning out to be my thread, is it? No, obviously the
compiler can't do that if there are side effects to process.

 

[Richard Heathfield]

Tor Rustad said:

Really?

Methinks, & operator always evaluate both operands, just like the |
operator.

I was thinking of cases such as 0 & 1, 0 & vanilla_int_object, and so on.

 

[Tor Rustad]

Tor Rustad said:


I was thinking of cases such as 0 & 1, 0 & vanilla_int_object, and so on.

The context was:

0 && ++a;
0 & ++b;

Unlike && operator, the & operator has is no sequence point after
evaluating an operand, and there is no guarantees for a left-to-right
evaluation of the operands.

The role of result of the & operator, is a bit setting role, I see no
reason for the optimiser to affect this evaluation, unless the result is
a constant with no side-effects, that can be pre-computed at compile-time.

 

[Richard Heathfield]

Tor Rustad said:

The context was:

0 && ++a;
0 & ++b;

In that context, of course, RHS evaluation is indeed required. I was guilty
of not reading the thread properly.

 

[Thad Smith]

This isn't really right.

Which statement do you consider incorrect?

The point of short circuit evaluation
of && and || is to suppress evaluation of the RHS when the LHS
establishes the truth of falsity of the boolean expression. This
is a programming convenience in code patterns like

if (ptr && foo(ptr)) {...}

I mentioned that it is a programming convenience. I was giving a rationale
for short circuit evaluation for logical operators and not bitwise
operators, saying that the implementation for logical short circuit is both
useful and efficient, in contrast to implementing short circuit bitwise
operators.

 

[Army1987]

Why? If theres a zero on the LHS of a bitwise AND you know the result
will be zero no matter what is on the RHS so why bother evaluating the
RHS?

By that reasoning, a * x++ shouldn't increment x when a is 0, either.
Or foo < bar() shouldn't call bar if it returns an int and foo is INT_MIN.

 

[Harald van Dijk]

By that reasoning, a * x++ shouldn't increment x when a is 0, either. Or
foo < bar() shouldn't call bar if it returns an int and foo is INT_MIN.

If foo == INT_MIN, the result of foo < bar() depends on whether bar also
returns INT_MIN. If foo == INT_MAX, the result doesn't depend on bar.

 

[vippstar]

If foo == INT_MIN, the result of foo < bar() depends on whether bar also
returns INT_MIN. If foo == INT_MAX, the result doesn't depend on bar.

Incorrect. Example:
--
#include <stdio.h>

int bar(void) { return 0; }
int foo = INT_MAX;
int main(void) {
printf("%d\n", foo < -bar());
return 0;
}

 

[Harald van Dijk]

#include <stdio.h>

int bar(void) { return 0; }
int foo = INT_MAX;
int main(void) {
printf("%d\n", foo < -bar());
return 0;
}

No, that's not allowed. -0 is always equal to plain old zero. I
understand the point you're making, and it is a valid one, but you
would've needed to use ~bar() as an example.

How about "If the evaluation of x is defined to produce a result, then
the value of INT_MAX < x does not depend on the value of x."? It also
covers the case where the evaluation of x leads to a call to exit() or
abort().

 

[vippstar]

No, that's not allowed. -0 is always equal to plain old zero. I
understand the point you're making, and it is a valid one, but you
would've needed to use ~bar() as an example.

-0 is valid but i think -- not sure at all -- that -x where x is 0
might be a trap representation..
Maybe someone else knows?

How about "If the evaluation of x is defined to produce a result, then
the value of INT_MAX < x does not depend on the value of x."? It also
covers the case where the evaluation of x leads to a call to exit() or
abort().

As long as 'x' is of type int, short or signed char yes, but now I
have lost your point..

 

[Harald van Dijk]

-0 is valid but i think -- not sure at all -- that -x where x is 0 might
be a trap representation..
Maybe someone else knows?

-x where x is 0 just means -0. When a is 1, and b is 2, you wouldn't
expect a+b to be different from 1+2, would you?

As long as 'x' is of type int, short or signed char yes, but now I have
lost your point..

I corrected a message which used INT_MIN instead of INT_MAX. That's all.

 

[Ben Bacarisse]

-0 is valid but i think -- not sure at all -- that -x where x is 0
might be a trap representation..
Maybe someone else knows?

I can't imagine why you'd believe me rather than anyone else, but
Harald is correct. You have to form your own opinion, but I'd want to
have good quotes to hand (from definitive documents) before correcting
a post from Harald van Dijk!

In this case I have them in support of what he says. First, to
find out what negative zero is:

6.2.6.2 Integer types
[para 2]
....

If the sign bit is one, the value shall be modified in one of the
following ways:

— the corresponding value with sign bit 0 is negated (sign and
magnitude);

— the sign bit has the value −(2**N) (two’s complement);

— the sign bit has the value −(2**(N−1)) (ones’ complement).

Which of these applies is implementation-defined, as is whether
the value with sign bit 1 and all value bits zero (for the first
two), or with sign bit and all value bits 1 (for ones’
complement), is a trap representation or a normal value. In the
case of sign and magnitude and ones’ complement, if this
representation is a normal value it is called a negative zero.

and then to see how they can come about:
[para 3]

If the implementation supports negative zeros, they shall be
generated only by:

— the &, |, ^, ~, <<, and >> operators with arguments that
produce such a value;

— the +, -, *, /, and % operators where one argument is a
negative zero and the result is zero;

— compound assignment operators based on the above cases.

It is unspecified whether these cases actually generate a negative
zero or a normal zero, and whether a negative zero becomes a
normal zero when stored in an object.

So for arithmetic operations like -, you can to have a negative zero
to start with.

 

[Ben Bacarisse]

So for arithmetic operations like -, you can to have a negative zero

^^^ have

to start with.

Sorry. My typing is getting worse and this one seemed particularly
yucky to leave uncorrected.

 

[Richard Bos]

Many C coding standards prohibits side-effects on the second operand of
the && and the || operators, because there are some clueless
programmers, not aware of the conditional evaluation of the second operand.

More fool them, then, since code like

if ((ch=*text++)=='&' && (ch=*text++)!='\0') /* Handle escape char*/

is both common and useful.

Richard