Version 1.1 of ais/ai-00340.txt

Unformatted version of ais/ai-00340.txt version 1.1
Other versions for file ais/ai-00340.txt

!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)
Replace the paragraph:
For every modular subtype S, the following attribute is defined:
by:
For every modular subtype S, the following attributes are defined:
!corrigendum 03.05.04(17)
Insert after the paragraph:
S'Modulus
S'Modulus yields the modulus of the type of S, as a value of the type universal_integer.
the new paragraphs:
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.
!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).

****************************************************************

Questions? Ask the ACAA Technical Agent