CVS difference for ais/ai-00095.txt

Differences between 1.1 and version 1.2
Log of other versions for file ais/ai-00095.txt

--- ais/ai-00095.txt	1998/09/30 00:17:16	1.1
+++ ais/ai-00095.txt	1999/06/26 01:11:13	1.2
@@ -1,5 +1,6 @@
-!standard RM-3.5.4 (07)                               96-11-16  AI95-00095/02
+!standard RM-3.5.4 (07)                               99-05-25  AI95-00095/03
 !class ramification 95-09-29
+!status Corrigendum 2000 99-05-25
 !status WG9 approved 96-12-07
 !status ARG Approved 6-0-5  96-10-07
 !status work item 95-09-29
@@ -8,18 +9,18 @@
 !difficulty Medium
 !subject Modular types on one's complement machines.
 
-!summary 95-09-29
+!summary
 
 Implementation Permission: On a one's complement machine, the
 implementation may support non-binary modulii above
 System.Max_Nonbinary_Modulus.
 
-!question 95-09-29
+!question
 
 How should an implementation on a one's complement machine implement
 modular types intended to use all the bits of a full word?
 
-!response 95-09-29
+!response
 
 Consider a 36-bit one's complement machine.  One should be able to
 declare a 36-bit modular type.  For logical operations to make sense,
@@ -41,8 +42,27 @@
 be 0..2**36-1.  This means that the all-ones bit pattern is a
 valid value of the type, and is not reduced via the modulus.
 
-!appendix 96-11-16
+!corrigendum 3.05.04(27)
 
+@dinsa
+For a one's complement machine, the high bound of the base range of a
+modular type whose modulus is one less than a power of 2 may be equal to the
+modulus, rather than one less than the modulus.  It is implementation defined
+for which powers of 2, if any, this permission is exercised.
+@dinst
+For a one's complement machine, modulus values which are not powers of
+2 greater than System.Max_Nonbinary_Modulus may be allowed. It is
+implementation-defined which values greater than System.Max_Nonbinary_Modulus,
+if any, are allowed.
+
+!ACATS test
+
+The implementation permissions are not testable, as there is no way to determine
+the value involved. In addition, most machines are 2's complement, so any tests
+would be of little value.
+
+!appendix
+
 !section RM-3.5.4(07)
 !subject Modular types on 1's complement machines.
 !reference RM95-3.5.4(7)
@@ -161,7 +181,7 @@
 Alternatively, you can just consider it a "nonstandard" integer type,
 defined in package Interfaces, and only available by deriving from
 the type declared in package Interfaces (that is, you can't declare
-one by using a "type U is mod 2**N-1;", but only by using "type U is new 
+one by using a "type U is mod 2**N-1;", but only by using "type U is new
 Interfaces.Unsigned_N;").
 Either is probably OK.
 
@@ -173,7 +193,7 @@
 > bound of the base range".  Whether that is true would depend on
 > what operations are being used, in what order, and possibly where the
 > operations are used.
-> 
+>
 > For instance, the presence of an extra value would eliminate the need to
 > check for overflow on add operations.  However, an occurrence of such a
 > value would probably compare as a zero, meaning its presence could not
@@ -200,25 +220,25 @@
 > OTOH, if the intent is to let implementions do what they want, full range
 > unsigned types will not be very portable.
 
-The intent is that all-ones is a distinct value, greater than 
-any other value (corresponding to 2**N-1), but when an operation 
-would "logically" produce a value that is outside the base range 
-(greater than 2**N-1, or less than zero), the result is "reduced" 
+The intent is that all-ones is a distinct value, greater than
+any other value (corresponding to 2**N-1), but when an operation
+would "logically" produce a value that is outside the base range
+(greater than 2**N-1, or less than zero), the result is "reduced"
 modulo 2**N-1 (hopefully by the hardware!).
 
 Hence 2**N-1 + 1 will give 1, not zero.  Similarly, 0 - 1 will give
 2**N-2, rather than 2**N-1.  This is the intent of 3.5.4(19).
-It is hoped that this semantics will be portable, though portability 
+It is hoped that this semantics will be portable, though portability
 between one's complement machines for this "funny" modular type is not
 a very high priority, in my mind.
 
 > ------
-> 
+>
 > Background:
-> 
+>
 > We are working with Unisys on an Ada 95 implementation for the 2200 series
 > machines.  Those machines are 36-bit, 1's complement machines.
-> 
+>
 > ...
 > We looked at the difficulty of implementing a true full range type.  Most of
 > the arithmetic operations are no problem.  The logical operations are also
@@ -227,13 +247,13 @@
 > be, we could write expensive versions of these operations which would work
 > properly.
 
-Why do you think subtraction would mistreat the largest value?  My 
+Why do you think subtraction would mistreat the largest value?  My
 understanding of the hardware is that it would do the right thing.
 
-Comparison is a different matter.  You need to do an unsigned/logical 
+Comparison is a different matter.  You need to do an unsigned/logical
 comparison.  I would hope that an unsigned/logical comparison would
 not treat all-zeros and all-ones as the same value.  If so, it is
-pretty hard to do meaningful and-ing and or-ing.  
+pretty hard to do meaningful and-ing and or-ing.
 
 -Tuck
 
@@ -853,483 +873,3 @@
 
 ****************************************************************
 
-!section 3.5.4(07)
-!subject One's complement modular type paper
-!reference RM95-3.5.4(07)
-!reference AI95-00095
-!from Bob Duff
-!reference 96-5716.a Robert A Duff 96-10-3>>
-!discussion
-
-I'm forwarding this on behalf of Randy Brukardt.
-
-- Bob
-
-----------------
-
-Bob and Ben:
-
-Here is the draft of the one's complement math paper.  Please comment
-ASAP, as I know time is short before the meeting.
-
-Bob, you can post this on Ada comment if you think it is OK; or
-I'll be happy to do it Monday.  If you have any questions, please ask.
-
-                        Randy Brukardt.
-
----------------------
-Revised comments on AI-95 - One's complement modular types.
-
-I've gotten a lot more information of the problems of one's complement
-modular types.  The result is that more problems with the standard have
-turned up.  I'll start with a summary of our recommendations, then discuss
-all of the issues.  Finally, I've attached a detailed summary of the behavior
-of the U2200 machine and code generators, synthesized from a series of
-E-Mail notes from Ben Hackner at Unisys.  I've trimmed the E-Mail to eliminate
-redunancies, Unisys proprietary information, discussion of compiler bugs,
-and irrelevant chatter.  I am (not Ben) responsible for any errors therin.
-
-Summary:
-
-Should the modulus of the full word modular type on a N bit one's complement
-machine be 2**N or 2**N-1?  (2**N-1)
-If the above answer is 2**N-1,
-        Does that imply that MAX_NONBINARY_MODULUS has to be 2**N-1? (No)
-        Can arithmetic operations produce the so-called negative 0 (the
-        all one's) value?
-                (No - really don't care)
-        Can logical operations produce the negative 0 value? (Yes)
-        Should "not" for the full-word type use the hardware operation,
-        rather than the definition in 4.5.6(5)? (Yes)
-"-" and "not" are defined by the standard to produce results differing
-by 1.  This is natural for 2's complement.  However, for 1's complement,
-these return the same value.  Should these operations follow the
-hardware or the standard definition? (The standard, except for full word
-types, which ought to follow the hardware operation)
-
-Discussion:
-
-The discussion of one's complement modular types in the standard is
-rather confused.  Rather than starting from that, we'll motivate the
-permissions from the actual requirements on a real 1's complement
-machine, the Unisys 2200 series.  The 2200 uses 36 bit, 1's complement
-math.  (No, this discussion is not academic; we're currently building an
-Ada 95 compiler for the 2200 platform.)
-
-Most of the interesting cases appear for the full word modular type.
-Types with smaller modulii are less interesting, so we will concentrate
-on the full word type.  (Note that we assume that the full word type is
-intended to be supported by the standard, although its strict wording
-would practically prevent that on a one's complement machine.  It would
-be easy, but not useful to users, to simply say that the full word type
-is not supported at all.)
-
-The first thing that must be decided is whether the modulus for the full
-word type is 2**36 or 2**36-1.  The 2200's addition and subtraction
-instructions cannot produce the -0 value (indeed, adding zero is how
-2200 code eliminates -0 results from other instructions).  This means
-that the largest value if the modulus is 2**36 cannot be produced by the
-hardware instructions.  Obviously, this cannot be the case, so 2**36-1
-must be chosen.
-
-Now, once the modulus of 2**36-1 is chosen, the standard says that
-Max_NonBinary_Modulus has to have the value 2**36-1.  Of course, modulii
-like 2**36-2 would then have to be supported, and this would be
-difficult.  The reason that Max_Binary_Modulus and Max_NonBinary_Modulus
-are different is to avoid the implementation burden of large nonbinary
-modulii on the (2's complement) compiler implementor.  It would be
-unfair, at least, to require that burden on implementors whose hardware
-happens to be 1's complement.
-
-Therefore, 1's complement machines should have a permission to support
-(one?) value(s) greater than Max_NonBinary_Modulus for the purpose of
-supporting the full word type.  We have chosen Max_Binary_Modulus :=
-2**35, and Max_Nonbinary_Modulus := 2**35-1.  Note that 13.7(24) and
-13.7(25) can be read to support this intepretation (they do not appear
-to prohibit larger modulus values).  However, 3.5.4(7) does prohibit it,
-so this change requires a binding intrepretation.
-
-Now that we've chosen a modulus of 2**36-1 (and asked for permission to
-actually use that value), we can turn to the effects of the operations
-on the type.  What we'd like to have is that the operations closely
-mimic the hardware operations of the target, and even more importantly,
-mimic the similar operation's in the machine's C compiler.
-
-We've already discussed "+" and "-".  "*" also generates a result
-without the -0 value.  "/","Rem", and "Mod" always generate values
-smaller than their dividend, so they cannot produce a 2**36-1 result
-(which would be represented as -0).  The actual divide instruction can
-produce -0, but this can easily be eliminated.
-
-"-" and "not" generate the same hardware instruction for signed integers
-on a one's complement machine.  However, the definitions of these
-operators in the standard (4.5.6(5) and 4.5.4(3) (a note, no less!))
-prevent them from having the same value.  For less than full word types,
-this has no real effect -- indeed, there is no run-time advantage to the
-1's complement version of "-" compared to the 4.5.4(3) definition.  We
-do not believe there is any advantage to ignoring 4.5.4(3) for the 2200.
-
-For a full word type, however, we must be careful.  The load negative
-instruction easily generates -0 from a zero value.  This must be
-eliminated (since it is an incorrect result).
-
-Comparisons also pose no special problems.  If presented a -0 (all ones)
-value, they produce a sensible result.  Equality does not treat 0 and -0
-as the same, and ordering comparisons use the carry flag, so they also
-produce the correct result for -0 operands.
-
-So far, the operations haven't presented any real problem.  However, the
-logical operations do provide problems.  The easiest case is And; if the
-the operands aren't -0, then the result cannot be either.
-
-For Or and Xor, however, the instructions can produce the -0 (all ones
-value) with any number of combinations of operands.  It is easy to
-eliminate the -0 produced, and generate the correct answer for the
-modulus of 2**36-1.  However, this would not be a useful result for the
-full word type.  Since the machine operations can produce the -0 (all
-ones value), and this can be useful, they should be allowed to
-manipulate them.  The C compiler for the 2200 does indeed allow using
-logical operations on the full word.
-
-The permission given in 3.5.4(27) can be useful here, if it was clear
-exactly what it meant.  The first time I asked the question, Tucker
-responded with an answer which essentially stated that no operation
-could produce the -0 (all ones) value.  That is not helpful to the user
-of the 2200 machine, who will want to access ALL of the bits of their
-values, in ANY combination.
-
-Intrepreting 3.5.4(27) is easy compared to the last problem: "Not" has
-altogether the wrong definition for a full word 1's complement type.
-Since the modulus of the full word type is 2**36-1, "not" is defined as
-2**36-2 - X, which provides the wrong answer.  Obviously, we would want
-to use the hardware operation for the "not".  As with "-", "not" X could
-produce the -0 (all ones) value, but unlike "-", we would want to
-produce that as a result -- both for compatibility with other languages,
-and for predictability (it is what the user would expect).
-
-Therefore, we recommend that the permission of 3.5.4(27) be intrepreted
-to provide for logical operations which return values with a "logical
-modulus" of 'Modulus + 1.  This would provide the arithmetic and logical
-operations that the user is expecting, without unduly comprimising the
-standard.
-
-----------------------------------------------------------------
-
-From: Ben Hackner, Unisys
-Date: 8/21/96
-Notes on unsigned behavior on the U2200.
-
-Comparisons using mod 2**36-1:
-
-Notes on eliminating negative zero.  According to Mark:
-
-For UAda, we eliminated -0 for the *, /, and unary -.
-Then we didn't have to worry about -0 and +0 on the comparisons.
-But for SX Ada 95, for signed, we don't eliminate -0 for *, /, and unary -.
-Then we have to make sure the compares test -0 and +0 as equal.
-
-The code for signed integer compare for SX Ada 95:
-b1 := i1=i2;
-  L (load)
-  AN (add negative)
-  JZ (jump zero - where +0 and =0 are the same for this instruction)
-
-Similarly, the code in an IF for signed integer compare for SX Ada 95:
-if i1 = i2
-  L
-  AN
-  JNZ (jump not zero - again +0 and -0 are the same for this instruction)
-
-The code that is generated for unsigned integer for SX Ada 95:
-b1 := i1 = i2;
-  L
-  TE (test equal, where +0 is not equal to -0).
-
-The unsigned skeletons for C (that we are using for SX Ada 95)
-seem to assume that the illegal value of all one bits (-0) will not be stored
-to a variable.
-
--0 can arise from:
--  0 * negative number (which could, of course, be a large positive number)
--  0 / negative number
--  unary minus
--  OR
--  XOR
-
-The UAda skeletons for multiply, divide, and unary minus all added 0 for signed
-integer.
-
-I think to be safe, we may have to eliminate -0 for certain cases for unsigned.
-(This is discussed below.)  Otherwise, the comparisons won't always work.
-
-* * * * *
-
-Add with mod 2**36-1
-
-Add instruction (can't generate -0).
-
-Subtract with mod 2**36-1
-
-Subtract instruction (can't generate -0).
-
-Multiply with mod 2**36-1
-
-Multiply instruction (single * single -> single), with an add of zero
-to eliminate -0.  Apparently the add of zero (after the single precision
-multiply instruction MSI; the add eliminates -0) comes from the C skeleton
-for unsigned.
-
-So multiply seems to be OK for this case.
-
-* * * * *
-
-Divide with mod 2**36-1.
-
-Divide instruction (double via a shift / single -> single).
-There is no add of zero in the skeleton, after the divide.
-
-We need such an add of zero, in order that 0 / Large_Value does not
-produce a -0.  I suppose I should change the skeletons in the back-end
-(like for UAda, I believe).
-
-* * * * *
-
-Unary minus with mod 2**36-1
-
-We originally generated a load negative instruction for this.
-
-This generates a -0 output (illegal unsigned value, of course) for 0 input.
-
-We now are generating:
-        temp := X;
-        if temp /= 0 then
-            temp := -temp;
-        end if;
-        Y := temp;
-which avoids the -0 (at the cost of a couple extra instructions).
-
-* * * * *
-AND mod 2**36-1, mod 7, and mod 16
-
-AND instruction. -0 is not possible from And (unless one of the operands
-was -0).
-
-v2 or v3: OR instruction.  No add of zero.  I think we decided that it is
-necessary.  However, the user is doing the bitwise operation, and I have got
-opinions from people here that we should NOT add zero to eliminate -0.
- (I.e., since it is a bitwise operation, leave the bits as is.)  No checks.
-
-* * * * *
-
-OR & XOR with mod 2**36-1
-
-OR (or XOR) instruction.  No add of zero.  These can generate a -0 from
-operands which are not -0.
-
-I have had discussions with people here in Roseville on our problems
-with OR and XOR possibly returning -0.  We decided that it doesn't make much
-sense to flip -0 to +0, since the user is probably looking at the result as
-a mask, with individual T/F bits.  Flipping all of the True bits to False
-would not work in this case, and the user's logic would fall apart.
-
-Of course, -0 is an illegal value, unless we change the permissions to allow
-the extra value.
-
-If there is no permission for the extra value, -0 has to be eliminated
-by adding zero.
-
-* * * * *
-
-NOT with mod 2**36-1
-
-Load negative instruction.  The load negative can generate a -0.  There
-is no add of zero.
-
-If we decide that there is no permission for the extra value,
-we must either test for a zero input (in text), or change the skeleton to add
-zero (in the back-end).
-
-(Randy's note: "Not" and unary "-" generate the same instruction, which is of
-course correct on a one's complement machine.)
-
-* * * * *
-
-">" with mod 2**36-1
-
-Our generated code does the following:
-
-b1 := v1 > v2;
-
-L      A5,v2       . load v2
-L,U    A0,1        . load True
-ANA    A5,v1       . subtract v1 from v2
-JNC    $+2         . skip next instruction if no carry
-L,U    A0,0        . load False
-
-So if there is no carry on v2 + (-v1) in the hardware, False is returned.
- Note that there is no test equal (where +0 /= -0).  Also, note the use of
-the carry operation instead of the test greater in the hardware (where
-negative numbers are of course less than positive numbers).
-
-Examples:
-
-v1 := 0;
-v2 := 2**36-2; -- octal 777 777 777 775
-v2 + (-v1) = 777 777 777 775 + 777 777 777 777, which of course has a carry.
- So False is returned.
-
-v1 := 0;
-v2 := (-0); -- octal 777 777 777 777 -> say that somehow we got all one bits
-(illegal value)
-v2 + (-v1) = 777 777 777 777 + 777 777 777 777, which has a carry, so False
-is returned.
-
-v1 := (-0);
-v2 := 0;
-v2 + (-v1) = 0 + 0, which has no carry, so True is returned.
-
-* * * * *
-
-Addition with mod 7
-
-type m2 is mod 7;
-q1, q2, q3: m2;
-
-q1 := q2 + q3;
-
-The code that gets generated looks like the following:
-
-        temp := q2 + q3;
-        if temp >= 7 then
-            temp := temp - 7;
-        end if;
-        q1 := Range_Check(temp);
-
-(Randy's note: the Range_Check would be eliminated if checking
-optimizations are on.)
-
-* * * * *
-
-Subtraction with mod 7
-
-For mod 7 subtract q2-q3, the text/code is:
-* Subtract to get intermediate result (to determine if q2>=q3).
-* If q2 >= q3 (i.e., no borrow on subtract, i.e., carry bit set), result is
-  q2-q3.
-* If q2 < q3 (i.e., borrow on subtract, i.e., carry bit not set), result is
-  7-(q3-q2).
-
-* * * * *
-
-OR & XOR with mod 7
-
-The code is similar to addition, above.
-
-* * * * *
-
-REM for mod 2**36-1 and mod 7
-
-Mod_Opr: The code is a divide (DI), with the remainder as the result.
-
-* * * * *
-
-MOD for mod 2**36-1 and mod 7
-
-Modulo_Opr: q2 mod q3.  The code is a divide.
-If the remainder is 0, return 0.
-If the result is positive, return the remainder.
-If the result is negative, return remainder + q3.
-
-* * * * *
-
-Mod 16 tests follow
-
-q2+q3
-
-  Result: (q2+q3) AND 15.
-
-* * * * *
-
-q2-q3
-
-  Result: (q2-q3) AND 15.
-
-* * * * *
-
-q2*q3
-
-  Result: ((q2*q3) + 0) AND 15.
-  The add of zero is the standard elimination of -0 inside the multiply
-  skeleton.
-
-* * * * *
-
-q2/q3
-
-  Result: q2/q3.
-  No add of zero.  No AND.
-
-* * * * *
-
--q2
-
-  Result: (16-q2).
-  (Randy's note: Note that this is cheaper than some sort of mask.  Also
-  note this does not work out the same as a one's complement "-", which
-  is the same as "not".  4.5.4(3) implies this is correct.)
-
-* * * * *
-
-q2=q3
-
-  TE (test equal) instruction.  No checks for +0 or -0.
-
-* * * * *
-
-q2 AND q3
-
-  Result: q2 AND q3.
-
-* * * * *
-
-q2 OR q3
-
-  Result: (q2 OR q3) AND 15.
-
-* * * * *
-
-q2 XOR q3
-
-  Result: (q2 XOR q3) AND 15.
-
-* * * * *
-
-NOT q2
-
-  Result: 15 - q2.
-
-* * * * *
-
-q2 REM q3
-
-  Result: Remainder of the divide q2/q3.
-
-* * * * *
-
-q2 MOD q3
-
-  Result: Modulo_Opr described above.
-  The code is a divide.
-  If the remainder is 0, return 0.
-  If the result is positive, return the remainder.
-  If the result is negative, return remainder + q3.
-
-* * * * *
-
-One weird thing I ran across is section 4.5.1(5) in the standard.  It almost
-seems to be saying that the result of a logical operation is zero or one.
-(I assume they mean that you do a bit by bit operation on zero or one bits,
-and that the result is any possible unsigned value in the range.)  Can you
-clarify this paragraph?
-
-****************************************************************

Questions? Ask the ACAA Technical Agent