Unconstrained base subtype questions

Unconstrained base subtype questions

[Alex Mentis]

The following does not cause a constraint error in my version of GNAT
on my system:

...

Integer_Result := (Integer'Last + Integer'Last) / 2;

...


If I understand correctly, this is because the Integer operators are
defined for operands of type Integer'Base, which is an unconstrained
subtype and allows the operands to be stored in extended-length
registers so that intermediate values in calculations do not overflow.

My questions are:

1) Do I understand correctly what's going on?

2) Does the language make any guarantees about preventing spurious
overflow, or am I just getting lucky with my compiler/architecture? If
guarantees are made by the language, what are they?

Thanks,
Alex

Re: Unconstrained base subtype questions

[Ludovic Brenta]

"Alex Mentis" <foo@invalid.invalid> writes:
> The following does not cause a constraint error in my version of GNAT
> on my system:
>
> ...
>
> Integer_Result := (Integer'Last + Integer'Last) / 2;
>
> ...
>
>
> If I understand correctly, this is because the Integer operators are
> defined for operands of type Integer'Base, which is an unconstrained
> subtype and allows the operands to be stored in extended-length
> registers so that intermediate values in calculations do not overflow.
>
> My questions are:
>
> 1) Do I understand correctly what's going on?

I suspect you compiled without the secret -gnato option, which enables
overflow checking.  Yes, by default GNAT omits these checks and is
therefore not strictly speaking a compliant Ada compiler.

With gnat-4.4 I even get:

$ gnatmake -g -O2 -gnato f
gcc-4.4 -c -g -O2 -gnato f.adb
f.adb:4:11: warning: value not in range of type "Standard.Integer"
f.adb:4:11: warning: "Constraint_Error" will be raised at run time
gnatbind -x f.ali
gnatlink f.ali -g

> 2) Does the language make any guarantees about preventing spurious
> overflow, or am I just getting lucky with my compiler/architecture? If
> guarantees are made by the language, what are they?

I'm not sure what you mean by "spurious overflow" (as opposed to
"overflow") but:

- static constants must be computed without any overflow checks at
  compile time (ARM 4.9(33)); this means that intermediate values can be
  arbitrarily large or small (ARM 4.9(35/2)) but the final result must
  be in the range specified for the constant.  If not, the compiler
  reports an error.

- during execution, there are two kinds of overflow checks.
  Intermediate results must lie within the "base range of the type"
  which, for all intents and purposes, is the full range of
  [[Long_]Long_]Integer (ARM 4.5.4(20)).  So, if an intermediate value
  exceeds e.g. Integer'Last you get a Constraint_Error.

- At the end of a computation, the result is either assigned to a
  variable, a constant, or a subprogram parameter.  This assignment
  involves a conversion to the target subtype, the range of which may be
  smaller than the base range of the type, and this conversion includes
  an overflow check (ARM 4.6(51/2)) which must raise Constraint_Error if
  it fails (ARM 4.6(57)).

For example:

type T is range 1 .. 10;
A : T := 95 - 90; -- OK

See also
http://en.wikibooks.org/wiki/Ada_Programming/Type_System#Elaborated_Discussion_of_Types_for_Signed_Integer_Types

HTH

-- 
Ludovic Brenta.

Re: Unconstrained base subtype questions

[Alex Mentis]

Ludovic Brenta wrote:

> "Alex Mentis" <foo@invalid.invalid> writes:
> > The following does not cause a constraint error in my version of
> > GNAT on my system:
> > 
> > ...
> > 
> > Integer_Result := (Integer'Last + Integer'Last) / 2;
> > 
> > ...
> > 
> > 
> > If I understand correctly, this is because the Integer operators are
> > defined for operands of type Integer'Base, which is an unconstrained
> > subtype and allows the operands to be stored in extended-length
> > registers so that intermediate values in calculations do not
> > overflow.
> > 
> > My questions are:
> > 
> > 1) Do I understand correctly what's going on?
> 
> I suspect you compiled without the secret -gnato option

No, I compiled with that option enabled. It still ran happily and
produced the correct output.

> > 2) Does the language make any guarantees about preventing spurious
> > overflow, or am I just getting lucky with my compiler/architecture?
> > If guarantees are made by the language, what are they?
> 
> I'm not sure what you mean by "spurious overflow" (as opposed to
> "overflow") but:

By "spurious overflow" I mean overflow from intermediate results of a
calculation in which the correct final result is actually still within
the type constraints.
 
> - during execution, there are two kinds of overflow checks.
>   Intermediate results must lie within the "base range of the type"
>   which, for all intents and purposes, is the full range of
>   [[Long_]Long_]Integer (ARM 4.5.4(20)).  So, if an intermediate value
>   exceeds e.g. Integer'Last you get a Constraint_Error.

Well, that's my question. In the calculation above, I clearly have an
intermediate value that exceeds Integer'Last. And I tried something
similar with Long_Long_Integer and still couldn't get an overflow
error! So what is the actual limit on the base range of the type? Is it
language defined, compiler defined, hardware defined, none of the above?

Re: Unconstrained base subtype questions

[Ludovic Brenta]

"Alex Mentis" <foo@invalid.invalid> writes:
>> - during execution, there are two kinds of overflow checks.
>>   Intermediate results must lie within the "base range of the type"
>>   which, for all intents and purposes, is the full range of
>>   [[Long_]Long_]Integer (ARM 4.5.4(20)).  So, if an intermediate value
>>   exceeds e.g. Integer'Last you get a Constraint_Error.
>
> Well, that's my question. In the calculation above, I clearly have an
> intermediate value that exceeds Integer'Last. And I tried something
> similar with Long_Long_Integer and still couldn't get an overflow
> error! So what is the actual limit on the base range of the type? Is it
> language defined, compiler defined, hardware defined, none of the above?

It is both language- and implementation-defined.  I gave you the
references to what the language says.  The implementation-defined part
is the "base range of the type"; a sane implementation would choose a
range that matches the hardware.

The reason why you did not get an overflow at runtime is because your
computation did not take place at run time.  The GNAT warnings and
Constraint_Error that I reported earlier were for the case of a run-time
computation similar to what Simon and Randy said.

-- 
Ludovic Brenta.

Re: Unconstrained base subtype questions

[Adam Beneschan]

On Mar 31, 2:36 pm, Ludovic Brenta <ludo...@ludovic-brenta.org> wrote:

> > Well, that's my question. In the calculation above, I clearly have an
> > intermediate value that exceeds Integer'Last. And I tried something
> > similar with Long_Long_Integer and still couldn't get an overflow
> > error! So what is the actual limit on the base range of the type? Is it
> > language defined, compiler defined, hardware defined, none of the above?
>
> It is both language- and implementation-defined.  I gave you the
> references to what the language says.  The implementation-defined part
> is the "base range of the type"; a sane implementation would choose a
> range that matches the hardware.

However, the language does specify that whatever base range the
implementation chooses, Integer'Last will be the top of the range.
It's not legally possible for the "base range" of Integer to include
values that are larger than Integer'Last.  (Note that that applies
only to Standard.Integer; it "should"
apply to other predefined signed integer types in Standard, but it
doesn't apply to user-defined integer types.)

The language does say, though (3.5.4(24)), that implementations don't
need to raise Constraint_Error for arithmetic operations on signed
integers as long as they produce correct results, even if intermediate
results are outside the base range---that's what Randy was referring
to, I think.

                             -- Adam

Re: Unconstrained base subtype questions

[Adam Beneschan]

On Mar 31, 1:25 pm, "Alex Mentis" <f...@invalid.invalid> wrote:
> The following does not cause a constraint error in my version of GNAT
> on my system:
>
> ...
>
> Integer_Result := (Integer'Last + Integer'Last) / 2;
>
> ...
>
> If I understand correctly, this is because the Integer operators are
> defined for operands of type Integer'Base, which is an unconstrained
> subtype and allows the operands to be stored in extended-length
> registers so that intermediate values in calculations do not overflow.

No, it's because all the operands are known at compile time and the
compiler can just figure out what the answer is.  There is no question
about "where operands are stored" or about how registers are used.
The code for this statement should not perform any addition or
division (or shift) operations.  See 4.9.

                            -- Adam

Re: Unconstrained base subtype questions

[Simon Wright]

"Alex Mentis" <foo@invalid.invalid> writes:

> The following does not cause a constraint error in my version of GNAT
> on my system:
>
> ...
>
> Integer_Result := (Integer'Last + Integer'Last) / 2;
>
> ...
>
>
> If I understand correctly, this is because the Integer operators are
> defined for operands of type Integer'Base, which is an unconstrained
> subtype and allows the operands to be stored in extended-length
> registers so that intermediate values in calculations do not overflow.
>
> My questions are:
>
> 1) Do I understand correctly what's going on?
>
> 2) Does the language make any guarantees about preventing spurious
> overflow, or am I just getting lucky with my compiler/architecture? If
> guarantees are made by the language, what are they?

That's a compile-time calculation, and any Ada compiler should work it
out using infinite-precision arithmetic.

   with Ada.Text_IO; use Ada.Text_IO;
   procedure Very_Large is
      Integer_Result : Integer;
   begin
      Integer_Result := 10**128 / 10**127;
      Put_Line (Integer'Image (Integer_Result));
   end Very_Large;

   $ gnatmake very_large.adb
   gcc -c very_large.adb
   gnatbind -x very_large.ali
   gnatlink very_large.ali
   $ ./very_large
    10

As against

   with Ada.Text_IO; use Ada.Text_IO;
   procedure Very_Large is
      Integer_Result : Integer;
   begin
      Integer_Result := Integer'Last;
      Integer_Result := Integer_Result + Integer'Last;
      Integer_Result := Integer_Result / 2;
      Put_Line (Integer'Image (Integer_Result));
   end Very_Large;

   $ gnatmake very_large.adb
   gcc -c very_large.adb
   very_large.adb:6:37: warning: value not in range of type "Standard.Integer"
   very_large.adb:6:37: warning: "Constraint_Error" will be raised at run time
   gnatbind -x very_large.ali
   gnatlink very_large.ali
   $ ./very_large
   raised CONSTRAINT_ERROR : very_large.adb:6 overflow check failed

Note that the compiler knew that was going to happen. If the overflow
wasn't visible at compile time, you'd have to tell GNAT to perform
run-time integer overflow checks using -gnato. Other compiler writers
may have different views about whether run-time integer overflow checks
should be off by default :-)

Re: Unconstrained base subtype questions

[Randy Brukardt]

"Alex Mentis" <foo@invalid.invalid> wrote in message 
news:in2nv8$v3e$1@dont-email.me...
> The following does not cause a constraint error in my version of GNAT
> on my system:
>
> ...
>
> Integer_Result := (Integer'Last + Integer'Last) / 2;
>
> ...
>
>
> If I understand correctly, this is because the Integer operators are
> defined for operands of type Integer'Base, which is an unconstrained
> subtype and allows the operands to be stored in extended-length
> registers so that intermediate values in calculations do not overflow.

Right. In this case, the compiler is probably just doing constant folding 
using unlimited precision numbers. Does the same thing happen when you use 
variables??

   Last : Integer := Integer'Last;

   Result : Integer :=  (Last + Last)/2;

(Even better, write a function that returns Integer'Last and call it; the 
ACATS uses this technique to reduce optimization of expressions.)

> My questions are:
>
> 1) Do I understand correctly what's going on?

I think so.

> 2) Does the language make any guarantees about preventing spurious
> overflow, or am I just getting lucky with my compiler/architecture? If
> guarantees are made by the language, what are they?

The language says effectively that you either will get the right answer or 
Constraint_Error. But it makes no guarantees about which you will get for 
values outside of the result subtype. So that is compiler-dependent.

The intent is to be able to use the hardware effectively. To take an 
example, older Intel X86 processors did all of their floating point 
calculations in 80-bit registers. The only certain way to use fewer bits was 
to store the register into memory and then reload it (which forced the 
needed rounding). Needless to say, this doesn't help performance!

In something like:
    F := (A * B) / (C * D);
you would have two extra store/load pairs. That's awful, thus the rule 
allowing extra precision.

For float types, Ada actually has an attribute to explicitly discard extra 
precision (S'Machine). For integer types, you'd have to explicitly store the 
subexpression into an object and do a validity test on it. (It's not clear 
to me that a type conversion alone would guarantee a check for a type like 
Integer where Integer has the same range as Integer'Base. The validity rules 
always allow delaying a constraint check, so only 'Valid is certain to smoke 
out overflowing values.)

But both of these operations are expensive, and should only be used when 
absolute portability is needed.

                                  Randy.

Re: Unconstrained base subtype questions

[Alex Mentis]

Randy Brukardt wrote:

> "Alex Mentis" <foo@invalid.invalid> wrote in message
> news:in2nv8$v3e$1@dont-email.me...
> > The following does not cause a constraint error in my version of
> > GNAT on my system:
> > 
> > ...
> > 
> > Integer_Result := (Integer'Last + Integer'Last) / 2;
> > 
> > ...
> > 
> > 
> > If I understand correctly, this is because the Integer operators are
> > defined for operands of type Integer'Base, which is an unconstrained
> > subtype and allows the operands to be stored in extended-length
> > registers so that intermediate values in calculations do not
> > overflow.
> 
> Right. In this case, the compiler is probably just doing constant
> folding using unlimited precision numbers. Does the same thing happen
> when you use variables??
> 
>   Last : Integer := Integer'Last;
> 
>   Result : Integer :=  (Last + Last)/2;
> 
> (Even better, write a function that returns Integer'Last and call it;
> the ACATS uses this technique to reduce optimization of expressions.)
> 
> > My questions are:
> > 
> > 1) Do I understand correctly what's going on?
> 
> I think so.
> 
> > 2) Does the language make any guarantees about preventing spurious
> > overflow, or am I just getting lucky with my compiler/architecture?
> > If guarantees are made by the language, what are they?
> 
> The language says effectively that you either will get the right
> answer or Constraint_Error. But it makes no guarantees about which
> you will get for values outside of the result subtype. So that is
> compiler-dependent.
> 
> The intent is to be able to use the hardware effectively. To take an
> example, older Intel X86 processors did all of their floating point
> calculations in 80-bit registers. The only certain way to use fewer
> bits was to store the register into memory and then reload it (which
> forced the needed rounding). Needless to say, this doesn't help
> performance!
> 
> In something like:
>    F := (A * B) / (C * D);
> you would have two extra store/load pairs. That's awful, thus the
> rule allowing extra precision.
> 
> For float types, Ada actually has an attribute to explicitly discard
> extra precision (S'Machine). For integer types, you'd have to
> explicitly store the subexpression into an object and do a validity
> test on it. (It's not clear to me that a type conversion alone would
> guarantee a check for a type like Integer where Integer has the same
> range as Integer'Base. The validity rules always allow delaying a
> constraint check, so only 'Valid is certain to smoke out overflowing
> values.)
> 
> But both of these operations are expensive, and should only be used
> when absolute portability is needed.
> 
>                                  Randy.

Using variables gave me the behavior I was expecting. I didn't know Ada
did infinite precision arithmetic on static expressions.

Thanks,
Alex

Re: Unconstrained base subtype questions

[Dmitry A. Kazakov]

On Thu, 31 Mar 2011 21:51:29 +0000 (UTC), Alex Mentis wrote:

> Using variables gave me the behavior I was expecting. I didn't know Ada
> did infinite precision arithmetic on static expressions.

It tries:

   P : constant := 1_000_000;
   I : constant := 2**P - 2**P;

will likely fail to compile.

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de