evaluation order (was Obfuscated SWAP: not portable!)

[Chris Torek]

>>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