Re: GCC 4.0 Ada.Containers Cursor danger.

[Mikhail Terekhov <terekhov@emc.com>]

Georg Bauhaus wrote:
> 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.

That is right. That is exactly what I'm trying to say. Except one thing. 
There is no need for cursors during iterations.

> I can hardly think of this as a restriction in practice.

This is not a restriction. This is clarity. Cursors are not needed for 
iteration. Cursors are a special case, they should be marked as such.

> On the contrary, why should I be satisfied with just membership

No you shouldn't. But membership test is a most basic operation which 
has exactly the same semantics for _any_ container type. This operation 
should be present for all container types and it doesn't depend on order 
or cursors.

> 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? ;-)

No, you shouldn't be limited with a fixed set of operations on sets and 
you shouldn't abandon sets. I'm not really sure where did you get this 
idea from. This is almost in reverse of what I'm trying to say. You 
should be able to chose whatever abstraction fits your application best 
and this abstraction should be familiar to anyone who will read your 
source code. Sorted sets and hashes probably are very useful in some 
special cases, but they are just a special cases. It is not a very good 
idea to put some special cases as a _basis_ of the standard library. 
There is nothing wrong to put them into standard library, but only as an 
addition to or specialization of basic abstractions.

> 
> 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 :-)

That is wonderful! Almost any example of using cursor doesn't really 
need cursors. Why this burden then?

> 
> 
>> 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

Try to think a little bit farther. If there is no order or sorting, what 
is the meaning of First and Last? In your example First and Last denote 
a subset where to search and this is possible (to denote a subset using 
First and Last) only for ordered containers.

> 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 couldn't get this part about proofs by induction, could you explain?
There is nothing wrong if some program needs a sorted container. But in 
this case (I'm afraid to use this controversal term now, but couldn't 
came up with anything better :)) it is natural to use containers that 
explicitly support sort operation, because there are probably a number 
of sort orders and Sorted_Set can support just one that is 
implementation defined. Then your algorithm will be clear, 
implementation independent, easily understandable and probably more 
efficient.

> 
> 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?

Index sets require indirection which is provided by the core language, 
i.e. access types; they require no 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?

Find is not a membership test. Membership test is more generic, i.e it 
has _the same_ semantics for _any_ kind of container, namely "does this 
container contain this element or not?" Membership test is not a 
replacement for various kinds of search and vice versa. Find is more 
diverse and is not always make sense. For "mappings" i.e. vectors and 
hashes for example "Find" could return a key (index for vectors) of the 
element or a list/vector/set of keys whose elements satisfy some 
predicate. For ordered containers that are not mappings (lists, trees) 
"Find" could degenerate into membership test or could became "FindNext", 
"FindPrev" or "Count". For sets "Find" degenerates into membership test 
or could return a subset according to some predicate (as in your example).
So, you see that "Find" differs for diffrent container types. It is 
"less generic" than membership test.

> 
>> 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:

Exactly, but "silly" example can't prove anything.

> 
> (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.

If you need just a set of references to some elements, then you are all 
set. Ada provides access types, why cursor?

> 
>> 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.

Cursors could be an implementation detail, they are not needed for 
general API. Start and Stop can have no sense for some containers. 
Algorithm can use internally whatever it needs to deliver result.

> 
>> 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.

Programmers are perfecly able to do their work without Cursors, at least 
most of them (I'm not counting authors of Ada.Containers ;). I would say 
Cursors add "double indirection" :) - for elements and container itself.

> Imagine programming without indirection, whatever the indirection
> mechanism looks like.

That would be a disaster :), let's say clear and loudly: "we love 
indirection", and let's use it explicitly via access types.:)

> 
> 
>> 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...
> 
Where did you get this idea from?

Regards,
Mikhail