Version 1.5 of ais/ai-00186.txt

Unformatted version of ais/ai-00186.txt version 1.5
Other versions for file ais/ai-00186.txt

!standard 03.05.04 (14)          04-04-01 AI95-00186/04
!standard 03.04 (9)
!class binding interpretation 99-03-21
!status work item 97-03-19
!status received 97-03-19
!priority Low
!difficulty Medium
!subject Range of root_integer
!summary
The base range of root_integer is extended to include extra positive values corresponding to modulartypes. The evaluation of expressions of type root_integer is defined to be a bounded error in some cases where an implementation cannot possibly find a type to perform the evaluation at run- time. In other cases, such an evaluation is safe and portable, even in generics with formal discrete types.
!question
Consider for example:
generic type T is (<>); package P is ... end P;
package body P is B : Boolean := T'Pos (T'Last) = 3; end P;
Is the evaluation of the expression allowed to raise Constraint_Error if P is instantiated with the largest modular type? (No.)
!recommendation
The base range of root_integer shall include at least System.Min_Int .. M where M is the maximum of System.Max_Int and System.Max_Nonbinary_Modulus - 1.
Let T be a discrete type. It is a bounded error to evaluate an expression of type root_integer if it contains simple_expressions of types T or T'Base unless:
o all simple_expressions of a discrete type are of types T, T'Base or
universal_integer; and
o all subexpressions of type universal_integer or root_integer, as well as
the result of applying the T'Pos attribute to all subexpressions of types T or T'Base, belong to the range:
o System.Min_Int .. System.Max_Int if T is a signed integer type; or o 0 .. System.Max_Nonbinary_Modulus - 1 if T is an enumeration or a modular type.
The possible outcomes are that the expression is evaluated correctly, Constraint_Error is raised, or Program_Error is raised.
<<Author's note: for enumeration types, the above rules work well in the absence of an enumeration representation clause. However, if there is a clause that gives negative representations for some literals, using a modular type for internal computations won't work. Do we care? I want to make sure that Wide_Wide_Character works, but enumeration representation clauses for huge enumeration types are not too exciting.>>
!wording
See !recommendation. I'll write the words if we agree on the intent.
!discussion
The main problem dealt with in this is that, because of the preference rule for root_integer (8.6(29)) some expressions are evaluated at run-time using root_integer. But in practice there is no good choice of range for root_integer because it would ideally have to cover three ranges:
System.Min_Int .. System.Max_Int -- For signed integer types. 0 .. System.Max_Binary_Modulus - 1 -- For binary modular types. 0 .. System.Max_Nonbinary_Modulus - 1 -- For nonbinary modular types.
On a typical 32-bit machine, these ranges might be:
-2 ** 31 .. 2 ** 31 - 1 0 .. 2 ** 32 - 1 0 .. 2 ** 32 - 2
It is clear that a 33-bit integer would be needed to cover their union. And even such a type would not be able to represent T'Modulus for the largest modular type. At any rate, we don't want to require implementations to have to do multiple precision in the root_integer arithmetic.
What we are doing here is essentially to specify circumstances under which an implementation is _not_ allowed to raise Constraint_Error during evaluation of an expression of type root_integer. This is phrased in terms of a bounded error, because we want implementations to be able to detect anomalies by raising an exception, or to do the correct evaluation, but we don't want to allow it to go berserk. So this is not an erroneous situation.
From the user's perspective, this AI guarantees that there is a class of expressions which can always be evaluated safely (i.e., without raising an exception) and portably, even in a generic with a formal discrete type. The expression mentioned in the question is an example of this case. On the other hand, evaluating the expression:
T'Modulus > 3
is a bounded error if T is the largest modular type because T'Modulus cannot in general be represented using root_integer. On the other hand, the expression:
T'Last >= 3
is safe.
The restriction on the expressions are intended to make it possible to evaluate expressions of type root_integer using the largest signed integer type (if T is signed) or the largest unsigned integer type (if T is modular or enumeration). The rules ensure that an implementation doesn't have to handle expressions involving mixed discrete types, as in:
Signed_Int'Pos (Signed_Int'First) + Unsigned_Int'Pos (Unsigned_Int'Last)
because such expressions could require multiple precision. An implementation could just recognize this situation (at compile-time) and raise Program_Error. Or it could use a signed integer and raise Constraint_Error on the conversion of Unsigned_Int'Last.
For macro-expanded generics, the nature of actual types is always known in an instance, so it should be straightforward to generate signed or unsigned arithmetic as needed. For shared generics the situation is a bit more complicated (as usual) but a possible implementation technique is to generate both signed and unsigned code, and select the appropriate code based on the nature of the type.
Finally this AI revises the base range of root_integer. It is clear that we want to allow extra positive values to support modular and enumeration types, so the range System.Min_Int .. System.Max_Int is too restrictive. root_integer must include all the values up to System.Max_Nonbinary_Modulus - 1.
Also, the base range of root_integer is not prevented from containing extra (negative or positive) values, to help support nonstandard integer types. There is no point in allowing nonstandard integer types if the implementations are then restricted from using them for root_integer computations. There might of course be implementation-defined restrictions in the case, but the language should not get in the way.
!ACATS Test
ACATS C-Tests should be created to check that a generic instantiated with the largest modular type does not overflow. The other cases are implementation-defined and thus are difficult to test.
!appendix

!section 3.5.4(14)
!subject Range of root_integer
!reference RM95 3.5.4(14)
!from Pascal Leroy 97-03-10
!reference 97-15727.g Pascal Leroy 97-3-10>>
!discussion

The referenced paragraph defines the base range of root_integer as
System.Min_Int .. System.Max_Int.  This range covers all signed integer types,
but it is possible for modular types to exceed System.Max_Int.  Because
root_integer is the type used at runtime for many computations, the fact that
it doesn't cover all standard integer types has surprising consequences.

Consider for example:

    generic
       type T is (<>);
    package P is
       ...
    end P;

    package body P is
       B : Boolean := T'Pos (T'Last) = 3;
    end P;

Assume a 32-bit architecture, where Min_Int is -2 ** 31, Max_Int is 2 ** 31 -
1, Max_Binary_Modulus is 2 ** 32, and Max_Nonbinary_Modulus is 2 ** 32 - 1.
 Instantiating P with any signed integer type works fine, but if it is
instantiated with a modular type with 'Modulus greater than 2 ** 31, the
elaboration of B raises Constraint_Error because the result of the attribute
Pos exceeds Max_Int.  This makes it very hard to write a generic that works
for any discrete type.

In fact, it is even very hard to write a generic that works for any modular
type.  Consider a second example:

   generic
      type T is mod <>;
   procedure P;

   procedure P is
   begin
      if T'Modulus > 3 then
         ...
      end if;
   end P;

The conversion of T'Modulus to root_integer raises Constraint_Error.

_____________________________________________________________________
Pascal Leroy                                    +33.1.30.12.09.68
pleroy@rational.com                             +33.1.30.12.09.66 FAX


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


Questions? Ask the ACAA Technical Agent