operators similar to functions?

[Eric Sosman]

Cited elsewhere, Harbison &Steele, 1991, p 207, section 7.12,
Order of evaluation. The section begins:

In general, the compiler can rearrange the order in which an
expression is evaluated. The rearrangement may consist of
evaluating only the arguments or the two operands of a binary
operator, in some particular order other than the obvious
left-to-right order. The binary ooperators +, *, &, ^, and | are
assumed to be completely associative and commutiative, and a
compiler is permitted to exploit this assumption.

Of course Harbison & Steele could be wrong, or the standard may
have been amended since then, but the text is quite clear. If
you disagree with the text feel free to point out where it is
wrong by citing the appropriate section of the standard.

5.1.2.3, with special attention to paragraph 5.

(And I feel like I'm doing you a favor here: *you*
have made the claim, so the burden of proof should be
yours. Asking the rest of the world to come up with a
disproof is an unnatural state of affairs -- although one
that could greatly simplify many complicated mathematical
proofs. For example, "Goldbach's conjecture is true.
If you disagree, disprove it." Where's my Fields Medal?)

 

[Harald van Dijk]

For your information:

lcc-win invoked with the -overflowcheck option will check each operation
that can generate an overflow. Any operation that does generate one will
provoke the end of the program with an error message.

Does it make sure to exclude unsigned wraparound (which isn't overflow)?
In other words, does a valid C program such as

#include <limits.h>
int main(void) {
unsigned u;
u = UINT_MAX / 2;
u++;
u = UINT_MAX;
u++;
return 0;
}

get accepted and does it run without aborting?

 

[Richard Harter]

5.1.2.3, with special attention to paragraph 5.

5.1.2.3 of what? Clearly not Harbison $=& Steele. I'm guessing
that it is from some standard, either C89, C90, or C99.
Whichever it is, I don't have a copy. Would it possible to
actually quote the paragraph in question, or failing that, point
to a publicly readable version on the web.

(And I feel like I'm doing you a favor here: *you*
have made the claim, so the burden of proof should be
yours. Asking the rest of the world to come up with a
disproof is an unnatural state of affairs -- although one
that could greatly simplify many complicated mathematical
proofs. For example, "Goldbach's conjecture is true.
If you disagree, disprove it." Where's my Fields Medal?)

Don't strain yourself patting yourself on the back.

Er, I did provide reasonable proof of what I claimed. H&S is,
after all, a standard reference work, and the quoted paragraph is
in clear agreement with what I claimed - though not, perhaps,
with what you think I claimed. I'm not sure what that msight be.

While it is possible that H&S is in error, I have to be
skeptical. An incomplete citation without text is not
reassuring.

Looking forward to being enlightened.










Richard Harter, (e-mail address removed)
http://home.tiac.net/~cri, http://www.varinoma.com
The good news is that things could be worse; the bad
news is that things aren't as good as they should be.

 

[jacob navia]

Does it make sure to exclude unsigned wraparound (which isn't overflow)?
In other words, does a valid C program such as

#include <limits.h>
int main(void) {
unsigned u;
u = UINT_MAX / 2;
u++;
u = UINT_MAX;
u++;
return 0;
}

get accepted and does it run without aborting?

Overflow check will be done for SIGNED types only

 

[Chris Torek]

... here is what Harbison (C - A reference Manual) has to say
(7.12 Order of Evaluation).

The assumption of commutativity and associativity is
always true for &, ^, and | on unsigned operands...
It may not be true for * and + because of the possibility
that the order indicated by the expression as written
might avoid overflow but another order might not.
Nevertheless, the compiler is allowed to exploit the
assumption. In such situations the programmer must use
assignments to temporary variable to force a particular
evaluation order:

H&S is simply wrong here (or, more charitably, they are referring
to "K&R C", before the original ANSI C Standard, when the
specification for C was quite loose).

During the original 1980s debates on standardization, there were
some who argued that the compiler should be free to do the above
kinds of rearrangment, and for a while, there was a proposal that
the unary "+" operator (but not plain parentheses) would suppress
it. Thus:

int i, j, k, sum;

i = INT_MAX; /* e.g., 32767 */
j = -i; /* e.g., -32767 */
k = 3;

sum = (i + j) + k;

could overflow, because while (i+j) is obviously 0, and 0+3 obviously
does not overflow, the compiler might compute (i+k) first. To
suppress this, the proposal went, one would write instead:

sum = +(i + j) + k;

which would force the compiler to do the i+j operation as a unit,
resulting in 0, so that the overall operation must succeed.

Fortunately, sanity prevailed, and the X3J11 committee folks
eventually agreed that the compiler *must* do the operations
"as if" they happened as specified by the abstract semantics.
The actual wording reads:

In the abstract machine, all expressions are evaluated
as specified by the semantics.

The compiler is free to rearrange expressions (under the "as if"
rule) only if it can prove that the "programmer-visible effects"
are the same (where "programmer-visible" includes things like
runtime traps, but not things like runtime speed). If the compiler
knows that signed-integer overflow traps are disabled, for instance,
so that (i+k)+j produces the same answer as (i+j)+k, it can use
either order. If it knows that signed-integer overflow traps are
enabled, or if it cannot be sure[%], it should avoid the rearrangement.

[% The compiler usually has a lot of leeway in the "cannot be sure"
department since, at least most of the time, anything the programmer
does to affect a trap-on-overflow flag is not done with Standard
C. (I use this "most of the time" wording only because I have not
yet studied the C99 floating point models.) Because a non-Standard
operation can *always* affect the rest of the system in ways the
compiler need not appreciate, a compiler could go ahead and
rearrange things anyway, by simply *assuming* that you -- the
programmer -- will not turn on the trap-on-overflow flag. After
all, we all know it is most important to get the wrong answer as
fast as possible -- getting the right answer slower is never any
use at all. ]

 

[Keith Thompson]

5.1.2.3, with special attention to paragraph 5.

(And I feel like I'm doing you a favor here: *you*
have made the claim, so the burden of proof should be
yours. Asking the rest of the world to come up with a
disproof is an unnatural state of affairs -- although one
that could greatly simplify many complicated mathematical
proofs. For example, "Goldbach's conjecture is true.
If you disagree, disprove it." Where's my Fields Medal?)

To be fair, it was Harbison & Steele who made the claim; their book is
generally considered to be quite reliable. But the 1991 edition is
not the latest; perhaps the current 5th edition has different wording.

And yes, IMHO H&S are wrong on this point.

 

[Keith Thompson]

5.1.2.3 of what? Clearly not Harbison $=& Steele. I'm guessing
that it is from some standard, either C89, C90, or C99.
Whichever it is, I don't have a copy. Would it possible to
actually quote the paragraph in question, or failing that, point
to a publicly readable version on the web.

You asked for a citation from the standard, and when presented with a
section number you're not sure that it refers to the standard?

Yes, it's section 5.1.2.3 of the standard. It could be either C90 or
C99, since that particular setion has the same number in both.

The latest post-C99 draft is at
<http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1256.pdf>; portions
not marked with change bars should be identical to the official C99
standard.

The section is more than a page long (nearly 4 pages including notes
and examples), so I'd rather not quote it all here. If you have
trouble obtaining or reading the PDF, I'll be glad to e-mail you the
plain text for that section.

[...]

 

[CJ]

lcc-win invoked with the -overflowcheck option will check
each operation that can generate an overflow. Any operation that
does generate one will provoke the end of the program
with an error message.

I believe that shows very bad quality of implementation. It's undefined
behavior, so your compiler can do what it likes, but I think it's much
better to let the program continue (maybe the programmer will check
errno for EOVERFLOW, either way I don't think *any* library, including
the standard library, has any business in aborting programs without
giving the programmer chance to recover).

 

[jacob navia]

I believe that shows very bad quality of implementation. It's undefined
behavior, so your compiler can do what it likes, but I think it's much
better to let the program continue (maybe the programmer will check
errno for EOVERFLOW, either way I don't think *any* library, including
the standard library, has any business in aborting programs without
giving the programmer chance to recover).

I haven't spelled out all the details. You can redefine this behavior if
you add a function called

void _overflow(int linenr, char *functionname);

What I described above is the default action.

 

[jacob navia]

The exact program I posted aborts, reporting an overflow, when compiled
with lcc's overflow checking. I was hoping you'd have tried it.

OO0O0OPS

Fixed

The intermediate code generated is:
stmt: ASGNI(addr,ADDU(mem,con1))

Asgn integer (address, Add unsigned(memory, constant 1))

I saw the Asgn integer and forgot to see that the add was an
unsigned add.

I checked all similar construct but that was the only one.

Thanks for this, now lcc-win is a bit better.
(Will be in the next release)

jacob

 

[CJ]

I haven't spelled out all the details. You can redefine this behavior if
you add a function called

void _overflow(int linenr, char *functionname);

What I described above is the default action.

Isn't it possible to turn this off completely, so that overflow is
silently ignored by default? Or do you have to write a no-op function
called _overflow? I think having a special function like this is likely
to encourage programmers using your compiler to rely on such special
overflow handling and write non-portable code.

But if you must have it, why not use existing mechanisms, for example,
you could send a signal to the program on overflow, and set a global
variable like _overflow_has_occurred so that if the programmer installs
a handler for the signal then he can know whether it was triggered by
your overflow mechanism or not.

 

[Harald van Dijk]

Overflow check will be done for SIGNED types only

The exact program I posted aborts, reporting an overflow, when compiled
with lcc's overflow checking. I was hoping you'd have tried it.

 

[jacob navia]

Isn't it possible to turn this off completely, so that overflow is
silently ignored by default?

I am ALWAYS wrong with you. As I said in my message
this is only done when lcc-win is invoked with the
-checkoverflow flag!

It is not ON by default.

Or do you have to write a no-op function
called _overflow? I think having a special function like this is likely
to encourage programmers using your compiler to rely on such special
overflow handling and write non-portable code.

???

But if you must have it, why not use existing mechanisms, for example,
you could send a signal to the program on overflow, and set a global
variable like _overflow_has_occurred so that if the programmer installs
a handler for the signal then he can know whether it was triggered by
your overflow mechanism or not.

Well, this all can be done in YOUR overflow function. Other users
will have other requirements, whatever... This is the most flexible
design.

 

[jameskuyper]

....

Cited elsewhere, Harbison &Steele, 1991, p 207, section 7.12,
Order of evaluation. The section begins:

In general, the compiler can rearrange the order in which an
expression is evaluated. The rearrangement may consist of
evaluating only the arguments or the two operands of a binary
operator, in some particular order other than the obvious
left-to-right order. The binary ooperators +, *, &, ^, and | are
assumed to be completely associative and commutiative, and a
compiler is permitted to exploit this assumption.

Of course Harbison & Steele could be wrong, or the standard may
have been amended since then, but the text is quite clear. If
you disagree with the text feel free to point out where it is
wrong by citing the appropriate section of the standard.

The text you cite from Harbison & Steele is incorrect. The standard is
the authoritative source for this issue, and it disagrees. It's a
little tricky to cite relevant sections from the standard, because
what I need to cite is the absence of any permission for
rearrangement. Since it's absent, it's hard to cite. It's also tricky
demonstrating that the standard requires a particular evaluation
order, not because it's not true, but because it's expressed
indirectly.

Basically, the standard requires that a+b+c be parsed as (a+b)+c;
there's no other way parse it that is consistent with the grammar
given in the standard. As a result, there are precisely two additive
expressions there. The first one has 'a' as it's left operand, and b
as it's right operand. The second additive expression has a+b as its
left operand, and c as it's right operand. The standard requires that
each additive expression have as it's value the sum of it's operands.
It can evaluate a or b in any order (which could be important if a or
b were expressions rather than variable names), but the result of the
second additive expression is the sum of the value of the first
expression and the value of c.

Section 5.1.2.3 p5 has been cited for your attention, which is the
formal version of the as-if rule. The key point is that it allows a
program to produce it's results without using precisely the semantics
specified by the standard, so long as it produces exactly the same
results as if the abstract semantics had been obeyed.

I described the abstract semantics for additive expressions earlier,
and those semantics don't allow for overflows when a+b doesn't
overflow, and (a+b)+c doesn't overflow, even if (a+c) or (b+c) do
overflow. Note that 5.1.2.3 does NOT provide any special exemptions
based upon the associative and commutative properties of mathematical
operators. The standard doesn't provide such an exemption anywhere
else, either. It would be pretty odd if it did, since computer
addition, unlike mathematical addition, is NOT associative. The
standard does mention integer overflow, and that is precisely the
thing that breaks the associativity of computer addition.

 

[Flash Gordon]

jacob navia wrote, On 04/12/07 22:44:

I am ALWAYS wrong with you. As I said in my message
this is only done when lcc-win is invoked with the
-checkoverflow flag!

It is not ON by default.

<snip>

Personally, I would say an option to trap on signed integer overflow is
a good thing. So now you know not everyone here always disagrees with
everything you have implemented.

 

[Ben Bacarisse]

jacob navia wrote, On 04/12/07 22:44:



<snip>

Personally, I would say an option to trap on signed integer overflow
is a good thing.

<off-topic>
In case anyone else is similarly in the dark, I only recently discovered
the very handy -ftrapv option in gcc.
</off-topic>

 

[Richard Heathfield]

CJ said:

I believe that shows very bad quality of implementation. It's undefined
behavior, so your compiler can do what it likes, but I think it's much
better to let the program continue (maybe the programmer will check
errno for EOVERFLOW, either way I don't think *any* library, including
the standard library, has any business in aborting programs without
giving the programmer chance to recover).

That isn't really a problem, since the behaviour is controlled by a switch
which, presumably, the programmer can choose not to throw. The problem is
not "this switch is bad" so much as "this switch has nothing whatsoever to
do with the topic of this newsgroup". The switch *is*, however, topical in
comp.compilers.lcc, and it would be good for those who wish to discuss it
to do so there, rather than here.

 

[Richard Heathfield]

jacob navia said:

I am ALWAYS wrong with you. As I said in my message
this is only done when lcc-win is invoked with the
-checkoverflow flag!

This is more properly a subject for comp.compilers.lcc - but it seems to me
that if overflow checking is only done when -checkoverflow is set, then
setting -overflowcheck (which was what you said last time) is a bit
pointless.

si tacuisses...

<snip>

 

[Philip Potter]

Well, no, that is not my understanding. I'm always open to
chapter and verse correction from the standard. However here is
what Harbison (C - A reference Manual) has to say (7.12 Order of
Evaluation).

The assumption of commutativity and associativity is
always true for &, ^, and | on unsigned operands...
It may not be true for * and + because of the possibility
that the order indicated by the expression as written
might avoid overflow but another order might not.
Nevertheless, the compiler is allowed to exploit the
assumption. In such situations the programmer must use
assignments to temporary variable to force a particular
evaluation order:

As stated elsethread, this is untrue.

This is quite true. To quote myself, the responsibility for
avoiding overflow rests with the programmer and not with the
compiler.

When you cannot even add two integers together without avoiding all
possibility of overflow, how do you propose the programmer achieves this?

You give all of the responsibility to the programmer but you do not give
him the tools to fulfill that responsibility.

 

[Richard Harter]

[snip quoted H&S]

Small order of crow ordered and consumed. The section in
question is wrong, or more charitably, was true of some
pre-standard K&R implementations.

You asked for a citation from the standard, and when presented with a
section number you're not sure that it refers to the standard?

Yes, it's section 5.1.2.3 of the standard. It could be either C90 or
C99, since that particular setion has the same number in both.

Let me grumble a bit. Just because one is a programmer doesn't
mean that one is exempt from the ordinary standards of
scholarship. Part of the drill is to include the identification
of references.

The latest post-C99 draft is at
<http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1256.pdf>; portions
not marked with change bars should be identical to the official C99
standard.

The section is more than a page long (nearly 4 pages including notes
and examples), so I'd rather not quote it all here. If you have
trouble obtaining or reading the PDF, I'll be glad to e-mail you the
plain text for that section.

Many thanks, much appreciated.

[...]

In this document the only relevant passage in paragraph 5 is a
general statement of the "as if" rule, e.g.:

"At program termination, all data written into files shall be
identical to the result that execution of the program according
to the abstract semantics would have produced."

To settle the question at hand one needs a definite statement of
the abstract semantics; it turns out that paragraph 14 (Example
6) is a clear statement of the application of the rule. I quote
in part:

"However, on a machine in which overflow silently generates some
value and where positive and negative overflows cancel, the
above expression statement can be rewritten by the implementation
in any of the above ways because the same result will occur."

Again, many thanks for the URL.



Richard Harter, (e-mail address removed)
http://home.tiac.net/~cri, http://www.varinoma.com
The good news is that things could be worse; the bad
news is that things aren't as good as they should be.