Ada.Containers.Vectors - querying multiple elements

Ada.Containers.Vectors - querying multiple elements

[Duncan Sands]

I've been playing around with Ada.Containers.Vectors (part of Ada 2005,
see http://charles.tigris.org/; look for AI-302) and noticed that
there's no way to view or operate on a "slice" of a vector.  There's a
routine

   procedure Query_Element
       (Container : in Vector;
        Index     : in Index_Type;
        Process   : not null access procedure (Element : in Element_Type));

for looking at one element; I'd like something like this:

   procedure Query_Elements
       (Container   : in Vector;
        First_Index : in Index_Type;
        Last_Index  : in Extended_Index;
        Process   : not null access procedure (Elements : in Element_Array));

where Element_Array would be:

   type Element_Array is array (Index_Type range <>) of Element_Type;

Is there any reason no such routine exists?  It would be good to have for both
efficiency reasons and simple implementation of certain classes of algorithms.
In my case I have a "divide and conquer" recursive algorithm which while it
can be written using the current package, would be simpler to write if something
like Query_Elements existed.

All the best,

Duncan.

Re: Ada.Containers.Vectors - querying multiple elements

[Georg Bauhaus]

Duncan Sands wrote:

>    procedure Query_Elements
>        (Container   : in Vector;
>         First_Index : in Index_Type;
>         Last_Index  : in Extended_Index;
>         Process   : not null access procedure (Elements : in Element_Array));


> It would be good to have for both
> efficiency reasons and simple implementation of certain classes of algorithms.
> In my case I have a "divide and conquer" recursive algorithm which while it
> can be written using the current package, would be simpler to write if something
> like Query_Elements existed.

Couldn't you use Cursors,

  here: Cursor := find_or_something(container, ...);
  there: constant Cursor := find_or_something(container, ...);

  while here /= there loop
     ...
     next(here);
  end loop;


-- Georg 

Re: Ada.Containers.Vectors - querying multiple elements

[Duncan Sands]

Hi Georg, thanks for replying.

> >    procedure Query_Elements
> >        (Container   : in Vector;
> >         First_Index : in Index_Type;
> >         Last_Index  : in Extended_Index;
> >         Process   : not null access procedure (Elements : in Element_Array));
> 
> 
> > It would be good to have for both
> > efficiency reasons and simple implementation of certain classes of algorithms.
> > In my case I have a "divide and conquer" recursive algorithm which while it
> > can be written using the current package, would be simpler to write if something
> > like Query_Elements existed.
> 
> Couldn't you use Cursors,
> 
>   here: Cursor := find_or_something(container, ...);
>   there: constant Cursor := find_or_something(container, ...);
> 
>   while here /= there loop
>      ...
>      next(here);
>   end loop;

I'm particularly concerned about:

(1) efficiency - suppose (for example) I want to transmit the contents
of my vector down a socket.  Then I would have to do an element-by-
element copy into a buffer (using code like you suggest), and then send
the buffer.  The element-by-element copy is inefficient, and with a
procedure like Query_Elements above simply wouldn't (necessarily) be
needed.  An element-by-element copy can't compete with memcpy (what
you'd probably get if you copied a slice directly, which would be
possible using Query_Elements), and certainly can't compete with no
copy at all.  By the way, this is not a real example, it's just the
first thing that came to mind.  In any case, it is a special case of
point (2):

(2) reuse of legacy code - I don't know about you, but I've a lot of
legacy code around that takes an array as a parameter.  I mean code
that doesn't change the length of the array (or anything like that) -
code that just operates on the array in-place.  Suppose I am using
a Vector, and want to have some legacy code operate on it, or on
part of it.  Right now I would have to copy the appropriate part of
the Vector into a buffer, and pass that to the legacy code, and then
copy it back.  Not very efficient - and not necessary if the Vectors
api was extended slightly.

Ciao,

D.

Re: Ada.Containers.Vectors - querying multiple elements

[Matthew Heaney]

Duncan Sands wrote:
>
> (1) efficiency - suppose (for example) I want to transmit the
contents
> of my vector down a socket.

You're not grokking the Ada95 way of doing things.  Use the stream
operations for that.  All containers (indeed, all non-limited types in
the predefined language environment) support streaming.

Your socket abstraction should have a selector function to return a
reference to a stream, so you can say:

declare
  S : Socket;
  V : Vector;
begin
 ...
  Vector'Write (Stream (S), V);
end;


> (2) reuse of legacy code - I don't know about you, but I've a lot of
> legacy code around that takes an array as a parameter...

A vector container isn't necessarily implemented as an array, so there
are no benefits to having array-based operations.

Re: Ada.Containers.Vectors - querying multiple elements

[Duncan Sands]

Hi Matthew, to summarize your reply: "that's the price you pay for
abstraction".  What I would really like to know is why there is a
significant advantage to allowing implementations that are far from
the pointer-to-an-array method.

> > I've been playing around with Ada.Containers.Vectors (part of 
>  > Ada 2005, see http://charles.tigris.org/; look for AI-302) and
> > noticed that there's no way to view or operate on a "slice" of 
>  > a vector.
> 
> There's nothing special about a vector, that it alone should provide 
> array-based operations.  A vector is a container just like any other, 
> but with constant time (O(1)) random access.

That is presumably how you like to think of it, but you could also say:
"A vector is a container just like any other, from which you can take
slices with O(length) time".

> The logical model for a vector is an array, but physically a vector can 
> have any representation consistent with logical specifications.

Sure, but that's not a restriction on the specification, that's a
restriction on the implementation.  You could add a procedure like
I mentioned to the spec - the implementations would have to implement
it, that's all.  The question is: what do you lose by adding such a
routine?  I fully appreciate that finding the "right" abstraction is
a delicate balancing act requiring a lot of time and experience.  So:
why is the current specification the right choice, and not one with
"slices" in it.  For example, Ada.Strings.Unbounded has slices - was
that a mistake?

> The reference implementation uses an array, but I know of a vendor who 
> plans to use a skip list, and another who plans to use a two-level 
> structure (not unlike an STL deque).

To my mind, this is the real argument.  It implicitly shows that there
can be real advantages to implementing Vector in a non-obvious way.
However I don't see why either of these is incompatible with taking
read-only slices.  It may not be as efficient as with a simple
pointer-to-array implementation, but it's not bad: the deque is no
problem, and the skip list should be pretty efficient too.  That's
fairly inevitable: if you can access elements in constant time, you can
access N of them in time O(N).  However it looks to me like in both
cases the "slice" operation can be done more efficiently than by
repeatedly calling "Element" to copy into a buffer.

> So there are no array-based operations for vector, just as there are no 
> array-based operations for any other container.

What's wrong with having operations that only apply to a vector and not
to other containers?  I guess you have a philosophy that tells you it is
a bad idea - care to explain?

> > I'd like something like this:
> > 
> >    procedure Query_Elements
> >        (Container   : in Vector;
> >         First_Index : in Index_Type;
> >         Last_Index  : in Extended_Index;
> >         Process   : not null 
>  >          access procedure (Elements : in Element_Array));
> > 
> > where Element_Array would be:
> > 
> >    type Element_Array is 
>  >      array (Index_Type range <>) of Element_Type;
>  >
>  > Is there any reason no such routine exists?
> 
> This wouldn't work, because a vector container doesn't guarantee that 
> the underlying data structure is a contiguous array.

As you mention below, it can be implemented by copying into a buffer
(read-only access), or copying to and from a buffer (read-write access).
So there is no logical objection, though limited stack space might be
a practical problem.

>  > It would be good to have for both
> > efficiency reasons 
> 
> No, there would be no efficiency benefit (in fact, there would be an 
> efficiency penalty, in order synthesize an array object) if the 
> underlying data structure were something other than an array.

Surely the question is whether it can be significantly more efficient to
implement it in the body, as compared to having the user do an element
by element copy.  For the pointer-to-an-array implementation, the body
can do a much more efficient job; I don't know how much you gain for
deques and skip lists.

>  > and simple implementation of certain classes of algorithms.
> > In my case I have a "divide and conquer" recursive algorithm which while it
> > can be written using the current package, would be simpler to write if something
> > like Query_Elements existed.
> 
> The thing I wish the API provided for vectors are operators such as:
> 
>    function "+" (C : Cursor; Off : Integer) return Cursor;
>    function "-" (L, R : Cursor) return Integer;
> etc.
> 
> I lobbied for this, but there was little enthusiasm among the ARG.

OK.

All the best,

Duncan.

Re: Ada.Containers.Vectors - querying multiple elements

[Duncan Sands]

Hi Matthew,

> > (1) efficiency - suppose (for example) I want to transmit the
> contents
> > of my vector down a socket.
> 
> You're not grokking the Ada95 way of doing things.  Use the stream
> operations for that.  All containers (indeed, all non-limited types in
> the predefined language environment) support streaming.

I agree it wasn't a good example.

> > (2) reuse of legacy code - I don't know about you, but I've a lot of
> > legacy code around that takes an array as a parameter...
> 
> A vector container isn't necessarily implemented as an array, so there
> are no benefits to having array-based operations.

Not so.  There is a benefit if array-based operations can be implemented
much more efficiently in the body of Ada.Containers.Vectors (where
properties of the data structure can be fully exploited), as compared to
implementing them outside the body (via copying to a buffer using multiple
calls to Element).  The pointer-to-an-array implementation is an example
where you get a big benefit from implementing in the body; that's not to
say there is no benefit for other implementations.

All the best,

Duncan.

Re: Ada.Containers.Vectors - querying multiple elements

[Duncan Sands]

> >>A vector container isn't necessarily implemented as an array, so there
> >>are no benefits to having array-based operations.
> > 
> > 
> > Not so.  There is a benefit if array-based operations can be implemented
> > much more efficiently in the body of Ada.Containers.Vectors (where
> > properties of the data structure can be fully exploited), as compared to
> > implementing them outside the body (via copying to a buffer using multiple
> > calls to Element).  The pointer-to-an-array implementation is an example
> > where you get a big benefit from implementing in the body; that's not to
> > say there is no benefit for other implementations.
> 
> 
> What you really want is to take advantage of the container 
> representation to implement an algorithm more efficiently.  That's fine. 
> Ada95 has a specific technique for that: make the algorithm a child 
> subprogram.
> 
> Instead of trying to bring the mountain to Mohammed, bring Mohammed to 
> the mountain...

But isn't it illegal to create a child of package Ada?

Ciao,

D.

Re: Ada.Containers.Vectors - querying multiple elements

[Duncan Sands]

> > But isn't it illegal to create a child of package Ada?
> 
> But you're not creating a child of Ada.  You're creating a child of 
> ada.containers.vectors.

That is also illegal.  By "child" I was referring to any descendant.

Ciao,

D.

Re: Ada.Containers.Vectors - querying multiple elements

[Martin Dowie]

Duncan Sands wrote:
>>>But isn't it illegal to create a child of package Ada?
>>
>>But you're not creating a child of Ada.  You're creating a child of 
>>ada.containers.vectors.
> 
> 
> That is also illegal.  By "child" I was referring to any descendant.

No it is _not_ 'illegal' to add a {grand}child to the "Ada" package
hierarchy.

It is the namespace under "Ada" that the ARG seem particularly keen
on reserving.

Cheers

-- Martin

Re: Ada.Containers.Vectors - querying multiple elements

[Duncan Sands]

> No it is _not_ 'illegal' to add a {grand}child to the "Ada" package
> hierarchy.
> 
> It is the namespace under "Ada" that the ARG seem particularly keen
> on reserving.

Yes, you and Matthew are quite right.  I was misled by the fact that
by default GNAT will not allow grandchildren.

All the best,

Duncan.

Re: Ada.Containers.Vectors - querying multiple elements

[Duncan Sands]

> >>A vector container isn't necessarily implemented as an array, so there
> >>are no benefits to having array-based operations.
> > 
> > 
> > Not so.  There is a benefit if array-based operations can be implemented
> > much more efficiently in the body of Ada.Containers.Vectors (where
> > properties of the data structure can be fully exploited), as compared to
> > implementing them outside the body (via copying to a buffer using multiple
> > calls to Element).  The pointer-to-an-array implementation is an example
> > where you get a big benefit from implementing in the body; that's not to
> > say there is no benefit for other implementations.
> 
> 
> What you really want is to take advantage of the container 
> representation to implement an algorithm more efficiently.  That's fine. 
> Ada95 has a specific technique for that: make the algorithm a child 
> subprogram.
> 
> Instead of trying to bring the mountain to Mohammed, bring Mohammed to 
> the mountain...

Well, Mohammed is still waiting for the mountain...  I can't say I like
the child unit suggestion: a different child would be needed for each
compiler, which is unpleasant.  If I was trying to do something weird,
then that would be fair enough.  But (IMHO) grabbing a "slice" of a
vector is a very normal thing to want to do.  Why not support it as
efficiently as possible?

Ciao,

D.

Re: Ada.Containers.Vectors - querying multiple elements

[Georg Bauhaus]

Duncan Sands wrote:

> But (IMHO) grabbing a "slice" of a
> vector is a very normal thing to want to do.  Why not support it as
> efficiently as possible?

I'm curious. Where is slicing a dynamically sized vector
done frequently?

-- Georg 

Re: Ada.Containers.Vectors - querying multiple elements

[Duncan Sands]

> > But (IMHO) grabbing a "slice" of a
> > vector is a very normal thing to want to do.  Why not support it as
> > efficiently as possible?
> 
> I'm curious. Where is slicing a dynamically sized vector
> done frequently?

Whenever you want to use legacy code that works on arrays?
It's true I have no statistics - I would like to hear some.
By the way, I would be perfectly satisfied if Matthew said:
"based on our code survey, hardly anybody needs this, so we
didn't include it".  However his arguments don't seem to be
of this kind.

Anyway, here's the example that started this whole thing: I have
a package that used GNAT.Dynamic_Tables (GDT).  These tables
are quite efficient and easy to manipulate, but they do have some
problems.  For example, if your table element type has some kind of
automatic initialization (eg: it is a pointer => initialized to null)
then that initialization won't happen.  This can cause strange bugs
if forgotten.  I ran into just such a bug this morning, which made
me do what I had long intended to do: ditch GDT.  Rather than writing
my own abstraction to replace it, I decided to look into the AI302
containers.  For the case in hand, Ada.Containers.Vectors seemed
perfect - and it was perfect (thanks Matthew!).  The only place
where I had any problem at all was in using one of our existing
debugging routines which turns an array into a formatted output
string.  For this it would have been nice to be able to access the
vector as an array.  Since you can't do that directly, I wrote a new
debugging routine which takes a vector as parameter - so there was
no real problem there either.  However it did strike me that the
ability to view parts of the vector as arrays would be generally
useful, and thus my original email.

All the best,

Duncan.

Re: Ada.Containers.Vectors - querying multiple elements

[Dr. Adrian Wrigley]

On Tue, 26 Apr 2005 21:05:28 +0200, Georg Bauhaus wrote:

> Duncan Sands wrote:
> 
>> But (IMHO) grabbing a "slice" of a
>> vector is a very normal thing to want to do.  Why not support it as
>> efficiently as possible?
> 
> I'm curious. Where is slicing a dynamically sized vector
> done frequently?

recursive algorithms!
(and plenty of other places too.)

(this was discussed in the endless C++/Ada rant a few weeks
ago.  Slicing arrays, and using array attributes 'First, 'Last
obviate the need for extra parameters.  Of course, the C++
enthusiasts didn't seem to be impressed.  To work properly,
arrays need to be able to start from any index, of course.)

I agree with Duncan's point.  It would be good to have
in the Vectors containers.  I rather hoped Vectors could do
everything that Arrays could.  I'm disappointed.

Adrian
-- 
Dr. Adrian Wrigley, Cambridge, UK

Re: Ada.Containers.Vectors - querying multiple elements

[Marius Amado Alves]

On 26 Apr 2005, at 22:47, Dr. Adrian Wrigley wrote:

> On Tue, 26 Apr 2005 21:05:28 +0200, Georg Bauhaus wrote:
>
>> Duncan Sands wrote:
>>
>>> But (IMHO) grabbing a "slice" of a
>>> vector is a very normal thing to want to do.  Why not support it as
>>> efficiently as possible?
>>
>> I'm curious. Where is slicing a dynamically sized vector
>> done frequently?
>
> recursive algorithms!
> (and plenty of other places too.)

Yes. I fought for slices in the ARG forum many months ago [1]. I was 
practically alone. Where were you guys? :-) You could have made the 
difference. It happened with indefinite elements. Here I pushed harder. 
It took three waves of discussion, at separate times. The final wave 
was started by a simple statement of need by someone else. 
Ada.Containers now have indefinite elements, but not slices. For slices 
there was only one wave. Now it's too late for Ada 2005.

[1] Discussion archived at
http://www.ada-auth.org/cgi-bin/cvsweb.cgi/AIs/AI-30302.TXT?rev=1.16

Re: Ada.Containers.Vectors - querying multiple elements

[Jeffrey Carter]

Georg Bauhaus wrote:

> Duncan Sands wrote:
> 
>>    procedure Query_Elements
>>        (Container   : in Vector;
>>         First_Index : in Index_Type;
>>         Last_Index  : in Extended_Index;
>>         Process   : not null access procedure (Elements : in 
>> Element_Array));
> 
> 
> Couldn't you use Cursors,

IMNSHO, a unbounded-array abstraction doesn't need such operations, nor 
cursors. One should use it in a manner very similar to an array:

for I in Index'First .. Last (Container) loop
    -- operate on Get (Container, I)
end loop;

During early discussions on AI-302 I implemented an unbounded-array 
package based on Ada.Strings.Unbounded, from the point of view that the 
basic operations in Unbounded are an instantiation of the 
unbounded-array with Character, Positive, and String. Here's the spec, 
if anyone's interested (lines may wrap):

with Ada.Finalization;
with System;
generic -- Unbounded_Arrays
    type Index is (<>);
    type Element is private;
    type Fixed is array (Index range <>) of Element;

    with function "=" (Left : Element; Right : Element) return Boolean 
is <>;
package Unbounded_Arrays is
    pragma Preelaborate;

    type Unbounded_Array is private;
    -- Initial value: null, equal to Null_Unbounded_Array, Length = 0.
    --
    -- An Unbounded_Array is similar to a Fixed. It has a lower bound of 
Index'First,
    -- and an upper bound that can vary dynamically up to Index'Last.

    Null_Unbounded_Array : constant Unbounded_Array;

    -- Conversions

    function To_Unbounded (Source : Fixed) return Unbounded_Array;
    function "+" (Source : Fixed) return Unbounded_Array renames 
To_Unbounded;
    -- Converts Source to an Unbounded_Array.

    function To_Fixed (Source : Unbounded_Array) return Fixed;
    function "+" (Source : Unbounded_Array) return Fixed renames To_Fixed;
    -- Converts Source to a Fixed. If Source is null and there is no 
representation
    -- for a null Fixed, raises Constraint_Error.

    -- Size and index information

    Invalid_Index : exception;
    -- Raised by operations dealing with Index when the Index is invalid.

    function Last (Source : Unbounded_Array) return Index;
    -- Returns the Index of the last position occupied in Source.
    -- If Source is null, returns Index'First.
    -- Similar to the array operation Source'Last.

    type Count is mod System.Max_Binary_Modulus;

    function Length (Source : Unbounded_Array) return Count;
    -- Returns the number of occupied positions in Source.
    -- Similar to the array operation Source'Length.
    -- If the result is > Count'Last, raises Constraint_Error.

    -- Access to Elements

    function Get (From : Unbounded_Array; Location : Index) return Element;
    -- Returns the Element stored in From at position Location.
    -- Similar to the array operation From (Location).
    --
    -- Precondition:
    --    Length (From) > 0 and
    --    Location in Index'First .. Last (From)     raises 
Invalid_Index if violated

    procedure Put (Into : in out Unbounded_Array; Location : in Index; 
Item : in Element);
    -- Changes the Element stored in Into at position Location to be Item.
    -- Similar to the array operation Into (Location) := Item.
    --
    -- Precondition:
    --    Length (Into) > 0 and
    --    Location in Index'First .. Last (Into)     raises 
Invalid_Index if violated
    --
    -- Postcondition:
    --    Get (Into, Location) = Item

    function Slice (From : Unbounded_Array; Low : Index; High : Index) 
return Fixed;
    function Slice (From : Unbounded_Array; Low : Index; High : Index) 
return Unbounded_Array;
    -- Return the slice of From with bounds Low .. High. Similar to the 
array operation
    -- From (Low .. High).
    -- The version that returns a Fixed returns a value with bounds of 
Low .. High.
    -- The version that returns an Unbounded_Array follows the 
specification of the type:
    -- the lower bound is always Index'First.
    --
    -- Precondition:
    --    Low > High                          or
    --    (Length (From) > 0                  and
    --     Low  in Index'First .. Last (From) and
    --     High in Index'First .. Last (From) )       raises 
Invalid_Index if violated

    procedure Replace_Slice (Into : in out Unbounded_Array; Low : Index; 
High : Index; Replacement : Fixed);
    procedure Replace_Slice (Into : in out Unbounded_Array; Low : Index; 
High : Index; Replacement : Unbounded_Array);
    -- Replaces the slice of Into with bounds Low .. High with Replacement.
    -- Similar to the array operation Into (Low .. High) := Replacement.
    --
    -- Preconditions:
    --    (Low > High and [Replacement'Length or Length (Replacement)] = 
0) or
    --    (Length (Into) > 0                  and
    --     Low  in Index'First .. Last (Into) and
    --     High in Index'First .. Last (Into) )       raises 
Invalid_Index if violated
    --
    --    [Replacement'Length or Length (Replacement)] =
    --    Length (Slice (Into, Low, High) )           raises 
Constraint_Error if violated
    --
    -- Postcondition:
    --    Slice (Into, Low, High) = Replacement

    -- Concatenation

    procedure Append (Onto : in out Unbounded_Array; Item : in Element);
    procedure Append (Onto : in out Unbounded_Array; Item : in Fixed);
    procedure Append (Onto : in out Unbounded_Array; Item : in 
Unbounded_Array);
    -- Equivalent to Onto := Onto & Item.

    function "&" (Left : Unbounded_Array; Right : Unbounded_Array) 
return Unbounded_Array;
    function "&" (Left : Unbounded_Array; Right : Fixed) 
return Unbounded_Array;
    function "&" (Left : Fixed;           Right : Unbounded_Array) 
return Unbounded_Array;
    function "&" (Left : Unbounded_Array; Right : Element) 
return Unbounded_Array;
    function "&" (Left : Element;         Right : Unbounded_Array) 
return Unbounded_Array;
    -- Similar to the equivalent array operations.

    -- Equality

    function "=" (Left : Unbounded_Array; Right : Unbounded_Array) 
return Boolean;
    function "=" (Left : Unbounded_Array; Right : Fixed) 
return Boolean;
    function "=" (Left : Fixed;           Right : Unbounded_Array) 
return Boolean;
    -- Returns True if Left and Right represent the same array value; 
False otherwise
private -- Unbounded_Arrays
    -- Not specified by the language ...
end Unbounded_Arrays;

Unlike the Vector container that will be part of Ada 0X, this has no 
restrictions on the Index subtype. Any discrete type is acceptable.

-- 
Jeff Carter
"What I wouldn't give for a large sock with horse manure in it."
Annie Hall
42

Re: Ada.Containers.Vectors - querying multiple elements

[Duncan Sands]

Hi Jeffrey,

> IMNSHO, a unbounded-array abstraction doesn't need such operations, nor 
> cursors. One should use it in a manner very similar to an array:
> 
> for I in Index'First .. Last (Container) loop
>     -- operate on Get (Container, I)
> end loop;

that isn't the only way of using an array.  The example of recursive
algorithms taking subarrays was already mentioned.  With the spec you
included, it looks like you would have to use the Slice function to
get a subarray - this means returning a copy on the stack, which is
unacceptable if the array is long, and also problematic (=maybe very
costly) if it contains controlled elements.

Also, if you want to use a low-level or legacy routine that operates
on an array, then you have a similar need to copy.

Ciao,

D.

Re: Ada.Containers.Vectors - querying multiple elements

[Duncan Sands]

Hi Marius,

> Yes. I fought for slices in the ARG forum many months ago [1]. I was 
> practically alone. Where were you guys? :-) You could have made the 
> difference. It happened with indefinite elements. Here I pushed harder. 
> It took three waves of discussion, at separate times. The final wave 
> was started by a simple statement of need by someone else. 
> Ada.Containers now have indefinite elements, but not slices. For slices 
> there was only one wave. Now it's too late for Ada 2005.
> 
> [1] Discussion archived at
> http://www.ada-auth.org/cgi-bin/cvsweb.cgi/AIs/AI-30302.TXT?rev=1.16

I'm reading that (long) discussion now.  How does one get onto this
mailing list?  You know, if vectors were called sequences, probably
I wouldn't be asking for slices - it's true that the name "vector"
carries a lot of mental baggage :)

Ciao,

D.

Re: Ada.Containers.Vectors - querying multiple elements

[Georg Bauhaus]

Dr. Adrian Wrigley wrote:
> On Tue, 26 Apr 2005 21:05:28 +0200, Georg Bauhaus wrote:
> 
> 
>>Duncan Sands wrote:
>>
>>
>>>But (IMHO) grabbing a "slice" of a
>>>vector is a very normal thing to want to do.  Why not support it as
>>>efficiently as possible?
>>
>>I'm curious. Where is slicing a dynamically sized vector
>>done frequently?
> 
> 
> recursive algorithms!
> (and plenty of other places too.)

Recursive algorithms on arrays that change their
'Length during recursion by removing or inserting slices?
Or are array parameters used for the side effect of passing
bounds which are really central to the algorithm? (This can
be expressed using nested subprograms of two index values,
like in quicksort, such that the array is visible to the
subprogram.)

Hmm. Is there really a big difference?
When I pass an array slice to a subprogram that takes an in mode
array parameter,
then inside the subprogram I can look at the array properties and
at elements within the array parameter's range.

OTOH, When I pass two vector cursors to an STL-like subprogram,
then inside the subprogram I can look at the vector properties and
at elements within the range specified by the two cursors.



> (this was discussed in the endless C++/Ada rant a few weeks
> ago.

IIRC, we had arrays of fixed size in these discussions, or else
array subprogram parameters. (Part of the comparison was
with std::valarray rather than std::vector, and valarray
which offers slicing is special among STL containers, as are
Ada arrays among Ada.Containers ;-)


-- Georg 

Re: Ada.Containers.Vectors - querying multiple elements

[Marius Amado Alves]

On 27 Apr 2005, at 09:15, Duncan Sands wrote:

>> Yes. I fought for slices in the ARG forum many months ago [1]...
>>
>> [1] Discussion archived at
>> http://www.ada-auth.org/cgi-bin/cvsweb.cgi/AIs/AI-30302.TXT?rev=1.16
>
> I'm reading that (long) discussion now.  How does one get onto this
> mailing list?

I don't remember exactly how I subscribed. Try sending an email with 
"help Ada-Comment" in the body to "listserv@ada-auth.org"

Re: Ada.Containers.Vectors - querying multiple elements

[Duncan Sands]

Hi Georg,

> Recursive algorithms on arrays that change their
> 'Length during recursion by removing or inserting slices?
> Or are array parameters used for the side effect of passing
> bounds which are really central to the algorithm? (This can
> be expressed using nested subprograms of two index values,
> like in quicksort, such that the array is visible to the
> subprogram.)

that's how I reimplemented the recursive algorithm that
started this thread: just pass the bounds around instead
of an actual array.  However this required rewriting the
code.  That's why I've been mentioning legacy code: what
about legacy code that I can't reasonably rewrite?  And
it seems wrong that if I want to use "vector" in some high
level abstraction built on low level building blocks, I
have to push the use of "vector" down into those building
blocks too.

Ciao,

Duncan.

Re: Ada.Containers.Vectors - querying multiple elements

[Randy Brukardt]

"Jeffrey Carter" <spam@spam.com> wrote in message
news:R_Ebe.13911$lP1.2554@newsread1.news.pas.earthlink.net...
...
> Unlike the Vector container that will be part of Ada 0X, this has no
> restrictions on the Index subtype. Any discrete type is acceptable.

Of course, you did that by having a goofy definition for Last:

    if Length(S0) = 0, Last(S0) = Index'First.
    if Length(S1) = 1, Last(S1) = Index'First.

I would have preferred to allow any discrete type in Ada.Containers.Vectors,
but I lost that battle because the natural instantiation would usually raise
Constraint_Error for enumerations and modular types. Other solutions
involving lots of special cases are possible, but ultimately, it wasn't
thought to be worth it. Enumerations as a Vector index is pretty strange,
but modular types seem useful to me.

                  Randy.


                    Randy.

Re: Ada.Containers.Vectors - querying multiple elements

[Randy Brukardt]

"Marius Amado Alves" <amado.alves@netcabo.pt> wrote in message
news:mailman.90.1114605018.24457.comp.lang.ada@ada-france.org...
>
> On 27 Apr 2005, at 09:15, Duncan Sands wrote:
>
> > I'm reading that (long) discussion now.  How does one get onto this
> > mailing list?
>
> I don't remember exactly how I subscribed. Try sending an email with
> "help Ada-Comment" in the body to "listserv@ada-auth.org"

There is a page outlining the process at
http://www.adaic.com/standards/articles/comment.html. You can find it on the
Ada 95 documents page: http://www.adaic.com/standards/ada95.html.

                Randy.

Re: Ada.Containers.Vectors - querying multiple elements

[Randy Brukardt]

"Duncan Sands" <baldrick@free.fr> wrote in message
news:mailman.79.1114531228.24457.comp.lang.ada@ada-france.org...
> Hi Matthew, to summarize your reply: "that's the price you pay for
> abstraction".  What I would really like to know is why there is a
> significant advantage to allowing implementations that are far from
> the pointer-to-an-array method.

Probably because it wouldn't have gotten enough support from the ARG without
an appropriate level of abstraction. There is a political aspect to
designing for an existing standard, after all, you don't always end up with
what someone might think is the best possible solution.

In our case, the way our generics are implemented (always shared bodies),
the "canonical" implementation would require thousands of tiny allocations.
That would work, of course, but it would hardly be high speed. By allocating
smaller chunks (and avoiding copying to/from those chunks), we can keep
those allocations down to something that is done only for the elements that
make up an expansion.


...
> > The logical model for a vector is an array, but physically a vector can
> > have any representation consistent with logical specifications.
>
> Sure, but that's not a restriction on the specification, that's a
> restriction on the implementation.  You could add a procedure like
> I mentioned to the spec - the implementations would have to implement
> it, that's all.  The question is: what do you lose by adding such a
> routine?  I fully appreciate that finding the "right" abstraction is
> a delicate balancing act requiring a lot of time and experience.  So:
> why is the current specification the right choice, and not one with
> "slices" in it.  For example, Ada.Strings.Unbounded has slices - was
> that a mistake?

The slices of Ada.Strings.Unbounded are copies, always. I don't think there
would be any problem with having a slice function -- it just would be rather
inefficient.

> > The reference implementation uses an array, but I know of a vendor who
> > plans to use a skip list, and another who plans to use a two-level
> > structure (not unlike an STL deque).
>
> To my mind, this is the real argument.  It implicitly shows that there
> can be real advantages to implementing Vector in a non-obvious way.
> However I don't see why either of these is incompatible with taking
> read-only slices.  It may not be as efficient as with a simple
> pointer-to-array implementation, but it's not bad: the deque is no
> problem, and the skip list should be pretty efficient too.  That's
> fairly inevitable: if you can access elements in constant time, you can
> access N of them in time O(N).  However it looks to me like in both
> cases the "slice" operation can be done more efficiently than by
> repeatedly calling "Element" to copy into a buffer.

A slice is a *contiguous* list of elements in every compiler that I'm
familiar with. If you have a non-contiguous representation (certainly the
case with a skip list or deque), the only way to provide that would be a
full-scale copy. (One could optimize it if it happened to be all within a
single chunk, but that seems unlikely to be of much benefit.)

> > So there are no array-based operations for vector, just as there are no
> > array-based operations for any other container.
>
> What's wrong with having operations that only apply to a vector and not
> to other containers?  I guess you have a philosophy that tells you it is
> a bad idea - care to explain?

We really wanted the Vector and List to be interoperable as much as
possible, and similarly for the Map and Set. We've tended to add operations
to the "other" container to make that possible. (In theory, you could have
an interface that would allow algorithms to work on both a Vector and a
List. That probably would be more valuable if there were more types of
sequence containers.) There are of course operations on one that isn't
allowed on the other. But I have little enthusiasm for making Vectors even
larger; it already has 240 paragraphs.

(Useless aside: When I first started formatting the containers library for
the draft AARM, I just dumped the entire text into the source file, with no
section breaks. It generated about 1200 paragraphs. I was impressed that the
tools didn't expire when given that many paragraphs at once. I'm rather glad
to not have to refer to A.18.2(1188/2). :-)

                      Randy Brukardt.

Re: Ada.Containers.Vectors - querying multiple elements

[Jeffrey Carter]

Duncan Sands wrote:

> that isn't the only way of using an array.  The example of recursive
> algorithms taking subarrays was already mentioned.  With the spec you
> included, it looks like you would have to use the Slice function to
> get a subarray - this means returning a copy on the stack, which is
> unacceptable if the array is long, and also problematic (=maybe very
> costly) if it contains controlled elements.

The standard components are not intended to be suitable for situations 
with exceptional requirements, as Randy B has made clear on many 
occasions. But if you can't accept the cost of Slice, you can always 
write your recursive algorithm to take the object and the 2 bounds.

> Also, if you want to use a low-level or legacy routine that operates
> on an array, then you have a similar need to copy.

I'm not clear how you'd expect to use a subprogram that operates on an 
array with a container, except by converting the contents to an array, 
or rewriting it to use the container.

-- 
Jeff Carter
"Son of a window-dresser."
Monty Python & the Holy Grail
12

Re: Ada.Containers.Vectors - querying multiple elements

[Jeffrey Carter]

Randy Brukardt wrote:

> "Jeffrey Carter" <spam@spam.com> wrote in message
> news:R_Ebe.13911$lP1.2554@newsread1.news.pas.earthlink.net...
> ...
> 
>>Unlike the Vector container that will be part of Ada 0X, this has no
>>restrictions on the Index subtype. Any discrete type is acceptable.
> 
> Of course, you did that by having a goofy definition for Last:
> 
>     if Length(S0) = 0, Last(S0) = Index'First.
>     if Length(S1) = 1, Last(S1) = Index'First.

It doesn't seem so goofy to me. The test for a null unbounded array is 
"S = Null_Unbounded_Array" or Length (S) = 0. Last is pretty meaningless 
if the array is null, so having it return something meaningless seemed 
better than having it raise an exception. If Length (S) = 1, then Last = 
First, by definition, so Last (S) = Index'First.

There didn't seem to be any way to return an appropriate result from 
To_Fixed if the unbounded array was null, so it raises an exception.

The definition of Last was driven by the decision to allow null 
unbounded arrays regardless of the base range of Index. Currently, 
unconstrained Ada array types can exist that don't have null arrays. 
IIRC, this will be corrected in Ada 0X; if you allow them for arrays, 
you ought to allow them for the unbounded-array abstraction.

-- 
Jeff Carter
"Son of a window-dresser."
Monty Python & the Holy Grail
12

Re: Ada.Containers.Vectors - querying multiple elements

[Duncan Sands]

> > I don't remember exactly how I subscribed. Try sending an email with
> > "help Ada-Comment" in the body to "listserv@ada-auth.org"
> 
> There is a page outlining the process at
> http://www.adaic.com/standards/articles/comment.html. You can find it on the
> Ada 95 documents page: http://www.adaic.com/standards/ada95.html.

Thanks Randy.  By the way, if you send the "help Ada-Comment" command it
tells you how to unsubscribe, but doesn't tell you how to subscribe (or
at least I didn't spot it)!

Ciao,

D.

Re: Ada.Containers.Vectors - querying multiple elements

[Duncan Sands]

> > Also, if you want to use a low-level or legacy routine that operates
> > on an array, then you have a similar need to copy.
> 
> I'm not clear how you'd expect to use a subprogram that operates on an 
> array with a container, except by converting the contents to an array, 
> or rewriting it to use the container.

When you have a container that is an extensible array, wanting to be
able to directly access slices of it as an array seems normal (and
useful) to me.  I guess the point is that Vector is not an extensible
array - the designers chose a more abstract design.  Calling it "Vector"
is just asking for confusion about what it is intended to be IMHO.

Ciao,

Duncan.

Re: Ada.Containers.Vectors - querying multiple elements

[Duncan Sands]

> The standard components are not intended to be suitable for situations 
> with exceptional requirements, as Randy B has made clear on many 
> occasions...

http://www.ada-auth.org/cgi-bin/cvsweb.cgi/AIs/AI-30302.TXT?rev=1.16

for those who are interested.

Ciao,

D.

Re: Ada.Containers.Vectors - querying multiple elements

[Matthew Heaney]

Duncan Sands <baldrick@free.fr> writes:

> Calling it "Vector" is just asking for confusion about what it is
> intended to be IMHO.

Well, the C++ ISO standard (1998) didn't require that type std::vector
be a contiguous array either.  That intepretation was added later.

Re: Ada.Containers.Vectors - querying multiple elements

[Matthew Heaney]

Duncan Sands <baldrick@free.fr> writes:

> When you have a container that is an extensible array, wanting to be
> able to directly access slices of it as an array seems normal (and
> useful) to me.

In the STL way of doing things, you don't write algorithms in terms of a
specific container.  You write algorithms in terms of an "abstract
container."  Iterators allow you to view a container in a
container-neutral way, as merely a "sequence of items," described using
an iterator pair to bound the sequence, and with iterator operations for
navigating among the elements of the sequence.

What people sometims forget is that the STL is really an algorithms
library.  The containers are designed to allow you to apply an algorithm
over the elements.

The nice thing about the STL is that it treats all containers, including
built-in arrays, the same.  Actually, I said that kinda backwards.  The
STL treats all containers just like built-in arrays.  This is because
the STL follows the C machine model, in which items exist at addresses,
and to view an item you deference a pointer with that address as its
value.

The problem you're having is that you have an algorithm written in terms
of a specific container: an array.  And now you want to apply that
algorithm to a different kind of container: a vector.  This is precisely
the kind of problem the STL algorithm model was designed to solve.

You can do this in Ada too, by writing algorithms in a way that is
container neutral.  See for example generic_anonymous_array_sort, which
is declared like this:

generic

   type Index_Type is (<>);

   with function Less (Left, Right : Index_Type)
       return Boolean is <>;

   with procedure Swap (Left, Right : Index_Type) is <>;

procedure Generic_Anonymous_Array_Sort
  (First, Last : in Index_Type'Base);

Now this is named "anonymous array sort," but in fact it works over any
container (hint: vector) that supports indexing with a discrete index
type.  The generic formal subprogram Less compares two items in the
"array", and Swap exchanges them.

<http://charles.tigris.org/source/browse/charles/src/ai302/a-cgaaso.ads>

Had you written your algorithm as above, then you wouldn't be having the
difficulties you're having now.  It would work for an array:

procedure Op (A : in out Array_Type) is
   function Less (L, R : IT) return Boolean is
   begin
      return A (L) < A (R);
   end;

   procedure Swap (L, R : IT) is
     LE : constant ET := A (L);
   begin
     A (L) := A (R);
     A (R) := LE;
  end;

  procedure Sort is new Generic_Anonymous_Array_Sort (IT);
begin
  Sort (A'First, A'Last);
end;

You'll note carefully that we don't pass the array type to the
instantiation.  That's why the algorithm is "container neutral."

The algorithm above would work equally well for a vector:

procedure Op (V : in out Vector) is
   function Less (L, R : IT) return Boolean is
   begin
      return V.Element (L) < V.Element (R);
   end;

   procedure Swap (L, R : IT) is
     LE : constant ET := V.Element (L);
   begin
     V.Replace_Element (L, V.Element (R));
     V.Replace_Element (R, LE);
  end;

  procedure Sort is new Generic_Anonymous_Array_Sort (IT);
begin
  Sort (First_Index (V), Last_Index (V));
end;


You could even write an array-specific, or vector-specific algorithm, in
terms of the non-specific algorithm, so you'd only have to write those
little binder operations once:

generic
   type IT is (<>);
   type ET is private;
   type Array_Type is array (IT range <>) of ET;
procedure Generic_Array_Sort (A : in out Array_Type);

procedure Generic_Array_Sort (A : in out Array_Type) is
   function Less (L, R : IT) return Boolean is
   begin
      return A (L) < A (R);
   end;

   procedure Swap (L, R : IT) is
     LE : constant ET := A (L);
   begin
     A (L) := A (R);
     A (R) := LE;
  end;

  procedure Sort is new Generic_Anonymous_Array_Sort (IT);
begin
  Sort (A'First, A'Last);
end Generic_Array_Sort;


For the vector, you could say:

generic
   with package Vector_Types is
     new Ada.Containers.Vectors (<>);
procedure Generic_Vector_Sort (V : in out Vector);

Or you could say:

generic
   type IT is (<>);
   type ET (<>) is private;
   type VT (<>) is limited private;
   with function Element (V : VT; I : IT) return ET is <>;
   with proc Repl_Elem (V : VT; I : IT; E : ET) is <>;
procedure Generic_Vector_Sort (V : in out VT);


Now, don't you think that's better than what you did?


> I guess the point is that Vector is not an extensible array - the
> designers chose a more abstract design.

An extensible array is the model for a vector, but of course a vector
doesn't have to be implemented that way.  

You want to view the elements in a vector as a contiguous array, but
that wouldn't confere any benefits unless if the underlying
implementation is a contiguous array.  

Re: Ada.Containers.Vectors - querying multiple elements

[Duncan Sands]

Hi Matthew, thanks for your detailed explanation.

> > When you have a container that is an extensible array, wanting to be
> > able to directly access slices of it as an array seems normal (and
> > useful) to me.
> 
> In the STL way of doing things, you don't write algorithms in terms of a
> specific container.  You write algorithms in terms of an "abstract
> container."  Iterators allow you to view a container in a
> container-neutral way, as merely a "sequence of items," described using
> an iterator pair to bound the sequence, and with iterator operations for
> navigating among the elements of the sequence.
...
> The problem you're having is that you have an algorithm written in terms
> of a specific container: an array.  And now you want to apply that
> algorithm to a different kind of container: a vector.  This is precisely
> the kind of problem the STL algorithm model was designed to solve.
> 
> You can do this in Ada too, by writing algorithms in a way that is
> container neutral.  See for example generic_anonymous_array_sort, which
> is declared like this:
...
> Had you written your algorithm as above, then you wouldn't be having the
> difficulties you're having now.  It would work for an array:
...
> Now, don't you think that's better than what you did?

You are certainly correct that when I quickly reworked the routine in
question to take a vector rather than an array, I should have done it
in a more abstract way, as in your example.  As for the other code I
have in mind, at some point things really have to be contiguous arrays
for efficiency reasons.  As pointed out in the AI discussion, efficiency
was not the main goal of the container libraries - people who need
something super efficient should write their own custom object.  That's
fine by me.

> > I guess the point is that Vector is not an extensible array - the
> > designers chose a more abstract design.
> 
> An extensible array is the model for a vector, but of course a vector
> doesn't have to be implemented that way.  

Extensible arrays are useful - it would have been nice to have them.

> You want to view the elements in a vector as a contiguous array, but
> that wouldn't confer any benefits unless if the underlying
> implementation is a contiguous array.

That's not entirely true, but in any case it would seem to go against
the philosophy you outlined above.

All the best,

Duncan.

Re: Ada.Containers.Vectors - querying multiple elements

[Duncan Sands]

> > (1) efficiency - suppose (for example) I want to transmit the
> contents
> > of my vector down a socket.
> 
> You're not grokking the Ada95 way of doing things.  Use the stream
> operations for that.  All containers (indeed, all non-limited types in
> the predefined language environment) support streaming.

By the way, I let this one drop, but in fact I wasn't thinking of sending/
receiving the whole vector down the socket, just parts of it: using the
vector as an extensible buffer for building up and processing packets
according to some communications protocol.  The Element_Type would be
Stream_Element in this case.  Sending the vector object itself makes
no sense in such a setting.  Anyway, it's my fault for forgetting to
say I only wanted to transmit slices.  The other kind of thing I had in
mind was linear algebra operations done by eg a Fortran library.  For
similar efficiency reasons you really have to be dealing with contiguous
memory - copying things all over the place costs too much.  No need to
reply to this email by the way - you've already explained that Vector was
not intended to necessarily be implemented as a contiguous array.

Ciao,

D.

Re: Ada.Containers.Vectors - querying multiple elements

[Randy Brukardt]

"Jeffrey Carter" <spam@spam.com> wrote in message
news:0uYbe.542$BE3.229@newsread2.news.pas.earthlink.net...
...
> The definition of Last was driven by the decision to allow null
> unbounded arrays regardless of the base range of Index. Currently,
> unconstrained Ada array types can exist that don't have null arrays.
> IIRC, this will be corrected in Ada 0X; if you allow them for arrays,
> you ought to allow them for the unbounded-array abstraction.

It's not really corrected in Ada 2006; it has additional aggregates that
help, but the basic problem of having to mess with the bounds still exists:

     Obj : Some_Array (Enum'First ..
Enum'Val(Enum'Pos(Enum'First)+Some_Length-1);

doesn't work if Some_Length = 0 and there is no general way to fix that. You
just have to special case Some_Length = 0 and that is unpleasant.

The solution that Ada.Containers.Vector took to this problem is essentially
to ban instantiating it with subtypes where 'First = 'Base'First. (OK, you
can do the instantiation, but it will raise Constraint_Error.) One can argue
whether that is the best solution, but it seems clear that all of the
possible solutions are ugly.

                  Randy.

Re: Ada.Containers.Vectors - querying multiple elements

[Jeffrey Carter]

Duncan Sands wrote:

> When you have a container that is an extensible array, wanting to be
> able to directly access slices of it as an array seems normal (and
> useful) to me.  I guess the point is that Vector is not an extensible
> array - the designers chose a more abstract design.  Calling it "Vector"
> is just asking for confusion about what it is intended to be IMHO.

I agree about the name. To further complicate matters, there's a type 
Vector in the matrix-math packages, violating a long-standing convention 
that the standard packages are use-friendly, even in combination.

-- 
Jeff Carter
"Beyond 100,000 lines of code you
should probably be coding in Ada."
P. J. Plauger
26

Re: Ada.Containers.Vectors - querying multiple elements

[Jeffrey Carter]

Randy Brukardt wrote:

> It's not really corrected in Ada 2006; it has additional aggregates that
> help, but the basic problem of having to mess with the bounds still exists:
> 
>      Obj : Some_Array (Enum'First ..
> Enum'Val(Enum'Pos(Enum'First)+Some_Length-1);
> 
> doesn't work if Some_Length = 0 and there is no general way to fix that. You
> just have to special case Some_Length = 0 and that is unpleasant.

Right, but you can say

Obj : Some_Array := Some_Array'(<>);

(I hope I've remembered the syntax correctly) and Obj'Length = 0; there 
was no way to do this before if Enum'First = Enum'Last. And you should 
be able to convert Obj into a corresponding unbounded array.

> The solution that Ada.Containers.Vector took to this problem is essentially
> to ban instantiating it with subtypes where 'First = 'Base'First. (OK, you
> can do the instantiation, but it will raise Constraint_Error.) One can argue
> whether that is the best solution, but it seems clear that all of the
> possible solutions are ugly.

Yes. I think this solution is uglier than having Last = First if Length = 0.

-- 
Jeff Carter
"Beyond 100,000 lines of code you
should probably be coding in Ada."
P. J. Plauger
26

Re: Ada.Containers.Vectors - querying multiple elements

[Dmitry A. Kazakov]

On Thu, 28 Apr 2005 15:55:25 -0500, Randy Brukardt wrote:

> "Jeffrey Carter" <spam@spam.com> wrote in message
> news:0uYbe.542$BE3.229@newsread2.news.pas.earthlink.net...
> ...
>> The definition of Last was driven by the decision to allow null
>> unbounded arrays regardless of the base range of Index. Currently,
>> unconstrained Ada array types can exist that don't have null arrays.
>> IIRC, this will be corrected in Ada 0X; if you allow them for arrays,
>> you ought to allow them for the unbounded-array abstraction.
> 
> It's not really corrected in Ada 2006; it has additional aggregates that
> help, but the basic problem of having to mess with the bounds still exists:
> 
>      Obj : Some_Array (Enum'First ..
> Enum'Val(Enum'Pos(Enum'First)+Some_Length-1);
> 
> doesn't work if Some_Length = 0 and there is no general way to fix that. You
> just have to special case Some_Length = 0 and that is unpleasant.
> 
> The solution that Ada.Containers.Vector took to this problem is essentially
> to ban instantiating it with subtypes where 'First = 'Base'First. (OK, you
> can do the instantiation, but it will raise Constraint_Error.) One can argue
> whether that is the best solution, but it seems clear that all of the
> possible solutions are ugly.

I wonder if introducing ranges as a type class could mend this. Provided a
fictitious attribute Enum'Range (0) would return a null-length range, one
could then create empty arrays without referencing to any concrete index
bounds. But then Obj'First and Obj'Last could potentially raise
Constraint_Error, which might appear unpleasant but perfectly consistent.
Could there be a distributed overhead in the implementations of 'First and
'Last then?

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

Re: Ada.Containers.Vectors - querying multiple elements

[Robert A Duff]

Jeffrey Carter <spam@spam.com> writes:

> I agree about the name. To further complicate matters, there's a type
> Vector in the matrix-math packages, violating a long-standing convention
> that the standard packages are use-friendly, even in combination.

That hardly seems like a big deal.  Anyway, there's precedent.
There are several types called File_Type.  If you say 'use'
on more than one I/O package, the exception names also clash.

- Bob

Re: Ada.Containers.Vectors - querying multiple elements

[Robert A Duff]

Jeffrey Carter <spam@spam.com> writes:

> Randy Brukardt wrote:
> 
> > It's not really corrected in Ada 2006; it has additional aggregates that
> > help, but the basic problem of having to mess with the bounds still exists:
> >      Obj : Some_Array (Enum'First ..
> > Enum'Val(Enum'Pos(Enum'First)+Some_Length-1);
> > doesn't work if Some_Length = 0 and there is no general way to fix
> > that. You
> > just have to special case Some_Length = 0 and that is unpleasant.
> 
> Right, but you can say
> 
> Obj : Some_Array := Some_Array'(<>);
> 
> (I hope I've remembered the syntax correctly)

I don't see any such syntax in the draft RM,
and I'm not sure which syntax you're referring to.

>... and Obj'Length = 0; there
> was no way to do this before if Enum'First = Enum'Last. And you should
> be able to convert Obj into a corresponding unbounded array.

Every array object has a 'Last in Ada.  It's simply impossible to create
an array with a 'Last that does not exist.  So a zero-length array
whose 'First is the lower bound of the base range is simply impossible.
I don't think this has changed in Ada 2006.

I don't think it's a problem, either.  If you want zero-length arrays,
then you're counting things, and signed integers are the appropriate
index type.  Arrays indexed by enums are usually things like tables,
and therefore not empty.  Can you think of an example where you want
an empty array, and a enum or modular type is appropriate for the index?
I can't think of any at the moment.

> > The solution that Ada.Containers.Vector took to this problem is essentially
> > to ban instantiating it with subtypes where 'First = 'Base'First. (OK, you
> > can do the instantiation, but it will raise Constraint_Error.) One can argue
> > whether that is the best solution, but it seems clear that all of the
> > possible solutions are ugly.
> 
> Yes. I think this solution is uglier than having Last = First if Length = 0.

Last = First seems just plain wrong, to me.  You want to loop from First
up to Last -- if Length = 0, that loop had better not do anything.

- Bob

Re: Ada.Containers.Vectors - querying multiple elements

[Randy Brukardt]

"Jeffrey Carter" <spam@spam.com> wrote in message
news:hlhce.936$HL2.780@newsread3.news.pas.earthlink.net...
> Randy Brukardt wrote:
...
> Right, but you can say
>
> Obj : Some_Array := Some_Array'(<>);
>
> (I hope I've remembered the syntax correctly) and Obj'Length = 0; there
> was no way to do this before if Enum'First = Enum'Last. And you should
> be able to convert Obj into a corresponding unbounded array.

I have no idea what you are talking about. That would represent an array
with exactly one default initialized element -- if it was allowed, which it
is not. That's because "<>" is only allowed with named notation, meaning you
have to give the bounds in the aggregate (or use "others").

                      Randy.

Re: Ada.Containers.Vectors - querying multiple elements

[Randy Brukardt]

"Robert A Duff" <bobduff@shell01.TheWorld.com> wrote in message
news:wccfyx94el8.fsf@shell01.TheWorld.com...
...
> I don't think it's a problem, either.  If you want zero-length arrays,
> then you're counting things, and signed integers are the appropriate
> index type.  Arrays indexed by enums are usually things like tables,
> and therefore not empty.  Can you think of an example where you want
> an empty array, and a enum or modular type is appropriate for the index?
> I can't think of any at the moment.

I can't think of any for enum, but for modular, it makes perfect sense.
Remember, a modular type is the only way to get an unsigned type in Ada, and
thus it's not unusual to declare such a value and give it a range, use it in
arrays, etc. Yes, it would be worlds better if there was a real, checked,
unsigned integer type in Ada (and I'd use that instead), but that was
screwed up by the Ada 9X team, and it isn't going to get fixed.

Most of my modern programs have a useful unsigned type somewhere near the
start:

    type Counter_Type is mod 2**32;

with various subtypes of that around. It's also not unusual to use a 16-bit
modular type when space is tight.

Now, I suppose if you're willing to assume that every Ada compiler supports
64-bit integers, supports unsigned storage representations, and doesn't do
64-bit operations when unsigned 32-bit operations will do, then you could
avoid using modular types in this way. But the above doesn't describe any
Ada compilers that I have used.

Once those types are in wide use, it isn't usual for them to be used to
index some data structure. And thus you get null array slices of modular
types and the like.

                         Randy.

Re: Ada.Containers.Vectors - querying multiple elements

[Randy Brukardt]

"Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> wrote in message
news:1wjh6qsazg3rg$.lupowyuqu0tw$.dlg@40tude.net...
...
> I wonder if introducing ranges as a type class could mend this. Provided a
> fictitious attribute Enum'Range (0) would return a null-length range, one
> could then create empty arrays without referencing to any concrete index
> bounds. But then Obj'First and Obj'Last could potentially raise
> Constraint_Error, which might appear unpleasant but perfectly consistent.
> Could there be a distributed overhead in the implementations of 'First and
> 'Last then?

Yes, there would be a distributed overhead. For Janus/Ada (the only compiler
for which I can speak definitively), in the general case array bounds are
stored in a descriptor record, along with a dimension length and a pointer
to the data. The dimension length is really redundant; I don't think most
compilers store it separately. In order to be able to represent an array as
you say, all compilers would have to store the dimension length and
presumably a bit mask to specify which bounds are invalid and raise C_E if
explicitly touched. And of course all references to 'First and 'Last would
have to check the bit mask. Not too expensive, but certainly a significant
change to compilers and some additional overhead.

Array indexing in the general case subtracts 'First from the calculated
value, so I don't think it would make sense to allow 'First to be an invalid
value - at least not unless the length of the array was 0 (in which case it
doesn't matter). But adding overhead to array indexing operations is not
going to win anyone friends. :-) More seriously, I think it would be a
non-starter.

You also have the problem of making the range check for any value when one
or the other bound could be invalid. More overhead in a particularly bad
spot.

So I don't think this idea is going to fly.

                  Randy.

Re: Ada.Containers.Vectors - querying multiple elements

[Jeffrey Carter]

Randy Brukardt wrote:

> I have no idea what you are talking about. That would represent an array
> with exactly one default initialized element -- if it was allowed, which it
> is not. That's because "<>" is only allowed with named notation, meaning you
> have to give the bounds in the aggregate (or use "others").

Apparently, neither do I. That's what I get for relying on my memory. I 
seem to recall something to allow declaration of a null aggregate for 
any array type, but I've now spent some time searching the AIs and can't 
find it. Sorry.

-- 
Jeff Carter
"Spam! Spam! Spam! Spam! Spam! Spam! Spam! Spam!"
Monty Python's Flying Circus
53

Re: Ada.Containers.Vectors - querying multiple elements

[Dmitry A. Kazakov]

On Fri, 29 Apr 2005 15:26:31 -0500, Randy Brukardt wrote:

> "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> wrote in message
> news:1wjh6qsazg3rg$.lupowyuqu0tw$.dlg@40tude.net...
> ...
>> I wonder if introducing ranges as a type class could mend this. Provided a
>> fictitious attribute Enum'Range (0) would return a null-length range, one
>> could then create empty arrays without referencing to any concrete index
>> bounds. But then Obj'First and Obj'Last could potentially raise
>> Constraint_Error, which might appear unpleasant but perfectly consistent.
>> Could there be a distributed overhead in the implementations of 'First and
>> 'Last then?
> 
> Yes, there would be a distributed overhead. For Janus/Ada (the only compiler
> for which I can speak definitively), in the general case array bounds are
> stored in a descriptor record, along with a dimension length and a pointer
> to the data. The dimension length is really redundant; I don't think most
> compilers store it separately. In order to be able to represent an array as
> you say, all compilers would have to store the dimension length and
> presumably a bit mask to specify which bounds are invalid and raise C_E if
> explicitly touched. And of course all references to 'First and 'Last would
> have to check the bit mask. Not too expensive, but certainly a significant
> change to compilers and some additional overhead.
>
> Array indexing in the general case subtracts 'First from the calculated
> value, so I don't think it would make sense to allow 'First to be an invalid
> value - at least not unless the length of the array was 0 (in which case it
> doesn't matter). But adding overhead to array indexing operations is not
> going to win anyone friends. :-) More seriously, I think it would be a
> non-starter.

I presume the compilers keep A'First and A'Last in T'Base, so all internal
index evaluations need not to check if 'First or 'Last is in T.

BTW, it seems that A'First is in T'Base anyway! I failed to find any clear
reference in ARM, but the following:

   X : String := "";
begin
   Ada.Text_IO.Put_Line (Integer'Image (X'First));

happily prints 0 with GNAT, no Constraint_Error!

As long as no empty enumeration *types* and no "mod 0" *types* allowed,
there is always a way to have A'First in T'Base (or better to say
"T'Implementation").

So the problem as I see it is with A'Last. Considering T is mod 1
implemented by some unsigned type, then A'First = 0, and 'Last is what? It
would be problematic to force all modular types to be internally
implemented as signed.

Yet one could have A'Last=T'Implementation'First and
A'First=T'Implementation'First+1 for empty arrays. Who cares?

Now consider the following test:

   type T is mod 1;
   type T_Array is array (T range <>);
   X : T_Array := <somehow-obtained-empty-array>;
begin
   for I in X'Range loop -- This is OK
      null;
   end loop;
   for I in X'First..X'Last loop -- This cannot be OK
      null;
   end loop;

Which is in a perfect contradiction with 3.6.2(7). It could probably be
mended too if we had universal index types. But this is yet another story.

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

Re: Ada.Containers.Vectors - querying multiple elements

[Randy Brukardt]

"Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> wrote in message
news:txah28f4zlnp$.1pqea609lovyn.dlg@40tude.net...
...
> Now consider the following test:
>
>    type T is mod 1;
>    type T_Array is array (T range <>);
>    X : T_Array := <somehow-obtained-empty-array>;
> begin
>    for I in X'Range loop -- This is OK
>       null;
>    end loop;
>    for I in X'First..X'Last loop -- This cannot be OK
>       null;
>    end loop;
>
> Which is in a perfect contradiction with 3.6.2(7). It could probably be
> mended too if we had universal index types. But this is yet another story.

In Ada as currently defined, you would get Constraint_Error from the attempt
to define the bounds. That happens with string types:

    type T is mod 1;
    type T_Array is array (T range <>) of Character;
    X : T_Array := ""; -- Raises Constraint_Error

There is actually an ACATS test to check this. (I remember it because one
vendor disputed the test; it was upheld.)

You'd get the same result if there was a way to describe a null array
aggregate:

   X : T_Array := (null array); -- Not Ada, and if it was, it would raise
Constraint_Error here.

It turns out that Interfaces.C.To_C has a similar problem, and it too raises
Constraint_Error for a null string (if not null terminated).

Of course, you could conceivably use other rules, but they'd be incompatible
with the current ones, which wouldn't be a problem in cases like these, but
they might be in other cases.

                     Randy.

Re: Ada.Containers.Vectors - querying multiple elements

[Dmitry A. Kazakov]

On Sun, 1 May 2005 22:21:42 -0500, Randy Brukardt wrote:

> "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> wrote in message
> news:txah28f4zlnp$.1pqea609lovyn.dlg@40tude.net...
> ...
>> Now consider the following test:
>>
>>    type T is mod 1;
>>    type T_Array is array (T range <>);
>>    X : T_Array := <somehow-obtained-empty-array>;
>> begin
>>    for I in X'Range loop -- This is OK
>>       null;
>>    end loop;
>>    for I in X'First..X'Last loop -- This cannot be OK
>>       null;
>>    end loop;
>>
>> Which is in a perfect contradiction with 3.6.2(7). It could probably be
>> mended too if we had universal index types. But this is yet another story.
> 
> In Ada as currently defined, you would get Constraint_Error from the attempt
> to define the bounds. That happens with string types:
> 
>     type T is mod 1;
>     type T_Array is array (T range <>) of Character;
>     X : T_Array := ""; -- Raises Constraint_Error
> 
> There is actually an ACATS test to check this. (I remember it because one
> vendor disputed the test; it was upheld.)

So "" is not allowed for any string type which index is not a
subtype/derived type S of some base type T, such that S'First>T'First. With
a nice consequence that:

type T1 is range -2147483647..0;
type T1_Array is array (T range <>) of Character;

type T2 is range -2147483648..0;
type T2_Array is array (T range <>) of Character;

type T3 is range -2147483649..0;
type T3_Array is array (T range <>) of Character;

X : T1_Array := ""; -- Legal
Y : T2_Array := ""; -- Illegal
Z : T3_Array := ""; -- Again legal!!!!!

That's really funny. What is so special in the number -2147483648? Should
it mean that potentially no program that uses negative indices and empty
strings is portable, you never know where *a* built-in integer type may
start?

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

Re: Ada.Containers.Vectors - querying multiple elements

[Robert A Duff]

"Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> writes:

> So "" is not allowed for any string type which index is not a
> subtype/derived type S of some base type T, such that S'First>T'First. With
> a nice consequence that:
> 
> type T1 is range -2147483647..0;
                    ^^^^^^^^^^
You misspelled "-2**31".  ;-)

> type T1_Array is array (T range <>) of Character;
> 
> type T2 is range -2147483648..0;
> type T2_Array is array (T range <>) of Character;
> 
> type T3 is range -2147483649..0;
> type T3_Array is array (T range <>) of Character;
> 
> X : T1_Array := ""; -- Legal
> Y : T2_Array := ""; -- Illegal
> Z : T3_Array := ""; -- Again legal!!!!!

Well, Ada's integer types are intended to be hardware-oriented, for
better or worse.  This empty-array issue is an extremely rare case.
Consider:

    X1: T1 := T1'First;
    X2: T2 := T2'First;
    X3: T3 := T3'First;

    X1 := (X1-1)/2;
    X2 := (X2-1)/2;
    X3 := (X3-1)/2;

Which of the above will raise Constraint_Error (due to overflow on the
subtraction)?  Well it's entirely implementation defined, but given
typical hardware and compiler, you'll get the same behavior as with the
empty strings.

Seems to me that arithmetic is a more common case.  I mean, nobody makes
arrays starting near -2**31.

> That's really funny. What is so special in the number -2147483648? Should
> it mean that potentially no program that uses negative indices and empty
> strings is portable, you never know where *a* built-in integer type may
> start?

Well, you know *something*.  The base range has to be symmetric about
zero (or have one extra negative value).  And you have control:

type T2_Base is range (-2**31)-1..0;
subtype T2 is T2_Base range -2**31..0;
type T2_Array is array (T2 range <>) of Character;

Now you can have empty string literals (presuming your compiler supports
signed integers as big as T2_Base).

I admit this stuff is a little bit error prone.  That's what you get
when the language is hardware oriented (for efficiency, of course).

- Bob

Re: Ada.Containers.Vectors - querying multiple elements

[Dmitry A. Kazakov]

On 02 May 2005 14:57:15 -0400, Robert A Duff wrote:

> "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> writes:
> 
>> So "" is not allowed for any string type which index is not a
>> subtype/derived type S of some base type T, such that S'First>T'First. With
>> a nice consequence that:
>> 
>> type T1 is range -2147483647..0;
>                     ^^^^^^^^^^
> You misspelled "-2**31".  ;-)

Actually it is 1 - 2**31 (:-)), but the point is that it can be any number!
The standard is silent about powers of 2. Can I write a compiler with a
built-in integer type Short_Int which range is -5..5? Is this illegal?

>> type T1_Array is array (T range <>) of Character;
>> 
>> type T2 is range -2147483648..0;
>> type T2_Array is array (T range <>) of Character;
>> 
>> type T3 is range -2147483649..0;
>> type T3_Array is array (T range <>) of Character;
>> 
>> X : T1_Array := ""; -- Legal
>> Y : T2_Array := ""; -- Illegal
>> Z : T3_Array := ""; -- Again legal!!!!!
> 
> Well, Ada's integer types are intended to be hardware-oriented, for
> better or worse.  This empty-array issue is an extremely rare case.
> Consider:
> 
>     X1: T1 := T1'First;
>     X2: T2 := T2'First;
>     X3: T3 := T3'First;
> 
>     X1 := (X1-1)/2;
>     X2 := (X2-1)/2;
>     X3 := (X3-1)/2;
> 
> Which of the above will raise Constraint_Error (due to overflow on the
> subtraction)?  Well it's entirely implementation defined, but given
> typical hardware and compiler, you'll get the same behavior as with the
> empty strings.

How would you formally, in the sense ARM 1.1.5, classify the error above
and one of using empty strings? It seems to me that to rely on
Constraint_Error above would be a bounded error. But programs using empty
strings would be illegal Ada programs.

> Seems to me that arithmetic is a more common case.  I mean, nobody makes
> arrays starting near -2**31.

I don't think that statistical approach is appropriate here. Anyway it
makes an implementation of many generic algorithms and container libraries
very difficult if possible.

> I admit this stuff is a little bit error prone.  That's what you get
> when the language is hardware oriented (for efficiency, of course).

Is this the only way to achieve efficiency?

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

Re: Ada.Containers.Vectors - querying multiple elements

[Robert A Duff]

"Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> writes:

> On 02 May 2005 14:57:15 -0400, Robert A Duff wrote:
> 
> > "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> writes:
> > 
> >> So "" is not allowed for any string type which index is not a
> >> subtype/derived type S of some base type T, such that S'First>T'First. With
> >> a nice consequence that:
> >> 
> >> type T1 is range -2147483647..0;
> >                     ^^^^^^^^^^
> > You misspelled "-2**31".  ;-)
> 
> Actually it is 1 - 2**31 (:-)),

Right.  Which proves my point, which is that your point would be clearer
if you used "2**31" or whatever instead of putting in a literal.
Without underscores, even!

>... but the point is that it can be any number!

Right.

> The standard is silent about powers of 2.

As well it should be, IMHO.

>... Can I write a compiler with a
> built-in integer type Short_Int which range is -5..5? Is this illegal?

Yes.  But the built-in types are irrelevant.  What's relevant is the
"base range" of a type.  The RM says it has to be (almost) symmetric
about zero.  So, yes, if you say "type T is range 2..3" the base range
could be -5..5 (according to the RM).

> >> type T1_Array is array (T range <>) of Character;
> >> 
> >> type T2 is range -2147483648..0;
> >> type T2_Array is array (T range <>) of Character;
> >> 
> >> type T3 is range -2147483649..0;
> >> type T3_Array is array (T range <>) of Character;
> >> 
> >> X : T1_Array := ""; -- Legal
> >> Y : T2_Array := ""; -- Illegal
> >> Z : T3_Array := ""; -- Again legal!!!!!
> > 
> > Well, Ada's integer types are intended to be hardware-oriented, for
> > better or worse.  This empty-array issue is an extremely rare case.
> > Consider:
> > 
> >     X1: T1 := T1'First;
> >     X2: T2 := T2'First;
> >     X3: T3 := T3'First;
> > 
> >     X1 := (X1-1)/2;
> >     X2 := (X2-1)/2;
> >     X3 := (X3-1)/2;
> > 
> > Which of the above will raise Constraint_Error (due to overflow on the
> > subtraction)?  Well it's entirely implementation defined, but given
> > typical hardware and compiler, you'll get the same behavior as with the
> > empty strings.
> 
> How would you formally, in the sense ARM 1.1.5, classify the error above
> and one of using empty strings? It seems to me that to rely on
> Constraint_Error above would be a bounded error. But programs using empty
> strings would be illegal Ada programs.

There's no "bounded error" here.  These things raise C_E, or return the
correct result.  If every intermediate result is in the base range, the
RM requires correct results; otherwise, it allows C_E or correct
results.  RM-4.9(34..35) might make some such things illegal -- I'm not
sure.  (Illegal = compile-time error.)

> > Seems to me that arithmetic is a more common case.  I mean, nobody makes
> > arrays starting near -2**31.
> 
> I don't think that statistical approach is appropriate here. Anyway it
> makes an implementation of many generic algorithms and container libraries
> very difficult if possible.

I don't see a big problem here.  If you're counting things, use signed
integers, and start counting at zero or one.  If you're using enums or
modulars, you're not "counting", and zero-length arrays/vectors/whatever
make no sense.

> > I admit this stuff is a little bit error prone.  That's what you get
> > when the language is hardware oriented (for efficiency, of course).
> 
> Is this the only way to achieve efficiency?

No.  I think I can design an efficent language that doesn't have these
problems.  But it ain't Ada.

- Bob

Re: Ada.Containers.Vectors - querying multiple elements

[Dmitry A. Kazakov]

On 03 May 2005 19:30:29 -0400, Robert A Duff wrote:

> "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> writes:
> 
>> I don't think that statistical approach is appropriate here. Anyway it
>> makes an implementation of many generic algorithms and container libraries
>> very difficult if possible.
> 
> I don't see a big problem here.  If you're counting things, use signed
> integers, and start counting at zero or one.  If you're using enums or
> modulars, you're not "counting", and zero-length arrays/vectors/whatever
> make no sense.

Come on, empty set appear *before* number and arithmetic. Further, to be
countable is much weaker than to be ordered. In an imaginary, better Ada
there should be unordered, uncountable types which would still allow
containers. There would be no way to enumerate elements in such container,
but for any given X it would be possible to Is_In (X, C). Even for such
weak types there should be empty containers such that Is_In returns false
for any X. 

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

Re: Ada.Containers.Vectors - querying multiple elements

[Matthew Heaney]

"Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> writes:

> In an imaginary, better Ada there should be unordered, uncountable
> types which would still allow containers. There would be no way to
> enumerate elements in such container, but for any given X it would be
> possible to Is_In (X, C). Even for such weak types there should be
> empty containers such that Is_In returns false for any X.


Tell me, Dmitry, how do you intend for predicate Is_In to be
implemented, if the objects in the container are neither ordered nor
enumerable?

Re: Ada.Containers.Vectors - querying multiple elements

[Dmitry A. Kazakov]

On Sat, 07 May 2005 01:20:21 GMT, Matthew Heaney wrote:

> "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> writes:
> 
>> In an imaginary, better Ada there should be unordered, uncountable
>> types which would still allow containers. There would be no way to
>> enumerate elements in such container, but for any given X it would be
>> possible to Is_In (X, C). Even for such weak types there should be
>> empty containers such that Is_In returns false for any X.
> 
> Tell me, Dmitry, how do you intend for predicate Is_In to be
> implemented, if the objects in the container are neither ordered nor
> enumerable?

That's an implementation detail! (:-)) But OK, here are many ways depending
on the concrete case. For example: an unordered, uncountable index is just
a public view. The container is free keep an array indexed by plain
numbers. Objects might be uncountable, but we can count containers instead.
So we attach the list of containers in which an object participates to the
object. Or else we could maintain a global incidence matrix ... and so on
and so far. My point actually was: empty containers and index ranges (sets)
must be!

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