Re: GCC 4.0 Ada.Containers Cursor danger.

[Georg Bauhaus <bauhaus@futureapps.de>]

Mikhail Terekhov wrote:

>     - First is that all containers have an order.
>       Again, sets and hashes in general are *not ordered*.
>       To impose an order on them standard needs to put a
>       restriction on implementarion algorithms.

Ada.Containers require that the elements of a set say can be
had one after the other through iteration using cursors.
I can hardly think of this as a restriction in practice.
On the contrary, why should I be satisfied with just membership
test? Or with a fixed set of operations on sets? Or why should I
abandon sets in favor of some other containers, because they
fit better with someone's ideas of how a mathematical structure
is sometimes defined? ;-)

Say I want a subset B of A,

  B := {x: x in A | x >= 0};

This could be done using a generic algorithm which is similar
to the Generic_Find algorithm that Matt has presented in that
there will be a generic formal procedure that acts
as the predicate ">= 0?".

generic
   with function Predicate(C: Cursor) return Boolean;
function Subset(S: Set) return Set;

function Subset(S: Set) return Set is
   C: Cursor := First(S);
   result: Set;
begin
   while Has_Element(C) loop
      if Predicate(C) then
         Include(result, Element(C));
      end if;
      Next(C);
   end loop;
   return result;
end Subset;

(The example doesn't really need iteration using cursors explicitly
because Iterate(S, Conditional_Include'access) or similar will do.
However, that's just an ad hoc example that I could think of and I wanted
to show cursors :-)


> You example
>       is completely legal generic function in the current
>       Ada.Containers framework. But if you decide at some
>       point to add unordered containers, then you generic
>       function became invalid because for unordered containers
>       "first" and "last" have no sence at all.

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.
Their purpose then is to start and end the enumeration of the elements
in the set. You can think of cursors as elements of a mathematical
index set (yes!) that is associated with the elements in some set.
Such as is used for example in proofs by induction, or when you want
to transform a set into a sorted set, etc.

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?

>     - Second is that find/search operation makes sence only
>       for a mapping container i.e. vector or hash;

Find is a membership test, how could it not make sense for
a set?

> there is no sence to search for the element
>       if you already have it.

(I had called my procedure "silly".) Programming is not equal
to logic ;-) Notice two uses:

(1) > True generic operation for all container types can be membership
> test not find/search.
This is a membership test, but only accidentally. Think of an extended
algorithm that gives you a set of cursors of all occurences of
some item in a container, whatever kind of container it is.

> Another problem with your example is that it is essentially a NOP.
> If you already have a cursor for your element why to search for it?

(2) The Cursor "item" designates an element in _some_ container.
This need not be the container that is searched.
Start and Stop can refer to a different container.
The algorithm will find the element in that container.

> Some times cursors replace
> collections completely! That kind of indirect interface is very
> dangerous in my view.

And Cursors enable programmers to do their work. Cursors add indirection.
Imagine programming without indirection, whatever the indirection
mechanism looks like.


> Now to answer you question, just replace "My_Container" by
> "My_Vector_Container", then "item: My_Vector_Container.Cursor" by
> "item: My_Vector_Container.Element_Type" and then "Cursor" by "Index"
> in that order and you will get a "vectorized" version of you
> function ;)

Forcing every client program to use vectors...


-- Georg