C++Talk.NET Forum Index C++Talk.NET
C++ language newsgroups
 
Archives   FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister 
 ProfileProfile   Log in to check your private messagesLog in to check your private messages   Log inLog in 

signed overflow is UB, what should numeric_limits<int>::is_m

 
Post new topic   Reply to topic    C++Talk.NET Forum Index -> C++ language, library and standards
View previous topic :: View next topic  
Author Message
scott douglass
Guest
PostPosted: Wed Feb 25, 2004 4:34 am    Post subject: signed overflow is UB, what should numeric_limits<int>::is_m Reply with quote


Hi,

In the C++ standard signed int overflow is undefined behavior (clause 5 para 5) [and the same is true in C]. Suppose a compiler takes advantage of this to optimize, for example:
bool f(int i) { return i + 1 < i; }
into this
bool f(int) { return false; }

Now, how should numeric_limits
Quote:

A type is modulo if it is possible to add two positive numbers and have a

result that wraps around to a third number that is less.
<<

The footnote there says "Required by LIA-1". LIA-1 gives a stronger definition of modulo in 5.1.2:
modulo is true if certain particular operations "wrap" and
modulo is false if overflows cause a notification

But C++ allows more than these two possibilities. For the implementatin I'm considering some cases will wrap and some will silently give results different from the wrapped results.

In this implementation, what should numeric_limits
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html ]


Back to top
James Dennett
Guest
PostPosted: Wed Feb 25, 2004 6:38 am    Post subject: Re: signed overflow is UB, what should numeric_limits<int>:: Reply with quote


scott douglass wrote:

Quote:
Hi,

In the C++ standard signed int overflow is undefined behavior (clause 5
para 5) [and the same is true in C]. Suppose a compiler takes advantage
of this to optimize, for example:
bool f(int i) { return i + 1 < i; }
into this
bool f(int) { return false; }

Now, how should numeric_limits set? The definition in the C++ standard seems pretty weak:


A type is modulo if it is possible to add two positive numbers and have a
result that wraps around to a third number that is less.


The footnote there says "Required by LIA-1". LIA-1 gives a stronger
definition of modulo in 5.1.2:
modulo is true if certain particular operations "wrap" and
modulo is false if overflows cause a notification

But C++ allows more than these two possibilities. For the implementatin
I'm considering some cases will wrap and some will silently give results
different from the wrapped results.

In this implementation, what should numeric_limits<int>::is_modulo be?

It would seem, just looking at what you've quoted above, that
the only options for an implementation that conforms to LIA-1
are either modular arithmetic or notification on overflow.

-- James.

---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html ]


Back to top
Gabriel Dos Reis
Guest
PostPosted: Wed Feb 25, 2004 8:17 pm    Post subject: Re: signed overflow is UB, what should numeric_limits<int>:: Reply with quote


scott douglass <sdouglass (AT) arm (DOT) com> writes:

Quote:
Hi,

In the C++ standard signed int overflow is undefined behavior
(clause 5 para 5) [and the same is true in C]. Suppose a compiler
takes advantage of this to optimize, for example:
bool f(int i) { return i + 1 < i; }
into this
bool f(int) { return false; }

Now, how should numeric_limits set? The definition in the C++ standard seems pretty weak:


A type is modulo if it is possible to add two positive numbers and have a
result that wraps around to a third number that is less.


The footnote there says "Required by LIA-1". LIA-1 gives a stronger
definition of modulo in 5.1.2:
modulo is true if certain particular operations "wrap" and
modulo is false if overflows cause a notification

But C++ allows more than these two possibilities. For the
implementatin I'm considering some cases will wrap and some will
silently give results different from the wrapped results.

In this implementation, what should numeric_limits<int>::is_modulo be?

It is known that the wordings for numeric_limits<> are quite weak and do
not clearly reflect the intent (as indicated in the footnotes).
Those should be fixed in C++0x.

I think LIA-1 words should apply and numeric_limits<int>::is_modulo
should be

(1) false, by default; and
(2) true only, when an implementation does chose to define the
"undefined behaviour" to be a modulo arithmetic -- in which
case, it cannot do arbitrary things.


--
Gabriel Dos Reis
[email]gdr (AT) cs (DOT) tamu.edu[/email]
Texas A&M University -- Computer Science Department
301, Bright Building -- College Station, TX 77843-3112

---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html ]


Back to top
Al Grant
Guest
PostPosted: Thu Feb 26, 2004 6:54 pm    Post subject: Re: signed overflow is UB, what should numeric_limits<int>:: Reply with quote
James Dennett <jdennett (AT) acm (DOT) org> wrote

Quote:
scott douglass wrote:
In this implementation, what should numeric_limits<int>::is_modulo be?

It would seem, just looking at what you've quoted above, that
the only options for an implementation that conforms to LIA-1
are either modular arithmetic or notification on overflow.

But the question is what is_modulo should be set to in an
implementation that doesn't conform to LIA-1. Specifically in the
UB case, setting it to false means a safety-conscious programmer
might complain "I added two positive numbers and got a number that
is less - but you told me this could never happen!" while setting
it to true means someone might say "You told me arithmetic 'wraps'
but I do not observe well-defined 'wrapping' behavior here."

My feeling is that the first programmer has a more serious and
more justified complaint and so is_modulo should be set to 'true'
if in doubt. Also, reading the standard literally would suggest
a 'true' setting on the grounds that anything is _possible_ in UB.

On the other hand on an implementation that defines integer arithmetic
to saturate (not allowed by LIA-1 but quite reasonable) the condition
"if it is possible to add two positive numbers and have a result that
wraps around to a third number that is less" is now not met and so
is_modulo must be set to false - but there is still no trap.

---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html ]


Back to top
Alberto Barbati
Guest
PostPosted: Thu Feb 26, 2004 9:33 pm    Post subject: Re: signed overflow is UB, what should numeric_limits<int>:: Reply with quote
Gabriel Dos Reis wrote:
Quote:
I think LIA-1 words should apply and numeric_limits<int>::is_modulo
should be

(1) false, by default; and
(2) true only, when an implementation does chose to define the
"undefined behaviour" to be a modulo arithmetic -- in which
case, it cannot do arbitrary things.

I am no LIA-1 expert, but I just found this
http://anubis.dkuug.dk/jtc1/sc22/wg14/www/docs/n750.htm
and, if I interpret it well, it contradicts you. About modulo (H.2.2.1),
it sais that:

"The parameter modulo is always true for the unsigned types [...]. The
parameter modulo is true when INT_OUT_OF_BOUNDS is 1 (wrap) or false
when INT_OUT_OF_BOUNDS is 2 (notify) and covers all LIA-1 conformant
signed types. The implementation picks the value of modulo. It is
implementation defined if the user can change the value of modulo."

That is (for signed types):
(1) false: notify about overflow via exception
(2) true: wrap modulo INT_MAX-INT_MIN+1

"Undefined behaviour" is not allowed.

It's interesting to notice that LIA-1 allows implementation to change
the value of modulo, however C++ defines is_modulo to be a const bool
and not a function, so the current definition is inadeguate to express
the LIA-1 requirements.

Alberto Barbati

---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html ]


Back to top
Alberto Barbati
Guest
PostPosted: Sun Feb 29, 2004 12:09 pm    Post subject: Re: signed overflow is UB, what should numeric_limits<int>:: Reply with quote
Gabriel Dos Reis wrote:

Quote:
Alberto Barbati <AlbertoBarbati (AT) libero (DOT) it> writes:

| Gabriel Dos Reis wrote:
| > I think LIA-1 words should apply and numeric_limits<int>::is_modulo
| > should be
| > (1) false, by default; and
| > (2) true only, when an implementation does chose to define the
| > "undefined behaviour" to be a modulo arithmetic -- in which
| > case, it cannot do arbitrary things.
|
| I am no LIA-1 expert, but I just found this
| http://anubis.dkuug.dk/jtc1/sc22/wg14/www/docs/n750.htm
| and, if I interpret it well, it contradicts you. About modulo
| (H.2.2.1), it sais that:
|
| "The parameter modulo is always true for the unsigned types [...].
| The parameter modulo is true when INT_OUT_OF_BOUNDS is 1 (wrap) or
| false when INT_OUT_OF_BOUNDS is 2 (notify) and covers all LIA-1
| conformant signed types. The implementation picks the value of
| modulo. It is implementation defined if the user can change the value
| of modulo."
|
| That is (for signed types):
| (1) false: notify about overflow via exception
| (2) true: wrap modulo INT_MAX-INT_MIN+1
|
| "Undefined behaviour" is not allowed.
|
| It's interesting to notice that LIA-1 allows implementation to change
| the value of modulo, however C++ defines is_modulo to be a const bool
| and not a function, so the current definition is inadeguate to express
| the LIA-1 requirements.

No, you're confused.

[...]

In that regard, the C++ definition for numeric_limits<T>::is_modulo
fulfills the spirit and the letter of the LIA specification.


Thanks Gabriel, you have been very informative. Is there a copy of ISO
10967-1 publicly available on the net? I looked here:
http://std.dkuug.dk/JTC1/SC22/WG11/ but it seems that access to the full
document is restricted.

Your remarks are only about my last statement, however. As you look to
be very competent in this area and it seems that you have access to
restricted documents, would you mind discussing my other statement, in
particular the one about the meaning of is_modulo==false which would
mean "notify" rather than "UB"?

Alberto Barbati


---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html ]


Back to top
Gabriel Dos Reis
Guest
PostPosted: Sun Feb 29, 2004 10:18 pm    Post subject: Re: signed overflow is UB, what should numeric_limits<int>:: Reply with quote
Alberto Barbati <AlbertoBarbati (AT) libero (DOT) it> writes:

Quote:
Gabriel Dos Reis wrote:

Alberto Barbati <AlbertoBarbati (AT) libero (DOT) it> writes:
| Gabriel Dos Reis wrote:
| > I think LIA-1 words should apply and numeric_limits<int>::is_modulo
| > should be
| > (1) false, by default; and
| > (2) true only, when an implementation does chose to define the
| > "undefined behaviour" to be a modulo arithmetic -- in which
| > case, it cannot do arbitrary things.
| | I am no LIA-1 expert, but I just found this
| http://anubis.dkuug.dk/jtc1/sc22/wg14/www/docs/n750.htm
| and, if I interpret it well, it contradicts you. About modulo
| (H.2.2.1), it sais that:
| | "The parameter modulo is always true for the unsigned types
[...].
| The parameter modulo is true when INT_OUT_OF_BOUNDS is 1 (wrap) or
| false when INT_OUT_OF_BOUNDS is 2 (notify) and covers all LIA-1
| conformant signed types. The implementation picks the value of
| modulo. It is implementation defined if the user can change the value
| of modulo."
| | That is (for signed types):
| (1) false: notify about overflow via exception
| (2) true: wrap modulo INT_MAX-INT_MIN+1
| | "Undefined behaviour" is not allowed.
| | It's interesting to notice that LIA-1 allows implementation to
change
| the value of modulo, however C++ defines is_modulo to be a const bool
| and not a function, so the current definition is inadeguate to express
| the LIA-1 requirements.
No, you're confused.
[...]
In that regard, the C++ definition for numeric_limits<T>::is_modulo
fulfills the spirit and the letter of the LIA specification.


Thanks Gabriel, you have been very informative. Is there a copy of ISO
10967-1 publicly available on the net? I looked here:
http://std.dkuug.dk/JTC1/SC22/WG11/ but it seems that access to the
full document is restricted.

At the best of my knowledge, there is no publically available copy of
LIA-* -- though you might try the drafts or working papers (with the
usual caveats that they are not the final standards).

Quote:
Your remarks are only about my last statement, however. As you look to
be very competent in this area and it seems that you have access to
restricted documents, would you mind discussing my other statement, in
particular the one about the meaning of is_modulo==false which would
mean "notify" rather than "UB"?

You're right that I completely missed that part when replying.
Both C99 and C++ do not require LIA-1 semantics. As a consequence,
when the C++ standard says overflow/underflow leads to undefined
behaviour, that specification overrides anything else.
Now, an implementation is free to chose to define that "undefined
bahaviour"; for example, it may say that an exception is thrown.
But that is no standard requirement. Therefore, I stand by my earlier
statement, namely:

numeric_limits<int>::is_modulo should be

(1) false, by default; and
(2) true only, when an implementation does chose to define the
"undefined behaviour" to be a modulo arithmetic -- in which
case, it cannot do arbitrary things.


Note however that the situation would be completely different did the
C++ standard require LIA-1. In such case, an implementation would
not have the latitude it currently has. In particular,

(1) if numeric_limits<int>::is_modulo is false, then it must notify
underflow/overflow in a non-ambiguous manner -- presumably using
exceptions as recommanded (not but required) by LIA-1 for
programming languages that have exception support;

(2) if numeric_limits<int>::is_modulo is true, the the "wrapping"
function should be documented. That would correspond to a
vaste majority of *modern* architectures.

I guess the C++ standards committee might probably want to revisit
this issue as part of "upgrading" the built-in types facilities.

--
Gabriel Dos Reis
[email]gdr (AT) cs (DOT) tamu.edu[/email]
Texas A&M University -- Computer Science Department
301, Bright Building -- College Station, TX 77843-3112

---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html ]


Back to top
Display posts from previous:   
Post new topic   Reply to topic    C++Talk.NET Forum Index -> C++ language, library and standards All times are GMT
Page 1 of 1

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum


Powered by phpBB © 2001, 2006 phpBB Group
SEO toolkit © 2004-2006 webmedic.