!standard 3.05.04 (16) 03-07-31 AI95-00340/01 !standard 3.05.04 (17) !class amendment 03-07-31 !status work item 03-07-31 !status received 03-01-17 !priority Medium !difficulty Easy !subject Reduce attribute !summary A new attribute of modular types is introduced to facilitate conversion from negative numbers. !problem There is no straightforward way to perform arithmetic on an value of a modular type and a negative value of a signed integer type. !proposal Add an attribute function, T'Reduce(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). !wording Add after 3.5.4(17): S'Reduce S'Reduce denotes a function with the following specification: function S'Reduce (Arg : universal_integer) return S'Base This function returns Arg mod S'Modulus, as a value of the type of S. The words "attribute is" would have to be changed to "attributes are" in 3.5.4(16). !example type Integer_32 is range -(2**31) .. 2**31 - 1; type Address is mod 2**32; Offset : Integer_32; Curr_Addr : Address; . . . Curr_Addr := Curr_Addr + Address'Reduce (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: 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. 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.> @dinss S'Reduce @xindent @xcode< @b S'Reduce (@i : @i) @b S'Base> @xindent @b S'Modulus.> !ACATS test Add an ACATS test checking the presence and operation of the Reduce attribute. !appendix !topic Proposal: 'Reduce attribute of modular types !reference RM95 3.5.4 !from Adam Beneschan 01-17-03 !summary A new attribute of modular types is introduced to facilitate conversion from negative numbers. !problem There is no straightforward way to perform arithmetic on an value of a modular type and a negative value of a signed integer type. !proposal Add an attribute function, T'Reduce(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). !wording Add after 3.5.4(17): S'Reduce S'Reduce denotes a function with the following specification: function S'Reduce (Arg : universal_integer) return S'Base This function returns Arg mod S'Modulus, as a value of the type of S. The words "attribute is" would have to be changed to "attributes are" in 3.5.4(16). !example type Integer_32 is range -(2**31) .. 2**31 - 1; type Address is mod 2**32; Offset : Integer_32; Curr_Addr : Address; . . . Curr_Addr := Curr_Addr + Address'Reduce (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: 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. 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. **************************************************************** From: Robert Dewar Sent: Sunday, January 19, 2003 10:25 AM I find Reduce a bit odd here as the name (though I understand the reasoning, I find it too "mathematical" :-) Not sure I can find an alternative that I like S'Convert perhaps? I agree this is nice to have, I just showed a customer the other day how to use UC to solve the problem, which is definitely not very pleasant. **************************************************************** From: Robert A. Duff Sent: Monday, January 20, 2003 1:07 PM The root of the problem is that normal type conversions from signed integer to modular integer check that the source is in range of the target. This is a huge mistake, because every *other* operation of modular types wraps around. It seems clear to me that M(Integer'(-1)) ought to return 2**32 (if M'Modulus = 2**32). Instead, it raises C_E. Unforunately, that was not clear to me during the language design. :-( Randy will no doubt point out that wrap-around semantics is evil. I have some symphathy with that view, but we're not going to change *that*. Given that we have chosen modular semantics for unsigned types, we should be consistent. Perhaps now is the time to change the semantics of type conversions. Surely programs do not *depend* on getting C_E -- they do it by accident. Surely it is better to make type_conversions do what they should, instead of adding a new type-conversion-like feature called T'Convert (or T'Reduce) that does what type_conversions ought to have done in the first place. > I agree this is nice to have, I just showed a customer the other day how > to use UC to solve the problem, which is definitely not very pleasant. Yes, especially when it's a generic formal type, so you don't necessarily know how to create a correct-sized type to Unchecked_Convert from. **************************************************************** From: Robert Dewar Sent: Monday, January 20, 2003 3:34 PM Well we discussed EXACTLY this point during the language design (meeting in Sherwood Forest), and decided quite deliberately, taking all the facts into account, that the decision made was the better one. I don't see anything that has changed the situation from when that decision was made (a decision which incidentally my memory says Bob agreed with). I understand perfectly the downside of the decision we made -- indeed we understood it at the time -- but to say that this was a huge mistake is a bit extreme. The (still very strong and decisive) argument is that to follow the path Bob suggests creates a very non-uniform and peculiar semantics for these conversions (note that there is nothing wrong from this point of view with the basic idea of wrap around arithmetic, but extending it implicitly to the conversions would indeed be very odd). The attribute is a good suggestion, and I think that if someone had suggested the attribute at the meeting, it would have a) been accepted as a good idea b) made it even clearer that the semantic choice for conversion was the right one, since it removes the one obvious disadvantage of the choice). **************************************************************** From: Tucker Taft Sent: Monday, January 20, 2003 3:57 PM I sort of hate to admit it ;-), but my memory jibes pretty well with Robert's. I remember a conversion applied to an [in-]out parameter was an example of a place where having the conversion not be value preserving was felt to be too confusing. I agree it is annoying, but whenever I want conversion to do the modular reduction, I know it, and wish I had a better, explicit way to do it. So I would favor the attribute as well. T'Reduce(X) should be essentially equivalent to T(X mod T'Modulus), but without any overflow possible. I suppose we could even rule by fiat that such a conversion of a "mod" never overflows if the result is in the range of the target type, and be done with it, somewhat in the spirit of the conversion applied to a fixed-point multiply. But that seems pretty groddy... **************************************************************** From: Adam Beneschan Sent: Monday, January 20, 2003 4:08 PM Assuming there's no user-defined "mod" function to get in the way, that is . . . **************************************************************** From: Robert A. Duff Sent: Monday, January 20, 2003 4:25 PM > Well we discussed EXACTLY this point during the language design (meeting > in Sherwood Forest), and decided quite deliberately, taking all the facts > into account, that the decision made was the better one. I don't see anything > that has changed the situation from when that decision was made (a decision > which incidentally my memory says Bob agreed with). Yes, I agreed with that decision (as I said in my earlier e-mail). I think I even argued strongly for it. I was wrong, I now believe. The only thing that has changed is "experience". >... I understand perfectly > the downside of the decision we made -- indeed we understood it at the > time -- but to say that this was a huge mistake is a bit extreme. OK, maybe not "huge", but still a mistake. ;-) Tucker mentions in another note the issue of 'in out' conversions. Yes, that could cause surprise. But to me that just seems like one case out of many -- wrap-around arithmetic *is* surprising, if you don't pay attention. > The (still very strong and decisive) argument is that to follow the path > Bob suggests creates a very non-uniform and peculiar semantics for these > conversions (note that there is nothing wrong from this point of view > with the basic idea of wrap around arithmetic, but extending it implicitly > to the conversions would indeed be very odd). I don't find it odd. It seems no different from the fact that when you convert float to integer you lose information. > The attribute is a good suggestion, and I think that if someone had > suggested the attribute at the meeting, it would have > > a) been accepted as a good idea > > b) made it even clearer that the semantic choice for conversion was the > right one, since it removes the one obvious disadvantage of the choice). I predict that if T'Convert/T'Reduce exists, people would *never* want to use a type_conversion from signed to modular; the attribute is always better. That seems fishy to me. Why have extra features? **************************************************************** From: Robert I. Eachus Sent: Monday, January 20, 2003 9:53 PM Tucker Taft wrote: > T'Reduce(X) should be essentially equivalent to > T(X mod T'Modulus), but without any overflow possible. > I suppose we could even rule by fiat that such a conversion > of a "mod" never overflows if the result is in the range > of the target type, and be done with it, somewhat > in the spirit of the conversion applied to a fixed-point multiply. > But that seems pretty groddy... I like the idea of having an attribute like this. I have written T(X mod T'Modulus) on occasion, but never without worrying about what the compiler might do. Of course if you know that you are converting a 32-bit signed number to a 32-bit modular type, the unchecked conversion works, but again there is too much extra thinking required. (Remember Tuck's little tests? The Unchecked_Conversion is a nasty one. It works correctly if the representation of the signed type is 32-bits, even if the range is smaller. But the unsigned type has to be explicitly declared as ...is mod 2**32; --or some other representation of that modulus--for the conversion to be correct.) One other advantage of having a 'Reduce attribute. The standard can define the cases where it must work without reference to static and non-static subtypes and values. That is the problem with the T(X mod T'Modulus) case. I can't imagine a compiler nasty enough to say, "A ha! The subtype of X (or the subtype T) is non-static here, so I don't have to get this correct." But since you normally want T'Modulus to be greater than System.Max_Int, the possibility exists, even though in the normal case no code needs to be generated. T'mod might be an alternative name--we already have attributes with reserved words as their names. But I think reduce is fine. (Of course now I want a native unbounded rational type with a 'Reduce that insures that the numerator and denominator are relatively prime--but I'll wait for the next revision to ask for that.) **************************************************************** From: Craig Carey Sent: Tuesday, January 21, 2003 5:49 PM I hope that "mod" itself is improved and that no attribute ever appears. I.e. the statement: C := A mod B is interpreted by the compiler in this way: (1) There are imagined to be two different types of "mod" operator in Ada. One returns the type of A, and the other returns the type of B. (2) The compiler gets it right when choosing between the two. That presumably corresponds to the style of mathematics. Mathematical statements are briefer when lacking type checking. If Ada reverses the natural ideal (when it is close to maths), of minimizing the type checking then there is some other principle around, e.g. having user program start to run correctly quicker. If the idea of type checking is set aside and also safety is made an aim, then presumably the current feature of 'mod' crashing could be fixed. (I agree with Mr Duff) people might actually use a "X'Mod". It can be a problem when users' are sure that the mod operator should have been fixed. An attribute of the proposed attribute is that it is a mistake to introduce it and the purpose was to avoid correcting a mistake elsewhere. That mismatches with the motive of taking advantage of Ada's tough checking to help guarantee that it crashes less. Then users might want to refuse to use the new X'This_Mod_Doesnt_Crash(Q) feature. Suppose the X'Mod attribute was introduced and later the 'mod' operator was made brighter so it didn't crash so often when otherwise being very close to getting the correct answer out. If the attribute is introduced then it can be followed later by arguments saying that it ought be removed. In mathematics, z := f(x,y), is to be viewed with the internals of f(x,y) being ignored. Of course, raising an exception is not obviously an hidden internal. But it could be if: (1) changing 'mod' did not result in a change to the way that users' programs behaved. (2) Warning messages could be added. Possibly the presence of warning messages could get the revision to the "mod" operator past this test: a fixup "is likely to fix more bugs than it creates" AARM 4.6(71.c): 4.6 Type Conversions ... | Because sliding of array bounds is now provided for operations | where it was not in Ada 83, programs that used to raise | Constraint_Error might now continue executing and produce a | reasonable result. This is likely to fix more bugs than it | creates. Probably the statement is not really true, but merely likely to be true, or likely to be believed. I.e. no checking of tens of millions of lines of code occurred. In the case of "mod" a better alternative than guessing on probabilities may be to require that in a few spots, vendors have their compilers produce warning messages. Fully automatic selection of type is not merely corresponding with mathematics, but Ada already does that in some cases: function "mod" (A : A_Type; B : B_Type) return A_Type is ... function "mod" (A : A_Type; B : B_Type) return B_Type is ... ... C := A mod B; I can't tell but I am interested if some of the advocacy for a new attribute was running like this: (1) Attributes are attribute-ishy; and (2) The "mod" operator currently isn't, and (3) there is aim to keep the mod operator from being of that 'type'. The 3rd is a weak spot in that (possibly not used) argument since it is not resting on some principle. Fixing up mod can be follow from a principle of keeping the type checking be minimal. Ada has an idea overloading so a solution is define at least another mod (which still saying it has just one). ****************************************************************