Normalizing array indices

Normalizing array indices

[Stefan.Lucks]

Hi all, does anyone know a way to change the array indices of a subprogram 
parameter to start with a default index? This question occurred to me when 
I happened to discover a subtle bug in a sort procedure I had implemented. 

  generic
    type Element_Type is private;
    type Sort_Array_Type is array (Positive range <>) of Element_Type;
    with function "<" (Left, Right: Element_Type) return Boolean is <>;
  procedure Sort(A: in out Sort_Array_Type); 

I had a reasonable amount of black box tests and Sort passed all of them. 

Some time later, I added a test with A'range being  
   Positive'Last -2 .. Positive'Last
and boooom -- got a Constraint_Error. As it turned out, there was a 
Positive index variable which could take the value A'Last+1 -- which is 
perfectly OK except when A'Last = Positive'Last. To rescue my 
implementation I considered something like 

  procedure Sort(A: in out Sort_Array_Type) is
    Alias_A: Sort_Array_Type(1 .. A'Length) renames A;
  begin
    ... -- apply your favorite sorting algorithm to Alias_A;
  end Sort;

but the compiler didn't like that renaming:
  "constraint not allowed in object renaming declaration". 
Is there a way to get that effect? The following works, but hey, 
this is ugly and (for large A) very inefficient:

  procedure Sort(A: in out Sort_Array_Type) is
    Copy_Of_A: Sort_Array_Type(1 .. A'Length) := A;
  begin
    ... -- apply your favorite sorting algorithm to Copy_Of_A;
    A := Copy_Of_A;
  end Sort;

I finally solved the problem at hand by changing the logic of the sort 
subprogram. But the problem still continues to haunt my mind, for the 
following reasons:

1. On most compilers/machines it is safe to assume that there is not 
   sufficient storage for arrays of length Positive'Last. So the problem 
   just disappears in a language where arrays always start with a fixed 
   index (say, 0 or 1). So the Ada program is buggy, where the same 
   C program would be perfectly OK. 

2. More generally, proper testing in Ada may require more test cases than 
   testing the apparently same subprogram in another language, like C. Is
   Ada actually less testing-friendly?

In many cases, array ranges starting with an arbitrary index are better 
(higher level) to model an application's demands. But sometimes, like when 
applying a sorting routine, this extra information is actually some 
ballast. 

Ideally, the specification of a subprogram would carry the information 
that the subprogram only uses "normalized" array indices, to free the 
tester from having to consider test cases with different A'First:

  procedure Sort(A: in out Sort_Array_Type(1 .. <>)); 

The user can still call Sort with any array of range, say, 4711 .. 9421, 
but Sort coldn't tell that apart from an array of range 1 .. 4711. Thus, 
there is no reason for additional test cases with different values 
for A'First. 

Such a change is probably too late for Ada 2012 :-/ ... but perhaps it 
would be OK for Ada 2020. :-)



-- 
---- Stefan.Lucks (at) uni-weimar.de, University of Weimar, Germany  ----
    <http://www.uni-weimar.de/cms/medien/mediensicherheit/home.html>
------  I  love  the  taste  of  Cryptanalysis  in  the  morning!  ------

Re: Normalizing array indices

[Adam Beneschan]

On Oct 28, 11:58 am, Stefan.Lu...@uni-weimar.de wrote:
> Hi all, does anyone know a way to change the array indices of a subprogram
> parameter to start with a default index? This question occurred to me when
> I happened to discover a subtle bug in a sort procedure I had implemented.
>
>   generic
>     type Element_Type is private;
>     type Sort_Array_Type is array (Positive range <>) of Element_Type;
>     with function "<" (Left, Right: Element_Type) return Boolean is <>;
>   procedure Sort(A: in out Sort_Array_Type);
>
> I had a reasonable amount of black box tests and Sort passed all of them.
>
> Some time later, I added a test with A'range being  
>    Positive'Last -2 .. Positive'Last
> and boooom -- got a Constraint_Error. As it turned out, there was a
> Positive index variable which could take the value A'Last+1 -- which is
> perfectly OK except when A'Last = Positive'Last. To rescue my
> implementation I considered something like
>
>   procedure Sort(A: in out Sort_Array_Type) is
>     Alias_A: Sort_Array_Type(1 .. A'Length) renames A;
>   begin
>     ... -- apply your favorite sorting algorithm to Alias_A;
>   end Sort;
>
> but the compiler didn't like that renaming:
>   "constraint not allowed in object renaming declaration".

procedure Sort (A : in out Sort_Array_Type) is
  subtype A_Type is Sort_Array_Type (1 .. A'Length);
  Alias_A : A_Type renames A_Type(A);
begin
  ...
end Sort;

The type conversion is necessary in order to get the indexes to
"slide".  If you do this:

  Alias_A : A_Type renames A;

the compiler will accept it, but you're likely to get
Constraint_Errors at runtime.

                        -- Adam

Re: Normalizing array indices

[Randy Brukardt]

<Stefan.Lucks@uni-weimar.de> wrote in message 
news:Pine.LNX.4.64.1110282013540.21821@medsec1.medien.uni-weimar.de...
> Hi all, does anyone know a way to change the array indices of a subprogram
> parameter to start with a default index? This question occurred to me when
> I happened to discover a subtle bug in a sort procedure I had implemented.
>
>  generic
>    type Element_Type is private;
>    type Sort_Array_Type is array (Positive range <>) of Element_Type;
>    with function "<" (Left, Right: Element_Type) return Boolean is <>;
>  procedure Sort(A: in out Sort_Array_Type);
>
> I had a reasonable amount of black box tests and Sort passed all of them.
>
> Some time later, I added a test with A'range being
>   Positive'Last -2 .. Positive'Last
> and boooom -- got a Constraint_Error. As it turned out, there was a
> Positive index variable which could take the value A'Last+1 -- which is
> perfectly OK except when A'Last = Positive'Last.

This is pretty typical. We've often talked about the need in Ada for 
one-sided array subtypes, but we don't have any first class ones at this 
point.

I probably would constrain the parameter to have a lower bound of 1. Using 
Ada 2012:

generic
   type Element_Type is private;
   type Sort_Array_Type is array (Positive range <>) of Element_Type;
   with function "<" (Left, Right: Element_Type) return Boolean is <>;
procedure Sort(A: in out Sort_Array_Type)
   with Pre => A'First 1;

You could do something similar with a subtype using a dynamic predicate (but 
not in a generic specification).

In Ada 2005 and earlier, I'd simply make it part of the spec with some 
English wording, and then start the code with
    if A'First /= 1 then raise Program_Error; end if;
(You could also use pragma Assert if you don't mind the possibility that 
someone turned it off.)

Then, if you had any calls that don't have the right bounds (which is likely 
to be rare), I'd use a sliding trick similar to the one Adam showed. (But 
I'd probably try hard to figure out how to avoid passing the slice in the 
first place.)

Of course, it's better to make the routine work for all possible bounds. And 
if you do that, you certainly need to add that to the testing burden (it's 
commonly forgotten and probably is one of the most common Ada bugs).

                                           Randy.

Re: Normalizing array indices

[Pascal Obry]

Le 28/10/2011 23:13, Randy Brukardt a écrit :
> I probably would constrain the parameter to have a lower bound of 1. Using
> Ada 2012:
>
> generic
>     type Element_Type is private;
>     type Sort_Array_Type is array (Positive range<>) of Element_Type;
>     with function "<" (Left, Right: Element_Type) return Boolean is<>;
> procedure Sort(A: in out Sort_Array_Type)
>     with Pre =>  A'First 1;

Or maybe something less radical:

generic
     type Element_Type is private;
     type Sort_Array_Type is array (Positive range<>) of Element_Type;
     with function "<" (Left, Right: Element_Type) return Boolean is<>;
procedure Sort(A: in out Sort_Array_Type)
     with Pre =>  A'Last < Positive'Last - 1;

I think this covers the problem expressed by the OP, right?

Pascal.

-- 

--|------------------------------------------------------
--| Pascal Obry                           Team-Ada Member
--| 45, rue Gabriel Peri - 78114 Magny Les Hameaux FRANCE
--|------------------------------------------------------
--|    http://www.obry.net  -  http://v2p.fr.eu.org
--| "The best way to travel is by means of imagination"
--|
--| gpg --keyserver keys.gnupg.net --recv-key F949BD3B

Re: Normalizing array indices

[Simon Wright]

Stefan.Lucks@uni-weimar.de writes:

> In many cases, array ranges starting with an arbitrary index are
> better (higher level) to model an application's demands. But
> sometimes, like when applying a sorting routine, this extra
> information is actually some ballast.
>
> Ideally, the specification of a subprogram would carry the information 
> that the subprogram only uses "normalized" array indices, to free the 
> tester from having to consider test cases with different A'First:
>
>   procedure Sort(A: in out Sort_Array_Type(1 .. <>)); 
>
> The user can still call Sort with any array of range, say, 4711 .. 9421, 
> but Sort coldn't tell that apart from an array of range 1 .. 4711. Thus, 
> there is no reason for additional test cases with different values 
> for A'First. 

But your problem was with A'Last, surely?

I've had more surprises with

   type Arr is array (Integer range <>) of Float;
   A : Arr := (1.0, 2.0, 3.0);

where A'First is Integer'First (on GNAT), ie -2**31.

Re: Normalizing array indices

[Dmitry A. Kazakov]

On Sat, 29 Oct 2011 10:05:42 +0100, Simon Wright wrote:

> Stefan.Lucks@uni-weimar.de writes:
> 
>> In many cases, array ranges starting with an arbitrary index are
>> better (higher level) to model an application's demands. But
>> sometimes, like when applying a sorting routine, this extra
>> information is actually some ballast.
>>
>> Ideally, the specification of a subprogram would carry the information 
>> that the subprogram only uses "normalized" array indices, to free the 
>> tester from having to consider test cases with different A'First:
>>
>>   procedure Sort(A: in out Sort_Array_Type(1 .. <>)); 
>>
>> The user can still call Sort with any array of range, say, 4711 .. 9421, 
>> but Sort coldn't tell that apart from an array of range 1 .. 4711. Thus, 
>> there is no reason for additional test cases with different values 
>> for A'First. 
> 
> But your problem was with A'Last, surely?
> 
> I've had more surprises with
> 
>    type Arr is array (Integer range <>) of Float;
>    A : Arr := (1.0, 2.0, 3.0);
> 
> where A'First is Integer'First (on GNAT), ie -2**31.

The problem is that for some algorithms for any valid array index Index,
there should exist Index - 1 and/or Index + 1. One possible solution might
be some sugar for

   subtype Safe_Integer is range Integer'First + 1..Integer'Last - 1;
   type Arr is array (Safe_Integer range <>) of Float;

Another solution is array interfaces with universal integer as the position
(offset) in addition to index. Some people are fond of [] brackets,
positional interfaces could use them. Algorithms written in terms of
indices sometimes become simpler when rewritten in terms of offsets.

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

Re: Normalizing array indices

[Jeffrey Carter]

On 10/29/2011 12:29 AM, Pascal Obry wrote:
>
> generic
>    type Element_Type is private;
>    type Sort_Array_Type is array (Positive range<>) of Element_Type;
>    with function "<" (Left, Right: Element_Type) return Boolean is<>;
> procedure Sort(A: in out Sort_Array_Type)

The problem is the use of Positive for the generic formal array index. One 
thinks of numbers as being infinite, so failing to think about the effect of 
adding 1 to an index is natural.

Why should a general-purpose sort procedure restrict the client to arrays 
indexed by Positive?

generic -- Sort
    type Element is private;
    type Index is (<>);
    type Sort_List is array (Index range <>) of Element;

    with function "<" (Left : Element; Right : Element) return Boolean is <>;
procedure Sort (List : in out Sort_List);

Now the developer is forced to think in terms of Index being finite, and so the 
cases of trying to take the Succ to Index'Last and the Pred of Index'First.

The PragmAda Reusable Components contain insertion, heap, quick, and radix 
sorts, all of which allow any discrete subtype for the indices and handle 
Index'Last correctly:

http://pragmada.co.cc/

-- 
Jeff Carter
"I don't know why I ever come in here. The
flies get the best of everything."
Never Give a Sucker an Even Break
102

Re: Normalizing array indices

[tmoran]

> > generic
> >    type Element_Type is private;
> >    type Sort_Array_Type is array (Positive range<>) of Element_Type;
> >    with function "<" (Left, Right: Element_Type) return Boolean is<>;
> > procedure Sort(A: in out Sort_Array_Type)

How about
   with function Earlier (Left, Right: Element_Type) return Boolean is<>;

Otherwise one gets oddities like
  procedure Sort_Decreasing is new Sort(..., "<" => ">");

Re: Normalizing array indices

[Randy Brukardt]

"Jeffrey Carter" <spam.jrcarter.not@spam.not.acm.org> wrote in message 
news:j8hnkv$30l$1@tornado.tornevall.net...
> On 10/29/2011 12:29 AM, Pascal Obry wrote:
>>
>> generic
>>    type Element_Type is private;
>>    type Sort_Array_Type is array (Positive range<>) of Element_Type;
>>    with function "<" (Left, Right: Element_Type) return Boolean is<>;
>> procedure Sort(A: in out Sort_Array_Type)
>
> The problem is the use of Positive for the generic formal array index. One 
> thinks of numbers as being infinite, so failing to think about the effect 
> of adding 1 to an index is natural.
>
> Why should a general-purpose sort procedure restrict the client to arrays 
> indexed by Positive?

Of course, there is little reason to create a general purpose sort of your 
own, given that the Standard already contains two (and there is a third one 
added in Ada 2012). You pretty much have to have some special purpose to 
justify the work. The ones in the Standard have the following 
specifications:

generic
   type Index_Type is (<>);
   type Element_Type is private;
   type Array_Type is array (Index_Type range <>) of Element_Type;
   with function "<" (Left, Right : Element_Type)
      return Boolean is <>;
procedure Ada.Containers.Generic_Array_Sort (Container : in out Array_Type);
pragma Pure(Ada.Containers.Generic_Array_Sort);

and

generic
   type Index_Type is (<>);
   with function Before (Left, Right : Index_Type) return Boolean;
   with procedure Swap (Left, Right : Index_Type);
procedure Ada.Containers.Generic_Sort
      (First, Last : Index_Type'Base);
pragma Pure(Ada.Containers.Generic_Sort);

(There is also a constrained version that's similar to the first.)

The last version allows sorting anything ordered (it does not have to be an 
array).

There are also sorting routines for the vector and list containers.

                           Randy.

Re: Normalizing array indices

[Simon Wright]

tmoran@acm.org writes:

>> > generic
>> >    type Element_Type is private;
>> >    type Sort_Array_Type is array (Positive range<>) of Element_Type;
>> >    with function "<" (Left, Right: Element_Type) return Boolean is<>;
>> > procedure Sort(A: in out Sort_Array_Type)
>
> How about
>    with function Earlier (Left, Right: Element_Type) return Boolean is<>;

That would be Before in the spirit of 2012 (A.18.26 9.1/3 ff). Though in
that case the reasoning is probably that the parameters of Before are
indices; so the semantics are something like Indexed_Element_Is_Before.

> Otherwise one gets oddities like
>   procedure Sort_Decreasing is new Sort(..., "<" => ">");

Odd but understandable after you've seen it once or twice.

Re: Normalizing array indices

[Stefan.Lucks]

On Fri, 28 Oct 2011, Adam Beneschan wrote:

> procedure Sort (A : in out Sort_Array_Type) is
>   subtype A_Type is Sort_Array_Type (1 .. A'Length);
>   Alias_A : A_Type renames A_Type(A);
> begin
>   ...
> end Sort;

Ah, that seems to work! Thank you!

-- 
---- Stefan.Lucks (at) uni-weimar.de, University of Weimar, Germany  ----
    <http://www.uni-weimar.de/cms/medien/mediensicherheit/home.html>
------  I  love  the  taste  of  Cryptanalysis  in  the  morning!  ------

Re: Normalizing array indices

[stefan-lucks]

On Fri, 28 Oct 2011, Randy Brukardt wrote:

> This is pretty typical. We've often talked about the need in Ada for 
> one-sided array subtypes, but we don't have any first class ones at this 
> point.
> 
> I probably would constrain the parameter to have a lower bound of 1. Using 
> Ada 2012:
> 
> generic
>    type Element_Type is private;
>    type Sort_Array_Type is array (Positive range <>) of Element_Type;
>    with function "<" (Left, Right: Element_Type) return Boolean is <>;
> procedure Sort(A: in out Sort_Array_Type)
>    with Pre => A'First 1;

Well, once I want to sort a slice X(Y .. Z) of X, this fails. The ease of 
slicing is one of the coolest features of Ada's arrays. In fact, the 
implementation of sort I mentioned would recursively perform 
  Sort(A(A'First .. M)); 
and 
  Sort(A(M+1 .. A'Last)); 
for M = (A'First+A'Last)/2 (with some exception treatment for 
A'First+A'Last>'Positive'Last and only if A'Length is above some 
threshold), followed by merging the two slices. So at some point of time, 
the slicing/renaming would become necessary -- either always at the 
beginning of Sort, or to re-slice A(M+1 .. A'Last). A better Ada-2012 
precondition would actually be
  with Pre => A'Last < Positive'Last;

> Then, if you had any calls that don't have the right bounds (which is likely 
> to be rare), I'd use a sliding trick similar to the one Adam showed. (But 
> I'd probably try hard to figure out how to avoid passing the slice in the 
> first place.)
> 
> Of course, it's better to make the routine work for all possible bounds. And 
> if you do that, you certainly need to add that to the testing burden (it's 
> commonly forgotten and probably is one of the most common Ada bugs).

I am relieved that I am not the only one who happened to suffer from such a 
problem. Still, I think a way to *specify* a formal subprogram parameter F 
such that F'First is a given constant, regardless of A'First if A is the 
actual parameter, would be ease testing and might be a good extension to 
Ada (2020?).

So long

Stefan


-- 
---- Stefan.Lucks (at) uni-weimar.de, University of Weimar, Germany ----
    <http://www.uni-weimar.de/cms/medien/mediensicherheit/home.html> 
------     I love the taste of Cryptanalysis in the morning!      ------

Re: Normalizing array indices

[stefan-lucks]

On Sat, 29 Oct 2011, Pascal Obry wrote:

> generic
>     type Element_Type is private;
>     type Sort_Array_Type is array (Positive range<>) of Element_Type;
>     with function "<" (Left, Right: Element_Type) return Boolean is<>;
> procedure Sort(A: in out Sort_Array_Type)
>     with Pre =>  A'Last < Positive'Last - 1;
> 
> I think this covers the problem expressed by the OP, right?

Yes thank you!

Stefan


-- 
---- Stefan.Lucks (at) uni-weimar.de, University of Weimar, Germany  ----
    <http://www.uni-weimar.de/cms/medien/mediensicherheit/home.html>
------  I  love  the  taste  of  Cryptanalysis  in  the  morning!  ------

Re: Normalizing array indices

[stefan-lucks]

On Sat, 29 Oct 2011, Randy Brukardt wrote:

> Of course, there is little reason to create a general purpose sort of your 
> own, given that the Standard already contains two (and there is a third one 
> added in Ada 2012). You pretty much have to have some special purpose to 
> justify the work. 

In that specific case, I wanted a sorting routine that would be able  
split its work between different "workers" (Ada tasks, hopefully runing on 
different processor cores), to benefit from parallelism. 

The only reason not to use a more general index type was the ease to 
compute the middle index ...

So long

Stefan


-- 
---- Stefan.Lucks (at) uni-weimar.de, University of Weimar, Germany  ----
    <http://www.uni-weimar.de/cms/medien/mediensicherheit/home.html>
------  I  love  the  taste  of  Cryptanalysis  in  the  morning!  ------

Re: Normalizing array indices

[stefan-lucks]

On Sat, 29 Oct 2011, Simon Wright wrote:

> Stefan.Lucks@uni-weimar.de writes:
> 
> But your problem was with A'Last, surely?

Yes. Especially, since I initially forgot about a test case with A'Last = 
Positive'Last. 

> I've had more surprises with
> 
>    type Arr is array (Integer range <>) of Float;
>    A : Arr := (1.0, 2.0, 3.0);
> 
> where A'First is Integer'First (on GNAT), ie -2**31.

That is the same ugly situation. Except that when you initialize an array 
by a constant (as in your code example above), A'First *is* the first 
element in the given range, i.e., Integer'First (in your case). In fact, 
without extra precautions (such as A: Arr(X .. X+2) := (1.0, 2.0, 3.0);), 
you may easily end up with a set of test cases where all have the property 
of A'First being Integer'First. This is very different for A'Last!

Stefan

-- 
---- Stefan.Lucks (at) uni-weimar.de, University of Weimar, Germany  ----
    <http://www.uni-weimar.de/cms/medien/mediensicherheit/home.html>
------  I  love  the  taste  of  Cryptanalysis  in  the  morning!  ------

Re: Normalizing array indices

[Robert A Duff]

Simon Wright <simon@pushface.org> writes:

> I've had more surprises with
>
>    type Arr is array (Integer range <>) of Float;
>    A : Arr := (1.0, 2.0, 3.0);
>
> where A'First is Integer'First (on GNAT), ie -2**31.

Yes.  It's usually a bad idea to declare an unconstrained array
(T range <>) where T'First = T'Base'First, because then empty
arrays don't work well.

E.g., "array (Enum_Type) ..." is OK, but "array (Enum_Type range <>) ..."
is probably wrong.

- Bob

Re: Normalizing array indices

[Robert A Duff]

stefan-lucks@see-the.signature writes:

> I am relieved that I am not the only one who happened to suffer from such a 
> problem. Still, I think a way to *specify* a formal subprogram parameter F 
> such that F'First is a given constant, regardless of A'First if A is the 
> actual parameter, would be ease testing and might be a good extension to 
> Ada (2020?).

I think you want it on the type.  Ada 9X proposed something like:

    type T (Last : Natural) is array (1..Last) of Blah;

to fix the lower bound at 1.  Slices should slide.

It's still a good idea, and will probably still be a good idea
in 2020.

- Bob