expression and evaluation order and precedence rules

[silpau]

hi,

i am a bit confused on expression evaluation order in expressions
involving unary increment.decrement operators along with binary
operators.

For example in the following expression

x += i + j + k++;

is the following the sequence of evaluations

1) as ++ has highest precedencce subexpression k++ gets evaluated
2) i + j is evaluated next and say the result is stored in a temporary
location say temp
3) next temp + k++ gets evaluated and result stored in temporary
location say temp1
4) next x + temp1 gets evaluated and the result is assigned back to x.

So is the sequence of evaluations correct or am i missing out
something here?


Would it be correct to assume tht given an expression all unary
oerators are evaluated followed by evaluation of binary operators


thanks,
silpa

 

[Richard Heathfield]

(e-mail address removed) said:

hi,

i am a bit confused on expression evaluation order in expressions
involving unary increment.decrement operators along with binary
operators.

For example in the following expression

x += i + j + k++;

is the following the sequence of evaluations

1) as ++ has highest precedencce subexpression k++ gets evaluated

No. You can think of precedence and associativity as sorting out which
expressions get to be the operands for any given operator. Precedence
and associativity rules mean that the above expression has the same
meaning as:

x += ((i + j) + (k++));

The order of evaluation of the expressions is unspecified. k++ might be
done first, or it might not. C doesn't say. What it does say, however,
is that the result of k++ is the value k had at the previous sequence
point, so it turns out that it doesn't actually matter anyway.

I cannot stress this enough: neither precedence nor associativity has
*anything* to do with order of evaluation.

Would it be correct to assume tht given an expression all unary
oerators are evaluated followed by evaluation of binary operators

No. See above.

 

[Chris Dollin]

I cannot stress this enough: neither precedence nor associativity has
*anything* to do with order of evaluation.

(fx:nitpick) False, since the P & A determines what's an operand of
what, and in general operands have to be evaluated before the operation
of which they are a part.

But that's only an indirect effect.

 

[Richard Heathfield]

Chris Dollin said:

(fx:nitpick) False,
Wrong.

since the P & A determines what's an operand of what,
True.

and in general operands have to be evaluated before the
operation of which they are a part.

That doesn't matter for my point. For example, consider the expression:

a = b() * c() + d();

Here is one legal possibility for the generated assembly language code:

JSR _d
MOV R20, R10 ; copy result of d() to reg 20
JSR _c
MOV R21, R10 ; copy result of c() to reg 21
JSR _b
MOV R22, R10 ; copy result of b() to reg 22
MOV R24, 0 ; reg 24 will hold the result of the entire expr
ADD R24, R20
MUL R21, R22
ADD R24, R21 ; the calculation is now complete
MOV _a, R24

Here, the order of evaluation is d(), c(), b(), addition,
multiplication, whereas the precedence and associativity ordering would
suggest pretty much the opposite.

But that's only an indirect effect.

And a misleading one.

I cannot stress this enough: neither precedence nor associativity has
*anything* to do with order of evaluation.

 

[Richard Tobin]

Chris Dollin said:

That doesn't matter for my point. For example, consider the expression:

a = b() * c() + d(); [...]
I cannot stress this enough: neither precedence nor associativity has
*anything* to do with order of evaluation.

I think Chris's point is that the relative precedence of + and *
forces the multiplication corresponding to the "*" operators to be
done before the addition corresponding to the "+" operator, and that
was true even in your example code.

Of course, you might be able to generate code sufficiently different
from the original expression that nothing can be identified as "the
addition corresponding to the '+' operator".

-- Richard

 

[Richard Heathfield]

Richard Tobin said:

For example, consider the expression:

a = b() * c() + d(); [...]
I cannot stress this enough: neither precedence nor associativity has
*anything* to do with order of evaluation.

I think Chris's point is that the relative precedence of + and *
forces the multiplication corresponding to the "*" operators to be
done before the addition corresponding to the "+" operator, and that
was true even in your example code.

My point is that one of the operands of the addition was actually
evaluated *first*, despite the fact that precedence and associativity
rules would suggest it should actually be evaluated *last* (if they
were even remotely relevant).

Of course, you might be able to generate code sufficiently different
from the original expression that nothing can be identified as "the
addition corresponding to the '+' operator".

Indeed. In fact, it would be easy - just replace the addition with an
AND, an XOR, a LSH, and a jump, with a Russian-peasant-multiplication
loop round the outside. Then you can mix all the additions and
multiplications up into one sorry mess in which it would be
unreasonable to say "this happens, and then that happens", because they
overlap so much.

I cannot stress this enough: neither precedence nor associativity has
*anything* to do with order of evaluation.

 

[Chris Dollin]

Chris Dollin said:


That doesn't matter for my point. For example, consider the expression:

a = b() * c() + d();

Here is one legal possibility for the generated assembly language code:

(fx:snip)

Here, the order of evaluation is d(), c(), b(), addition,
multiplication, whereas the precedence and associativity ordering would
suggest pretty much the opposite.

(fx:nitpick) False.

Given the expression `b() * c() + d()`, it is /exactly/ the precedence
that determines that the addition is done after the multiplication
(in the C abstract machine) -- because one operand of the addition
is the result of the multiplication.

It doesn't determine the order of those particular /operands/, of course;
that doesn't matter, because of "nitpick" and-jointly "*anything*".

(I share with you the idea that it's important for newbies to learn
that P&A doesn't determine OOE; but your extreme wording leaves your
lesson more subject to attack than a less extreme wording would. IMAO.)

--
"You're not supposed to /think/ about it, /The Beiderbeck Connection/
you're supposed to say NO!" Jill Swinburn

Hewlett-Packard Limited registered no:
registered office: Cain Road, Bracknell, Berks RG12 1HN 690597 England

 

[Richard Tobin]

I think Chris's point is that the relative precedence of + and *
forces the multiplication corresponding to the "*" operators to be
done before the addition corresponding to the "+" operator, and that
was true even in your example code.

[/QUOTE]

My point is that one of the operands of the addition was actually
evaluated *first*, despite the fact that precedence and associativity
rules would suggest it should actually be evaluated *last* (if they
were even remotely relevant).

That's not enough to show that precedence has *nothing* to do with
evaluation order. b(), c(), and d() can be evaluated in any order,
but the addition can't be evaluated before the multiplication. At
best you can say there might not be any order, but some orders are
not possible.

-- Richard

 

[Richard Heathfield]

Chris Dollin said:

(fx:nitpick) False.

Given the expression `b() * c() + d()`, it is /exactly/ the precedence
that determines that the addition is done after the multiplication
(in the C abstract machine) -- because one operand of the addition
is the result of the multiplication.

Neither the C abstract machine nor the Standard impose an order of
evaluation on the implementation. For example, 2 * 2 + 2 need not
result in any additions or multiplications being carried out. The
implementation could easily code this as (2 << 1) | 2 if it wanted. Or
even as 6, with no runtime evaluation happening at all!

It doesn't determine the order of those particular /operands/, of
course; that doesn't matter, because of "nitpick" and-jointly
"*anything*".

Right - it doesn't determine the order of those operands. Neither does
it determine the *order in which they are evaluated*.

(I share with you the idea that it's important for newbies to learn
that P&A doesn't determine OOE; but your extreme wording leaves your
lesson more subject to attack than a less extreme wording would.
IMAO.)

Oh, attack away, my dear chap - with any luck, you'll prove I'm wrong,
and then I'll have learned something.

 

[Chris Hills]

I cannot stress this enough: neither precedence nor associativity has
*anything* to do with order of evaluation.

You are correct.
Precedence is laid down in the standard
Associatively is also defined in the standard

The Order of Evaluation is NOT defined in the standard.
A line of C code can be evaluated left to right, right to left, middle
out or any order.

This has caused problems in the past. The most common single method is
Left to right. I am not sure if it has a majority though.

 

[Richard Heathfield]

Richard Tobin said:

My point is that one of the operands of the addition was actually
evaluated *first*, despite the fact that precedence and associativity
rules would suggest it should actually be evaluated *last* (if they
were even remotely relevant).

That's not enough to show that precedence has *nothing* to do with
evaluation order. b(), c(), and d() can be evaluated in any order,
but the addition can't be evaluated before the multiplication.[/QUOTE]

Okay, I agree that I've overstated my case (or at least can't prove I
haven't). My apologies to you and Chris.

At
best you can say there might not be any order,

That is the point I was trying to make.

but some orders are not possible.

I spent a good five minutes trying to construct a counter-example, and
failed. This may be due to my lack of imagination, of course, but the
more likely explanation is that you are correct.

 

[Eric Sosman]

My point is that one of the operands of the addition was actually
evaluated *first*, despite the fact that precedence and associativity
rules would suggest it should actually be evaluated *last* (if they
were even remotely relevant).

That's not enough to show that precedence has *nothing* to do with
evaluation order. b(), c(), and d() can be evaluated in any order,
but the addition can't be evaluated before the multiplication. At
best you can say there might not be any order, but some orders are
not possible.[/QUOTE]

Precede the above with

#define d() 0

.... or with any definition of d() that allows the optimizer
to discover that no side-effects are produced and the value
returned is zero. Now, with as straight a face as you can
muster, tell us all again that the addition must come after
the multiplication. Chances are, the addition will occur at
compile time and thus precede the multiplication by a *lot*.

Or instead, use

#define d() c()

.... and suppose a c() that the optimizer can see is "pure."
There's a decent chance that the compiler may generate the
same code as for

a = (b() + 1) * c();

Muster that straight face yet again, please.

 

[Chris Hills]

Richard Tobin said:


Okay, I agree that I've overstated my case (or at least can't prove I
haven't). My apologies to you and Chris.


That is the point I was trying to make.


I spent a good five minutes trying to construct a counter-example, and
failed. This may be due to my lack of imagination, of course, but the
more likely explanation is that you are correct.

This one is interesting but a bit of a red herring...
http://www.phaedsys.demon.co.uk/chris/sweng/swengtips3.htm
and
http://www.phaedsys.demon.co.uk/chris/sweng/swengtips3a.htm

It clearly shows that you have to take care.

 

[Chris Dollin]

Precede the above with

#define d() 0

... or with any definition of d() that allows the optimizer
to discover that no side-effects are produced and the value
returned is zero. Now, with as straight a face as you can
muster, tell us all again that the addition must come after
the multiplication. Chances are, the addition will occur at
compile time and thus precede the multiplication by a *lot*.

Sure. That's invisible to the abstract machine, though, as
are all the as-ifs.

(I'm interpreting Richard T's "can't" as "can't, in general",
which is what I'd mean if I'd written it in this discussion.)

 

[Richard Tobin]

That's not enough to show that precedence has *nothing* to do with
evaluation order. b(), c(), and d() can be evaluated in any order,
but the addition can't be evaluated before the multiplication. At
best you can say there might not be any order, but some orders are
not possible.

[/QUOTE]

Precede the above with

#define d() 0
[...]

Well obviously. But all that means is that there are some more cases
where the order isn't fixed, when the claim I was addressing is that
precedence *never* constrains evaluation order.

Richard Heathfield is entirely right to separate precedence and
associativity - which apply to the mapping from program syntax to
semantics - from evaluation order, which can be chosen in any way that
implements the semantics. He just went too far in denying that the
syntactic features have *any* consequences for the evaluation order.

-- Richard

 

[Kenneth Brody]

(fx:nitpick) False, since the P & A determines what's an operand of
what, and in general operands have to be evaluated before the operation
of which they are a part.

But that's only an indirect effect.

Yes, in order to evaluate "a + b", the values of "a" and "b" must be
determined before the addition takes place. But, there is nothing
that says anything about which gets evaluated first. The order of
evaluation is not specified.

Taking this further:

( a + b ) * ( c - d )

Again, "a" and "b" must be evaluated some time before the addition
is done, and "c" and "d" must be evaluated some time before the
subtraction is done, and both the addition and subtraction must be[*]
done some time before the multiplication is done. However, there
is nothing which specifies the order in which a, b, c, and d are
evaluated.

[*] In fact, as far as I understand it, nothing really requires
that "a+b" or "c-d" be evaluated before the multiplication is done,
as long as the result is the same. Although inefficient, I believe
it is possible for the compiler to treat the above as if it were
written as:

a*c + b*c - a*d - b*d;

as long as any side effects aren't duplicated.

--
+-------------------------+--------------------+-----------------------+
| Kenneth J. Brody | www.hvcomputer.com | #include |
| kenbrody/at\spamcop.net | www.fptech.com | <std_disclaimer.h> |
+-------------------------+--------------------+-----------------------+
Don't e-mail me at: <mailto:[email protected]>

 

[Richard Tobin]

The Order of Evaluation is NOT defined in the standard.
A line of C code can be evaluated left to right, right to left, middle
out or any order.

This has caused problems in the past. The most common single method is
Left to right. I am not sure if it has a majority though.

For most compilers, within an expression, optimisation will choose
factors such as making best use of registers, so that choice of
syntactic order for equivalent expressions will have little if any
effect.

-- Richard

 

[Chris Dollin]

Yes, in order to evaluate "a + b", the values of "a" and "b" must be
determined before the addition takes place. But, there is nothing
that says anything about which gets evaluated first. The order of
evaluation is not specified.

The order of evaluation /of the operands/ is not specified; I haven't
claimed otherwise.

In `a + b`, there's no room for P & A to make a difference.

In `a + b * c`, without P & A [1] there are two possible unambiguous
readings: `(a + b) * c`, and `a + (b * c)`. In both of these, the
order of the evaluation of the /operands/ `a`, `b`, `c` is unspecified.
However, in one the result of the addition is an operand of the
multiplication, and so /in general/ [2] the addition (not the
evaluation of its operands, the addition itself) has to be
done before the multiplication; and t'other way about for the
other one.

[1] And ignoring the detail that C proper doesn't use P&A at all,
and the grammar gives an unambiguous reading to `a + b * c`.

[2] ie one can construct /specific/ counter-examples, but without
that specicifity you can't assume otherwise.

--
"Our future looks secure, but it's all out of our hands." /Man and Machine/
- Magenta

Hewlett-Packard Limited Cain Road, Bracknell, registered no:
registered office: Berks RG12 1HN 690597 England

 

[Johan Bengtsson]

For most compilers, within an expression, optimisation will choose
factors such as making best use of registers, so that choice of
syntactic order for equivalent expressions will have little if any
effect.

I have seen cases where the order of evaluation changed between debug
(fast - non optimizing compiler) and release (optimizing compiler). This
was at the time when I was not entirely aware that it could change
myself and therefore introduced an error - of course the error only
existed in the hard to debug release version of the program.

 

[Peter Nilsson]

(e-mail address removed) said:

No. You can think of precedence and associativity as sorting
out which expressions get to be the operands for any given
operator. Precedence and associativity rules mean that the
above expression has the same meaning as:

x += ((i + j) + (k++));

The order of evaluation of the expressions is unspecified.

The order of sub-expressions is unspecified, except for ||, &&
and ?: operators. As you point out yourself, there is an implied
ordering of the + operations from the associativity.

I cannot stress this enough: neither precedence nor
associativity has *anything* to do with order of
evaluation.

The expression i + j + k++ is evaluated on the virtual machine
as (i + j) + k++, not as i + (j + k++). There is potentially
a real difference on some machines.

Given...

#define CONV (-'0')

....and assuming *p is a digit, consider...

n = *p + CONV + n * 10;

This is a correct form only because there is an implied
ordering of evaluation. Without the implied ordering, I
would have to use parentheses, or break the statement
into multiple statements.

[Of course in practice I would write n = n * 10 + (*p - '0'),
but that doesn't alter the above comments.]