INTEGER'FIRST mod (-1) = 0 = INTEGER'FIRST rem (-1) AI-00889/00 1
91-02-11 pa WI
!standard 04.05.05 (03) 91-02-11 AI-00889/00
!standard 04.05.05 (12)
!editor Wichmann/Goodenough 90-12-21
!class pathology 90-02-11 (provisional classification)
!status work-item 91-02-11
!status received 89-01-06
!topic INTEGER'FIRST mod (-1) = 0 = INTEGER'FIRST rem (-1)
!summary 91-02-11 (DRAFT)
For an integer type T,
- the value of T'BASE'FIRST rem (-1) is zero.
- the value of T'BASE'FIRST mod (-1) is zero.
- the value of T'BASE'FIRST/(-(-1)) is T'BASE'FIRST.
No exception is raised for these expressions.
!question 91-02-11 (DRAFT)
4.5.5(3-4) defines the effect of the rem operator:
Integer division and remainder are defined by the relation
A = (A/B)*B + (A rem B)
where (A rem B) has the sign of A and an absolute value less than the
absolute value of B.
According to the latter part of this definition, INTEGER'FIRST rem (-1)
equals zero, since zero is the only integer whose value is less than the
absolute value of -1. On the other hand, the specified relation requires the
evaluation of INTEGER'FIRST/(-1), and this evaluation is allowed to raise
NUMERIC_ERROR (or CONSTRAINT_ERROR; see AI-00387) for twos-complement
machines since 4.5(7) says:
The predefined operations on integer types either yield the
mathematically correct result or raise the exception NUMERIC_ERROR.
A predefined operation that delivers a result of an integer type
(other than universal_integer) can only raise the exception NUMERIC_
ERROR if the mathematical result is not a value of the type.
For a twos-complement machine, the value of -INTEGER'FIRST exceeds the value
of INTEGER'LAST, so NUMERIC_ERROR can be raised. Is an implementation
therefore required (or allowed) to raise NUMERIC_ERROR for INTEGER'FIRST rem
(-1)? Is it required (or allowed) to return the value zero? Are
implementations free to choose one of these alternatives?
DRAFT DRAFT DRAFT
INTEGER'FIRST mod (-1) = 0 = INTEGER'FIRST rem (-1) AI-00889/00 2
91-02-11 pa WI
The same questions arise for INTEGER'FIRST mod (-1), since 4.5.5(5) says:
The result of the modulus operation is such that A mod B) has the
sign of B and an absolute value less than the the absolute value of
B; in addition, for some integer value N, this result must satisfy
the relation
A = B*N + (A mod B)
For twos-complement machines, when B is -1 and A is INTEGER'FIRST, N must
have a value one greater than the value of INTEGER'LAST. Since this value
cannot be represented as a value of type INTEGER, is INTEGER'FIRST mod (-1)
allowed to raise NUMERIC_ERROR?
Finally, 4.5.5(4) also says:
Integer division satisfies the identity
(-A)/B = -(A/B) = A/(-B)
Consider the expression INTEGER'FIRST/(-1), which is allowed to raise
NUMERIC_ERROR for twos-complement machines. Therefore, according to the
above identity, since B is (-1) and since -(INTEGER'FIRST/(-1)) is allowed to
raise NUMERIC_ERROR, is INTEGER'FIRST/(-(-1)) also allowed to raise NUMERIC_
ERROR?
!recommendation 91-02-11 (DRAFT)
Integer division and remainder are defined by the following mathematical
relation
A = (A/B)*B + (A rem B)
where (A rem B) has the sign of A and an absolute value less than the
absolute value of B.
The result of the modulus operation is such that (A mod B) has the sign of B
and an absolute value less than the absolute value of B; in addition, for
some integer value N, this result must satisfy the mathematical relation
A = B*N + (A mod B)
Finally, integer division satisfies the mathematical identity
(-A)/B = -(A/B) = A/(-B)
!discussion 91-02-11 (DRAFT)
The intention in using equations to specify the effect of integer division,
mod, and rem was to interpret the equations in a mathematical sense. In
particular, the identity in 4.5.5(4) was clearly intended in a mathematical
sense since the identity is not a legal Ada expression.
DRAFT DRAFT DRAFT
INTEGER'FIRST mod (-1) = 0 = INTEGER'FIRST rem (-1) AI-00889/00 3
91-02-11 pa WI
The effect of interpreting the equations in a mathematical sense is that the
rem and mod operators yield the value zero when the second operand has the
value -1. Similarly, the identity given in 4.5.5(4) has no effect on the
interpretation of INTEGER'FIRST/(-(-1)).
A survey of compilers from major vendors showed that A rem B and A mod B
yields zero when A has the value T'BASE'FIRST (for integer type T) and the
value of B is -1. Therefore there is no penalty in requiring that zero be
returned for both rem and mod in these cases.
!appendix 90-12-21
*****************************************************************************
!section 04.05 (07) Gary Morris 89-01-06 83-01256
!version 1983
!topic Raising NUMERIC_ERROR on remainder operations
I have a question about the "rem" operation and the Ada rules that
apply to it. Specifically: Is it acceptable to raise NUMERIC_ERROR
for a "rem" (or "mod") operation when the operands are integer'first
(-32768) and -1?
Consider a machine with twos complement integer arithmetic, where the
predefined integer type has a range that is symmetric around zero with
an extra negative value (such as -32768..32767). The result of the
operation (-32768 rem -1) has a valid mathematical result of 0 but the
division operation (-32768/-1) used to compute the remainder yields a
NUMERIC_ERROR (because the mathematical result of the division is
32768, outside the range of the type).
Note that this problem only arises with these two values of the
operands, all other values for either operand yield the desired
result.
In the RM 4.5/7, this operation may raise NUMERIC_ERROR only if the
mathematical result is not a value of the type. Since the
mathematical result (0) is a value for this type, RM 4.5/7 requires
that no exception be raised.
However, according to the RM 4.5.5/3-4, integer remainder is defined
in terms of integer divide and multiply:
> Since integer division and remainder are defined by the relation 3
>
> A = (A/B)*B + (A rem B) 4
Or: A - (A/B)*B = (A rem B)
With a 16 bit twos complement integer type, where A is -32768 and B is
-1, the mathematical result of the division is 32768. This value is
DRAFT DRAFT DRAFT
INTEGER'FIRST mod (-1) = 0 = INTEGER'FIRST rem (-1) AI-00889/00 4
91-02-11 pa WI
outside the range of the base type (range -32768..32767) and
NUMERIC_ERROR is raised on divide. Since a divide is used on most all
machines in the computation of remainder (divide instructions
typically return both quotient and remainder) it makes sense for
NUMERIC_ERROR to be allowed for "rem" (and "mod") when it is allowed
for divide. To disallow NUMERIC_ERROR for this situation would
require an explicit check of the operands on every remainder operation
to see if they were 'first and -1. This seems an unreasonable
overhead for an unusual case.
A survey of three different Ada compilers, showed that all three are
not in compliance with the RM 4.5/7 when performing of a "rem" or
"mod" with the values of 'first and -1. The compilers tested were
TeleSoft VAX/VMS Ada version 3.22, Sun Ada 1.3, and DEC VAX Ada 1.5.
The two VAX compilers raised a NUMERIC_ERROR and the Sun compiler
returned an incorrect result without raising an exception. I have an
ACVC style test program that I used to test these compiler and would
be willing to provide it if requested.
Is it acceptable to raise NUMERIC_ERROR in this situation, even though
the mathematical result of the "rem" (or "mod") is in the range of the
integer type?
*****************************************************************************
!section 04.05.05 (12) B Wichmann 90-08-15 83-01395
!version 83
!topic Meaning of INTEGER'FIRST rem (-1)
The referenced paragraph defines a relationship between INTEGER
division and remainder. However, in the case of a 2's complement
machine, INTEGER'FIRST/(-1) overflows. It is therefore not clear
if:
a) INTEGER'FIRST rem (-1) should raise CONSTRAINT_ERROR (AI-00387),
given that there is no appeal to 11.6
b) The result 0 should be produced.
Paragraph 4.5.5(14) states that:
INTEGER'FIRST rem (-1) = INTEGER'FIRST rem 1, which is clearly 0;
and also:
INTEGER'FIRST rem (-1) = -((-INTEGER'FIRST) rem (-1)), which
clearly overflows.
Paragraph 4.5.5(12) does not help since it clearly does not give all
the cases in which NUMERIC_ERROR (CONSTRAINT_ERROR, AI-00387), can
DRAFT DRAFT DRAFT
INTEGER'FIRST mod (-1) = 0 = INTEGER'FIRST rem (-1) AI-00889/00 5
91-02-11 pa WI
arise, since INTEGER'FIRST / (-1) will raise an exception on a
2's complement machine (ignoring 11.6).
The Language Compatible Arithmetic Standard defines the result to be
zero. (This is because the rounding function rndI gives a result in
Z, not in the integer type.) Note that this problem did not arise in
the NPL report DITC 167/90, since 'rem' is not defined in Pascal and
the coding produced to implement this (function remI, page 23), made
a special case of this.
*****************************************************************************
!section 04.05.05 (03) J. Goodenough 91-02-11
!version 1983
!topic Minutes from September 1990 ARG meeting
Brian Wichmann noted that if the operators in 4.5.5(3) are taken to be Ada
operators rather than mathematical notation, the value INTEGER'FIRST
REM (-1) is not defined by the reference manual. Wichmann suggested that
Ada semantics ought to be consistent with the proposed Language-Compatible
Arithmetic Standard (LCAS). LCAS calls for X REM (-1) to complete
normally and return zero.
This approach was approved unanimously in a straw vote. Wichmann will write
an AI of class "pathology."
*****************************************************************************
!section 04.05.05 (03) B Wichmann 90-12-21 83-01405
!version 83
!topic Meaning of INTEGER'FIRST rem (-1)
The referenced paragraph defines a relationship between INTEGER division and
remainder. However, in the case of a 2's complement machine,
INTEGER'FIRST/(-1) overflows. It is therefore not clear if:
a) INTEGER'FIRST rem (-1) should raise CONSTRAINT_ERROR (AI-00387),
given that there is no appeal to 11.6
b) The result 0 should be produced.
Paragraph 4.5.5(14) states that:
INTEGER'FIRST rem (-1) = INTEGER'FIRST rem 1, which is clearly 0;
and also:
INTEGER'FIRST rem (-1) = -((-INTEGER'FIRST) rem (-1)), which
clearly overflows.
Paragraph 4.5.5(12) does not help since it clearly does not give all the
cases in which NUMERIC_ERROR (CONSTRAINT_ERROR, AI-00387), can arise, since
DRAFT DRAFT DRAFT
INTEGER'FIRST mod (-1) = 0 = INTEGER'FIRST rem (-1) AI-00889/00 6
91-02-11 pa WI
INTEGER'FIRST / (-1) will raise an exception on a 2's complement machine
(ignoring 11.6).
The Language Compatible Arithmetic Standard defines the result to be zero.
(This is because the rounding function rndI gives a result in Z, not in the
integer type.) Note that this problem did not arise in the NPL report DITC
167/90, since 'rem' is not defined in Pascal and the coding produced to
implement this (function remI, page 23), made a special case of this.
This issue was orginally combined with other cases in which NUMERIC_ERROR is
raised in performing various operations (AI-00159). However, it has been
decided that this issue should be separated out. The tentative conclusion of
a discussion of this at the ARG meeting in September 1990 was that
implementation should be allowed to raise at exception, although the language
requires that 0 be produced. The rationale for this is that adding a
performance penalty for this one case did not seem reasonable.
Note that the situation with INTEGER'LAST mod (-1) is somewhat different
since the wording in 4.5.5(5) conjectures an 'integer value N' which
could imply that the value need not be of the appropriate integer type
(which it is not in this case, due to overflow). Implementation may well
use similar code sequences for rem and mod and therefore the fact that
the wording in the RM is different is not so relevant to the resolution.
Since then, the only compiler known to NPL which gave NUMERIC_ERROR has been
amended to give 0. Hence the case for raising an exception seems rather weak.
The following compilers give 0: VADS (Sun/3), VAX (DEC), XD-68000 and Alsys
(IBM-PC). One vendor made a decision to add one machine instruction to ensure
that 0 was produced.
I conclude from the above that the ARG should reconsider the issue and make
it a requirement that the result be 0. I do not agree to the issue being
regarded as a pathology for two reasons. Firstly, I do not think the
performance penalty is too high, and secondly making this a special case
would adversely effect program proof tools. In practice, and implementation
for which the performance penalty was high would invoke the 'incorrect'
optimization by a mode switch, not used for validation.
Extract from Minutes of September 1990 ARG meeting
The Raising of CONSTRAINT_ERROR by REM and MOD
Brian Wichmann noted that if the operators in 4.5.5(3) are taken to be Ada
operators rather than mathematical notation, the value INTEGER'FIRST REM -1
is not defined by the reference manual. Wichmann suggested that Ada
semantics ought to be consistent with the proposed Language-Compatible
Arithmetic Standard (LCAS). LCAS calls for X REM -1 to complete normally and
return zero.
This approach was approved unanimously in a straw vote. Wichmann will write
an AI of class "pathology."
DRAFT DRAFT DRAFT