controlling expressions evaluation

[Pietro Cerutti]

Hi group,
here I come with a question which is quite simple per se, but for which
I can't find an answer.

Does the C standard guarantee that inside an expression such as

(x && y)

"y" is not evaluated if "x" evaluates to 0?

Are we guaranteed that a conforming compiler cannot, for whatever
purpose, evaluate "y" first?

The reason for my question is that in my code I have to fill a structure
(say "my_table") with a function (say "fill_table()"), and fill_table
should be called only if my_table is NULL (i.e. wasn't filled before).

if this always going to be correct?

if(!my_table && fill_table())

Thank you.

 

[CryptiqueGuy]

Hi group,
here I come with a question which is quite simple per se, but for which
I can't find an answer.

Does the C standard guarantee that inside an expression such as

(x && y)

"y" is not evaluated if "x" evaluates to 0?

C standards gurantee left to right evlauation in this respect.
The C standards is clear about this.

Here I quote 6.5.13 Logical AND operator:

Syntax
1 logical-AND-expression:
inclusive-OR-expression
logical-AND-expression && inclusive-OR-expression
Constraints
2 Each of the operands shall have scalar type.
Semantics
3 The && operator shall yield 1 if both of its operands compare
unequal to 0; otherwise, it
yields 0. The result has type int.
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

I hope this should answer your doubt completely.

Are we guaranteed that a conforming compiler cannot, for whatever
purpose, evaluate "y" first?

As per the standards, 'y' won't be evaluated first. But by "as if"
rule, I think a compiler might do that, if it doesn't affect the
behavior of the code. But ultimately the result produced by the code
should be such that, there is left to right evaluation.

So you could very well think that 'x' is evaluated before 'y' without
bothering, if it is internally done that way or not.

 

[Eric Sosman]

Hi group,
here I come with a question which is quite simple per se, but for which
I can't find an answer.

Does the C standard guarantee that inside an expression such as

(x && y)

"y" is not evaluated if "x" evaluates to 0?

Yes.

Are we guaranteed that a conforming compiler cannot, for whatever
purpose, evaluate "y" first?

Yes. If you study the generated code you might doubt
this "yes," because in some situations you might find that
the evaluation of y begins before the evaluation of x is
finished (imagine x and y not as single variables, but as
more complicated expressions). But don't worry: the outcome
must be "as if" y's evaluation is strictly later than x's,
or doesn't happen at all if x is zero. No side-effects or
errors that could occur in the evaluation of y can happen
until after x is finished and found to be non-zero; if x
turns out to be zero then no side-effects or errors from
evaluating y can occur at all.

The reason for my question is that in my code I have to fill a structure
(say "my_table") with a function (say "fill_table()"), and fill_table
should be called only if my_table is NULL (i.e. wasn't filled before).

if this always going to be correct?

if(!my_table && fill_table())

Yes. There is a similar guarantee for || (second term
evaluates after the first, and only if the first is zero).
The ?: operator and the , operator also enforce ordering.

 

[Pietro Cerutti]

Yes. If you study the generated code you might doubt
this "yes," because in some situations you might find that
the evaluation of y begins before the evaluation of x is
finished (imagine x and y not as single variables, but as
more complicated expressions). But don't worry: the outcome
must be "as if" y's evaluation is strictly later than x's,
or doesn't happen at all if x is zero. No side-effects or
errors that could occur in the evaluation of y can happen
until after x is finished and found to be non-zero; if x
turns out to be zero then no side-effects or errors from
evaluating y can occur at all.

Thank you for your answer (and also thank you CryptiqueGuy for yours,
which is basically the same).

I'm only a bit worried about your sentence "[...] in some situations you
might find that the evaluation of y begins before the evaluation of x".
What does it mean, practically?

 

[Richard Heathfield]

Pietro Cerutti said:

I'm only a bit worried about your sentence "[...] in some situations
you might find that the evaluation of y begins before the evaluation
of x".

Don't be. The "as if" rule applies.

What does it mean, practically?

Practically, it means you don't need to be a bit worried.

 

[Eric Sosman]

Yes. If you study the generated code you might doubt
this "yes," because in some situations you might find that
the evaluation of y begins before the evaluation of x is
finished (imagine x and y not as single variables, but as
more complicated expressions). But don't worry: the outcome
must be "as if" y's evaluation is strictly later than x's,
or doesn't happen at all if x is zero. No side-effects or
errors that could occur in the evaluation of y can happen
until after x is finished and found to be non-zero; if x
turns out to be zero then no side-effects or errors from
evaluating y can occur at all.

Thank you for your answer (and also thank you CryptiqueGuy for yours,
which is basically the same).

I'm only a bit worried about your sentence "[...] in some situations you
might find that the evaluation of y begins before the evaluation of x".
What does it mean, practically?

Essentially, it means "Don't let the generated code
confuse you." Imagine a y that is a multi-term expression,
and suppose that some parts of y will be used no matter
how the test comes out:

if (x && r + s > t)
printf ("Boo!\n");
z = r + s + t;

Here, y is the entire expression `r + s > t', which we have
said will only be evaluated if x is non-zero. But the compiler
might decide to evaluate the sub-expression `r + s' early, since
it will produce no side-effects (let's assume) and the sum will
be needed anyhow. The compiler might do something like

tmp = r + s;
if (x && tmp > t)
printf ("Boo!\n");
z = tmp + t;

.... and this would be perfectly all right. The compiler could
*not* do this if evaluating `r + s' could produce a side-effect
(overflow generating a signal, for instance), because the value
of x should govern whether the signal occurs before or after the
output, and in the rewritten code it would always occur first.
But if the compiler can figure out that `r + s' has no side-
effects to worry about, it can evaluate that component of y
before it finishes evaluating x.

Practical effects: From the C programmer's perspective,
none, because the program operates "as if" x==0 completely
suppressed the evaluation of y. Someone studying the compiled
code might be confused by seeing some parts of y evaluated
early, but that's just a distraction. The only reason I brought
it up was in response to your phrase "for whatever purpose."

 

[Pietro Cerutti]

Pietro Cerutti wrote:
Hi group,
here I come with a question which is quite simple per se, but for which
I can't find an answer.

Does the C standard guarantee that inside an expression such as

(x && y)

"y" is not evaluated if "x" evaluates to 0?
Yes.

Are we guaranteed that a conforming compiler cannot, for whatever
purpose, evaluate "y" first?
Yes. If you study the generated code you might doubt
this "yes," because in some situations you might find that
the evaluation of y begins before the evaluation of x is
finished (imagine x and y not as single variables, but as
more complicated expressions). But don't worry: the outcome
must be "as if" y's evaluation is strictly later than x's,
or doesn't happen at all if x is zero. No side-effects or
errors that could occur in the evaluation of y can happen
until after x is finished and found to be non-zero; if x
turns out to be zero then no side-effects or errors from
evaluating y can occur at all.

Thank you for your answer (and also thank you CryptiqueGuy for yours,
which is basically the same).

I'm only a bit worried about your sentence "[...] in some situations you
might find that the evaluation of y begins before the evaluation of x".
What does it mean, practically?

Essentially, it means "Don't let the generated code
confuse you." Imagine a y that is a multi-term expression,
and suppose that some parts of y will be used no matter
how the test comes out:

if (x && r + s > t)
printf ("Boo!\n");
z = r + s + t;

Here, y is the entire expression `r + s > t', which we have
said will only be evaluated if x is non-zero. But the compiler
might decide to evaluate the sub-expression `r + s' early, since
it will produce no side-effects (let's assume) and the sum will
be needed anyhow. The compiler might do something like

tmp = r + s;
if (x && tmp > t)
printf ("Boo!\n");
z = tmp + t;

... and this would be perfectly all right. The compiler could
*not* do this if evaluating `r + s' could produce a side-effect
(overflow generating a signal, for instance), because the value
of x should govern whether the signal occurs before or after the
output, and in the rewritten code it would always occur first.
But if the compiler can figure out that `r + s' has no side-
effects to worry about, it can evaluate that component of y
before it finishes evaluating x.

Practical effects: From the C programmer's perspective,
none, because the program operates "as if" x==0 completely
suppressed the evaluation of y. Someone studying the compiled
code might be confused by seeing some parts of y evaluated
early, but that's just a distraction. The only reason I brought
it up was in response to your phrase "for whatever purpose."

Thank you, your example was clear!

One more question, if I can...

What if "y" is a function modifying "x"? Can the compiler figure our
that evaluating "y" has effects on "x"? In this case, is the function
not entered at all, or stopped before modifying "x"?

Thank you again.

 

[CryptiqueGuy]

Eric Sosman wrote:
Pietro Cerutti wrote:
Hi group,
here I come with a question which is quite simple per se, but for which
I can't find an answer.
Does the C standard guarantee that inside an expression such as
(x && y)
"y" is not evaluated if "x" evaluates to 0?
Yes.
Are we guaranteed that a conforming compiler cannot, for whatever
purpose, evaluate "y" first?
Yes. If you study the generated code you might doubt
this "yes," because in some situations you might find that
the evaluation of y begins before the evaluation of x is
finished (imagine x and y not as single variables, but as
more complicated expressions). But don't worry: the outcome
must be "as if" y's evaluation is strictly later than x's,
or doesn't happen at all if x is zero. No side-effects or
errors that could occur in the evaluation of y can happen
until after x is finished and found to be non-zero; if x
turns out to be zero then no side-effects or errors from
evaluating y can occur at all.
Thank you for your answer (and also thank you CryptiqueGuy for yours,
which is basically the same).
I'm only a bit worried about your sentence "[...] in some situations you
might find that the evaluation of y begins before the evaluation of x".
What does it mean, practically?

Essentially, it means "Don't let the generated code
confuse you." Imagine a y that is a multi-term expression,
and suppose that some parts of y will be used no matter
how the test comes out:

if (x && r + s > t)
printf ("Boo!\n");
z = r + s + t;

Here, y is the entire expression `r + s > t', which we have
said will only be evaluated if x is non-zero. But the compiler
might decide to evaluate the sub-expression `r + s' early, since
it will produce no side-effects (let's assume) and the sum will
be needed anyhow. The compiler might do something like

tmp = r + s;
if (x && tmp > t)
printf ("Boo!\n");
z = tmp + t;

... and this would be perfectly all right. The compiler could
*not* do this if evaluating `r + s' could produce a side-effect
(overflow generating a signal, for instance), because the value
of x should govern whether the signal occurs before or after the
output, and in the rewritten code it would always occur first.
But if the compiler can figure out that `r + s' has no side-
effects to worry about, it can evaluate that component of y
before it finishes evaluating x.

Practical effects: From the C programmer's perspective,
none, because the program operates "as if" x==0 completely
suppressed the evaluation of y. Someone studying the compiled
code might be confused by seeing some parts of y evaluated
early, but that's just a distraction. The only reason I brought
it up was in response to your phrase "for whatever purpose."

Thank you, your example was clear!

One more question, if I can...

What if "y" is a function modifying "x"? Can the compiler figure our
that evaluating "y" has effects on "x"?

It has to in order that it is conforming.
As per the "as if" rule, the behavior should be as if the result
produced by the abstract machine described by the standards.

In this case, is the function
not entered at all,

Depends on the value of 'x'.

One more thing you need to note is that there is a sequence point at
&&. I add this statement, in case you had not known that.

 

[Richard]

Eric Sosman wrote:
Pietro Cerutti wrote:
Hi group,
here I come with a question which is quite simple per se, but for which
I can't find an answer.

Does the C standard guarantee that inside an expression such as

(x && y)

"y" is not evaluated if "x" evaluates to 0?
Yes.

Are we guaranteed that a conforming compiler cannot, for whatever
purpose, evaluate "y" first?
Yes. If you study the generated code you might doubt
this "yes," because in some situations you might find that
the evaluation of y begins before the evaluation of x is
finished (imagine x and y not as single variables, but as
more complicated expressions). But don't worry: the outcome
must be "as if" y's evaluation is strictly later than x's,
or doesn't happen at all if x is zero. No side-effects or
errors that could occur in the evaluation of y can happen
until after x is finished and found to be non-zero; if x
turns out to be zero then no side-effects or errors from
evaluating y can occur at all.

Thank you for your answer (and also thank you CryptiqueGuy for yours,
which is basically the same).

I'm only a bit worried about your sentence "[...] in some situations you
might find that the evaluation of y begins before the evaluation of x".
What does it mean, practically?

Essentially, it means "Don't let the generated code
confuse you." Imagine a y that is a multi-term expression,
and suppose that some parts of y will be used no matter
how the test comes out:

if (x && r + s > t)
printf ("Boo!\n");
z = r + s + t;

Here, y is the entire expression `r + s > t', which we have
said will only be evaluated if x is non-zero. But the compiler
might decide to evaluate the sub-expression `r + s' early, since
it will produce no side-effects (let's assume) and the sum will
be needed anyhow. The compiler might do something like

tmp = r + s;
if (x && tmp > t)
printf ("Boo!\n");
z = tmp + t;

... and this would be perfectly all right. The compiler could
*not* do this if evaluating `r + s' could produce a side-effect
(overflow generating a signal, for instance), because the value
of x should govern whether the signal occurs before or after the
output, and in the rewritten code it would always occur first.
But if the compiler can figure out that `r + s' has no side-
effects to worry about, it can evaluate that component of y
before it finishes evaluating x.

Practical effects: From the C programmer's perspective,
none, because the program operates "as if" x==0 completely
suppressed the evaluation of y. Someone studying the compiled
code might be confused by seeing some parts of y evaluated
early, but that's just a distraction. The only reason I brought
it up was in response to your phrase "for whatever purpose."

Thank you, your example was clear!

One more question, if I can...

What if "y" is a function modifying "x"? Can the compiler figure our
that evaluating "y" has effects on "x"? In this case, is the function
not entered at all, or stopped before modifying "x"?

How or why would a compiler allow that function to be called and then
"stop it before modifying x"?

y is not evaluated if x is true.

Thank you again.

--

 

[Pietro Cerutti]

Pietro Cerutti wrote:
Eric Sosman wrote:
Pietro Cerutti wrote:
Hi group,
here I come with a question which is quite simple per se, but for which
I can't find an answer.
Does the C standard guarantee that inside an expression such as
(x && y)
"y" is not evaluated if "x" evaluates to 0?
Yes.
Are we guaranteed that a conforming compiler cannot, for whatever
purpose, evaluate "y" first?
Yes. If you study the generated code you might doubt
this "yes," because in some situations you might find that
the evaluation of y begins before the evaluation of x is
finished (imagine x and y not as single variables, but as
more complicated expressions). But don't worry: the outcome
must be "as if" y's evaluation is strictly later than x's,
or doesn't happen at all if x is zero. No side-effects or
errors that could occur in the evaluation of y can happen
until after x is finished and found to be non-zero; if x
turns out to be zero then no side-effects or errors from
evaluating y can occur at all.
Thank you for your answer (and also thank you CryptiqueGuy for yours,
which is basically the same).
I'm only a bit worried about your sentence "[...] in some situations you
might find that the evaluation of y begins before the evaluation of x".
What does it mean, practically?
Essentially, it means "Don't let the generated code
confuse you." Imagine a y that is a multi-term expression,
and suppose that some parts of y will be used no matter
how the test comes out:
if (x && r + s > t)
printf ("Boo!\n");
z = r + s + t;
Here, y is the entire expression `r + s > t', which we have
said will only be evaluated if x is non-zero. But the compiler
might decide to evaluate the sub-expression `r + s' early, since
it will produce no side-effects (let's assume) and the sum will
be needed anyhow. The compiler might do something like
tmp = r + s;
if (x && tmp > t)
printf ("Boo!\n");
z = tmp + t;
... and this would be perfectly all right. The compiler could
*not* do this if evaluating `r + s' could produce a side-effect
(overflow generating a signal, for instance), because the value
of x should govern whether the signal occurs before or after the
output, and in the rewritten code it would always occur first.
But if the compiler can figure out that `r + s' has no side-
effects to worry about, it can evaluate that component of y
before it finishes evaluating x.
Practical effects: From the C programmer's perspective,
none, because the program operates "as if" x==0 completely
suppressed the evaluation of y. Someone studying the compiled
code might be confused by seeing some parts of y evaluated
early, but that's just a distraction. The only reason I brought
it up was in response to your phrase "for whatever purpose."

Thank you, your example was clear!

One more question, if I can...

What if "y" is a function modifying "x"? Can the compiler figure our
that evaluating "y" has effects on "x"?

It has to in order that it is conforming.
As per the "as if" rule, the behavior should be as if the result
produced by the abstract machine described by the standards.

In this case, is the function
not entered at all,

Depends on the value of 'x'.

One more thing you need to note is that there is a sequence point at
&&. I add this statement, in case you had not known that.

or stopped before modifying "x"?

Clear enough!
Thank you for your time!

 

[santosh]

I'm only a bit worried about your sentence "[...] in some situations you
might find that the evaluation of y begins before the evaluation of x".
What does it mean, practically?

Practical effects: From the C programmer's perspective,
none, because the program operates "as if" x==0 completely
suppressed the evaluation of y. Someone studying the compiled
code might be confused by seeing some parts of y evaluated
early, but that's just a distraction. The only reason I brought
it up was in response to your phrase "for whatever purpose."

Thank you, your example was clear!

One more question, if I can...

What if "y" is a function modifying "x"?

Same "as if" rule holds. "y" is executed only if "x" evaluates true.

Can the compiler figure our
that evaluating "y" has effects on "x"?

Yes. An optimising compiler can.

In this case, is the function
not entered at all, or stopped before modifying "x"?

The function would most likely not be executed if "x" evaluates to
false. It makes no sense to enter the function but "stop" before
modifying "x".

 

[Eric Sosman]

Pietro Cerutti wrote On 07/09/07 09:02,:

[...]

One more question, if I can...

What if "y" is a function modifying "x"? Can the compiler figure our
that evaluating "y" has effects on "x"? In this case, is the function
not entered at all, or stopped before modifying "x"?

If x is zero, the program must behave as if y is
never evaluated at all. Any side-effects of evaluating
y -- like modifying x -- must not occur if x was zero
to begin with.

if (j > 0 && --j > 0) ...

If j is zero or negative before this test, --j will not
be evaluated and j's value will not change.

 

[Keith Thompson]

Lots of context snipped. An example of what we're now talking about is

if (x && y()) /* ... */

How or why would a compiler allow that function to be called and then
"stop it before modifying x"?

In any way it likes. For example, if the call to y is inlined, then
'x && y()' could become a single large expression not involving a
function call. The compiler can then manipulate this large expression
in various ways, as long as the required semantics are not violated.
In particular, the sequence points are still there, and the compiler
has to be very careful about moving code across sequence points.

y is not evaluated if x is true.

You mean "if x is false" (more precisly, if x is equal to zero).

That's true in the abstract machine. It's not necessarily true in the
actual generated code, as long as the code behaves *as if* y is not
evaluated if x is true.

 

[CBFalconer]

here I come with a question which is quite simple per se, but for
which I can't find an answer.

Does the C standard guarantee that inside an expression such as
(x && y)
"y" is not evaluated if "x" evaluates to 0?

To make a long, complicated answer: Yes. See the standard.

 

[Richard]

Lots of context snipped. An example of what we're now talking about is

if (x && y()) /* ... */


In any way it likes. For example, if the call to y is inlined, then
'x && y()' could become a single large expression not involving a
function call. The compiler can then manipulate this large expression
in various ways, as long as the required semantics are not violated.
In particular, the sequence points are still there, and the compiler
has to be very careful about moving code across sequence points.


You mean "if x is false" (more precisly, if x is equal to zero).

*blush* Sorry. Obvious typo.

That's true in the abstract machine. It's not necessarily true in the
actual generated code, as long as the code behaves *as if* y is not
evaluated if x is true.

In which case, to simplify things since the observed results are the
same, maybe better to say "is not executed". Not everything needs to be
caveated IMO - it leads to confusion for nOObs.

--

 

[Keith Thompson]

*blush* Sorry. Obvious typo.

*I* meant "if x is false". (I also meant "precisely", not
"precisly".)

In which case, to simplify things since the observed results are the
same, maybe better to say "is not executed". Not everything needs to be
caveated IMO - it leads to confusion for nOObs.

I don't see how "is not executed" is less confusing than "is not
evaluated"; it's less accurate, but it means the same thing. Code
that evaluates y could very well be executed, as long as the end
result is as if it were not.