evaluation order (was Obfuscated SWAP: not portable!)
Chris Torek
chris at mimsy.UUCP
Sat Sep 9 13:58:24 AEST 1989
>>In article <149 at cpsolv.UUCP> rhg at cpsolv.UUCP (Richard H. Gumpertz) writes:
>>>The exchange of x and y that has been under discussion:
>>> x ^= y ^= x ^= y
>>>is non-portable because it depends on right-to-left evaluation which is NOT
>>>specified in the C standard.
This is correct.
>In article <1400 at levels.sait.edu.au> CCDN at levels.sait.edu.au (DAVID NEWALL) writes:
>>I think it is specified. (Perhaps it depends on whose standard you follow?)
No, it is not specified.
>>K&R I, page 19:
>> ... an assignment has a value and assignments associate right to left."
In article <1007 at m3.mfci.UUCP> karzes at mfci.UUCP (Tom Karzes) writes:
>No, it is not specified. The K&R example is merely pointing out that the
>assignment is parsed as:
>
> nl = (nw = (nc = 0));
Tom is correct.
We have two separate concepts here. The one to which K&R p. 19 refers
is *grouping*; grouping is affected by *precedence* and *associativity*.
(Parentheses are a syntactic construct that---at least in Classic C---serve
only to give specific precedence: the highest precedence that exists.)
The concept we have to worry about in the `obfuscated swap' above is
*evaluation order*.
It is easy to see that evaluation order and grouping differ. Consider
the expression
a + b
This has no grouping (there is only one operator, hence nothing to group
it with), but does have order of evaluation (do we inspect `b' first, or
`a'?). Precedence and associativity come into play only when there are
multiple operators:
a + b * c + d
If an expression has two or more of a single operator `in a row', as in
a + b + c
we apply the associativity rule (here `left associative') to decide
whether the result should be `add a to result of adding b and c' or
`add c to result of adding a and b'. When two different operators
mingle, their precedence determines the result. `*' is `higher' than
`+', so a+b*c+d means `add d to sum of result of b*c and a'.
In some languages, grouping and/or parentheses determine evaluation
order as well; but in classic C, they do neither. The proposed
standard makes parentheses force a limited amount of evaluation order
under certain circumstances, although deciding exactly when you can
get away with what can be difficult.
In any case,
a + b
can be done as either `fetch b, fetch a, add' or `fetch a, fetch b, add'.
Normally, the result is identical, so the evaluation order does not matter.
Similar reasoning applies to
x ^= y ^= x ^= y;
We have lots of choices in implementing this, but this time, some of them
do matter:
>When evaluating a ^= b, the compiler may generate any of the following:
>
> 1. evaluate a, evaluate b, xor, assign
> 2. evaluate b, evaluate a, xor, assign
> 3. some hybrid of 1 and 2
>
>If it chooses the first sequence for the outer assignment in the original
>^= example, the example will fail.
The draft standard includes the concept of `sequence points', which helps
to answer questions about evaluation order. Sequence points are, in
effect, `places where everything gets written down'. There are no
sequence points in x^=y^=x^=y. We can add one:
x ^= y, x ^= y ^= x;
and then enumerate all the possible evaluation orders to decide whether
that sequence point is sufficient to guarantee the expected result.
--
In-Real-Life: Chris Torek, Univ of MD Comp Sci Dept (+1 301 454 7163)
Domain: chris at mimsy.umd.edu Path: uunet!mimsy!chris
More information about the Comp.lang.c
mailing list