!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). **************************************************************** From: John Barnes Sent: Monday, September 29, 2003 6:45 AM Here are some comments on the recent proposals on ... the reduce attribute from one of my colleagues. ------------------------------------------------- Most computers have both an Add instruction and a Subtract instruction (although logically you only need Subtract). Most but not all computers have an "immediate" address mode, where you take one of the operands of the Add or Subtract, provided it is a constant, from the address field of the instruction, rather than from a register or from the memory pointed to by the address field. This has always struck me as a little odd, because, say, for 16-bit numbers, you can add any constant between -32768 and +32767 with an Add instruction, and you can ADD any constant between +32768 and -32767 with a subtract instruction. What a waste! I've always thought that it would be more useful if Add-immediate added a number between 0 and +65535, and subtract-immediate added a number in 0 to -65535, (setting the carry & overflow flags appropriately). This is perfectly meaningful even for SIGNED numbers. Turning now from machines to high-level languages, I should, for example, be able to add, say, +64000 to a signed 16-bit signed integer which happens to be in -32768..-31233 (and get an exception otherwise). This should apply even if the hardware does not support it. The compiler simply has to generate two add or subtract instructions, (or perhaps just one instruction: add -1536 in the above example, and interpret the carry & overflow flags differently?) A similar problem arose in Ada83 when writing a package to manipulate angles in "BAMS", where the requirement is to "wrap round" without overflow, as in Track := Cyclic (Heading + Drift); function "+" (LEFT, RIGHT: WORD) return WORD_ADD is begin return (LEFT, RIGHT); -- A record. end "+"; function Cyclic (ITEM: WORD_ADD) return WORD is begin if ITEM.LEFT >= 0 and then ITEM.RIGHT >= 0 and then ITEM.LEFT + WORD'FIRST + ITEM.RIGHT >= 0 then return ITEM.LEFT + WORD'FIRST + ITEM.RIGHT + WORD'FIRST; elsif ITEM.LEFT < 0 and then ITEM.RIGHT < 0 and then ITEM.LEFT - WORD'FIRST + ITEM.RIGHT < 0 then return ITEM.LEFT - WORD'FIRST + ITEM.RIGHT - WORD'FIRST; end if; return ITEM.LEFT + ITEM.RIGHT; end Cyclic; Here, in the tests, I want to add +32768, which I can just do, by adding -(-32768), written more sensibly as -'FIRST. (In the return statements, I want to add +65536, but this has to be split anyway, to avoid overflow). Of course, in Ada95 I can use modular types for BAMS, provided I view angles as in 0..360 rather than -180..+180, and I get the wrap-round for free. But the problem posed by this AI in Ada95 is similar to the BAMS problem in Ada83 and can be solved by similar code. An argument based on "writing a simulator" is dangerous. (I wrote a simulator for my Elliott 900, in Ada, before the 1983 standard was published. It's on the Internet somewhere.) Many machines have a multiply instruction which returns a product twice as long as the longest add instruction, and hence probably twice as long as the longest Ada type. Making this product visible would certainly make writing simulators easier, especially writing a simulator for a machine on to run on the same machine. (And if this product were made visible to the Ada programmer, we could dispense with fixed-point arithmetic!) And cyclic shifts, and bit-count, and bit-reverse...? So I think we have a slippery slope here. The AI poses a problem no worse than many others. If we are going to fix it, we probably should fix the "add 64000" problem, and should probably consider other problems associated with mixed-mode arithmetic too. **************************************************************** From: Tucker Taft Sent: Monday, September 29, 2003 7:45 AM For what it is worth, I think the "'Reduce" attribute is a good idea. I understand the point being made that there are other similar problems in other places that we aren't fixing, but this particular one comes up very often when using modular types. It is natural to think that conversion might already do this automatically, but that violated a fairly basic assumption that conversions are generally reversible (which is important for "view" conversions), in the absence of a Constraint_Error. [Of course conversion from float to integer bends this rule, but that's the old "exception that proves the rule" I suppose.] In any case, by adding an attribute to do what conversion might otherwise do, we might actually reduce (;-) confusion, or at least misconceptions, about the conversion. We would also make it easier to use modular and signed integer types together, something which today is not so pleasant. **************************************************************** From: Robert I. Eachus Sent: Monday, September 29, 2003 11:39 AM I'm with Tucker here. I'll just add that some of the painful cases involve numeric literals at compile time. For example, I recently found myself needing to write: type Modular is ...; X: Modular; Residue: constant := 16#FFFF_FFFF_FFFF_FFFF# mod Modular'Modulus; ... X := X + Residue; Now of course the interesting case to me was when Residue was small and non-zero. But I had to go through the (potentially error-prone) process of writing a constant of type _universal_integer_ just to get the number I needed. X := X + Modular'Reduce(16#FFFF_FFFF_FFFF_FFFF#); Should generate the same code and do away with the magic. Note that there may be no run-time type that can be used to represent 16#FFFF_FFFF_FFFF_FFFF# or Modular'Modulus, but that is not an issue for the 'Reduce attribute. Either the function can be evaluated at compile time, or it can be converted to a divide operation. Of course, the magic of the reduce attribute comes when it can be replaced by nothing or by a change of sign at compile time: Y: Integer; ... X := X + Reduce(-Y); -- not that a user would write this... Can be converted to a type conversion--but not the Ada defined type conversion--and then subtracting the result from X. So adding this attribute should not involve any code generator changes, but simplifies the process of writing code in some problem cases. Note that this particular case, as I said, is one that really takes a language lawyer to write the code correctly without the attribute, and is easy for anyone with 'Reduce. **************************************************************** From: Randy Brukardt Sent: Monday, September 29, 2003 6:35 PM > Should generate the same code and do away with the magic. Note > that there may be no run-time type that can be used to represent > 16#FFFF_FFFF_FFFF_FFFF# or Modular'Modulus, but that is not an > issue for the 'Reduce attribute. This assumes that 'Modulus is known at compile-time, which isn't true in code-shared generic bodies. ... > So adding this attribute should not involve any code generator > changes, but simplifies the process of writing code in some > problem cases. Note that this particular case, as I said, is one > that really takes a language lawyer to write the code correctly > without the attribute, and is easy for anyone with 'Reduce. But this is still true; the implementation already has some way to handle dynamic 'modulus values if it implements shared generics for modular types. So I'm in favor of the attribute as well. I've run into cases where getting it right is a real pain, and 'Reduce would have eliminated the pain. ****************************************************************