Path: utzoo!news-server.csri.toronto.edu!cs.utexas.edu!sun-barr!lll-winken!uwm.edu!bionet!agate!dog.ee.lbl.gov!elf.ee.lbl.gov!torek
From: torek@elf.ee.lbl.gov (Chris Torek)
Newsgroups: comp.lang.c
Subject: Re: Increment Operators vs. Precedence
Message-ID: <10648@dog.ee.lbl.gov>
Date: 6 Mar 91 01:18:07 GMT
References: <THOMSON.91Mar5173421@zazen.macc.wisc.edu>
Reply-To: torek@elf.ee.lbl.gov (Chris Torek)
Organization: Lawrence Berkeley Laboratory, Berkeley
Lines: 136
X-Local-Date: Tue, 5 Mar 91 17:18:08 PST

In article <THOMSON.91Mar5173421@zazen.macc.wisc.edu>
thomson@zazen.macc.wisc.edu (Don Thomson) writes:
>The example on the board is y = x++ ...  So the dilemma is how to explain
>that precedence is not the issue here, that the order of operations is
>tied to the definition of prefix versus postfix increment operators.

Precedence is purely syntactic; order of operations is semantic.

All `precedence' does is assign some particular grouping to a set of
symbols that otherwise have none.  For instance, given

	x = a + b * c++;

there is no grouping, and precedence (and associativity) is a simple way
of describing how the expression is parsed.

Exclusive of precedence and associativity, all of the following are possible
parses for the sentence above:

	((x = a) + (b * c))++

	(x = (a + b)) * (c++)

	(((x = a) + b) * c)++

	x = (a + (b * (c++)))

The last one is the one we actually want, and we can obtain it by using
precedence and associativity rules:

	post-increment > multiply > add > assign

In

	a = b = 0;

a right-associative rule for assignment is necessary to force

	a = (b = 0)

rather than

	(a = b) = 0

, and in

	x = a / b * c / d;

a left-associative rule is necessary to force

	x = (((a / b) * c) / d)

rather than

	x = ((a / (b * c)) / d)

or some such.

All of these simply give us some particular parse tree for some sentence.
It is up to us to assign semantics to each parse.  The semantics for `c++'
are `get the current value of c, and eventually---by the time you reach
the next sequence point---store that value, plus 1, in c'.

So in

	y = x++;

the parse tree looks like this:


		=

	     /     \
	    /       \
	   /         \

	  y	 postfix-++

		     |

		     x

or in list notation, (= y (postfix-++ x)), but the order of operations is:

	A. fetch current value of x

	B. [store in y] and [add 1 to x]

In particular, in an expression like:

	x = ++x;

we have a very specific parse tree, namely (= x (pre++ x)), but we may have
a nonspecific result, depending on implementation details:

	A. fetch current value of x
	B. [add 1 and store in x] and [add 1 to x]

If preincrement is implemented internally as:

	- put an `add 1 to x' on the list of things to do
	- fetch value of x and add 1
	- store in x
	- do the list of things to do

this expression might add 2 to x.  If, on the other hand, it is
implemented as:

	- fetch current value of x, add 1, store result in x, use result
	- store result in x

the expression will add 1 to x.  Since a compiler could even
(conceivably) `interleave' operations, it is possible that this might
act like `x += 0x101'.%  This is rather unlikely, but explains why no
more than one side effect should be applied to any individual object
between sequence points.
----
% Consider a machine in which `add 1 to x' is implemented as `fetch low byte
 of x, add 1, store; if result is 0, fetch high byte of x, add 1, store'
 and where there are two `processing units' and some peculiar delays:

		unit 1:				unit 2:
		------				------
	fetch low byte of x: (255)	(busy with something else)
	add 1: (0)			fetch low byte of x: (255)
	store: (low byte of x now 0)	add 1: (0)
	(delay)				store: (low byte of x still 0)
	(delay)				fetch high byte of x: (17)
	(delay)				add 1: (18)
	(delay)				store: (x is now 1 larger)
	fetch high byte of x: (18)	(do something else)
	add 1: (19)
	store: (x is now 0x101 larger)
-- 
In-Real-Life: Chris Torek, Lawrence Berkeley Lab EE div (+1 415 486 5427)
Berkeley, CA		Domain:	torek@ee.lbl.gov