Precedence & Associativity

Question

Hello,

I thought I understood this but now I'm beginning to wonder.  Given the following expression:

a + b + c

My understanding is that the order of evaluation of operands and the order of operations is implementation dependent, as long as the resulting value and data type is "as if" the operations (but not necessarily the operand evaluations) occurred left-to-right (since addition is left-to-right associative).  If I am correct so far, then here is where I am now uncertain.  I had previously assumed that this would result in the answer being computed by first adding a + b, then adding the result to c.  That is, it would be computed as if it honored the parentheses in

(a + b) + c

However, I just saw an example in a C text book that said the correct interpretation would be that it would add a to the sum of b and c as if it honored the parentheses in

a + (b + c)

So now I'm not sure what the term "associativity" really means in a case like this.

Thanks,

Ray

Answer 1

On 8/15/2012 8:04 PM, Benevolent Deity wrote:

I thought I understood this but now I'm beginning to wonder.  Given the following expression:

a + b + c

My understanding is that the order of evaluation of operands and the order of operations is implementation dependent, as long as the resulting value and data type is "as if" the operations (but not necessarily the operand evaluations) occurred left-to-right (since addition is left-to-right associative).  If I am correct so far, then here is where I am now uncertain.  I had previously assumed that this would result in the answer being computed by first adding a + b, then adding the result to c.  That is, it would be computed as if it honored the parentheses in

(a + b) + c

However, I just saw an example in a C text book that said the correct interpretation would be that it would add a to the sum of b and c as if it honored the parentheses in

a + (b + c)

So now I'm not sure what the term "associativity" really means in a case like this.

A conforming program running on a two's-complement machine won't be able to tell the difference. Thus, the compiler is free to choose either.

---

Igor Tandetnik

Answer 2

How about a 1's complement or signed magnitude machine?

Answer 3

On 8/15/2012 8:16 PM, Benevolent Deity wrote:

How about a 1's complement or signed magnitude machine?

The compiler must group left-to-right (that is, (a+b)+c) ) on an architecture where reordering would be detectable. Now, I have never worked with any non-two's-complement machine, and can't off the top of my head figure out whether the reordering would in fact be detectable on such (how did they treat integer overflow?)
 From the C++11 standard:

1.9p9 [ Note: Operators can be regrouped according to the usual mathematical rules only where the operators really are associative or commutative. For example, in the following fragment

int a, b;
 ... 
a = a + 32760 + b + 5;

the expression statement behaves exactly the same as

a = (((a + 32760) + b) + 5);

due to the associativity and precedence of these operators. Thus, the result of the sum (a + 32760) is next added to b, and that result is then added to 5 which results in the value assigned to a. On a machine in which overflows produce an exception and in which the range of values representable by an int is [-32768,+32767], the implementation cannot rewrite this expression as

a = ((a + b) + 32765);

since if the values for a and b were, respectively, -32754 and -15, the sum a + b would produce an exception while the original expression would not; nor can the expression be rewritten either as

a = ((a + 32765) + b);

or

a = (a + (b + 32765));

since the values for a and b might have been, respectively, 4 and -8 or -17 and 12. However on a machine in which overflows do not produce an exception and in which the results of overflows are reversible, the above expression statement can be rewritten by the implementation in any of the above ways because the same
result will occur. —end note ]

---

Igor Tandetnik

Answer 4

Thanks Igor,

You have answered my question and I obviously should have consulted the standard myself before I posted this.  So it appears that my trusty textbook was not so trusty in this case!

Ray

Answer 5

Hello,

I thought I understood this but now I'm beginning to wonder.  Given the following expression:

a + b + c

My understanding is that the order of evaluation of operands and the order of operations is implementation dependent, as long as the resulting value and data type is "as if" the operations (but not necessarily the operand evaluations) occurred left-to-right (since addition is left-to-right associative).  If I am correct so far, then here is where I am now uncertain.  I had previously assumed that this would result in the answer being computed by first adding a + b, then adding the result to c.  That is, it would be computed as if it honored the parentheses in

(a + b) + c

snip

Associativity and precedence are different than order of evaluation.  As Igor pointed out, the expression must be processed as it were (a+b)+c but that does not mean that a+b is evaluated before c.  The order of evaluation is unspecified and the compiler is free to choose either (and on the next compile choose the other).

Answer 6

On 8/15/2012 8:04 PM, Benevolent Deity wrote:

I thought I understood this but now I'm beginning to wonder.  Given the following expression:

a + b + c

My understanding is that the order of evaluation of operands and the order of operations is implementation dependent, as long as the resulting value and data type is "as if" the operations (but not necessarily the operand evaluations) occurred left-to-right (since addition is left-to-right associative).  If I am correct so far, then here is where I am now uncertain.  I had previously assumed that this would result in the answer being computed by first adding a + b, then adding the result to c.  That is, it would be computed as if it honored the parentheses in

(a + b) + c

However, I just saw an example in a C text book that said the correct interpretation would be that it would add a to the sum of b and c as if it honored the parentheses in

a + (b + c)

So now I'm not sure what the term "associativity" really means in a case like this.

A conforming program running on a two's-complement machine won't be able to tell the difference. Thus, the compiler is free to choose either.

---

Igor Tandetnik

At the very least, if we are talking about signed int, it is entirely possible for (a+b) to result in overflow while a+(b+c) does not.  Consider when a and b are both set to INT_MAX and c is set to INT_MIN.

Answer 7

Barry-Schwarz wrote:

Igor Tandetnik <[e-mail]> wrote:

A conforming program running on a two's-complement machine won't be  able to tell the difference. Thus, the compiler is free to
choose either.

At the very least, if we are talking about signed int, it is entirely  possible for (a+b) to result in overflow while a+(b+c) does
not.

So? The overflow would just wrap around, and adding c would wrap it  right back.

Consider when a and b are both set to INT_MAX and c is set to INT_MIN.

a + b == -2; -2 + c == INT_MAX - 1
b + c == -1; a + (-1) == INT_MAX - 1

What again seems to be the problem? How may a conforming program detect  which order of evaluation has been chosen by the compiler?

---

Igor Tandetnik

Answer 8

Barry-Schwarz wrote:

Associativity and precedence are different than order of evaluation.  As Igor pointed out, the expression must be processed as it
were (a+b)+c but that does not mean that a+b is evaluated before c.

I don't think that's what the OP asked. As far as I can tell, the  question was whether the compiler must add up a and b and then add c to  the result, or it could also legally add up b and c and then add a to  the result.

---

Igor Tandetnik

Answer 9

Overflow wraps around for unsigned int.  Not for signed!  My comment served only as a counter example to your assertion that it didn't matter if the expression were evaluated as (a+b)+c or a+(b+c)

I have no idea how a program could determine order of evalution in general nor why it would want to.  Whether overflow occurs or not is not dependent on the order of evaluation but on the associativity mandated by the standard.  a+b+c must be evaluated as (a+b)+c.  What is unknown (to all but the compiler writer) is whether a+b is evaluated before of after c.

Answer 10

On 8/16/2012 2:30 PM, Barry-Schwarz wrote:

Overflow wraps around for unsigned int.  Not for signed!

It does too for signed int on all modern architectures. Note that we aren't talking about what a conforming program is legally allowed to do, but what an optimizing compiler can get away with. The compiler can use every trick in the book that's supported by the platform it's generating code for. As long as a conforming program cannot observe a change in behavior, it's fair game.

My comment served only as a counter example to your assertion that it didn't matter if the expression were evaluated as (a+b)+c or a+(b+c)

I stand by my assertion. On a typical modern two's-complement machine, it indeed doesn't matter. Try it, see for yourself.

I have no idea how a program could determine order of evalution in general nor why it would want to.  Whether overflow occurs or not is not dependent on the order of evaluation but on the associativity mandated by the standard.  a+b+c must be evaluated as (a+b)+c.

Not quite. More precisely, the result of the expression must be as if it were evaluated as (a+b)+c. As long as the observable behavior of the program doesn't change, the compiler is free to rewrite the expression as it sees fit.
 From the C++ standard:

1.9p1 The semantic descriptions in this International Standard define a parameterized nondeterministic abstract machine. This International Standard places no requirement on the structure of conforming implementations. In particular, they need not copy or emulate the structure of the abstract machine. Rather, conforming implementations are required to emulate (only) the observable behavior of the abstract machine as explained below.5

Footnote 5: This provision is sometimes called the “as-if” rule, because an implementation is free to disregard any requirement of this International Standard as long as the result is as if the requirement had been obeyed, as far as can be determined from the observable behavior of the program. For instance, an actual implementation need not evaluate part of an expression if it can deduce that its value is not used and that no side effects affecting the observable behavior of the program are produced.

What is unknown (to all but the compiler writer) is whether a+b is evaluated before of after c.

Or whether a + c is evaluated before b, or whether b + c is evaluated before a.

---

Igor Tandetnik