From: torek@horse.ee.lbl.gov (Chris Torek)
Newsgroups: comp.lang.c
Subject: Re: Question to test general C knowledge
Date: 18 Dec 92 19:54:16 GMT
Organization: Lawrence Berkeley Laboratory, Berkeley CA
NNTP-Posting-Host: 128.3.112.15

In article <fjeske.0knf@amiganet.chi.il.us>
fjeske@amiganet.chi.il.us (Felix Jeske) writes:
>        i=++i;
>should be broken up like when taking operator precedence into account ...

As Wayne Throop and others have pointed out, precedence and order of
evaluation have little to do with each other.  Moreover, ANSI C does
not even *have* precedence.  (It achieves the same goal by careful
use of an explicit grammar.)

As an illustration, consider the sub-expression:

	/* assume x, y, z are some variables */

	x + y + z

This involves no precedence at all, but it does have an (unspecified)
evaluation order.[1]  If this is not obvious, replace it with:

	f() + g() + h()

In this case the parentheses after f, g, and h bind more tightly than
the additions, and it happens to be true that f, g, and h must all be
called before the final sum can be computed---but a compiler is free to
use, say:

	call f
	temp1 <- result
	call g
	temp2 <- temp1 + result
	call h
	temp1 <- temp2 + result
	/* result is now in temp1 */

Here the sum f() + g() has been computed *before* h() is called.

Now, as it happens, I have been unable to think of a way to write a
compiler such that `i = ++i' would act as if it were `i += 2'---a truly
dumb compiler will simply emit all preincrements before handling the
rest of the expression, and a truly smart one will notice that i
appears twice (and, one hopes, emit a warning) and only generate one
increment.  But I have not considered VLIW machines---I am not
familiar enough with compilation techniques for these---in which
it would be possible to run two independent additions simultaneously.[2]

The only proposal I have seen that justifies `i = ++i' as being defined
in ANSI C is (I think) Chris Volpe's, which hinges on the definition of
`modify'.

Again, grammar-level concepts such as `precedence' and `associativity'
are useful in determining a particular parse (a `tree' of operations,
if you will); but once you have that, semantics take over, and semantics
are a separate issue.  The problem with `i = ++i' lies in semantics,
and the grammars involved in getting there are not important.

-----
[1] Note that it has associativity, not precedence.  `Precedence' is a
    thing humans and some computer grammars use to decide how to parse
    ambiguous sentences (sentences with more than one valid meaning).
    We take `a = b + c * d' to mean `a = b + (c * d)', and we can
    instruct a computer to do so as well, but there are other ways to
    accomplish this.  `Associativity' is a related concept in which
    no operation is `more powerful' than another, but we decide to
    evaluate right-to-left or left-to-right, or to reject the sentence
    entirely.  Subtraction is considered left-associative because we
    take `a = b - c - d' to mean `a = (b - c) - d' rather than
    `a = b - (c - d)', but again, we can specify associativity to a
    computer parser in several ways.  The ANSI C standard uses a
    long-winded method; most people, and some grammars, prefer the
    operator-precedence style as being easier to remember and carry
    out.

[2] To stop old Al E. from spinning in his grave, `simultaneous' really
    means `the times overlap':  A VLIW, or Very Long Instruction Word,
    machine typically has several separate integer and floating point
    ALUs, and a single instruction can start all of them on different
    tasks.  A dumb VLIW compiler, if one existed, might hand the `++i'
    job to one ALU and the `i = i + 1' job---derived from the rule
    that `x = ++y' sets x to `old-y + 1'---to a second.  In this case
    the two results would come out at about the same time and would
    collide in trying to `land in' i.  If bits were eggs, one would
    wind up with a mess of yolk on the floor.

    Of course, bits are not eggs---but if you program as if they were,
    you will not break any bits, whatever they may be, and thus you
    will never have to clean up the mess.
-- 
In-Real-Life: Chris Torek, Lawrence Berkeley Lab CSE/EE (+1 510 486 5427)
Berkeley, CA		Domain:	torek@ee.lbl.gov
Newsgroups: comp.lang.c