🚀 go-pugleaf

In article <912351722.217465@optional.cts.com> Will Rose wrote:
>>>The operations * and / are both left-associative, so 5 * 3 / 2 comes
>>>to 7, and 5 / 2 * 3 comes to 6.

In article <912357376.6545.0.nnrp-03.9e9809e7@news.demon.co.uk>
(and I see why people omit these references!) Chris Marriott
(chris@NOSPAM.skymap.com) asks:
>>If you don't use parentheses to force the order of evaluation, does the C
>>language guarentee left-to-right evaluation? I don't have a copy of the
>>language reference at hand to check.

In article <912362255.713357@optional.cts.com> Will Rose <cwr@cts.com>
answers:
>You rapidly step off into deep water here, and I don't trust myself to
>get the technical terms right.  [... See the] C faq, section 3.8 ...
>
>Probably the best simple summary is in K&R, but for the full story
>you probably need the syntax rules of the standard, which express
>the precedence and associativity rules mentioned above.  ISTR this
>was discussed about a year ago, and either Lawrence Kirby or Chris
>Torek gave a much better explanation that I can; try Dejanews.

These are not from last year, but rather from several years ago.
The first two deal directly with precedence and order of evaluation.
The third (which is actually dated between the other two) I included
as an example of how "it works on my compiler" can surprise people.

		---------------------------------

From: torek@elf.bsdi.com (Chris Torek)
Subject: precedence vs order of evaluation (was Quick C test)
Date: 18 Feb 1995 07:34:22 -0800

[quotes omitted]

Both of these articles make the same basic mistake: they equate
*parse* order with *evaluation* order.

While there is some connection---for instance, it is impossible to
evaluate an expression without first parsing it---these two steps
are essentially independent.  `Operator precedence' ONLY affects
parsing.  Like associativity, the concept of precedence is used
only to choose one of several possible parses.  Given:

	result = a - b + c * d - e;

we must choose some grouping for the various operations.  We could
use strict left-to-right grouping and treat this as:

	((((a - b) + c) * d) - e)

but this would upset people who expect the multiply to occur first.
The same problem would occur if we used strict right-to-left grouping.
In modern languages, one easy way to get the desired grouping is to
use an operator-precedence grammar to parse the expression.  In such a
grammar, each operator is assigned a precedence---hence the name---and
operators with higher precedence group more tightly than those with
lower precedence.

The C Standard, however, uses a different technique.  It has a
fully factored grammar, in which the parser never has to choose
between two different groupings, because only one grouping is
accepted by the grammar.  Thus, strictly speaking, C does not *have*
precedence.  Of course, individual compilers are free to implement
parsing via precedence grammars, as long as the result is correct.

Now, once more, remember that all of this is simply in order to obtain
the correct *parse* while compiling.  We want:

	i = f() + g();

to mean:

	i = (f() + g());

and not:

	(i = f()) + g();

Once we have done that, however, there is still the question of
*evaluation* order at run-time.

Except at sequence points, the C Standard leaves the order of
evaluation unspecified.

A compiler can call f() first, then g(), or it can call g() first,
then f().  Note that when we have:

	i = (f() + g());

in the source, there is hardly any question of `operator precedence'
(there are no ambiguous sentences, even in an operator-precedence parser), 
but we still have questions of order of evaluation, since f() and g()
might have side effects (such as `printf("in function f()\n")').

A separate rule in the Standard requires that no single object have
more than one side effect applied to it between any two sequence points.
Since both `assignment' and `increment' are side effects, this has the
effect of rendering `i = i++' undefined.  This is independent of the
fact that the order of *evaluation* of the assignment and the increment
is unspecified; in turn, the unspecified evaluation order is independent
of the fact that the grouping during parsing is well-defined.

Thus, whenever you go to analyze some C code, you must first parse
it to see what it says.  During this step, you can refer to precedence
tables to see whether to multiply before adding, or follow the `->'
operator before a `++'.  Once you have a valid parse, you must then
decide, separately, whether the semantics are well-defined; this
includes examining the types and values in the expression, whether
there are side effects, when they might take place, and so on.  If
all of that is valid, only then can you say what the statement must
do.

Remember:

	>>> Precedence and associativity are only for parsing. <<<

Do not equate `higher precedence' with `done first at runtime.'


	>>> Evaluation order is effectively unspecified. <<<

Make sure your code does not depend on the actual order of evaluation.


	>>> Side effects `finish' at sequence points. <<<

Loosely speaking, this means:  `At a semicolon, or after the left
half of an && or || operator, or after the control expression of
a loop, or after the ? part of a ?: expression, variables take on
their assigned values.'


	>>> Multiple side effects between two sequence points can
	    result in undefined behavior. <<<

Be careful not to use several side effects on a single variable.
Operations such as `i = i++' are right out.  Operations such as
`++*p++' are technically OK, but are confusing and are generally
best avoided.  Given a choice between `clever' and `clear', go for
`clear'.

		---------------------------------

From: Chris Torek <torek@elf.bsdi.com>
Subject: Re: Explaining precedence vs. sequence
Date: 27 Mar 1996 06:34:41 -0600

In article <4ja3pu$p8r@solutions.solon.com> bcalbridge@dcccd.edu writes:
>... I'm not positive on this, but I suspect that a logical operator
>imposes a sequence point that forces the evaluation of the left side.
>(Please confirm if this is true.)  

This is correct.

To refer back to the subject line, probably the best way to explain
the difference between `precedence' and `order of evaluation or
execution' is to point out that, technically, C has *no* precedence.
The grammar specified in the Standard is fully factored, so that
given any expression, there is only one way to parse it.

Typically, humans (and operator-precedence grammars, which mimic
human parsing) use `precedence' to distinguish between two or more
possible ways to group a set of items.  For instance:

	a + b * c - d / e

There are lots of possible ways to group this, and the easy way
for most *people* to work out which grouping to use is for them to
remember grade-school lessons that say `multiplication and division
first, then addition and subtraction'.

The Standard, on the other hand, simply says (in part) that an
expression can include the following:

	multiplicative-expression:
		cast-expression
		multiplicative-expression * cast-expression
		multiplicative-expression / cast-expression
		multiplicative-expression % cast-expression

	additive-expression:
		multiplicative-expression
		additive-expression + multiplicative-expression
		additive-expression - multiplicative-expression

In this case, `a', `b', `c', `d', and `e' can all be handled via
`cast-expression', but to put together `b * c' and `d / e' requires
using the multiplicative-expression derivations, and to put together
`a + ...' and `... - e' requires using the additive-expression
derivations.  The resulting parse groups `b * c' and `d / e' together
before allowing `a + ...' or `... - e'.  Moreover, since an additive-
expression can only have a multiplicative-expression on the right,
the addition must be grouped before the subtraction -- the
multiplicative-expression simply cannot consist of two things being
subtracted.

The resulting grouping matches what you would get for:

	(a + (b * c)) - (d / e)

but the ideas of `precedence' and `associativity' have not been
invoked.

This is likely to leave some lingering confusion; at this point,
one can bring up another example:

	extern int f(), g();

	f() + g();

Few, if any, students will argue that there is any precedence
involved here: we simply call f() and g() and add the results.
If, however, f() and g() contain printf() calls or similar, it
becomes obvious that evaluation order can affect the output.  Thus,
here we have an example of an expression with ordering, but no
precedence.

(The order is `unspecified', meaning that either f() runs first, then
g() runs, or g() runs first, then f(), but we cannot say which.)

>I wrote a short program to prove this and the instructor demoed it in
>class.  Unfortunately, I don't believe the instructor is familiar with
>sequence points ...

Further details on sequence points (and on the above) can be found
in the comp.lang.c FAQ.

		---------------------------------

From: torek@elf.bsdi.com (Chris Torek)
Subject: Re: Is this behaviour defined ?
Date: 20 Feb 1995 09:54:04 -0800

In article <PGOLDA.199.0@eleceng.uct.ac.za> Pete Golda
<PGOLDA@eleceng.uct.ac.za> notes:
>... [undefined operations] don't come out [as the original programmer
>had intended] on Unix, as explained by many of you. Borland seems to
>be more "defined?" when it comes to these so it worked.

This probably happens for one of two reasons:

 a) The original code was written under Borland C.

In this case, any undefined behavior that happens to work out some
particular way under Borland C will, of course, work out that way
under Borland C, making the program act the same when it is compiled
with Borland C.

 b) The dumber the compiler, the more likely it is to obey stupid/simple
    code generation rules.

Thus, if `a++ + a++' or `i = i++' does something `odd' on system A and
`always works the way John Doe expects' on system B, chances are that
system A has a compiler that produces faster/better object code.

The reasons behind this are pretty simple, actually.  A dumb compiler
will take each individual subexpression one at a time and generate code
for it, without looking to see what is happening nearby.  Thus we
might see:

	i++

and generate assembly code that looks something like this:

	load _i, r0		# r0 holds value from expr.
	inc r0			# have to increment i
	store r0, _i		# and store it back,
	dec r0			# then restore previous value.

The next thing we might notice is that this is the entire statement
(that is, the source line was `i++;') and say `ok, now we are done,
move on to the next statement'---making the final `dec r0' useless,
but doing it anyway simply because we did not notice that the
expression's value was not needed.

If we add a small bit of cleverness, we might have a flag in the
compiler that says `this expression's value is to be discarded', so
that we could avoid that last instruction.  Then if we had:

	j = i++ + i++;

we might generate:

	load _i, r0		# do first i++
	inc r0
	store r0, _i
	dec r0

	copy r0, r1		# must save value for addition

	load _i, r0		# do second i++
	inc r0
	store r0, _i
	dec r0

	add r1, r0		# do the add

	store r0, _j		# j = result

This is still pretty stupid code-wise.  A really clever compiler
will notice that there is no need to pre-increment i, and that the
same variable is loaded twice, and might do *this*:

	load _i, r0		# load i
	copy r0, r1		# for the add
	add r1, r1		# double it
	store r1, _j		# set j

	# now execute deferred increment or decrement operations
	# on values stored in holding registers, per the flags per
	# register.
	inc r0			# r0 is marked as `increment and store in i'
	store r0, _i

*This* code is probably pretty close to optimal.  Of course, it
does not `do what John Doe intended'---but since the two modifications
without an intervening sequence point results in undefined behavior,
that is OK.  This particular scheme will work fine for *defined* code,
however, and as shown above, it can cut the number of instructions in
half.
-- 
In-Real-Life: Chris Torek, Berkeley Software Design Inc
El Cerrito, CA	Domain:	torek@bsdi.com	+1 510 234 3167
http://claw.bsdi.com/torek/  (not always up)