Bug or feature?

Bug or feature?

[Laurent]

Hi

While studying recursion I tried to develop an iterative version of the fibonacci sequence.

It works but on N>47 the function outputs negative numbers,buffer overflow. No difference between my iterative version and the recursive one given in the book (recursion is quite slow...).

Build a small test program which throws a Constraint error. So why does the test functions correctly where as the fibonacci program doesn't?

I have added an Exception for the buffer overflow to the iterative version to check if this solves the problem and it does.

Positive is defined as : subtype Positive is Integer range 1 .. Integer'Last;
So if the result gets negative it should raise an constraint error without needing to add a raise myself?

Output of fibonacci:

Please enter an integer (>= 1) > 50

The fibonacci sequence for N = 50 is: 
1
1
2
3
5
8
13
21
34
55
.
.
.
1134903170
1836311903
-1323752223  <==
512559680
-811192543 <==
-298632863 <==
[2014-05-14 20:57:08] process terminated successfully (elapsed time: 02.29s)

Output of buffer_overflow test:

enter an integer: 10

raised CONSTRAINT_ERROR : buffer_overflow.adb:11 range check failed 
(normal 10*2*10^9 = too big for 32 bit int)
[2014-05-14 20:55:07] process exited with status 1 (elapsed time: 01.51s)

Thanks

Laurent

with Ada.Text_IO;
with Ada.Integer_Text_IO;

procedure Test_Fibonacci is
   N : Positive;
   Result : Positive := 1;
   Buffer_Overflow : exception;

   function Fibonacci_Iter (N : in Positive) return Positive is
   -- Returns the Nth Fibonacci number, computed iteratively
   -- Pre : N is defined and N >= 1
   -- Post: returns N!

      First : Positive := 1;
      Second : Positive := 1;

   begin -- Fibonacci Iteration

      if N = 1 or N = 2 then
         return Result;
      else
         for Count in 3 .. N loop
            Result := First + Second;
            First := Second;
            Second := Result;
         end loop;
         if Result'Valid then            
            return Result;
         else
            raise Buffer_Overflow;
         end if;            
      end if;
   end Fibonacci_Iter;
   
   function Fibonacci_Rec (N : in Positive) return Positive is
   -- Returns the Nth Fibonacci number, computed recursively
   -- Pre : N is defined and N >= 1
   -- Post: returns N!
  
   begin  -- Fibonacci Recursion

      if (N = 1) or (N = 2) then
         return 1;
      else
         return Fibonacci_Rec (N - 2) + Fibonacci_Rec (N - 1);        
      end if;
   end Fibonacci_Rec;

begin -- Test Fibonacci

   Ada.Text_IO.Put (Item => "Please enter an integer (>0) > ");
   Ada.Integer_Text_IO.Get (Item => N);
   Ada.Text_IO.New_Line;
   Ada.Text_IO.Put (Item => "The fibonacci sequence for N ="
                    & Positive'Image (N) & " is: " );
   Ada.Text_IO.New_Line;

   for Count in 1..N loop
      --Ada.Integer_Text_IO.Put (Item => Fibonacci_Iter (N => Count), Width => 1);
      Ada.Integer_Text_IO.Put (Item => Fibonacci_Rec (N => Count), Width => 1);
      Ada.Text_IO.New_Line;
      --Ada.Text_IO.Put(Item => ' ');
   end loop;

   end Test_Fibonacci;

-----------------------------

with Ada.Integer_Text_IO;
with Ada.Text_IO;

procedure Buffer_Overflow is
   Result : Positive;
   N      : Positive;

begin
   Ada.Text_IO.Put (Item => "enter an integer: ");
   Ada.Integer_Text_IO.Get(Item => N);
   Result := N * 2_000_000_000;
   Ada.Integer_Text_IO.Put (Item => Result, Width => 1);
end Buffer_Overflow;

Re: Bug or feature?

[Adam Beneschan]

On Wednesday, May 14, 2014 12:06:52 PM UTC-7, Laurent wrote:
> Hi
> 
> While studying recursion I tried to develop an iterative version of the fibonacci sequence.
> 
> It works but on N>47 the function outputs negative numbers,buffer overflow. No difference between my iterative version and the recursive one given in the book (recursion is quite slow...).
> 
> Build a small test program which throws a Constraint error. So why does the test functions correctly where as the fibonacci program doesn't?

When you ran the small test program, what value did you put in for N?  When I compile with GNAT and don't use -gnato, I find that the program gives me an exception when N=6 but not when N=5.  I think it matters whether (N * 2_000_000_000) mod 32 produces a value with the high bit set or not.  If it's set, then it looks like a negative number.

In any event, if you're using GNAT, it doesn't check for overflow automatically; you have to use -gnato to get it to check that arithmetic operations don't overflow.  Your Buffer_Overflow test is not really a valid test, because it's possible that the operation N * 2_000_000_000 will overflow, and the overflow won't be checked, but the result will appear to be a negative number, which will violate the range checks on Positive.

It does appear that GNAT may not always check the range properly when a function whose result is Positive tries to return a negative value due to overflow.  That would explain why the recursive version doesn't get an exception.

                                  -- Adam

Re: Bug or feature?

[Adam Beneschan]

On Wednesday, May 14, 2014 12:57:47 PM UTC-7, Adam Beneschan wrote:

> It does appear that GNAT may not always check the range properly when a
> function whose result is Positive tries to return a negative value due to
> overflow.  That would explain why the recursive version doesn't get an
> exception.

Here's an example:

with Ada.Integer_Text_IO;
with Ada.Text_IO;

procedure Test is
   Result : Integer;

   function Add (X1, X2 : Positive) return Positive is
   begin
      return X1 + X2;
   end Add;

   function Multiply (X1, X2 : Positive) return Positive is
   begin
      return X1 * X2;
   end Multiply;

begin
   Result := Add(2_000_000_000, 2_000_000_000);
   Ada.Integer_Text_IO.Put (Item => Result, Width => 1);
   Result := Multiply(6, 2_000_000_000);
   Ada.Integer_Text_IO.Put (Item => Result, Width => 1);
end Test;

Compiled without -gnato.  The result is that a negative number is output after the call to Add, but the call to Multiply raises an exception.  So it looks like when the function result is Positive, a "return" that returns the result of an addition doesn't check to make sure the result is in range (when overflow is possible), but a "return" that returns the result of a multiplication does check.  That would also explain why the original Buffer_Overflow test case works but the recursive Fibonacci routine doesn't.

                                 -- Adam

Re: Bug or feature?

[Laurent]

Hi

Using GNAT and GPS. Didn't change anything on the compiler flags.

>When you ran the small test program, what value did you put in for N?

I used 10.

This one I didn't see: 5*2_000_000_000 = 1_410_065_408
So there is also an overflow. Didn't count the digits before. (Is there a way to add '_' to separate
the thousands automatically in GPS?)

Seems this behavior happens only with functions.

Yeah my test is quite cheap. Was more to see if I coded something strange together or if it is an other problem.

Modified my little test with Result:= 2_000_000_000 + 2_000_000_000;
Doesn't compile:

/Volumes/Kingston/GPS/Chapter 14/buffer_overflow.adb
        11:27 static expression fails Constraint_Check
        11:27 value not in range of type "Standard.Integer"

So it is a bug?  Or just a matter of putting an additional flag?

Checked the Stack Overflow check (-gnato) under Project Properties/Switches/Ada and disabling my own overflow detection the fibonacci program(iteration or recursion) crashes with Constraint Error. The behavior I expected. I am a bit disappointed/afraid of this. Or perhaps I have forgotten to read the small printed text somewhere at the end :)

Thanks

Laurent

Re: Bug or feature?

[Adam Beneschan]

On Wednesday, May 14, 2014 2:24:57 PM UTC-7, Laurent wrote:

> Modified my little test with Result:= 2_000_000_000 + 2_000_000_000;
> Doesn't compile:
> 
> /Volumes/Kingston/GPS/Chapter 14/buffer_overflow.adb
>         11:27 static expression fails Constraint_Check
>         11:27 value not in range of type "Standard.Integer"

Yes, you have to use variables.  2_000_000_000 + 2_000_000_000 is a static expression that can be computed at compile-time, and some of the checks that would normally cause exceptions at run-time will cause errors at compile-time, due to special rules in the language about static expressions.

                            
> So it is a bug?  Or just a matter of putting an additional flag?

The requirement to add -gnato to get full checking has been discussed quite a bit on this newsgroup and elsewhere.  Basically, overflow checking adds a lot of code on most processors, and I think the decision was made early on to disable it by default.  Not everyone likes this.  It looks like there's a bug in how range checking is handled if -gnato isn't used, over and above the lack of overflow checking.  But it appears to be a bug that cannot come up if -gnato is used.

                            -- Adam

Re: Bug or feature?

[Robert A Duff]

Laurent <daemon2@internet.lu> writes:

> This one I didn't see: 5*2_000_000_000 = 1_410_065_408
> So there is also an overflow. Didn't count the digits before. (Is there a way to add '_' to separate
> the thousands automatically in GPS?)

I don't know, but recent versions of gnatpp have that capability.

I don't like having to squint to tell the difference between
(say) "one million" and "ten million".  I wonder why most languages
don't support that feature -- it's trivial.

> Checked the Stack Overflow check (-gnato) ...

It's not "stack overflow" -- that has to do with overflowing the
call stack.  I think you also called it "buffer overflow", which
actually means array index out of bounds.  -gnato turns on checks for
"integer overflow".  I believe -gnato will be the default soon,
if it's not already.

- Bob

Re: Bug or feature?

[Randy Brukardt]

"Laurent" <daemon2@internet.lu> wrote in message 
news:224148c3-2a31-4f3e-a3a3-0a588773798b@googlegroups.com...
...
>Checked the Stack Overflow check (-gnato) under Project 
>Properties/Switches/Ada and
>disabling my own overflow detection the fibonacci program(iteration or 
>recursion) crashes
>with Constraint Error. The behavior I expected. I am a bit 
>disappointed/afraid of this. Or
>perhaps I have forgotten to read the small printed text somewhere at the 
>end :)

To get what the Ada Standard calls "standard mode" for Ada with GNAT, you 
need to compile with a bunch of options. The default behavior of GNAT is NOT 
standard mode as described in the RM.

To compile ACATS tests in GNAT, I have to use a small boatload of options:

gnatmake 
C457003.adb -eS -gnat12 -O0 -gnatE -gnato -gnatv -gnatws -gnatd7 -bargs - T0

Some of these are about warnings and disabling of optimizations, and of 
course -gnat12 sets Ada 2012 mode (which I think is the default these days). 
[B-Tests also need -gnatf and -gnatq, but that's not important to most since 
they're not worried about broken programs.]

I use that set of options anytime I'm compiling test programs from GNAT 
(including the ones that appear here), because several of them are needed to 
get standard behavior. GNAT's default behavior might be "better" in some 
ways, but it's confusing because it doesn't necessarily do what you'll find 
in an Ada book.

                                     Randy.

Re: Bug or feature?

[Robert A Duff]

Adam Beneschan <adambeneschan@gmail.com> writes:

>...  It looks like there's a bug in how range checking is
> handled if -gnato isn't used, over and above the lack of overflow
> checking.

No, I don't think so.  If you don't use -gnato, it's equivalent
to having pragma Suppress(Overflow_Check), so if it overflows,
all bets are off.

There is also 11.5(27/2).

- Bob

Re: Bug or feature?

[Adam Beneschan]

On Wednesday, May 14, 2014 3:02:16 PM UTC-7, Robert A Duff wrote:
 
> >...  It looks like there's a bug in how range checking is
> > handled if -gnato isn't used, over and above the lack of overflow
> > checking.
> 
> No, I don't think so.  If you don't use -gnato, it's equivalent
> to having pragma Suppress(Overflow_Check), so if it overflows,
> all bets are off.

I see your point, so I guess "bug" may have been the wrong term.  "Interesting inconsistency" may be better.  It's interesting that, when overflow checking is suppressed, the compiler seems to figure out that it can assume "+" of two Positive values is Positive and doesn't need to be checked, but doesn't figure this out for "*".

OK, without trying to look at the compiler's source code, this seems like a reasonable explanation:

   subtype S1 is Integer range Low1 .. High1;
   subtype S2 is Integer range Low2 .. High2;
   X1 : S1;
   X2 : S2;

X1+X2 is always in the range Low1+Low2 .. High1+High2, but there's no such simple way to express the range of X1*X2 (in general).  Could that be the reason for the difference in behavior?  

                                    -- Adam

Re: Bug or feature?

[Robert A Duff]

"Randy Brukardt" <randy@rrsoftware.com> writes:

> gnatmake 
> C457003.adb -eS -gnat12 -O0 -gnatE -gnato -gnatv -gnatws -gnatd7 -bargs - T0

Of those, only "-gnatE", "-gnato", and "-bargs -T0" are needed for
standards conformance.  And as I said, "-gnato" is no longer, or soon
will no longer be needed.

The above options are definitely not what the OP should be using.
For example, don't use -gnatE unless you are porting a large program
to GNAT and it won't work otherwise.

> Some of these are about warnings and disabling of optimizations, and of 
> course -gnat12 sets Ada 2012 mode (which I think is the default these days). 

Right, Ada 2012 is now the default.

> [B-Tests also need -gnatf and -gnatq, but that's not important to most since 
> they're not worried about broken programs.]
>
> I use that set of options anytime I'm compiling test programs from GNAT 
> (including the ones that appear here), because several of them are needed to 
> get standard behavior. GNAT's default behavior might be "better" in some 
> ways, but it's confusing because it doesn't necessarily do what you'll find 
> in an Ada book.

Yes, it is confusing.

- Bob

Re: Bug or feature?

[Simon Wright]

Robert A Duff <bobduff@shell01.TheWorld.com> writes:

> Of those, only "-gnatE", "-gnato", and "-bargs -T0" are needed for
> standards conformance.  And as I said, "-gnato" is no longer, or soon
> will no longer be needed.

-gnato isn't the default for GNAT GPL 2014 or FSF GCC 4.9.0.

Add -fstack-check ?

Re: Bug or feature?

[Georg Bauhaus]

On 14/05/14 23:42, Robert A Duff wrote:
> I don't like having to squint to tell the difference between
> (say) "one million" and "ten million".  I wonder why most languages
> don't support that feature -- it's trivial.

If initial exposition to lexing means learning by imitation,
then one typically learns, very early:
    "digit { digit }" for integers, and then
    some rules for floats, composed of integers around '.'.
Readability will be a distraction, pedagogically shifting focus.

But '_' in number literals should be a good exercise! Maybe that's
a way to get '_' into education, thus into more languages.

Re: Bug or feature?

[Georg Bauhaus]

On 14/05/14 23:48, Randy Brukardt wrote:
> To compile ACATS tests in GNAT, I have to use a small boatload of options:
>
> gnatmake
> C457003.adb -eS -gnat12 -O0 -gnatE -gnato -gnatv -gnatws -gnatd7 -bargs - T0

Would it be meaningful when testing any compiler, to include
the optimizers typically used when translating production code?
-O2 seems commonly used with GNAT.

Re: Bug or feature?

[Randy Brukardt]

"Simon Wright" <simon@pushface.org> wrote in message 
news:ly8uq3mown.fsf@pushface.org...
> Robert A Duff <bobduff@shell01.TheWorld.com> writes:
>
>> Of those, only "-gnatE", "-gnato", and "-bargs -T0" are needed for
>> standards conformance.  And as I said, "-gnato" is no longer, or soon
>> will no longer be needed.
>
> -gnato isn't the default for GNAT GPL 2014 or FSF GCC 4.9.0.
>
> Add -fstack-check ?

That's probably a good idea for real programs. The ACATS doesn't need it as 
the tests that used to attempt to exhaust memory have been reigned in. (They 
had nasty effects on targets supporting virtual memory. I remember the first 
time we ran the ACATS on Windows NT, one of those tests allocated an insane 
amount of swap space and then essentially ran from the disk drive. It would 
have taken months to complete. I had to artifically bound the heap size on 
NT in order to eliminate that problem; that's the sort of counterproductive 
thing that one would hope the ACATS is not requiring.) The tests now 
allocate a few megabytes and then give up - thus on virtual memory hosts 
they don't try to test for Storage_Error.

                                           Randy.

Re: Bug or feature?

[Randy Brukardt]

"Georg Bauhaus" <rm-host.bauhaus@maps.futureapps.de> wrote in message 
news:5374819a$0$6696$9b4e6d93@newsspool2.arcor-online.net...
> On 14/05/14 23:48, Randy Brukardt wrote:
>> To compile ACATS tests in GNAT, I have to use a small boatload of 
>> options:
>>
>> gnatmake
>> C457003.adb -eS -gnat12 -O0 -gnatE -gnato -gnatv -gnatws -gnatd7 -bargs - 
>> T0
>
> Would it be meaningful when testing any compiler, to include
> the optimizers typically used when translating production code?
> -O2 seems commonly used with GNAT.

I picked these options originally because they were the ones used during the 
latest formal conformity assessment of GNAT. (I've since modified them a bit 
on the advice of the AdaCore ACATS test person.) That's the only set of 
options that anyone ever guaranteed actually met the Standard.

One would expect that internally, AdaCore tests other sets of options as 
well. Optimization is sometimes a problem, as really powerful optimizers can 
sometimes eliminate or invalidate ACATS tests. ACATS tests have been 
repaired to avoid optimization effects, but its a never-ending game of 
whack-a-mole. (As optimizers get better, new problems emerge, which require 
still more test repairs, etc.) In addition, some optimization modes probably 
aren't standards-conformant. (For instance, Janus/Ada has a mode where all 
objects are assumed to be in range. This matches our Ada 83 compiler, but 
it's not correct for Ada 95 and later.)

For Janus/Ada, I run 3 different sets of optimization options, combined with 
3 different language settings. But that's for in-house use only; a formal 
conformity assessment would be done with the optimization off. The in-house 
goal is to minimize failures with the optimizer on but there are a few 
failures that are effectively unfixable, so I doubt it would ever be 
perfect.

                                 Randy.