CVS difference for ais/ai-00340.txt

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

--- ais/ai-00340.txt	2003/09/30 02:01:13	1.2
+++ ais/ai-00340.txt	2003/11/20 02:52:54	1.3
@@ -1,16 +1,15 @@
-!standard  3.05.04    (16)                             03-07-31  AI95-00340/01
-!standard  3.05.04    (17)
+!standard  3.05.04    (16)                             03-11-19  AI95-00340/02
 !class amendment 03-07-31
 !status work item 03-07-31
 !status received 03-01-17
 !priority Medium
 !difficulty Easy
-!subject Reduce attribute
+!subject Mod attribute
 
 !summary
 
-A new attribute of modular types is introduced to facilitate
-conversion from negative numbers.
+A new attribute of modular types is introduced to facilitate mixing of signed
+and unsigned numbers.
 
 !problem
 
@@ -19,7 +18,7 @@
 
 !proposal
 
-Add an attribute function, T'Reduce(Val), which is defined for modular
+Add an attribute function, T'Mod(Val), which is defined for modular
 types T. Its parameter is a universal integer. The result is a value
 of type T whose value is (Val mod T'Modulus).
 
@@ -27,8 +26,8 @@
 
 Add after 3.5.4(17):
 
-S'Reduce        S'Reduce denotes a function with the following specification:
-                   function S'Reduce (Arg : universal_integer)
+S'Mod           S'Mod denotes a function with the following specification:
+                   function S'Mod (Arg : universal_integer)
                       return S'Base
                 This function returns Arg mod S'Modulus, as a value of the
                 type of S.
@@ -44,128 +43,149 @@
     Offset    : Integer_32;
     Curr_Addr : Address;
     . . .
-    Curr_Addr := Curr_Addr + Address'Reduce (Offset);
+    Curr_Addr := Curr_Addr + Address'Mod (Offset);
 
 !discussion
 
-Suppose you are writing a simulator for some processor that has 32-bit
-addressing. It seems natural to use a modular type to represent an
-address on the processor:
+It can be difficult or impossible to mix signed and unsigned expressions, yet
+this is a common programming problem. To see just how painful this can be,
+let's consider a particular example:
+
+Suppose we are writing a processor simulator framework. In order to make it
+as general as possible, we make the framework a generic which takes the
+types of the entities as parameters:
+
+    generic
+       type Address_Type is mod <>;
+       type Offset_Type is range <>;
+       type Address_Register_Type is (<>);
+       ...
+    package Simulator_Framework is
+
+       function Address_Register_Value (Addr_Reg : Address_Register_Type)
+            return Address_Type;
+
+       function Calculate_Effective_Address (Addr_Reg : Address_Register_Type;
+            Offset : Offset_Type) return Address_Type;
+
+       ...
+    end Simulator_Framework;
+
+It seems natural to use a modular type to represent an address on the processor,
+while address offsets are clearly of some signed type.
+
+Now, consider the implementation of Calculate_Effective_Address:
+
+    function Calculate_Effective_Address (Addr_Reg : Address_Register_Type;
+        Offset : Offset_Type) return Address_Type is
+        Base_Address : Address_Type :=
+            Address_Register_Value (Addr_Reg);
+    begin
+        return Base_Address + Offset;
+    end Calculate_Effective_Address;
+
+Of course, this is illegal, because Offset_Type and Address_Type are different
+types. So we can replace the return by:
+
+        return Base_Address + Address_Type'Base(Offset);
+
+(We use 'Base to avoid problems if Address_Type has a subtype constraint.)
+But this raises Constraint_Error for negative Offsets. We could try:
+
+        return Base_Address + Address_Type'Base(Offset mod
+                                   Offset_Type'Base(Address_Type'Modulus));
+
+but this raises Constraint_Error if Address_Type'Modulus >
+Offset_Type'Base'Last (which is the most common case). We have to resort to
+an explicit test:
+
+        if Offset >= 0 then
+            return Base_Address + Address_Type'Base(Offset);
+        else
+            return Base_Address - Address_Type'Base(-Offset);
+        end if;
+
+However, if Address_Type'Base'Last < Offset_Type'Last, this will raise
+Constraint_Error for some possible values of Offset. (Remember, we're in a
+generic, so we want any possible combination to work.) So we have to write
+more code to take care of that case:
+
+        if Address_Type'Modulus <= Offset_Type'Last then
+            return Base_Address + Address'Base(Arg mod
+                                     Offset_Type'Base(Address_Type'Modulus));
+        elsif Offset >= 0 then
+            return Base_Address + Address_Type(Offset);
+        else
+            return Base_Address - Address_Type(-Offset);
+        end if;
+
+But this is illegal, because the type of the first test don't match. Moreover,
+
+        if Offset_Type'Base(Address_Type'Modulus) <= Offset_Type'Last then
+
+raises Constraint_Error if the condition would be False, and
+
+        if Address_Type'Modulus <= Address_Type'Base(Offset_Type'Last) then
+
+raises Constraint_Error if the condition would be True. We have to declare
+the largest possible modular type in order to make the check:
+
+    declare
+        type Big_Modular is mod System.Max_Binary_Modulus;
+    begin
+        if Big_Modular'Modulus /= Address_Type'Modulus and then
+           Big_Modular(Address_Type'Modulus) <= Big_Modular(Offset_Type'Last) then
+            return Base_Address + Address'Base(Arg mod
+                                     Offset_Type'Base(Address_Type'Modulus));
+        elsif Offset >= 0 then
+            return Base_Address + Address_Type(Offset);
+        else
+            return Base_Address - Address_Type(-Offset);
+        end if;
+    end;
+
+Even this can fail if the implementation doesn't follow Implementation Advice
+3.5.4(29) and allows an integer bigger than System.Max_Binary_Modulus. To make
+this work in that case would require handling Constraint_Error if it is
+raised by the test. (The exact code needed will be left as an exercise for the
+reader.)
+
+
+The new attribute allows this to be written as:
+
+        return Base_Address + Address_Type'Mod(Offset);
+
+which is many times easier and much more likely to be correct.
+
+
+The Mod attribute can be implemented by just this code (with Base_Address
+replaced by 0). It will never overflow. But a compiler, unlike an Ada
+programmer, can evaluate the first test properly without introducing additional
+types. Moreover, in most circumstances, that test can be evaluated at
+compile-time, and the code can be simplified. Indeed, if Address_Type'Modulus =
+2**Offset_Type'Base'Size, no code at all is needed to implement 'Mod. It seems
+unlikely that a compiler would be smart enough to reduce the entire block of
+code needed in the generic as outlined above to the machine code for:
 
-    type Address is mod 2**32;
-
-Suppose also that this processor has a "repeat" instruction that
-processes elements of an array forward or backward, where the element
-has arbitrary size. It seems natural that one might want to write a
-procedure that interprets the instruction and returns the value that
-will have to be added to each address:
-
-    procedure Interpret_Repeat_Instruction
-                  (...; Offset : out Integer_32) is
-    . . .
-       Offset := [some value extracted from the instruction word];
-       if Reverse_Bit then
-          Offset := -Offset;
-       end if;
-    . . .
-
-The problem is here, once you have the address of the array element
-you're currently working on and the offset, how do you add the offset
-to the current address?
-
-    Curr_Addr : Address;
-    Offset    : Integer_32;  -- output of Interpret_Repeat_Instruction
-    . . .
-    while ... loop
-        ...
-        Curr_Addr := Curr_Addr + Offset;
-    end loop;
-
-The above use of "+" is what you want to do, although it's obviously
-wrong because the types don't match. But the two most obvious
-solutions don't work:
-
-    Curr_Addr := Curr_Addr + Address (Offset);
-
-raises Constraint_Error if Offset is negative (4.6(28)).
-
-    Curr_Addr := Curr_Addr + Address (Offset mod Address'Modulus);
-
-won't work because Address'Modulus doesn't fit in an Integer_32.
+        return Base_Address + Offset;
 
-    Curr_Addr := Curr_Addr + Address
-                              (Integer_64 (Offset) mod Address'Modulus);
 
-will work, but it seems odd to have to go through a 64-bit type when
-what you want is basically a 32-bit operation (adding Offset to
-Curr_Addr). Plus, it won't work if the processor being simulated has
-64-bit addressing, and there is no larger integer type on the host
-machine.
-
-    if Offset < 0
-        then Curr_Addr := Curr_Addr - Address (-Offset);
-        else Curr_Addr := Curr_Addr + Address (Offset);
-    end if;
-
-will work, but do we want to go through all this just to get a simple
-addition operation?
-
-    Curr_Addr := Curr_Addr + Conv_To_Address (Offset);
-
-where Conv_To_Address is an instantiation of Unchecked_Conversion.
-This won't work on a ones-complement machine, and requiring an
-Unchecked_Conversion to convert between two integer types seems
-bizarre anyway.
-
-Note that in the example above:
-
-    Curr_Addr := Curr_Addr + Address'Reduce (Offset);
-
-the 'Reduce operation will be a no-op on most machines.
-
-
-The 'Reduce operation can always be implemented without overflow, no matter
-what the properties of the source and target types. To see this, let S be the
-signed integer source type, and T be the modular target type. Then:
-
-    if T'Modulus <= S'Base'Last then
-        Result := T'Base(Arg mod S'Base(T'Modulus));
-    elsif Arg >= 0 then
-        Result := T'Base(Arg);
-    else
-        Result := T'Base'(0) - T'Base(-Arg);
-    end if;
-
-Never overflows. Note that the first condition can't actually be written in Ada,
-as if it is False, you'll get an error as the value of T'Modulus is out of range
-for the type S'Base. But there is no problem for a compiler to make this
-calculation and generate the appropriate code (which, if T'Modulus =
-2**S'Base'Size, can simplified to no code at all).
-
-
 !corrigendum 03.05.04(16)
 
 @drepl
 For every modular subtype S, the following attribute is defined:
 @dby
 For every modular subtype S, the following attributes are defined:
-
-!corrigendum 03.05.04(17)
 
-@dinsa
-S'Modulus
-@xindent<S'Modulus yields the modulus of the type of S, as a value of
-the type @i<universal_integer>.>
-@dinss
-S'Reduce
-@xindent<S'Reduce denotes a function with the following specification:>
-@xcode<        @b<function> S'Reduce (@i<Arg> : @i<universal_integer>)
+S'Mod
+@xindent<S'Mod denotes a function with the following specification:>
+@xcode<        @b<function> S'Mod (@i<Arg> : @i<universal_integer>)
              @b<return> S'Base>
 @xindent<This function returns @i<Arg> @b<mod> S'Modulus.>
 
 !ACATS test
 
-Add an ACATS test checking the presence and operation of the Reduce attribute.
+Add an ACATS test checking the presence and operation of the Mod attribute.
 
 !appendix
 

Questions? Ask the ACAA Technical Agent