Re: GCC 4.0 Ada.Containers Cursor danger.

["Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de>]

On Fri, 15 Jul 2005 12:39:50 +0200, Georg Bauhaus wrote:

> Dmitry A. Kazakov wrote:
> 
>>>  B := {x: x in A | x >= 0};
>>>
>> See the well-ordering theorem and then the axiom of choice. (:-))
> 
> Yes, therefore Ada.Containers can't be contradicting basic
> mathematics that much. :-)

Ask Goedel! (:-))

>> Think about differences between:
>> 
>> - An unordered set of unordered elements
>> - An unordered set of ordered elements
>> - An ordered set of unordered elements
>> - An ordered set of ordered elements (and these orders are different)
> 
> Can we resolve the name overloading by using
> "as if physically positioned" and
> "accessible in sort order", respectively, for the moment?
> Then there may or may not be an overlap between the two orders in practice.
> An implementation may choose to physically position
> the elements in sort order in an internal structure, or not.

An implementation may choose anything that does not violate the contract.
If the contract tells that it is the same order, then I can use it in my
program as follows:

if Pos_Of_A < Pos_Of_B then
   pragma Assert (A < B);

This program becomes illegal if orders are different. It is all about
safety.

>>>For me, First and Last (or whatever you call them) *do* make sense
>>>for any reasonable notion of a set in programming, sorted or not,
>>>even when used in computer science.
>> 
>> Hmm, what about ring buffers?
> 
> You don't mean the two pointers in a ring buffer cannot
> make sense?

But pointers are unordered in Ada, for many good reasons, BTW. Note also
that the designers of Ada 83 knew the difference. This is why we have:

   for I in A'Range loop ...

because

   for I in A'First..A'Last loop ...

could potentially be meaningless. This potential is not used because Ada's
ADT is still underdeveloped, nevertheless.

>>>I find Cursors useful when I want to put an index set into operations
>>>inside a computer. When I'm can use any container,
>>>how could I implement index sets without Cursors?
>> 
>> You are mixing implementation and interface.
> 
> How can I think about "putting into operations" with just interfaces?
> (In any practical sense of operation inside a computer.)
> So how can I implement index sets without Cursors?

Index is not Cursor. If you need an indexed collection then it must be one.
Plain sets are not indexed. That is, the contract of a plain set does not
provide any way of indexing. You can have an indexed collection a subtype
of a plain set, not the opposite. [Though Ada.Containers is a macro library
following the bad example of STL, but this is another story.]

>>>Find is a membership test, how could it not make sense for
>>>a set?
>> 
>> No. Find is more general.
> 
> (It is still also a membership test.)

No. Because the result is not Boolean.

>> [and again, sets could be searchable and not]
> 
> What do you mean by a set container that is used in a program
> and that you cannot search?

type Square_Matrix is array (...) of Element;

Searching in matrices is quite meaningless. Note that multi-dimensional
indexed containers have no order, because their indices are unordered.
[countable /= has native order, BTW] Now consider a search, which finds one
element in your program and another when you pass the same matrix to a
FORTRAN program, just because FORTRAN allocates arrays by columns. This is
the essence of the C-style of programming. Have fun!

> You can't find members, so how
> is a set that you cannot search more useful than one in which
> you can actually find an element?

It is not *a* set. It is a contract of a class of sets. To make this class
wide enough to include all interesting sets, the contract should be as weak
as possible. This is the whole idea of generic programming. The algorithms
based on least premises are more powerful than less generic ones. The
trade-off is genericity vs. efficiency.

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