Re: GCC 4.0 Ada.Containers Cursor danger.

[Matthew Heaney <matthewjheaney@earthlink.net>]

Mikhail Terekhov <terekhov@emc.com> writes:

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

Cursors are tied to the iteration mechanism, because the language
doesn't have support for "real" iterators.


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

But it *is* present for *all* containers, nor does it depend on cursors.
(The operation is named Contains, and returns a Boolean result.)


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

That's why the library comprises a suite of containers: you pick the
container that best fits your needs.


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

To what "basic" abstractions are you referring?


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

See section 5 here:

http://www.sgi.com/tech/stl/table_of_contents.html

Several of those algorithms have been converted to Ada for use with the
Charles library (see the operations in Charles.Algorithms.*):

http://charles.tigris.org/source/browse/charles/src/

The next phase of development of the standard library will be to
compliment the containers with a suite of algorithms.  (One problem I
haven't quite figured out is how to best describe a range.)


> Try to think a little bit farther. If there is no order or sorting,
> what is the meaning of First and Last? 

First and Last describe the (half-open) endpoints of a range.  That's
all they mean.  Whether it's important that elements are ordered of
course depends on the algorithm.


> Index sets require indirection which is provided by the core language,
> i.e. access types; they require no cursors.

Note that access types won't work, since the ARG required that
unconstrained types remain mutable when they're container elements.
This is one of the differences between Charles and the standard library.

To be more specific, if you have a record type with a default
discriminant, like this:

   type DT is (A, B, C);
   type RT (D : DT := A) is record ... end record;

then this type has to be allowed as a container element, and you must be
able to mutate the element (that is, change its discriminant) when it's
inside a container.

Access types wouldn't work, since you would have to declare the
container element as "aliased" in order to return an access value, but
that would constrain the object (fix the value of the discriminant).


> Find is not a membership test. 

Of course it's a membership test.  It finds the element in a sequence
that matches a given value.


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

Well, the containers all do have a membership test, named Contains, that
returns type Boolean.  (But containers do have a Find operation too.)


> Find is more diverse and is not always make sense.

OK, then just use Contains if all you want is a membership test.


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

Vectors have both a Find (that returns a cursor) and Find_Index (that
returns an index).

If this is a map, and you want a Generic_Find to return a key, then why
not just write it that way?  (You'll have to decide what to return if
the element is not in the map, e.g. return a value that you know can
never be a key).



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

As explained above, access types wouldn't work.  (A cursor is the
container analog of an access type, but it's at a higher level of
abstraction, since it must hide private representation details.)

Your question is a bit odd, though, since you seem to be advocating that
containers should use access types instead of cursors.  But that doesn't
make any sense, since your earlier complaint was that cursors are too
low-level.


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

You're still confused.  Start and Stop describe endpoints of a range,
but that range can be a subset of what's in a container.

Generic algorithms accept a range (described a cursor pair) since it
makes an algorithm container-neutral, and because it allows one to apply
an algorithm to a (logically contiguous) subset of elements.


> Programmers are perfecly able to do their work without Cursors, at
> least most of them (I'm not counting authors of Ada.Containers ;).

And of course you're not counting thousands of C++ programmers either.


> I would say Cursors add "double indirection" :) - for elements and
> container itself.

Yes of course.  The point of a cursor is to abstract-away the container,
and to allow a container element to be manipulated without exposing
container representation.  (Remember my mantra that "Elements are
everything.  Containers are nothing.")


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

Access types wouldn't work, as explained above.

If you have a container design that uses access types in the interface,
and allows unconstrained types to remain mutable, then please let's see
it.  Perhaps you're using some technique I hadn't thought of.