A seemingly buggy paragraph in the C99 rationale

[arnab chatterjee]

Hello all,

I think there might be a small inconsistency in section 6.5 (Expressions) of the C99 rationale <www.open-std.org/jtc1/sc22/wg14/www/C99RationaleV5.10.pdf>. Please correct me if my understanding is based on some misinterpretation of the following paragraph:
"Loss of the regrouping rule does not in fact prohibit much regrouping of integer expressions. The bitwise logical operators can be arbitrarily regrouped since any regrouping gives the same result as if the expression had not been regrouped. This is also true of integer addition and multiplication in implementations with two’s-complement arithmetic and silent wraparound on overflow. Indeed, in any implementation, regroupings which do not introduce overflows behave as if no regrouping had occurred. (Results may also differ in such an implementation if the expression as written results in overflows; but in such a case the behavior is undefined, so any regrouping couldn’t be any worse.)"

Consider the following integer expression:
printf("left ") | printf("mid ") | printf("right ")

Since associativity of bitwise operators is left-to-right, the correct grouping is done as:
(printf("left ") | printf("mid ")) | printf("right ")

As the operand evaluation sequence is implementation-defined, the above expression may yield one of these four different outcomes (depending on the compiler):
left mid right
mid left right
right left mid
right mid left

The other possible regrouping (which is not done due to associativity rule is):
printf("left ") | (printf("mid ") | printf("right "))

But now the four different outcomes are:
left mid right
left right mid
mid right left
right mid left

The two outcome sets are not identical; the middle two outcomes of each set does not appear in the other. So for certain expression that contain non-trivial sub-expressions, regrouping may change the program behavior (regardless of any overflow issues).

I believe this distinction was not the original intent of the quoted paragraph.

Regards,
cHaR.

[Kaz Kylheku]

On 2022-09-15, arnab chatterjee <arnabchatte...@gmail.com> wrote:
[ reformatted for punched cards and readability ]

> Hello all,
>
> I think there might be a small inconsistency in section 6.5
> (Expressions) of the C99 rationale
> <www.open-std.org/jtc1/sc22/wg14/www/C99RationaleV5.10.pdf>. Please
> correct me if my understanding is based on some misinterpretation of
> the following paragraph:
>
> "Loss of the regrouping rule does not in fact prohibit much regrouping
> of integer expressions. The bitwise logical operators can be
> arbitrarily regrouped since any regrouping gives the same result as if
> the expression had not been regrouped. This is also true of integer
> addition and multiplication in implementations with two’s-complement
> arithmetic and silent wraparound on overflow. Indeed, in any
> implementation, regroupings which do not introduce overflows behave as
> if no regrouping had occurred. (Results may also differ in such an
> implementation if the expression as written results in overflows; but
> in such a case the behavior is undefined, so any regrouping couldn’t
> be any worse.)"
>
> Consider the following integer expression:
> printf("left ") | printf("mid ") | printf("right ")
>
> Since associativity of bitwise operators is left-to-right, the correct grouping is done as:
> (printf("left ") | printf("mid ")) | printf("right ")
>
> As the operand evaluation sequence is implementation-defined, the above expression may yield one of these four different outcomes (depending on the compiler):

It is unspecified behavior, not implementation-defined.

Because functions are executed sequentially by a single thread, there
are six possible orders for the calls to printf.

An implementation must choose one of these, but is not required to
document what choice is made, how that choice is made.

It doesn't have to choose it the same way in every such expression.

> left mid right
> mid left right
> right left mid
> right mid left

You are incorrect; there are six possible outcomes.

The thing you have to understand that the associative grouping
has no bearing on the order in which the operands are prepared.

Given the expression x = A() | B() | C(), how the abstract machine can
evaluate it is this:

1. Fetch the values of A(), B() and C() into temporary registers:

t1 = A() }
t2 = B() > this can happen in 3! = 6 different orders!
t3 = C() }

2. Evaluate the OR expression:

t4 = t1 | t2 | t3

3. Store the result:

x <= t4

In the expression ( A() | B() ) | C() there is no constraint that
A() and B() are evaluated together, separately from C().

The possible orders are not just AB C, BA C, C AB and C BA.

BA are not bundled together.

The evaluation order B(), C(), A() is perfectly possible,
as is A(), C(), B(). Those two possibilities give us six.

[Richard Damon]

The 3 printfs can be evaluated in ANY order, as the order of evaluating
them has NOTHING to do with "regrouping" the or operations.

(f1() | f2()) | f3() just requires that the results of f1 and f2 are
or'ed before the results of f3 is or'ed on but doesn't say anything
about when we determine what the result of f3 actually is. That just has
to happen before we or it with the results of f1() | f2().

Yes, we need to call f1 and f2 before we can or their results, and we
need to call f3 before we can or that into that result, but there is no
rule that says be can't call f3 in ANY sequence with respect to f1 and
f2, they are totally unordered.

[arnab chatterjee]

Thanks to Kaz Kylheku for the reformatting and detailed reply (particularly the correction on unspecified behavior). I had bungled the concept of sequence point (which is not introduced by bitwise-OR); indeed the text from the rationale makes sense when we consider the six possible outcomes, which is independent of the grouping (the abstract machine evaluation clarifies this aspect).

Also, thanks to Richard Damon for pointing out the erroneous conflation of operand evaluation and performing the operation itself.