GCC 4.0 Ada.Containers Cursor danger.

GCC 4.0 Ada.Containers Cursor danger.

[Dmitriy Anisimkov]

IMHO the cursors in the Ada.Containers implemented in GCC 4.0
dangerouse like pointers in C/C++.

Look at the code below.
----------------------------------------------
with Ada.Containers.Indefinite_Hashed_Maps;
with Ada.Strings.Hash;

package HTab is new Ada.Containers.Indefinite_Hashed_Maps
                      (String, Integer, Ada.Strings.Hash, "=", "=");
-----------------------------------------------------------------
with Ada.Text_IO;
with HTab;

procedure AC1 is
   use Ada.Text_IO;

   package Table renames HTab;

   Cursor    : Table.Cursor;
   Cursor2   : Table.Cursor;
   Container : Table.Map;
   Success   : Boolean;
begin
   Table.Insert (Container, "one", 11111, Cursor, Success);
   pragma Assert (Success);
   Table.Insert (Container, "two", 22222, Cursor, Success);
   pragma Assert (Success);
   Table.Insert (Container, "three", 33333, Cursor, Success);
   pragma Assert (Success);

   Table.Insert (Container, "two", 2222, Cursor, Success);
   pragma Assert (not Success);

   --  Delete element "two" independently.

   Cursor2 := Table.Find (Container, "two");
   Table.Delete (Container, Cursor2);

   --  The erroreneous line below do nothing and do not raise any
exception.

   Table.Replace_Element (Cursor, -22222);

   Cursor := Table.First (Container);

   --  Print all lines, and see that we do not have a key "two".

   while Table.Has_Element (Cursor) loop
      Put_Line (Table.Key (Cursor) & ' ' & Integer'Image (Table.Element
(Cursor)));
      Table.Next (Cursor);
   end loop;
end AC1;
------------------------------------------------------------
The code above have to raise at least runtime error at
Table.Replace_Element (Cursor, -22222); but it do nothing and do not
raise any exception.

valgrind showing the memory corruption
---------------------------
==24602== Invalid read of size 4
==24602==    at 0x804F1EC: htab__replace_element (a-cihama.adb:630)
==24602==    by 0x805024D: _ada_ac1 (ac1.adb:31)
==24602==    by 0x8049C2F: main (b~ac1.adb:157)
==24602==  Address 0x1BA4EAF8 is 8 bytes inside a block of size 16
free'd
==24602==    at 0x1B903B0D: free (vg_replace_malloc.c:152)
==24602==    by 0x805D257: __gnat_free (s-memory.adb:113)
==24602==    by 0x804D8CD: htab(float, long double,...)(...)
(a-cihama.adb:338)
==24602==    by 0x804CAE5: htab__delete__2 (a-cihama.adb:205)
==24602==    by 0x805021E: _ada_ac1 (ac1.adb:27)
==24602==    by 0x8049C2F: main (b~ac1.adb:157)
==24602==
==24602== Invalid write of size 4
==24602==    at 0x804F223: htab__replace_element (a-cihama.adb:632)
==24602==    by 0x805024D: _ada_ac1 (ac1.adb:31)
==24602==    by 0x8049C2F: main (b~ac1.adb:157)
==24602==  Address 0x1BA4EAF8 is 8 bytes inside a block of size 16
free'd
==24602==    at 0x1B903B0D: free (vg_replace_malloc.c:152)
==24602==    by 0x805D257: __gnat_free (s-memory.adb:113)
==24602==    by 0x804D8CD: htab(float, long double,...)(...)
(a-cihama.adb:338)
==24602==    by 0x804CAE5: htab__delete__2 (a-cihama.adb:205)
==24602==    by 0x805021E: _ada_ac1 (ac1.adb:27)
==24602==    by 0x8049C2F: main (b~ac1.adb:157)
---------------------------

I am using "ADT Components" from
http://lgl.epfl.ch/ada/components/index.html too.
I'm writting in ADT but have to use code with AI302.
I did not found so much errors with ADT as with AI302 and with
Ada.Containers cursors.

ADT do not have a cursors at all. All get/put operations from container
is just per key. All iterations via the containers are with simple
generic procedures.

I'm not sure that it is possible to implement runtime error detection
in such cursor situation.

I think that ADT is much more on the Ada way then proposed
Ada.Containers with cursors.

Re: GCC 4.0 Ada.Containers Cursor danger.

[Georg Bauhaus]

Dmitriy Anisimkov wrote:
> IMHO the cursors in the Ada.Containers implemented in GCC 4.0
> dangerouse like pointers in C/C++.

I think saying that Cursors are as dangerous as Ada pointers
is more to the point. IIRC there are significant
differences between Ada.Containers and STL, more checks i.e.

Not sure though why Replace_Element doesn't raise an exception,
possibly because messing around with two pointers to the same object
and then deleting the object can lead to erroneous execution:

"Erroneous Execution

"A Cursor value is *invalid* if any of the following have occurred since it was
created:
  ...
  * The node it designates has been deleted from the map."

Why are you using two different cursors (pointers),
then delete their element (set the pointee to null) using one,
and then expect the other cursor (pointer) to be designating
some object still? (I guess you don't but expect this the example
is made up to convey this impression.)


> valgrind showing the memory corruption
> ---------------------------

> I am using "ADT Components" from
> http://lgl.epfl.ch/ada/components/index.html too.

> I think that ADT is much more on the Ada way then proposed
> Ada.Containers with cursors.

Should access types not be in Ada? At what cost?

Cc: charles users list at tigris


Georg 

Re: GCC 4.0 Ada.Containers Cursor danger.

[Georg Bauhaus]

Georg Bauhaus wrote:

> some object still? (I guess you don't but expect this the example
some object still? (I guess you don't expect this but the example

Sorry

Re: GCC 4.0 Ada.Containers Cursor danger.

[Dmitriy Anisimkov]

<<"A Cursor value is *invalid* if any of the following have occurred
since it was
created:
  ...
  * The node it designates has been deleted from the map." >>

Sure i understand that cursor become invalid. If the danger is written
in RM it is not become less danger.

<<Should access types not be in Ada?>>

Should be, because we could not make access to be invalid other then to
do *Unchecked_Deallocation* on it. Cursors could become invalid a much
more easier. I think access types in Ada safer than cursors in proposed
Ada.Containers.

<<Why are you using two different cursors (pointers),
then delete their element (set the pointee to null)>>

Because it is just example. Real code was different, and mistake was
made by the different person, i just found the error.
----------------------------
Table.Insert (Container, "two", 2222, Cursor, Success);

if not Success then
   Some_Package.Delete_From_Container (Key => "two");
end if;

Table.Replace_Element (Cursor, -22222); 
--------------------

Re: GCC 4.0 Ada.Containers Cursor danger.

[Matthew Heaney]

Dmitriy Anisimkov wrote:
> ----------------------------
> Table.Insert (Container, "two", 2222, Cursor, Success);
>
> if not Success then
>    Some_Package.Delete_From_Container (Key => "two");
> end if;
>
> Table.Replace_Element (Cursor, -22222);
> --------------------

This is confused.  No matter what value is returned for Success (BTW:
the formal parameter is named "Inserted"), the key "two" is in the map.
 So the predicate that follows the Insert is not necessary.

As has already been pointed out, the call to Replace_Element is
erroneous, since the element designated by Cursor was deleted (at least
that's what I think the example is doing).

The solution to the problem is to simply not use cursors:

Container.Include ("two", 2222);
...
Container.Include ("two", -22222);

Now all is well.  Just use Include, and you won't have any problems.
Alternatively, you can say:

Container.Include ("two", 2222);
...
declare
   C : Cursor;
   B : Boolean;
begin
   Container.Insert ("two", -22222, C, B);
   if not B then
      Replace_Element (C, By => -22222);
   end if;
end;

You really need to sit down and read the AI:

<http://www.ada-auth.org/cgi-bin/cvsweb.cgi/AIs/AI-20302.TXT?rev=1.21>

-Matt

Re: GCC 4.0 Ada.Containers Cursor danger.

[Maxim Reznik]

Georg Bauhaus wrote:
> Dmitriy Anisimkov wrote:
> 
>> IMHO the cursors in the Ada.Containers implemented in GCC 4.0
>> dangerouse like pointers in C/C++.
> 

I agree with Dmitry such behavior of Cursors is very dangerous
and should be avoided.

> 
> "Erroneous Execution
> 
> "A Cursor value is *invalid* if any of the following have occurred since
> it was
> created:
>  ...
>  * The node it designates has been deleted from the map."
> 

Why dont request to set such invalid cursor to No_Element to avoid
dangling references?
If container knows all his cursors it can do it easy.
There are a very few cursors per container in typical program,
so it is not big work.
And safety here is much important then performacne.

> 
>> valgrind showing the memory corruption
>> ---------------------------

Using such hard tool to debug operations with containers is
certainly be avoided.

-- 
Maxim Reznik
http://www.ada-ru.org/

Re: GCC 4.0 Ada.Containers Cursor danger.

[Georg Bauhaus]

Maxim Reznik wrote:

> I agree with Dmitry such behavior of Cursors is very dangerous
> and should be avoided.

That's what Matthew has said: You don't have to use
Cursors with maps. The library is generous enough to
provide Cursors, should you need them for some reason.

> If container knows all his cursors it can do it easy.

The knowledge + checking results in performance loss.

> There are a very few cursors per container in typical program,
> so it is not big work.

Care to give some data? It is difficult to argue about
hot air.

> And safety here is much important then performacne.

Sometimes performance is a *requirement* for achieving
safety, there is no trade-off between speed and checking
access then. E.g. response time must be within some limit,
therefore the container algorithm must work within
O(the-function-here).


Georg 

Re: GCC 4.0 Ada.Containers Cursor danger.

[Maxim Reznik]

Georg Bauhaus wrote:
> Maxim Reznik wrote:
> 
>> I agree with Dmitry such behavior of Cursors is very dangerous
>> and should be avoided.
> 
> 
> That's what Matthew has said: You don't have to use
> Cursors with maps. The library is generous enough to
> provide Cursors, should you need them for some reason.
> 

I mean it should be avoided by Ada (by standard), not by the user.

>> If container knows all his cursors it can do it easy.
> 
> The knowledge + checking results in performance loss.
> 
>> There are a very few cursors per container in typical program,
>> so it is not big work.
> 
> 
> Care to give some data? It is difficult to argue about
> hot air.
> 

I look in all my Ada programs. There are a few loops per container,
no more that 2 or 3 at once. Because cursors's main purpose is
iteration over containers I think there will be a few cursors per
container usually.

If make container remember all its cursors we can implement
all operations which make cursors invalid so that they
reset invalid cursors to No_Element.

For instance, Remove will iterate over all cursors for
the container, check target of cursor and set cursor to
No_Element if target match removed element.

>> And safety here is much important then performacne.
> 
> 
> Sometimes performance is a *requirement* for achieving
> safety, there is no trade-off between speed and checking
> access then. E.g. response time must be within some limit,
> therefore the container algorithm must work within
> O(the-function-here).
> 

The method I propose costs O(cursors per container) performance
penalty. I think it's acceptable cost for safety.

If we should choise between safe and good performance
Ada containers I would choose safe ones.
In rare cases when user encounter performace limits he
could easy implement his own container, with limited functionality.
And he will know exactly where dangling references cound apear.

Now cursor is like grenade. You don't know what happens if you
use it. Because you can't check is it valid cursor.
Even objects imported form other language are safer, because
you can check them with 'Valid attribute before use them.

> 
> Georg

Re: GCC 4.0 Ada.Containers Cursor danger.

[Georg Bauhaus]

Maxim Reznik wrote:

> I look in all my Ada programs. There are a few loops per container,
> no more that 2 or 3 at once. Because cursors's main purpose is
> iteration over containers I think there will be a few cursors per
> container usually.

Are these inner loops or outer loops? How often are
they run?


> For instance, Remove will iterate over all cursors for
> the container, check target of cursor and set cursor to
> No_Element if target match removed element.

> The method I propose costs O(cursors per container) performance
> penalty. I think it's acceptable cost for safety.

Could you indicate which cost you have in mind,
and in which cases it is acceptable? E.g. explaining in T(n) etc terms
your Remove analysis above?


> In rare cases when user encounter performace limits he
> could easy implement his own container,

Just repeating the word "easily" doesn't convince me that programming
NIH containers is an easy task. I find it puzzling that people
keep talking safe, safe, safe, and then roll their own
containers, thinking this is easy and safe.

OTOH, Matthew demonstrates how you can add checking on top
of Ada.Containers when you have reason not to trust your Cursors.


> with limited functionality.
> And he will know exactly where dangling references cound apear.
> 
> Now cursor is like grenade. You don't know what happens if you
> use it. Because you can't check is it valid cursor.

We don't know what happens if we blindly use a pointer,
too. They could have been deallocated without check,
for a reason. Cursors aren't fully checked pointers, true. But
there is a reason that Unchecked_Deallocation is in the
Ada language. You could ban Unchecked_Deallocation for
the same reasons you give for banning Cursors.

Re: GCC 4.0 Ada.Containers Cursor danger.

[Matthew Heaney]

Maxim Reznik wrote:
>
> I mean it should be avoided by Ada (by standard), not by the user.

This is completely wrong.  You have no business legislating behavior
for everyone else.

This reminds me of our laws here in the US during the time of
prohibition.  These little old ladies complained that "We don't drink,
and we don't want anyone else to drink either," and so the sale of
alcohol was made illegal.  Well that's ridiculous.  If you yourself
choose not to consume alcohol, then that is your own business.  You
have no right to take away someone else's freedoms.

(Thankfully the laws against the sale of alcohol were repealed.  It's
still a sorry state of affairs here, however, since we still have laws
criminalizing the use of other recreational drugs such as marijuana,
which has only created a huge, billion-dollar black market.  So much
for our belief in limited government and free market capitalism.  But I
digress...)

The point is that you should only worry about your own behavior.  If
other developers make choices different from you, then those are their
choices.  Stop worrying about everyone else.


> If make container remember all its cursors we can implement
> all operations which make cursors invalid so that they
> reset invalid cursors to No_Element.

If you want that abstraction, then you can write it yourself.  That's
what freedom means.


> For instance, Remove will iterate over all cursors for
> the container, check target of cursor and set cursor to
> No_Element if target match removed element.

Fine, then you can implement the Remove operation of your container
abstraction that way.  You have complete freedom to do so.


> The method I propose costs O(cursors per container) performance
> penalty. I think it's acceptable cost for safety.

Fine, then you have the freedom to implement such an abstraction.


> If we should choise between safe and good performance
> Ada containers I would choose safe ones.

Fine, then that's your choice.  Why are you so obsessed with what
everyone else does?


> In rare cases when user encounter performace limits he
> could easy implement his own container, with limited functionality.
> And he will know exactly where dangling references could apear.

Yes, and that user is you.  You have the freedom to implement such a
container.


> Now cursor is like grenade. You don't know what happens if you
> use it.

The solution is simple: don't use cursors.  You have that freedom.

-Matt

Re: GCC 4.0 Ada.Containers Cursor danger.

[Dmitriy Anisimkov]

Matthew,

Of cause we have a freedom to choose safest of dangerouse programming
language. But if we choose the safest language, we should not make it
dangerous.

Human freedom is a much different than programming freedom. Who want
the programing freedom should go to C/C++. There are a lot of "free to
make mistake" programmers.

I prefer that compiler detect all my possible errors at compile time
and runtime as early as possible. There a so much possabilities to
write program, and if compiler and standard library would lead me to
the safest way, it would a help a lot and dramatically reduce
development time.

Re: GCC 4.0 Ada.Containers Cursor danger.

[Matthew Heaney]

Dmitriy Anisimkov wrote:
>
> I prefer that compiler detect all my possible errors at compile time
> and runtime as early as possible. There a so much possabilities to
> write program, and if compiler and standard library would lead me to
> the safest way, it would a help a lot and dramatically reduce
> development time.

If you think that it's safer to write Ada programs using the standard
container library, but without using its cursors, then do so.  You have
that freedom.

Re: GCC 4.0 Ada.Containers Cursor danger.

[Randy Brukardt]

"Maxim Reznik" <reznikmm@front.ru> wrote in message
news:dagnvs$2s9f$1@pandora.alkar.net...
...
> I look in all my Ada programs. There are a few loops per container,
> no more that 2 or 3 at once. Because cursors's main purpose is
> iteration over containers I think there will be a few cursors per
> container usually.

Most programs will have no cursors at all, or only one in stored in a local
variable. It would be almost impossible for there to be any trouble with
such a cursor.

Other programs will store cursors in other data structures. Such a program
could store a large number of cursors.

> If make container remember all its cursors we can implement
> all operations which make cursors invalid so that they
> reset invalid cursors to No_Element.

Yes, that is the "checked" implementation of cursors. The standard certainly
allows such an implementation, and you're welcome to implement such an
implementation. But it is likely to be too slow for any application that
uses a lot of cursors (especially if they create and destroy a lot of
cursors).

I would have preferred that we require a check for dangling cursors so long
as the container itself still exists. (Once the container is destroyed,
checks are pretty much impossible.) But I lost that battle, because the
implementation is not quite bullet-proof.

Anyway, this is a quality of implementation issue. If you care about checks,
you should insist that your Ada vendor provide them. (RRS will certainly
make checks in its implementation of containers. They should catch all
obvious mistakes [like your example], and most others as well.) If you care
about certain types of performance, ditto. Nothing in the standard prevents
either.

                             Randy.

Re: GCC 4.0 Ada.Containers Cursor danger.

[Alex R. Mosteo]

Maxim Reznik wrote:
> Georg Bauhaus wrote:
> 
>>Maxim Reznik wrote:
>>>There are a very few cursors per container in typical program,
>>>so it is not big work.
>>
>>
>>Care to give some data? It is difficult to argue about
>>hot air.
>>
> 
> 
> I look in all my Ada programs. There are a few loops per container,
> no more that 2 or 3 at once. Because cursors's main purpose is
> iteration over containers I think there will be a few cursors per
> container usually.

There are cases where keeping around several (or many) cursors can be 
handy. A need I encountered was to keep a set of elements ordered by two 
different criteria. In my case I wanted to access the objects by "Id" 
and by "Age". Instead of having two copies of each object, or use access 
types, another possible implementation is creating a new container which 
internally uses two maps, one of them containing the objects and the 
other containing cursors for the other set. In this way all dynamic 
memory management is done by the standard containers.

Re: GCC 4.0 Ada.Containers Cursor danger.

[Matthew Heaney]

Maxim Reznik <reznikmm@front.ru> writes:

> If container knows all his cursors it can do it easy.

No, a container does *not* "know all his cursors".  It only has the
storage it needs for elements.

It certainly would be possible to implement a container abstraction this
way: maintain a reference count for each node, to count how many extant
cursors designate that node.  When the element is deleted from the
container, then check the reference count: if it's greater than 0, then
move the element (really, it's internal storage node) onto a pending
delete list.  When a cursor attempts to dereference an element on the
pending delete list, then raise an exception.

This is all possible.  But notice that it comes at a significant cost:
there is additional per-element storage overhead, and the cursor type
must be controlled.

Re: GCC 4.0 Ada.Containers Cursor danger.

[Matthew Heaney]

Maxim Reznik wrote:
> If container knows all his cursors it can do it easy.

This is like saying, "Flying airplanes is dangerous.  But if a plane
uses anti-gravity, then flying will be safe."

So I must reject your conclusion, because I reject your premise:
containers don't know about extant cursors.  If you want a container
that has such knowledge, then just implement it yourself.

Re: GCC 4.0 Ada.Containers Cursor danger.

[Randy Brukardt]

"Georg Bauhaus" <bauhaus@arcor.de> wrote in message
news:42C98672.3020705@arcor.de...
> Dmitriy Anisimkov wrote:
> > IMHO the cursors in the Ada.Containers implemented in GCC 4.0
> > dangerouse like pointers in C/C++.
>
> I think saying that Cursors are as dangerous as Ada pointers
> is more to the point. IIRC there are significant
> differences between Ada.Containers and STL, more checks i.e.
>
> Not sure though why Replace_Element doesn't raise an exception,
> possibly because messing around with two pointers to the same object
> and then deleting the object can lead to erroneous execution:

Yes. It's very expensive to make such checks that would be bulletproof (a
cursor would need to be a controlled type with an indirect reference to the
container, and the container would need to maintain a list of all existence
cursors). Thus the checks aren't mandated.

However, these checks are relatively easy to make in cases like the one
given. And nothing in the standard prevents an implementation from making a
check in this case. I believe that Ada implementations ought to make such
checks in the easy cases (certainly the Janus/Ada implementation will). One
of the real advantages to cursors in this case is that checks *can* be made;
if we had used access types directly, no such checks would be possible.

One can imagine a debugging version of the containers that made all possible
checks, no matter what the cost. (I think my design is good enough for
general use, because we can check almost all errors for a small additional
cost in the size of cursors.)

                  Randy Brukardt

                          Randy Brukardt

Re: GCC 4.0 Ada.Containers Cursor danger.

[Matthew Heaney]

Dmitriy Anisimkov wrote:
> begin
>    Table.Insert (Container, "one", 11111, Cursor, Success);
>    pragma Assert (Success);
>    Table.Insert (Container, "two", 22222, Cursor, Success);
>    pragma Assert (Success);
>    Table.Insert (Container, "three", 33333, Cursor, Success);
>    pragma Assert (Success);

You don't need conditional insertion here.  Just use the 3-param
Insert:

  Container.Insert ("one", 1);
  Container.Insert ("two", 2);
  Container.Insert ("three", 3);


>    Table.Insert (Container, "two", 2222, Cursor, Success);
>    pragma Assert (not Success);
>
>    --  Delete element "two" independently.
>
>    Cursor2 := Table.Find (Container, "two");
>    Table.Delete (Container, Cursor2);
>
>    --  The erroreneous line below do nothing and do not raise any
> exception.
>
>    Table.Replace_Element (Cursor, -22222);

Well of course this is erroneous, since the element designated by
Cursor was deleted in the previous statement!


> ------------------------------------------------------------
> The code above have to raise at least runtime error at
> Table.Replace_Element (Cursor, -22222); but it do nothing and do not
> raise any exception.

It certainly does not have to raise a runtime error.  It can do
anything it likes, since the behavior is undefined.


> valgrind showing the memory corruption

That's good, since what you did corrupts the memory.


> ADT do not have a cursors at all. All get/put operations from container
> is just per key. All iterations via the containers are with simple
> generic procedures.

This is like saying, Tall buildings shouldn't have windows, since if
there's a window, you might jump out of the window and hurt yourself.

The solution is simple: don't jump out of windows...


> I'm not sure that it is possible to implement runtime error detection
> in such cursor situation.

It's software, we can doing anything we want.  So of course you can
detect dangling cursors -- but not without a runtime penalty (in both
time and space).


> I think that ADT is much more on the Ada way then proposed
> Ada.Containers with cursors.

If you don't like cursors, then don't use 'em.  Certainly with a map,
you never need to use cursors.

Re: GCC 4.0 Ada.Containers Cursor danger.

[Dmitriy Anisimkov]

>   Container.Insert ("one", 1);
>   Container.Insert ("two", 2);
>   Container.Insert ("three", 3);
>
> >    Table.Insert (Container, "two", 2222, Cursor, Success);
> >    pragma Assert (not Success);
> >
> >    --  Delete element "two" independently.
> >
> >    Cursor2 := Table.Find (Container, "two");
> >    Table.Delete (Container, Cursor2);
> >
> >    --  The erroreneous line below do nothing and do not raise any
> > exception.
> >
> >    Table.Replace_Element (Cursor, -22222);
>
> Well of course this is erroneous, since the element designated by
> Cursor was deleted in the previous statement!

Matthew,

I know that code have an error. I'm saying that the errors like this is
easy to create, and hard to find. Neither compiler not runtime check
for this errors. So, my point is trying to avoid using cursors, for
safety reasons. The Ada is designed to be safe language, Ada is a
hardly checking operations with access types, it is because we have
Unchecked_Deallocation and Unchecked_Access and Unrestricted_Access for
see, where could be danger. I do not see any "Unchecked_" operations
with a cursors. As I understand all cursors operations is "Unchecked_".
If i have to use cursors, i'm in the danger of errors like this. I'm
sure we could use containers without cursors. ADT doing it with
success.

I would propose to have a Ada.Containers subset without cursors for
safety reasons.

<<> valgrind showing the memory corruption

That's good, since what you did corrupts the memory.>>

Note that there is no way in Ada to currupt memory other then by
Unchecked_ or Unrestricted_ access operations. Ada.Containers introduce
a more "legal" way to do memory curruption. Why Java has so much
popularity. One of the reasons that there is absolutely no way to
currupt memory. I do not like Java for some reasons, but I hope Ada
would not be in the C "freedom" to currupt memory.

> The solution is simple: don't jump out of windows...

Where the "windows" safer in C or in Ada ?

Re: GCC 4.0 Ada.Containers Cursor danger.

[Matthew Heaney]

Dmitriy Anisimkov wrote:
>
> I would propose to have a Ada.Containers subset without cursors for
> safety reasons.

You are free to write Ada *programs* that don't use cursors, but that
is far different from proposing that the *library* not use cursors.


> Where the "windows" safer in C or in Ada ?

We are not debating here anything about the language proper.  We are
simply debating the choices in the design of the standard container
library.

Of course it would be possible to design the library such that cursor
misuse is required to be detected.  But not without incurring a
substantial time and space penalty.

The solution in your case is for *you* to either not use cursors, or to
implement a higher-level abstraction that either prevents or detects
cursor misuse.  Something like:

package Container_Types is
   type Container_Type is limited private;
   type Cursor is private;
   function Find (C : CT; E : ET) return Cursor;
...
private
   type Node_Type is record
      E : ET;
      Cursor_Count : Natural := 0;
   end record;

   package Rep_Types is
     new Ada.Containers.Ordered_Maps (KT, Node_Type, ...);
     --whatever container suits your needs
...
   type Container_Type is
      new Limited_Controlled with record
         H : Handle_Type (Container_Type'Access); -- rosen trick
         Rep : Rep_Types.Map;
         Cursor_Count : Natural := 0;
      end record;
...
   type Cursor is
      new Controlled with record
        Rep : Rep_Types.Cursor;
      end record;
...
end Container_Types;

Now you can record the fact that there are extant cursors:

  function Find (C : CT; E : ET) return Cursor is
    Result : Rep_Types.Cursor := Rep_Types.Find (C, E);
  begin
    if not Has_Element (Result) then
       return Cursor'(Controlled with Rep_Types.No_Element);
    end if;

    declare
       procedure Inc_Count (Node : in out Node_Type) is
       begin
          Node.Cursor_Count := Node.Cursor_Count + 1;
       end;
   begin
       Update_Element (Result, Inc_Count'Access);
   end;

   C.H.Cursor_Count := C.H.Cursor_Count + 1;

   return (Controlled with Result);
  end Find;

Now when you attempt to Delete an element (as you did in your earlier
example), you can inspect the node's cursor count and take appropriate
action.

In the Finalize operation of your Container_Type, you can detect
whether there exist extant cursors, and if so take appropriate action.

Of course, all these checks have a time and space cost.  If you're
willing to pay that cost, then by all means implement your container
abstractions as above.  The standard container library is flexible and
efficient enough that it allows you to implement any other (less
flexible and less efficient but putatively safer) abstraction.

-Matt

Re: GCC 4.0 Ada.Containers Cursor danger.

[Dmitriy Anisimkov]

<<The solution in your case is for *you* to either not use cursors, or
to
implement a higher-level abstraction that either prevents or detects
cursor misuse.>>

I think that 2nd method is too hard to reach safety. I prefer to reach
safety by the 1st method. It is not problem for me to reach safety. I
just fill bad about such unsafety in new Ada standard.

Re: GCC 4.0 Ada.Containers Cursor danger.

[Matthew Heaney]

Dmitriy Anisimkov wrote:
> <<The solution in your case is for *you* to either not use cursors, or
> to implement a higher-level abstraction that either prevents or detects
> cursor misuse.>>
>
> I think that 2nd method is too hard to reach safety.

Too hard for whom?  You're the one who is always fulminating against
the evils of pointers, so perhaps you should follow your own advice...


> I prefer to reach safety by the 1st method. It is not a problem for
> me to reach safety.

Then what are we arguing about?  If writing safe abstractions is not a
problem for you, then clearly there is no problem.


> I just feel bad about such unsafety in new Ada standard.

As the Irish say, "Never scald your lips with another man's porridge."

-Matt

Re: GCC 4.0 Ada.Containers Cursor danger.

[Dmitriy Anisimkov]

> I prefer to reach safety by the 1st method. It is not a problem for
> me to reach safety.

<< Then what are we arguing about? >>

About new Ada standard. I did try to connect to AI302 discussion, but
it was closed.

<<As the Irish say, "Never scald your lips with another man's
porridge.">>

Safety is not a matter of taste, it is a matter of software quality.
Ada without safety is not better then C++.

Re: GCC 4.0 Ada.Containers Cursor danger.

[Matthew Heaney]

Dmitriy Anisimkov wrote:
> << Then what are we arguing about? >>
>
> About new Ada standard.

That is silly.  We should be arguing whether you personally are able to
write correct programs in Ada.

> Safety is not a matter of taste, it is a matter of software quality.
> Ada without safety is not better then C++.

Safety is a matter of degree.  Safety is also in tension with
flexibility and efficiency.

In fact the Ada 2005 standard container library is much safer than the
C++ STL, so your argument is specious, and your comparison to C++ is
invidious.

Re: GCC 4.0 Ada.Containers Cursor danger.

[Dmitriy Anisimkov]

<<so your argument is specious>>

Do you think that arguments below is "specious" ?

<<Ada is a
hardly checking operations with access types, it is because we have
Unchecked_Deallocation and Unchecked_Access and Unrestricted_Access for
see, where could be danger.>>

<<Note that there is no way in Ada95 to currupt memory other then by
Unchecked_ or Unrestricted_ access operations. Ada.Containers cursors
introduce a more "legal" way to do memory curruption.>>

Re: GCC 4.0 Ada.Containers Cursor danger.

[Randy Brukardt]

"Dmitriy Anisimkov" <anisimkov@yahoo.com> wrote in message
news:1120615856.997416.158870@g14g2000cwa.googlegroups.com...
...
> <<Note that there is no way in Ada95 to currupt memory other then by
> Unchecked_ or Unrestricted_ access operations. Ada.Containers cursors
> introduce a more "legal" way to do memory curruption.>>

Yes, this argument is incorrect. You can corrupt memory in Ada 95 with
address clauses, Unchecked_Conversion, pragma Suppress, streams,
Sequential_IO, Direct_IO, Storage_IO, and probably some other ways that I've
forgotten.

And, as I've said several times, I think a containers implementation that
corrupts memory as you describe is wrong. Not wrong by the letter of the
Standard, but wrong from the intent of Ada.

If you want to claim that the Standard should say something else, that's
fine, but the truth is that there are a lot of things that the Standard
allows that implementers really should not take advatange of. For instance,
most uses of Unchecked_Conversion allow erroneous execution (and likely
memory corruption) in code far away from the conversion. This is a really
bad thing, and I would hope that most implementations don't take advantage
of it. But the Standard still allows it, because it is thought to be
critical to getting appropriate performance in some cases.

                        Randy Brukardt

Re: GCC 4.0 Ada.Containers Cursor danger.

[Dmitriy Anisimkov]

<<You can corrupt memory in Ada 95 with
address clauses, Unchecked_Conversion, pragma Suppress, >>

The danger of this operations is undersood, at least for me.

<<streams, Sequential_IO, Direct_IO, Storage_IO, >>

I do not know how the streams and IO could broke memory. Could you
explain a bit more ?

I think Ada.Containers cursors should not be in the same danger as
Unchecked_*** operations.

Re: GCC 4.0 Ada.Containers Cursor danger.

[Randy Brukardt]

"Dmitriy Anisimkov" <anisimkov@yahoo.com> wrote in message
news:1120707674.230510.280700@g47g2000cwa.googlegroups.com...
> <<You can corrupt memory in Ada 95 with
> address clauses, Unchecked_Conversion, pragma Suppress, >>
>
> The danger of this operations is undersood, at least for me.
>
> <<streams, Sequential_IO, Direct_IO, Storage_IO, >>
>
> I do not know how the streams and IO could broke memory. Could you
> explain a bit more ?

Input of binary data is essentially the same operation as an
Unchecked_Conversion from an array of byte to the output object. If the
output object is composite, what is read in can make the object "abnormal";
any use of an abnormal object afterwards causes erroneous execution and thus
may corrupt memory.

Most problems happen if an object with embedded pointers (explicit or
implicit) is read, because it is never safe to read in pointers. (The memory
that they point at is unlikely to contain the same objects.)

But (almost) any binary input can cause problems if the stream of bytes is
corrupted. And the program really has no control over that, as anything can
happen to the file after it is written and before it is read.

                    Randy.

Re: GCC 4.0 Ada.Containers Cursor danger.

[Dmitriy Anisimkov]

<<Input of binary data is essentially the same operation as an
Unchecked_Conversion from an array of byte to the output object.>>

I think we could have a check for about 99.9% errors in stream reading
if we put some checking bytes into input data format.

Re: GCC 4.0 Ada.Containers Cursor danger.

[Simon Wright]

"Dmitriy Anisimkov" <anisimkov@yahoo.com> writes:

> I think we could have a check for about 99.9% errors in stream reading
> if we put some checking bytes into input data format.

*You* can if you want to but *I* might say to myself, "This is a
TCP-based stream, why should I double-check what the transport layer
is doing anyway?"

If on the other hand my system is built up of many parts, not all of
which are under my control, and some of which are built in C, I might
want checks built in if only to make sure I can integrate the
thing. But then I doubt I'll be able to use Ada.Streams all that
easily.

Re: GCC 4.0 Ada.Containers Cursor danger.

[Dmitriy Anisimkov]

<< *You* can if you want to but *I* might say to myself, "This is a
TCP-based stream, why should I double-check what the transport layer
is doing anyway?" >>

The transport layer is protected enought. I'm talking about protection
of the reader side from errors on the writers side. So the errors (or
malicious intent) on the sender would not cause broken memory on the
reader side.

Re: GCC 4.0 Ada.Containers Cursor danger.

[Dmitriy Anisimkov]

Simon Wright :
<< *You* can if you want to but *I* might say to myself, "This is a
TCP-based stream, why should I double-check what the transport layer
is doing anyway?" >>

The transport layer is protected enought. I'm talking about protection
of the reader side from errors on the writers side. So the errors (or
malicious intent) on the sender would not cause broken memory on the
reader side.

Re: GCC 4.0 Ada.Containers Cursor danger.

[Martin Dowie]

Dmitriy Anisimkov wrote:
> I would propose to have a Ada.Containers subset without cursors for
> safety reasons.

I doubt if that Ada.Containers would be used in systems that have safety 
concerns.

Cheers

-- Martin

Re: GCC 4.0 Ada.Containers Cursor danger.

[Dmitriy Anisimkov]

I think that safety is a good feature even for the regular
applications. It would help to reduce debugging time

Matthew told:
<<Safety is also in tension with flexibility and efficiency. >>

I think that containers without cursors could loose some flexibility,
but do not loose functionality and performance. And definately gaining
in safety and in the debugging time.

Re: GCC 4.0 Ada.Containers Cursor danger.

[Georg Bauhaus]

Dmitriy Anisimkov wrote:
> I think that safety is a good feature even for the regular
> applications. It would help to reduce debugging time
> 
> Matthew told:
> <<Safety is also in tension with flexibility and efficiency. >>
> 
> I think that containers without cursors could loose some flexibility,
> but do not loose functionality and performance.

If you remove cursors, like for example from Insert/4,
then you will definitly have algorithms that will run
more slowly using more memory cells or register cells.

This is because cursors on dynamic containers work to achieve
some efficiency. It's worthwhile to read up on the AI 302.

I'm assuming you somehow found a way around the case where you have
to compare strings and/or hash them in order to repeatedly
find a key? Or how do you remember a position in a dynamic
container? Using a cursor, certainly O(1) is less than
O(hashing + string comparisons)?

And how do you _not_ loose efficiency if on every loop
iteration you check the validity of your variables related
to container elements?

> And definately gaining
> in safety and in the debugging time.

You are gaining exceptions in some cases.

If there were a number of generic algorithms working on
top of Ada.Containers, would they be useful in your work?

How about idiomatic uses of the library?


Georg 

Re: GCC 4.0 Ada.Containers Cursor danger.

[Dmitriy Anisimkov]

<<If you remove cursors, like for example from Insert/4,
then you will definitly have algorithms that will run
more slowly using more memory cells or register cells.>>

Depend on what to do with returned cursor later.
In some cases it would be enought to have Insert_Or_Replace without
cursors routine.

<<I'm assuming you somehow found a way around the case where you have
to compare strings and/or hash them in order to repeatedly
find a key? Or how do you remember a position in a dynamic container?>>


Algorithm should be designed for be able to get value by key just once.
Use and modify it and put it back. Other option is to use
Generic_Update_Element routine.

<<And how do you _not_ loose efficiency if on every loop
iteration you check the validity of your variables related
to container elements? >>

Iteration could be done in the generic routine too.  Like in
Generic_Iteration but with a one more out parameter "Quit : out
Boolean" in Process procedure generic parameter.

<< If there were a number of generic algorithms working on
top of Ada.Containers, would they be useful in your work?

How about idiomatic uses of the library? >>

AWS (Ada Web Server) was based on ADT containers before move to AI302
containers.  I found a lot of errors in AWS after move to AI302, all of
them was a broken memory on invalid cursors.

I'm using ADT containers to keep forex trading accounts, prices,
positions and configuration of the operative part of the Internet
Currency Trading system.
There is a indexed containers

Currency_Pairs
Accounts
Accounst in Currency_Pairs
Currency_Pairs in Accounts
Trades
Trades in Accounts/Currency Pairs

Some of the elements linked directly by Access type.

The operations on them is get by key, modify by key, iteration untill
condition, and all of them is without cursors and without find more
then once.

Re: GCC 4.0 Ada.Containers Cursor danger.

[Pascal Obry]

"Dmitriy Anisimkov" <anisimkov@yahoo.com> writes:

> AWS (Ada Web Server) was based on ADT containers before move to AI302
> containers.  I found a lot of errors in AWS after move to AI302, all of
                       ^^^^^^^^
                       some :)
> them was a broken memory on invalid cursors.

Pascal.

-- 

--|------------------------------------------------------
--| Pascal Obry                           Team-Ada Member
--| 45, rue Gabriel Peri - 78114 Magny Les Hameaux FRANCE
--|------------------------------------------------------
--|              http://www.obry.net
--| "The best way to travel is by means of imagination"
--|
--| gpg --keyserver wwwkeys.pgp.net --recv-key C1082595

Re: GCC 4.0 Ada.Containers Cursor danger.

[Georg Bauhaus]

Dmitriy Anisimkov wrote:


> Depend on what to do with returned cursor later.

Precisely.

> In some cases

And why should we base decisions about the design of a standard
library on "In some cases..."?


> <<I'm assuming you somehow found a way around the case where you have
> to compare strings and/or hash them in order to repeatedly
> find a key? Or how do you remember a position in a dynamic container?>>
> 
> 
> Algorithm should be designed for be able to get value by key just once.
> Use and modify it and put it back.

Are you suggesting that all library algorithms can be designed so
that each value in a container is used no more than one time only?

> <<And how do you _not_ loose efficiency if on every loop
> iteration you check the validity of your variables related
> to container elements? >>
> 
> Iteration could be done in the generic routine too. 

You don't address the problem of checking access, as being behind a
generic iteration or using cursors in your programs has nothing
to do with checking or not. Checking takes time.
Therefore, if iteration is checking every access, iteration will
have to run more slowly, unless you have found some miraculous
speedup device called "zero cost access check". Have you found one?

Did you have a look at

  Iterate(C, P'access);


> Like in
> Generic_Iteration but with a one more out parameter "Quit : out
> Boolean" in Process procedure generic parameter.

Again, this doesn't say anything about checking multiple
Cursors pointing to the same element.


> << If there were a number of generic algorithms working on
> top of Ada.Containers, would they be useful in your work?
> 
> How about idiomatic uses of the library? >>

Again, will idiomatic use of library algorithms help?
Will generic algorithms help? (Notice that generic algorithms here are
not generic subprograms in the container packages. They are algorithms
of general use that can be used with many containers.)


> Some of the elements linked directly by Access type.
> 
> The operations on them is get by key, modify by key, iteration untill
> condition, and all of them is without cursors and without find more
> then once.
> 

And? If you have "some elements linked directly by access type"
that sounds like a linked list to me. I guess you do "iteration
until" by pointers, and prepare for null access exceptions for
unexpected cases.
If this is the way and the truth and the light for a general
library...


Consider an iteration-until approach with a linked list in
the following situation:

- you get m stock exchange records per second
- you have to filter out some of them
- the filter changes every <insert time interval here>

The filter is: belongs_to_this_set_of_certificates(...)
where the set isn't tiny. It is also changing with time,
as I said.

We use a Set and Find to see whether a record is in the set.
(C++ STL, by availability)

Should we be looking upt certificates by building our own linked
list and use it as a set?
And therefore have every lookup run in T(n/2) where n is the size of
the linked-list-set?
You can't do this linear search when time matters, i.e. when
you build a real time system.



-- 
----------------------------------------------------------------
Georg Bauhaus                              bauhaus@futureapps.de
Future Apps GmbH                        http://www.futureapps.de
phone: +49 203 306 1560

Re: GCC 4.0 Ada.Containers Cursor danger.

[Pascal Obry]

Martin Dowie <martin.dowie@btopenworld.com> writes:

> I doubt if that Ada.Containers would be used in systems that have safety
> concerns.

I think Dmitriy has a good point. For the first time in Ada we have the
possibility to create easily a dangling pointer using Cursor. This was not
possible before except by using Unchecked_Deallocation.

Now I do not see this as an argument to remove them. But in fact the problem
we are talking about has happened in AWS. We can't dismiss this just by saying
do not use Cursor :) It is a potential problem, we must be sure that it is a
known one. As Matthew said it is possible to wrap cursors to avoid this
problem for safety reasons.

Pascal.

-- 

--|------------------------------------------------------
--| Pascal Obry                           Team-Ada Member
--| 45, rue Gabriel Peri - 78114 Magny Les Hameaux FRANCE
--|------------------------------------------------------
--|              http://www.obry.net
--| "The best way to travel is by means of imagination"
--|
--| gpg --keyserver wwwkeys.pgp.net --recv-key C1082595

Re: GCC 4.0 Ada.Containers Cursor danger.

[Dmitriy Anisimkov]

<<We can't dismiss this just by saying do not use Cursor :)>>

We did not use cursors in AWS with ADT (Table_Of_...), is it ?

<< As Matthew said it is possible to wrap cursors to avoid this
problem for safety reasons. >>

It would spend a lot of performance. I prefer to do not use the
cursors, and keep performance.

Re: GCC 4.0 Ada.Containers Cursor danger.

[Pascal Obry]

"Dmitriy Anisimkov" <anisimkov@yahoo.com> writes:

> <<We can't dismiss this just by saying do not use Cursor :)>>
> 
> We did not use cursors in AWS with ADT (Table_Of_...), is it ?

Right since the Table_Of... had no cursor. But using cursor it is possible
to have better performance. You can replace an element in-place.

Pascal.

-- 

--|------------------------------------------------------
--| Pascal Obry                           Team-Ada Member
--| 45, rue Gabriel Peri - 78114 Magny Les Hameaux FRANCE
--|------------------------------------------------------
--|              http://www.obry.net
--| "The best way to travel is by means of imagination"
--|
--| gpg --keyserver wwwkeys.pgp.net --recv-key C1082595

Re: GCC 4.0 Ada.Containers Cursor danger.

[Dmitriy Anisimkov]

<<Right since the Table_Of... had no cursor. But using cursor it is
possible
to have better performance. You can replace an element in-place.>>

   procedure Insert_Or_Replace_Value (Table : in out Table_Type;
                                      Key : in Key_Type;
                                      Value : in Value_Type);
   --  OVERVIEW:
   --    Inserts the couple (KEY, VALUE) into TABLE if there is no
entry with
   --  this key. Otherwise the given VALUE replaces the previous one.

   procedure Replace_Value (Table : in out Table_Type;
                            Key : in Key_Type;
                            Value : in Value_Type);
   --  OVERVIEW:
   --    An entry having key KEY is searched for in TABLE. The given
VALUE then
   --  replaces the previous one.
   --  ERROR:
   --    If there is no entry with the given key, the exception
   --  MISSING_ITEM_ERROR is raised.

   procedure Replace_Value (Table : in out Table_Type;
                            Key : in Key_Type;
                            Value : in Value_Type;
                            Found : out Boolean);
   --  OVERVIEW:
   --    An entry having key KEY is searched for in TABLE. The given
   --  VALUE then replaces the previous one. No action is taken and no
error
   --  occurs if there is no entry with the given key, except that
FOUND
   --  is set to false.


What is slower ?

Re: GCC 4.0 Ada.Containers Cursor danger.

[Pascal Obry]

"Dmitriy Anisimkov" <anisimkov@yahoo.com> writes:

>    procedure Insert_Or_Replace_Value (Table : in out Table_Type;
>                                       Key : in Key_Type;
>                                       Value : in Value_Type);

Ok, we had Insert_Or_Replace_Value. Cursors are more versatile though.

Pascal.

-- 

--|------------------------------------------------------
--| Pascal Obry                           Team-Ada Member
--| 45, rue Gabriel Peri - 78114 Magny Les Hameaux FRANCE
--|------------------------------------------------------
--|              http://www.obry.net
--| "The best way to travel is by means of imagination"
--|
--| gpg --keyserver wwwkeys.pgp.net --recv-key C1082595

Re: GCC 4.0 Ada.Containers Cursor danger.

[Dmitriy Anisimkov]

What is closer to Ada ideology versatility or safety ?

Re: GCC 4.0 Ada.Containers Cursor danger.

[Georg Bauhaus]

Dmitriy Anisimkov wrote:
> What is closer to Ada ideology versatility or safety ?
> 
Well, both of course, how else could you write
versatile real-time programs which have to be safe?

Re: GCC 4.0 Ada.Containers Cursor danger.

[Dmitriy Anisimkov]

Maybe i do not good understand the meaning of "versatility", but I was
able fast to do whatever i want whithout cursors under ADT.

If you could show me the code where you think cursors is fastest, i
could try to provide example with same functionality without cursors
with the same or better speed.

Re: GCC 4.0 Ada.Containers Cursor danger.

[Matthew Heaney]

Dmitriy Anisimkov wrote:
> Maybe i do not good understand the meaning of "versatility", but I was
> able fast to do whatever i want whithout cursors under ADT.
>
> If you could show me the code where you think cursors is fastest, i
> could try to provide example with same functionality without cursors
> with the same or better speed.

If you think that it's safer to write Ada programs using the standard
container library, but without using its cursors, then do so.  You have
that freedom.

Re: GCC 4.0 Ada.Containers Cursor danger.

[Dmitriy Anisimkov]

I just need a bit more routines without cursors. Is Ada.Containers open
for new routine proposals ?

Re: GCC 4.0 Ada.Containers Cursor danger.

[Matthew Heaney]

All such requests for language changes should be directed to the
ada-comment list at ada-auth.org.

Re: GCC 4.0 Ada.Containers Cursor danger.

[Georg Bauhaus]

Dmitriy Anisimkov wrote:

(I can't tell for sure whether you are responding to my message because your
answer doesn't provide context, but after guessing and inspecting
message headers, I think you are responding to my post?)

> Maybe i do not good understand the meaning of "versatility", but I was
> able fast to do whatever i want whithout cursors under ADT.

You keep saying, "Mine was fast!" and you don't tell us how
fast compared to what. How can repeated hashing be as fast as
direct access via a cursor? How can a linear search be as fast as
direct access via a cursor?  Fast enough for you is very different
from being fast enough for an application that expects O(1) or
O(N log N) with a suitable factor.

As has been said, there is a performance cost if
you don't use cursors and use, for example, copying.
There is a performance cost if a library forces its user to
repeatedly look up a key by recomputing slots each time, for example.

There is a different cost if checking is done everywhere.


Or consider (I'm picking up your linked list example)

   while
     my_pointer_from_node_to_node /=  find_sentinel_node(container)
   loop
      mess_around_with_elements;
      update(my_pointer_from_node_to_node);
   end loop;

This is a place where there is a performance issue.
For "normal" algorithms, a recommendation might be to find the sentinel
node just once.

declare
   stop_here: Some_Node_Type := find_sentinel_node(container);
begin
   while
     my_pointer_from_node_to_node /= stop_here
   loop
      mess_around_with_elements;
      update(my_pointer_from_node_to_node);
   end loop;
end;

Can you assume that the sentinel node found before the first
iteration remains valid when you mess around with the elements inside
the loop?  No.

So you say we need a safe container and we need the first
formulation of the loop, not the second, which is likely faster.

However, even if find_sentinel_node(container) finds a valid
node each time, how do we know whether mess_around_with_elements
will do no harm? So we should have checking in each and every place,
you say? And you say that there is no significant cost if we
check every use of an element? No cost if a library allows
only recomputed searches for the very same element, no caching
via cursors?

But why do we mess_around_with_elements in the first place?


> If you could show me the code where you think cursors is fastest, i
> could try to provide example with same functionality without cursors
> with the same or better speed.

I though we were talking
about using keys for lookup or using cursors for lookup. Here is
a silly example using Cursors (which of course can be programmed
differently, e.g. not using Containers at all etc. but this is beside
the point). I don't think that *using* *lookup* *by* *key* will
be faster than direct access via Cursor.  See the case statement.



with Ada.Calendar;
with String_Maps;
  -- String values associated with Time values

procedure Silly is

   use Ada.Calendar;

   type Request_From_Somewhere is (On, Off);
   procedure read(r: out Request_From_Somewhere; t: out Time) is separate;

   request: Request_From_Somewhere;

   box: String_Maps.Map;
   now: Time;
   zero: constant Time := Clock;

   here, there: String_Maps.Cursor;
   yes: Boolean;

begin
   -- insert the two elements, assigning Cursors on the way:

   String_Maps.Insert(box, "one", zero, here, yes);
   String_Maps.Insert(box, "another", zero, there, yes);

   loop
      -- read a request, and depending on the requested value,
      read(request, now);

      -- swap the values stored with "one" and "another".
      case request is
         when On =>
            String_Maps.replace_element(here, now);
            String_Maps.replace_element(there, zero);
         when Off =>
            String_Maps.replace_element(here, zero);
            String_Maps.replace_element(there, now);
      end case;
   end loop;

end Silly;

Re: GCC 4.0 Ada.Containers Cursor danger.

[Dmitriy Anisimkov]

<<
> Maybe i do not good understand the meaning of "versatility", but I was
> able fast to do whatever i want whithout cursors under ADT.

You keep saying, "Mine was fast!" and you don't tell us how
fast compared to what. How can repeated hashing be as fast as
direct access via a cursor?>>

I do not think that "repeated hashing be as fast as
direct access via a cursor".

If I need direct access to elements, I put dynamically allocated object
(maybe smart pointer) into container, and keep access where i need.
I think it is more honestly than to keep cursors.
So I take responsibility for deallocation. And library does not have to
check
for invalid cursors.

<<How can a linear search be as fast as
direct access via a cursor?>>

Strange question. I do not know answer. I did not propose linear
search.

<<There is a performance cost if a library forces its user to
repeatedly look up a key by recomputing slots each time, for example.>>

If user need direct access, he has to create this access himself.

<<So you say we need a safe container and we need the first
formulation of the loop, not the second, which is likely faster.>>

In the safe containers loop should be inside generic procedure, and
without
cursors.

generic
   procedure Process (Key : Key_Type; Value : Value_Type; Stop : out
Boolean);
procedure Generic_Iteration (Container : Container_Type);
--  Process all elements untill Stop.

<<procedure Silly is>>

The container is not thread safe I see, so, the nobody would modify it
untill
we are working on it. It would be better to put elements into container
after
the loop. If we really need to put it there before loop, I would put
access
into containers and modify content via access.

Re: GCC 4.0 Ada.Containers Cursor danger.

[Matthew Heaney]

"Dmitriy Anisimkov" <anisimkov@yahoo.com> writes:

> In the safe containers loop should be inside generic procedure, and
> without cursors.
> 
> generic
>    procedure Process (Key   : Key_Type; 
>                       Value : Value_Type; 
>                       Stop  : out Boolean);
> procedure Generic_Iteration (Container : Container_Type);
> --  Process all elements untill Stop.

Fine, then write this yourself:

procedure Generic_Iteration (Container : Map) is
   Done : Boolean;

   procedure Process (K : KT; E : ET) is
   begin
      Process (K, E, Done);
   end;

   C : Cursor := Container.First;
begin
   while Has_Element (C) loop
      Query_Element (C, Process'Access);
      exit when Done;
      Next (C);
   end loop;
end Generic_Iteration;

Re: GCC 4.0 Ada.Containers Cursor danger.

[Dmitriy Anisimkov]

<< Fine, then write this yourself: >>

I could write it for sure. But why Ada.Containers user have to write
safety wrappers for Ada standard library ? Users who want and
understand safety would prefer different containers library.

Don't say please that "You are free to use whatever containers
library".

I think everybody whant that Ada standard containers should be safe.

Re: GCC 4.0 Ada.Containers Cursor danger.

[Matthew Heaney]

"Dmitriy Anisimkov" <anisimkov@yahoo.com> writes:

> << Fine, then write this yourself: >>
> 
> I could write it for sure. But why Ada.Containers user have to write
> safety wrappers for Ada standard library ? Users who want and
> understand safety would prefer different containers library.

Of course the library already has a passive iterator, declared like this:

procedure Iterate 
  (Container : CT; 
   Process   : not null access procedure Process (Posn : Cursor));

We designed the passive iterator around the common case, which is to
visit every element in the container.  

You have a special need: for a stop parameter, and to always pass both
the key and the element to the process procedure.  The library gives you
the tools to construct such an abstraction, which is what I showed in my
previous post.


> Don't say please that "You are free to use whatever containers
> library".
> 
> I think everybody whant that Ada standard containers should be safe.

During the container library design process, the ARG was *very*
concerned about safety.  This library has many more checks than you get
in the C++ STL, for example.

You still don't seem to grok the idea that safety, efficiency, and
flexibility are in tension.  You can't optimize for all three
simultaneously, so you have to make a choice about how efficient vs. how
safe.

Re: GCC 4.0 Ada.Containers Cursor danger.

[Georg Bauhaus]

Dmitriy Anisimkov wrote:

> If I need direct access to elements, I put dynamically allocated object
> (maybe smart pointer) into container, and keep access where i need.

But you can do that now with Ada containers.

> generic
>    procedure Process (Key : Key_Type; Value : Value_Type; Stop : out

If you are worried about Ada 2006's Iterate using Cursors internally
(in the Process procedure), what makes you sure that the programmers
writing the procedure for Process in Generic_Iterate above will
not use the wrong key in their procedure?

If the use the (logically) wrong key, there will be a bug that is even
harder to find than if a Cursor becomes invalid. This is because
you can't notice the error. No checks and not even detectable memory
corruption due to erroneous execution. So are keys really always
more safe than Cursors?

Second, we loose a few things of general use
if we can only use smart pointers or keys instead of standard Ada
cursors.
 For example, for any algorithm working on Cursors using their
operations and little else (generic algorithms a la STL) we will have to
reinvent and reconsider every cursor operation as a smart pointer
operation.


> I think it is more honestly than to keep cursors.

"maybe smart pointer"... 
What is a maybe-type? :-)


> So I take responsibility for deallocation. And library does not have to
> check
> for invalid cursors.

If you take the responsibility that's fine. But why do you expect
your programmers to produce improved code lacking Cursors,
when they will have to write their own deallocation instead?



> <<How can a linear search be as fast as
> direct access via a cursor?>>
> 
> Strange question. I do not know answer. I did not propose linear
> search.

When you mentioned the Internet Currency Trading system, you said,
"Some of the elements linked directly by Access type."
I had interpreted this to mean a linked list. I guess this interpretation
was wrong?


> It would be better to put elements into container
> after
> the loop.

Hmm... My point was to show a repeated update of elements
in a map; I had omitted later processing in each loop
iteration but anyway, to complete the picture:

  loop
    read input used for element replacement
    modify element values in the map (, graph, net, ...)
    foreach need loop
       recompute value based on elements in the container  -- omitted
       write output -- omitted
    end loop;
  end loop;

So there isn't necessarily a tasking issue.

Re: GCC 4.0 Ada.Containers Cursor danger.

[Dmitriy Anisimkov]

<<
> generic
>    procedure Process (Key : Key_Type; Value : Value_Type; Stop : out

If you are worried about Ada 2006's Iterate using Cursors internally
(in the Process procedure), what makes you sure that the programmers
writing the procedure for Process in Generic_Iterate above will
not use the wrong key in their procedure? >>

Because they get it in "in" parameter from library, they do not have
any reason to change it.

<<So are keys really always more safe than Cursors? >>

For sure. There is only 2 possible situations,  found/not found. Some
routines could raise exception if not found. others raise exceptions in
found, others returns boolean value depend on found or not found.

Re: GCC 4.0 Ada.Containers Cursor danger.

[Georg Bauhaus]

Dmitriy Anisimkov wrote:
> <<
> 
>>generic
>>   procedure Process (Key : Key_Type; Value : Value_Type; Stop : out
> 
> 
> If you are worried about Ada 2006's Iterate using Cursors internally

> Because they get it in "in" parameter from library, they do not have
> any reason to change it.

Well I suspect in the same situation they won't have
reason to change a Cursor they get?
Anyway, I don't see that further speculations will will get us
anywhere without substantial data. Else nothing demonstrates
that Adaified STL style algorithms must be a desaster.

Re: GCC 4.0 Ada.Containers Cursor danger.

[Dmitriy Anisimkov]

<< Else nothing demonstrates
that Adaified STL style algorithms must be a desaster. >>

So Ada.Containers is an "Adaified STL". Cursors in the C++ STL looks
normally,
because it looks like high level analog of the pointer arithmetic. I
don't think that
such analog should be ported into Ada, where was no pointer arithmetic
due to the safety
reasons.

I think runtime checks of the Ada cursors is worse then do not use the
cursors
at all. If programmer want to keep pointer to container elements in the
somewhere else, he
should put elements into container dynamically allocated, and have an
access to
it whereever he need.

Re: GCC 4.0 Ada.Containers Cursor danger.

[Matthew Heaney]

"Dmitriy Anisimkov" <anisimkov@yahoo.com> writes:

> So Ada.Containers is an "Adaified STL". 

Yes.


> Cursors in the C++ STL looks normally, because it looks like high
> level analog of the pointer arithmetic.

The pointer arithmetic in C conforms to the "machine model."  Iterators
in the C++ STL look like pointer arithmetic, because both follow the
machine model.

You can do pointer arithmetic in Ada too (see System.Storage_Elements),
so there's nothing special about C++ here.


> I don't think that such analog should be ported into Ada, where was no
> pointer arithmetic due to the safety reasons.

But Ada does support pointer arithmetic.

If you don't like the design of the Ada standard container library, then
you should have submitted a proposal sans cursors 2 years ago.


> I think [that if] runtime checks of the Ada cursors are worse, then do
> not use the cursors at all.

But didn't just complain that there were too few checks?  Do you want
the library to detect dangling cursors, or not?

I can only speak about the GCC implementation (I am its author), but the
overhead of a cursor compared to the overhead of a raw access type is
minimal.

I have recently started adding additional checks to detect dangling
cursors, that are enabled via pragma Assert.

You don't have to guess about whether using a cursor instead of an
access type is less efficient, since you can just read the sources
yourself.  You can get the sources from either of these sites:

<http://charles.tigris.org/>
<http://gcc.gnu.org/>


> If programmer wants to keep pointer to container elements in the
> somewhere else, he should put elements into container dynamically
> allocated, and have an access to it whereever he need.

You appear to not understand the machine model, upon which the library
is based.  I recommend reading about the design of the STL.

I thought you didn't like things that aren't safe?  Your suggestion to
use raw access types is *less* safe than using cursors, since the
programmer would have to assume responsability for memory management.

Of course, the current library design doesn't preclude your approach.
If you don't like cursors, then don't use them...

Re: GCC 4.0 Ada.Containers Cursor danger.

[Dmitriy Anisimkov]

<<But Ada does support pointer arithmetic.>>

It is *Address* arithmetic, not pointer.
Address could be trasformet into access only via
System.Address_To_Access_Conversions and

----RM---------------
The To_Pointer and To_Address subprograms convert back and forth
between values of types Object_Pointer and Address.
To_Pointer(X'Address) is equal to X'Unchecked_Access for any X that
allows Unchecked_Access.
------------------

So, we have "Unchecked_". Pointer arithmetic in Ada. If the name of the
Cusrosrs would be Unchecked_Cursor, and there is in Ada.Containers
would be complete set of access routines without cursors, it would be
Ok.

<<If you don't like the design of the Ada standard container library,
then
you should have submitted a proposal sans cursors 2 years ago.>>

Yes, I'm late, but I guess not only me do not like such unsafety. (or
checking the cursors gotten from machine model unsafety.)
Maybe  we should review Ada.Containers interface. The implementation is
good, but we should have a safer interface i think.

<<You appear to not understand the machine model, upon which the
library
is based. >>

I think high level interfaces should not be based on machine model in
Ada. It is good for C, but not good for Ada. Ada have an access to
machine model, but it is all in Unchecked and system representation
parts. Machine model is isolated from safety programming in Ada.

<<I have recently started adding additional checks to detect dangling
cursors, that are enabled via pragma Assert.>>
<<But didn't just complain that there were too few checks?  Do you want
the library to detect dangling cursors, or not? >>

If there is a cursor, it should be checked for sure, not only with
turned on assert checking. But I prefer to work without cursors, so I
need the complete set of access routines without such checking cursors.
Every time you say "if you need, do it." i could, but i could guess
from this thread that not only me have a vision of containers library
interface without cursors.

Re: GCC 4.0 Ada.Containers Cursor danger.

[Matthew Heaney]

"Dmitriy Anisimkov" <anisimkov@yahoo.com> writes:

> So, we have "Unchecked_". Pointer arithmetic in Ada. If the name of the
> Cusrosrs would be Unchecked_Cursor, and there is in Ada.Containers
> would be complete set of access routines without cursors, it would be
> Ok.

This is a false analogy, since the name of the operations are To_Pointer
and To_Address.  Nary an "unchecked" in site...


> Yes, I'm late, but I guess not only me do not like such unsafety. (or
> checking the cursors gotten from machine model unsafety.)
> Maybe  we should review Ada.Containers interface. The implementation is
> good, but we should have a safer interface i think.

But we can detect dangling cursors.  What other safety do you want?


> I think high level interfaces should not be based on machine model in
> Ada. 

That's fine, but you should have submitted this mystery design of yours
2 years ago.


> It is good for C, but not good for Ada. 

If you don't like cursors, then you don't have to use them.


> Ada have an access to
> machine model, but it is all in Unchecked and system representation
> parts. Machine model is isolated from safety programming in Ada.

If you compile with assertions enabled, then you can detect dangling
cursors.  What's not safe about that?


> If there is a cursor, it should be checked for sure, not only with
> turned on assert checking. But I prefer to work without cursors, so I
> need the complete set of access routines without such checking cursors.

Without a cursor you'd have to search for the key.  A cursor allows you to
optimize-away the lookup.


> Every time you say "if you need, do it." i could, but i could guess
> from this thread that not only me have a vision of containers library
> interface without cursors.

Whatever your vision is, you should have ennunciated it 2 years ago...

Re: GCC 4.0 Ada.Containers Cursor danger.

[Randy Brukardt]

"Dmitriy Anisimkov" <anisimkov@yahoo.com> wrote in message
news:1120739383.801736.224270@o13g2000cwo.googlegroups.com...
...
> If I need direct access to elements, I put dynamically allocated object
> (maybe smart pointer) into container, and keep access where i need.
> I think it is more honestly than to keep cursors.
> So I take responsibility for deallocation. And library does not have to
check
> for invalid cursors.

This makes no sense at all. The major advantage of using containers over
writing the code yourself is that you don't have to do memory management. If
you're going to require users to do their own memory management, there is
almost no need for containers in the first place. Only the map is
sufficiently hard to write to justify a special package, and that would only
need a handful of operations.

                             Randy.

Re: GCC 4.0 Ada.Containers Cursor danger.

[Dmitriy Anisimkov]

<<he major advantage of using containers over
writing the code yourself is that you don't have to do memory
management. >>

I think that major advandage is to be able to keep a lot of data and
have a fast
access to it. Memory managemant could be done by mean of smart pointers
in the Ada standard library too.

Re: GCC 4.0 Ada.Containers Cursor danger.

[Randy Brukardt]

"Dmitriy Anisimkov" <anisimkov@yahoo.com> wrote in message
news:1120642489.101644.74190@o13g2000cwo.googlegroups.com...
>    procedure Insert_Or_Replace_Value (Table : in out Table_Type;
>                                       Key : in Key_Type;
>                                       Value : in Value_Type);

This is called "Include", and is present in the Containers library.

>    procedure Replace_Value (Table : in out Table_Type;
>                             Key : in Key_Type;
>                             Value : in Value_Type);

This is called "Replace", and is present in the Containers library.

For deleting an element by value, look at "Exclude". For Iterating, look at
"Iterate".

There is very little reason to be using cursors with a Map. Cursors exist
with maps so that the same algorithms can be used on any container (list,
set, vector, map). But you really have little reason to use them with Maps
or Vectors. And if you do use them, making them a local variable that goes
away as soon as the operation is finished avoids almost all problems.

                    Randy.

Re: GCC 4.0 Ada.Containers Cursor danger.

[Randy Brukardt]

"Pascal Obry" <pascal@obry.net> wrote in message
news:uk6k42wvf.fsf@obry.net...
>
> Martin Dowie <martin.dowie@btopenworld.com> writes:
>
> > I doubt if that Ada.Containers would be used in systems that have safety
> > concerns.
>
> I think Dmitriy has a good point. For the first time in Ada we have the
> possibility to create easily a dangling pointer using Cursor. This was not
> possible before except by using Unchecked_Deallocation.

I think the problem is an early implementation of the Containers library.

Perhaps I need to write a paper: "Matt Heaney's Container implementation
considered harmful." :-)

I strongly believe that the Containers implementations provided by default
with compilers should do some minimal checking for dangling cursors (that
is, err somewhat on the side of safety). Not necessarily going all the way
to perfect checking, but at least detect the obvious cases of dangling
cursors like the one given previously. OTOH, there will be cases where
implementations like Matt's are necessary -- but I'd prefer to call them
"Unchecked_Containers" and use them only when performance is critical.

                                     Randy.

Re: GCC 4.0 Ada.Containers Cursor danger.

[Matthew Heaney]

"Randy Brukardt" <randy@rrsoftware.com> writes:

> Perhaps I need to write a paper: "Matt Heaney's Container implementation
> considered harmful." :-)

It hurts me when you say that, Randy.  ;^)

Re: GCC 4.0 Ada.Containers Cursor danger.

[Randy Brukardt]

"Matthew Heaney" <matthewjheaney@earthlink.net> wrote in message
news:uoe9fv4wx.fsf@earthlink.net...
> "Randy Brukardt" <randy@rrsoftware.com> writes:
>
> > Perhaps I need to write a paper: "Matt Heaney's Container implementation
> > considered harmful." :-)
>
> It hurts me when you say that, Randy.  ;^)

I plead temporary insanity, caused by reading too many c.l.a. messages at
once. Hopefully, no offense was taken (I did clearly mark it as a joke.)

                          Randy.

Re: GCC 4.0 Ada.Containers Cursor danger.

[Dmitry A. Kazakov]

On 5 Jul 2005 10:11:10 -0700, Dmitriy Anisimkov wrote:

> I would propose to have a Ada.Containers subset without cursors for
> safety reasons.

Yes, or even to remove them completely.

It is not clear to me what the semantics a cursor has. Is it a location in
the container? Then that should be an index or position. Is it a pointer to
an individual element? Then that should be an access type object. Cursor
looks like an amorphous mixture inheriting disadvantages of both.

> Where the "windows" safer in C or in Ada ?

Equally safe. It is just so that in C they are located on the floor...
(:-))

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

Re: GCC 4.0 Ada.Containers Cursor danger.

[Georg Bauhaus]

Dmitry A. Kazakov wrote:
> On 5 Jul 2005 10:11:10 -0700, Dmitriy Anisimkov wrote:
> 
> 
>>I would propose to have a Ada.Containers subset without cursors for
>>safety reasons.
> 
> 
> Yes, or even to remove them completely.
> 
> It is not clear to me what the semantics a cursor has.

Then it's best to have a look at AI302 or the new standard,
and learn what semantics a cursor has, before suggesting
their removal.

What's the translation of "Was der Bauer nicht kennt,
das frisst er nicht?"

Georg

Re: GCC 4.0 Ada.Containers Cursor danger.

[Dmitriy Anisimkov]

<<It is not clear to me what the semantics a cursor has.>>

   type Cursor is
      record
         Container : Map_Access;
         Node      : Node_Access;
      end record;

So, Remove_Element is wrapped Unchecked_Deallocation.

Re: GCC 4.0 Ada.Containers Cursor danger.

[Dmitry A. Kazakov]

On Wed, 06 Jul 2005 09:50:05 +0200, Georg Bauhaus wrote:

> Dmitry A. Kazakov wrote:
>> On 5 Jul 2005 10:11:10 -0700, Dmitriy Anisimkov wrote:
>> 
>>>I would propose to have a Ada.Containers subset without cursors for
>>>safety reasons.
>> 
>> Yes, or even to remove them completely.
>> 
>> It is not clear to me what the semantics a cursor has.
> 
> Then it's best to have a look at AI302 or the new standard,
> and learn what semantics a cursor has, before suggesting
> their removal.
>
> What's the translation of "Was der Bauer nicht kennt,
> das frisst er nicht?"

   "All of the containers specify positions using a cursor,
which is similar to an access type in that it designates an element."

So? Is it position or access?

   "Each container includes a cursor, which is a reference to an element
within a container. Cursors generally remain valid as long as the container
exists and the element referenced is not deleted."

Here it drifts to: a pointer to some element in the container. And what
does it mean to "generally remain valid"? What could a particularly
*invalid* cursor be?

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

Re: GCC 4.0 Ada.Containers Cursor danger.

[Georg Bauhaus]

Dmitry A. Kazakov wrote:

> So? Is it position or access?

I suggest you have a closer look at AI 302 to find out.


> What could a particularly
> *invalid* cursor be?
> 

It is invalid, as per the paragraph about erroneous
execution.

Re: GCC 4.0 Ada.Containers Cursor danger.

[Randy Brukardt]

"Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> wrote in message
news:ldco4pwrxop4$.1py0a7isiagea.dlg@40tude.net...
...
>    "All of the containers specify positions using a cursor,
> which is similar to an access type in that it designates an element."
>
> So? Is it position or access?

We don't say, on purpose. Its is not either, it has elements of both. It
doesn't matter anyway.

>It is not clear to me what the semantics a cursor has. Is it a location in
the container?
> Then that should be an index or position.

It's not a location, and it wouldn't make sense for it to be one (other than
for a Vector). A linked list position, for instance, would require a O(N)
walk through the list. Yuck.

> Is it a pointer to an individual element? Then that should be an access
type object.

No. A raw access type could never be checked, while a Cursor can (and IMHO,
should) be checked for problems.

> Cursor looks like an amorphous mixture inheriting disadvantages of both.

We don't say exactly what it is in part because it is different for the
different containers. But you still can use the same abstraction on any
container.

                        Randy.

Re: GCC 4.0 Ada.Containers Cursor danger.

[Dmitry A. Kazakov]

On Wed, 6 Jul 2005 18:07:38 -0500, Randy Brukardt wrote:

> "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> wrote in message
> news:ldco4pwrxop4$.1py0a7isiagea.dlg@40tude.net...
> ...
>>    "All of the containers specify positions using a cursor,
>> which is similar to an access type in that it designates an element."
>>
>> So? Is it position or access?
> 
> We don't say, on purpose. Its is not either, it has elements of both. It
> doesn't matter anyway.

That's the point. In my view a decision about which checks are appropriate
must follow from the semantics of the thing. Especially the case of mutable
containers shows the problem. Depending on whether cursors are bound to a
container's location, an element at some specific location, the element at
a location, one or another implementation requirement should follow.

>>It is not clear to me what the semantics a cursor has. Is it a location in the container?
>>Then that should be an index or position.
> 
> It's not a location, and it wouldn't make sense for it to be one (other than
> for a Vector). A linked list position, for instance, would require a O(N)
> walk through the list. Yuck.

But it definitely refers to a location. Otherwise iteration using cursor
would be impossible. So it is to define what precisely happens when the
location it refers disappear. Or when the element it refers goes to another
location etc. So far it seems that the *implied* semantics is sort of "the
element at the location". Which is obviously incompatible with many
operations on mutable containers.

>> Is it a pointer to an individual element? Then that should be an access type object.
> 
> No. A raw access type could never be checked, while a Cursor can (and IMHO,
> should) be checked for problems.

Ditto

>> Cursor looks like an amorphous mixture inheriting disadvantages of both.
> 
> We don't say exactly what it is in part because it is different for the
> different containers. But you still can use the same abstraction on any
> container.

The problem with cursors is that they are quite difficult to get right for
mutable containers. I tend to believe that cursor is a wrong abstraction
there.

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

Re: GCC 4.0 Ada.Containers Cursor danger.

[Georg Bauhaus]

Dmitry A. Kazakov wrote:
> On Wed, 6 Jul 2005 18:07:38 -0500, Randy Brukardt wrote:
 
>>>It is not clear to me what the semantics a cursor has. Is it a location in the container?

>>It's not a location, and it wouldn't make sense for it to be one (other than
>>for a Vector).

> But it definitely refers to a location. Otherwise iteration using cursor
> would be impossible.

Why? A cursor designates an element. There are operations
on cursors, some of them let us move a cursor from one
element to another. Then the cursor designates another element.

I don't think there an implied requirement to think of locations.

    type Cursor is private;
  private
    type Cursor is access function (c: Container) return Pointer;


-- Georg 

Re: GCC 4.0 Ada.Containers Cursor danger.

[Dmitry A. Kazakov]

On Thu, 07 Jul 2005 12:38:57 +0200, Georg Bauhaus wrote:

> Dmitry A. Kazakov wrote:
>> On Wed, 6 Jul 2005 18:07:38 -0500, Randy Brukardt wrote:
>  
>>>>It is not clear to me what the semantics a cursor has. Is it a location in the container?
> 
>>>It's not a location, and it wouldn't make sense for it to be one (other than
>>>for a Vector).
> 
>> But it definitely refers to a location. Otherwise iteration using cursor
>> would be impossible.
> 
> Why? A cursor designates an element. There are operations
> on cursors, some of them let us move a cursor from one
> element to another. Then the cursor designates another element.

Rather it does some element at another location. The element is of little
matter here (for this concrete case, note.) Otherwise "Replace" would have
no sense. BTW the parameters of the type Cursor are routinely named
"Position"!

> I don't think there an implied requirement to think of locations.

Then you have to throw out "Next", "First" etc.

It is the location that tells you what's next. You could make elements
carrying the location with, like by deriving them from an abstract list
element. But that is not the design of the containers. Neither you will
need any cursors then, though a lot of other problems instead... (:-)) 

As I said before, it is difficult if possible to assign any definite
semantics to cursors, such that would be consistent across all operations
on them.

-------------
It is really time to think about downward closures (subroutine types),
ranges as ADTs (user-defined index types) etc.

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

Re: GCC 4.0 Ada.Containers Cursor danger.

[Matthew Heaney]

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

> Rather it does some element at another location. The element is of
> little matter here (for this concrete case, note.) Otherwise "Replace"
> would have no sense. BTW the parameters of the type Cursor are
> routinely named "Position"!

Part of the benefit of cursors is precisely that they abstract-away the
container, and allow you to view the elements in the container simply as
an abstract sequence, in which the elements are logically contiguous.
That's the sense of "position" or "location" of an element.  The benefit
is that this model applies to all containers, which means you can write
an algorithm in terms of cursors, that works for any container.

Stepanov refers to this as the "machine model."  In this model, you can
think of elements as having an address.  A cursor a like a pointer, in
the sense that it designates an element at a particular address.  You
can navigate among addresses (Next, Previous, etc), and dereference the
pointer (Element, Query_Element, Replace_Element, etc).

Yes, it's a rather low-level view of a container, but that's why it's so
flexible.  (Of cousre, if this model doesn't suit you, then you don't
have to use cursors, especially for a map.)

Our philosophy during the design of the standard container library was
to not reinvent the wheel, and so we borrowed heavily from the STL.  In
order to understand the design of the Ada standard container library,
you really need to understand the design of the STL.  There are lots of
interviews with Alexander Stepanov on the WWW, as well as many STL
tutorials.

Re: GCC 4.0 Ada.Containers Cursor danger.

[Georg Bauhaus]

Dmitry A. Kazakov wrote:
> On Thu, 07 Jul 2005 12:38:57 +0200, Georg Bauhaus wrote:
> 
> 
>>Dmitry A. Kazakov wrote:
>>
>>>On Wed, 6 Jul 2005 18:07:38 -0500, Randy Brukardt wrote:
>>
>> 
>>
>>>>>It is not clear to me what the semantics a cursor has. Is it a location in the container?
>>
>>>>It's not a location, and it wouldn't make sense for it to be one (other than
>>>>for a Vector).
>>
>>>But it definitely refers to a location.

It designates an element.

>>> Otherwise iteration using cursor
>>>would be impossible.
>>
>>Why? A cursor designates an element. There are operations
>>on cursors, some of them let us move a cursor from one
>>element to another. Then the cursor designates another element.
> 
> 
> Rather it does some element at another location.

As long as we have no clear definition of "location",
the argument can go on. Certainly there are relative
locations if you think of a List say, this element comes
before that. There are locations implied by sorting order.
But sorting order depends on the comparison, so location
is in fact not a spatial position, but there is a position
in some sorting order. Which then isn't fixed per
element in a container. Then I might imagine an element
designated by a cursor to have a place in some imaginary
picture, hence to have a location. But I can dispense with
a location when the container's cursors actually synthesize
the elements on read, so elements don't exist at all before
--in this imaginary implementation-- my program dereferences
a cursor. The elements could be stored in some electrically
charged gel, highly dispersed. Or I could be your container
as long as my operations will give you what the operation
descriptions tell. Do I have to tell you where (and whether)
I store your information in locations?



> The element is of little
> matter here (for this concrete case, note.) Otherwise "Replace" would have
> no sense.

Sorry, I don't understand this.

> BTW the parameters of the type Cursor are routinely named
> "Position"!

Anything better?


>>I don't think there an implied requirement to think of locations.
> 
> 
> Then you have to throw out "Next", "First" etc.

I don't understand. I'm just thinking in terms of elements
and cursors that designate elements. There are subprograms
named Next, First, etc. with a description of what they do.
Where is the pressing need for a location? How do you use
"location" in your programs?

> It is the location that tells you what's next.

Next is providing me with something that designates
another element, or No_Element.
To me, that's what is next, plus what Has_Element says.
By the operations of Next, First, etc., I don't know yet what's
next. I will know what is next when I look at the element
designated by the next cursor, after Next's execution.


> As I said before, it is difficult if possible to assign any definite
> semantics to cursors, such that would be consistent across all operations
> on them.

Could you explain some inconsistencies among the Cursor
operations?

Re: GCC 4.0 Ada.Containers Cursor danger.

[Dmitry A. Kazakov]

On Fri, 08 Jul 2005 00:12:11 +0200, Georg Bauhaus wrote:

> Dmitry A. Kazakov wrote:
>> On Thu, 07 Jul 2005 12:38:57 +0200, Georg Bauhaus wrote:
>> 
>>>> Otherwise iteration using cursor
>>>>would be impossible.
>>>
>>>Why? A cursor designates an element. There are operations
>>>on cursors, some of them let us move a cursor from one
>>>element to another. Then the cursor designates another element.
>> 
>> Rather it does some element at another location.
> 
> As long as we have no clear definition of "location",
> the argument can go on.

That's easy. Enumerate all elements in the container [i.e. define an order
there.] Location will be that number 1..n.

> Certainly there are relative
> locations if you think of a List say, this element comes
> before that. There are locations implied by sorting order.
> But sorting order depends on the comparison, so location
> is in fact not a spatial position, but there is a position
> in some sorting order. Which then isn't fixed per
> element in a container.

Yes.

> Then I might imagine an element
> designated by a cursor to have a place in some imaginary
> picture, hence to have a location. But I can dispense with
> a location when the container's cursors actually synthesize
> the elements on read, so elements don't exist at all before
> --in this imaginary implementation-- my program dereferences
> a cursor. The elements could be stored in some electrically
> charged gel, highly dispersed. Or I could be your container
> as long as my operations will give you what the operation
> descriptions tell. Do I have to tell you where (and whether)
> I store your information in locations?

You did, if elements are ordered.

>> The element is of little
>> matter here (for this concrete case, note.) Otherwise "Replace" would have
>> no sense.
> 
> Sorry, I don't understand this.

Replace =  "to take or fill the place of". Notice "the place of"! (:-))

>> BTW the parameters of the type Cursor are routinely named
>> "Position"!
> 
> Anything better?

"Element", isn't cursor <=> element? (:-))

>>>I don't think there an implied requirement to think of locations.
>> 
>> Then you have to throw out "Next", "First" etc.
> 
> I don't understand. I'm just thinking in terms of elements
> and cursors that designate elements.

But the elements type don't have "Next" and "First". If Integer X is in A
then Integer'Succ (X) is not necessarily in A. And A'First is not
necessarily Integer'First.

> There are subprograms
> named Next, First, etc. with a description of what they do.
> Where is the pressing need for a location? How do you use
> "location" in your programs?

A (Location) := X;

>> It is the location that tells you what's next.
> 
> Next is providing me with something that designates
> another element, or No_Element.
> To me, that's what is next, plus what Has_Element says.
> By the operations of Next, First, etc., I don't know yet what's
> next. I will know what is next when I look at the element
> designated by the next cursor, after Next's execution.

>> As I said before, it is difficult if possible to assign any definite
>> semantics to cursors, such that would be consistent across all operations
>> on them.
> 
> Could you explain some inconsistencies among the Cursor
> operations?

What is the semantics they implement? See your example with Next. We have:

1. An order defined on elements (=locations in some "pre-container" (:-))
2. An order defined by the container (=locations)
3. Instances of elements (value semantics)
4. References to elements (=locations in some third container! (:-))

We need to define what "Next" does in terms of 1-4. I doubt you will be
able to define it without 2. Note that you could replace 2 with

2.a A membership test for an element to be in the container

But then 2 could be trivially derived from 2.a and 1. In other cases 2
could be an order completely unrelated to 1, like it is in the case of
unsorted arrays.

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

Re: GCC 4.0 Ada.Containers Cursor danger.

[Georg Bauhaus]

Dmitry A. Kazakov wrote:

>>As long as we have no clear definition of "location",
>>the argument can go on.
> 
> That's easy. Enumerate all elements in the container [i.e. define an order
> there.] Location will be that number 1..n.

I can see about N! ways of enumerating elements in an unordered
container. Any such enumeration is fine. All I need is the operations
defined for containers and possibly cursors. There is no need for
me to think of the possible location of an element in an
unordered container. I can also pretty much ignore the
arbitrary order established by the finished enumeration
in _my_ program.

In fact, I wonder whether it might be useful to have an operation
that allows picking a really arbitrary element.
(Could be done in a program using a random number modulo
the number of elements in the set, and then approaching
the element by iteration or by index, but I guess this is
rather slow, at least for sets.)



>> Or I could be your container
>>as long as my operations will give you what the operation
>>descriptions tell. Do I have to tell you where (and whether)
>>I store your information in locations?
> 
> 
> You did, if elements are ordered.

But elements aren't ordered when I play the part of the hashed
set container, and decide to hide any internal order.

Even if I, the hashed set container, store your elements in some
internal order, I'm allowed to change locations of elements at will,
as a function of execution time, as long as A.18 isn't violated.
Provided I store elements in locations at all, and do not remember
them in a different way.
I'm just not allowed to disturb your algorithms. For example,
I have to make sure that when you call Next, I present to you
a cursor to some (!) next element. No need for a location.
An order may be established *after* the fact. During iteration,
the elements have been presented in some order, but this order may be
quite volatile. So from this perspective there is no need to
think of the location of an element in this container. I find
it misleading to do so.


>>>BTW the parameters of the type Cursor are routinely named
>>>"Position"!
>>
>>Anything better?
> 
> 
> "Element", isn't cursor <=> element? (:-))

What about No_Element then?

>>>>I don't think there an implied requirement to think of locations.
>>>
>>>Then you have to throw out "Next", "First" etc.
>>
>>I don't understand. I'm just thinking in terms of elements
>>and cursors that designate elements.
> 
> 
> But the elements type don't have "Next" and "First". If Integer X is in A
> then Integer'Succ (X) is not necessarily in A. And A'First is not
> necessarily Integer'First.

Well, yes, but containers can store
non-scalar values, too. Did you mean that if some value is an
element in a container, then another element given by its successor
in the type should be an element in the container, too?
Like numbers defined by the Peano axioms? How could I store
pointers in hashed sets, then, that have no 'succ?


>>There are subprograms
>>named Next, First, etc. with a description of what they do.
>>Where is the pressing need for a location? How do you use
>>"location" in your programs?
> 
> 
> A (Location) := X;

For vectors, yes, that is the Index_Type. For containers
like hashed sets I don't see how location should be needed.


>>>As I said before, it is difficult if possible to assign any definite
>>>semantics to cursors, such that would be consistent across all operations
>>>on them.
>>
>>Could you explain some inconsistencies among the Cursor
>>operations?
> 
> 
> What is the semantics they implement? See your example with Next. We have:
> 
> 1. An order defined on elements (=locations in some "pre-container" (:-))

It isn't always relevant that some Ada types are ordered, some not.
Not every container needs elements that can be ordered, for a start.
Next, First etc. do not have to refer to a type's order if any,
so why and when should we have to respect the type's ordering in Cursor's
First, Next etc.?

> 2. An order defined by the container (=locations)

What is this? Ordered containers can be made to exhibit a kind of
ordered collection only because (a) they are made for this
and (b) because you, the programmer, provides ordering
functions or (c) if your algorithm orders the elements.
What other order needs to be defined by an unordered set?
How does it make sense to speak of the unique location of an
element in an unordered set?


> 3. Instances of elements (value semantics)

?

> 4. References to elements (=locations in some third container! (:-))

Which third container is this? A container of references?


> We need to define what "Next" does in terms of 1-4.

Uhm, why is that?


> In other cases 2
> could be an order completely unrelated to 1, like it is in the case of
> unsorted arrays.

I think that in other cases an order could be completely
redundant. ;-)

Re: GCC 4.0 Ada.Containers Cursor danger.

[Dmitry A. Kazakov]

On Fri, 08 Jul 2005 12:41:18 +0200, Georg Bauhaus wrote:

> Dmitry A. Kazakov wrote:
> 
>>>As long as we have no clear definition of "location",
>>>the argument can go on.
>> 
>> That's easy. Enumerate all elements in the container [i.e. define an order
>> there.] Location will be that number 1..n.
> 
> I can see about N! ways of enumerating elements in an unordered
> container. Any such enumeration is fine.

No. You cannot use an arbitrary order, because it is an implementation
detail which no user application should rely on. "Location" is either a
contract or does not exist. A naive user might reason: last time I found it
by the iteration number 32. So be it the next time. Is s/he right?

> All I need is the operations
> defined for containers and possibly cursors. There is no need for
> me to think of the possible location of an element in an
> unordered container. I can also pretty much ignore the
> arbitrary order established by the finished enumeration
> in _my_ program.

I think it would be a bad design. Unordered containers should not allow
iteration.

> In fact, I wonder whether it might be useful to have an operation
> that allows picking a really arbitrary element.

No problem if that is a primitive operation, as well as to copy a
container, set theoretic operations (and, or, xor).

> (Could be done in a program using a random number modulo
> the number of elements in the set, and then approaching
> the element by iteration or by index, but I guess this is
> rather slow, at least for sets.)

>>> Or I could be your container
>>>as long as my operations will give you what the operation
>>>descriptions tell. Do I have to tell you where (and whether)
>>>I store your information in locations?
>> 
>> You did, if elements are ordered.
> 
> But elements aren't ordered when I play the part of the hashed
> set container, and decide to hide any internal order.

Then elements are unordered, a hash function is the parameter.

> Even if I, the hashed set container, store your elements in some
> internal order, I'm allowed to change locations of elements at will,
> as a function of execution time, as long as A.18 isn't violated.
> Provided I store elements in locations at all, and do not remember
> them in a different way.
> I'm just not allowed to disturb your algorithms. For example,
> I have to make sure that when you call Next, I present to you
> a cursor to some (!) next element. No need for a location.
> An order may be established *after* the fact. During iteration,
> the elements have been presented in some order, but this order may be
> quite volatile. So from this perspective there is no need to
> think of the location of an element in this container. I find
> it misleading to do so.

This is why it is IMO safer to provide no iteration here, because the order
is in fact arbitrary. There could be other ways. For example: one could
provide a "Sort" operation which would return a sorted container. That
container can be iterated.

The order iteration is based on has to be documented. I.e. the user should
know how and when the operations on the container influence that order.
When order is induced by some "hard" facts as below, then you can document
it. But I cannot see a way to document an implementation detail!
 
>>>>BTW the parameters of the type Cursor are routinely named
>>>>"Position"!
>>>
>>>Anything better?
>> 
>> "Element", isn't cursor <=> element? (:-))
> 
> What about No_Element then?

Are you now defending my point? (:-))

>>>>>I don't think there an implied requirement to think of locations.
>>>>
>>>>Then you have to throw out "Next", "First" etc.
>>>
>>>I don't understand. I'm just thinking in terms of elements
>>>and cursors that designate elements.
>> 
>> But the elements type don't have "Next" and "First". If Integer X is in A
>> then Integer'Succ (X) is not necessarily in A. And A'First is not
>> necessarily Integer'First.
> 
> Well, yes, but containers can store
> non-scalar values, too. Did you mean that if some value is an
> element in a container, then another element given by its successor
> in the type should be an element in the container, too?
> Like numbers defined by the Peano axioms? How could I store
> pointers in hashed sets, then, that have no 'succ?
> 
>>>There are subprograms
>>>named Next, First, etc. with a description of what they do.
>>>Where is the pressing need for a location? How do you use
>>>"location" in your programs?
>>  
>> A (Location) := X;
> 
> For vectors, yes, that is the Index_Type. For containers
> like hashed sets I don't see how location should be needed.

Right, and what should "Replace" mean for a hashed set? Is it
Remove/Insert? Which influence does it have on iterations?

>>>>As I said before, it is difficult if possible to assign any definite
>>>>semantics to cursors, such that would be consistent across all operations
>>>>on them.
>>>
>>>Could you explain some inconsistencies among the Cursor
>>>operations?
>> 
>> What is the semantics they implement? See your example with Next. We have:
>> 
>> 1. An order defined on elements (=locations in some "pre-container" (:-))
> 
> It isn't always relevant that some Ada types are ordered, some not.
> Not every container needs elements that can be ordered, for a start.

Right.

> Next, First etc. do not have to refer to a type's order if any,
> so why and when should we have to respect the type's ordering in Cursor's
> First, Next etc.?

It is just a possible information source for defining what's going on. To
iterate you have to get an order somewhere. The problem is that having at
least three ways to define that order, it becomes quite difficult to bring
all types of containers supporting iterations under one roof.

>> 2. An order defined by the container (=locations)
> 
> What is this? Ordered containers can be made to exhibit a kind of
> ordered collection only because (a) they are made for this
> and (b) because you, the programmer, provides ordering
> functions or (c) if your algorithm orders the elements.
> What other order needs to be defined by an unordered set?
> How does it make sense to speak of the unique location of an
> element in an unordered set?

It does not. But it does in an ordered set. Also see above.

>> 3. Instances of elements (value semantics)
> 
> ?

The values you are working with.

>> 4. References to elements (=locations in some third container! (:-))
> 
> Which third container is this? A container of references?

The memory pool the objects live in.

>> We need to define what "Next" does in terms of 1-4.
> 
> Uhm, why is that?

Because I cannot think up 5,6... (:-)) Which other sources for ordering
exist?

>> In other cases 2
>> could be an order completely unrelated to 1, like it is in the case of
>> unsorted arrays.
> 
> I think that in other cases an order could be completely redundant. ;-)

Exactly!

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

Re: GCC 4.0 Ada.Containers Cursor danger.

[Matthew Heaney]

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

> Right, and what should "Replace" mean for a hashed set? Is it
> Remove/Insert? Which influence does it have on iterations?

There is some debate about the exact semantics of Replace.  If you don't
change the equivalence class of the key, then Replace simply replaces
the key/element with a new value.  

The current AI-302 draft does allow you to change the equivalence class
of the key (semantics I don't like), in which case the element is
reinserted at a different position, not unlike a Delete followed by an
Insert (the difference is that Replace can reuse the same memory).  The
equivalence class of the key is what determines its relative order.

So if the equivalence class stays the same, then the order of elements
as returned during iteration won't change.  If the equivalence class
changes, then the order of elements during iteration will change (one
element will have moved to another position).

Re: GCC 4.0 Ada.Containers Cursor danger.

[Randy Brukardt]

"Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> wrote in message
news:1o398w3zo2zf1$.f1f7tukylueo$.dlg@40tude.net...
...
> I think it would be a bad design. Unordered containers should not allow
> iteration.

That's a rather silly idea. There has to be some way to find out the
complete contents of the container, for debugging if for no other reason.
Moreover, the implementation needs to be able to access all of the elements
in order to stream a container, and it seems bad to have important
capabilities that the implementation has but doesn't provide to the user.

The abstract view of iteration is that it produces *every* element of the
container, and no others, in *some* unspecified order. That applies both the
the passive iterator Iterate and the cursor based routines like Next.

Many containers have specific, stricter requirements than that. But the
general notion does not include (nor need) a "location" or "ordering". (Here
I disagree with Matt; his view is a bit too implementation-oriented.)

> The order iteration is based on has to be documented.
> I.e. the user should
> know how and when the operations on the container influence that order.
> When order is induced by some "hard" facts as below, then you can document
> it. But I cannot see a way to document an implementation detail!

It's not necessary to document the order. And there is no such requirement;
the order is unspecified in general. Relying on the order in an iterator is
wrong in the general case, even if there are *no* other operations.

Of course, specific containers do require a specific order, and *then* you
can rely upon it. But not in a generic algorithm.

                      Randy.

Re: GCC 4.0 Ada.Containers Cursor danger.

[Dmitry A. Kazakov]

On Sat, 9 Jul 2005 21:12:30 -0500, Randy Brukardt wrote:

> "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> wrote in message
> news:1o398w3zo2zf1$.f1f7tukylueo$.dlg@40tude.net...
> ...
>> I think it would be a bad design. Unordered containers should not allow
>> iteration.
> 
> That's a rather silly idea.

Maybe unordered containers aren't needed at all. However as a common
[abstract] ancestor of all containers they might be useful. I think it is
logical.

> There has to be some way to find out the
> complete contents of the container, for debugging if for no other reason.
> Moreover, the implementation needs to be able to access all of the elements
> in order to stream a container, and it seems bad to have important
> capabilities that the implementation has but doesn't provide to the user.

Right, but that would be an ordered container then. Unordered = no order.

> The abstract view of iteration is that it produces *every* element of the
> container, and no others, in *some* unspecified order. That applies both the
> the passive iterator Iterate and the cursor based routines like Next.

An unspecified order is still an order. What could be said about that
unspecified order? May the order vary for a constant container? How does it
when the container gets changed? I think it is cleaner to take an ordered
copy of, or an ordered view on an unordered container and then iterate that
well-defined thing.

> Many containers have specific, stricter requirements than that. But the
> general notion does not include (nor need) a "location" or "ordering". (Here
> I disagree with Matt; his view is a bit too implementation-oriented.)
> 
>> The order iteration is based on has to be documented.
>> I.e. the user should
>> know how and when the operations on the container influence that order.
>> When order is induced by some "hard" facts as below, then you can document
>> it. But I cannot see a way to document an implementation detail!
> 
> It's not necessary to document the order. And there is no such requirement;
> the order is unspecified in general. Relying on the order in an iterator is
> wrong in the general case, even if there are *no* other operations.

Right, this is my concern.

> Of course, specific containers do require a specific order, and *then* you
> can rely upon it. But not in a generic algorithm.

A generic algorithm is just a class-wide procedure. The problem is the
contract of the class. If iteration is in the contract, then its behavior
must be defined. So that the correctness of the algorithm would be
independent on any possible implementation. If it is outside, then there
must be no [easy] way to use it.

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

Re: GCC 4.0 Ada.Containers Cursor danger.

[Georg Bauhaus]

Dmitry A. Kazakov wrote:

> An unspecified order is still an order. What could be said about that
> unspecified order? May the order vary for a constant container?

Unspecified order can be thought of as an advantage, too.
You don't have to worry about the concrete actual order generated
by one iteration. The requirements are more flexible.
If you need order, why not just use a container that has a specified
order?



--  Georg 

Re: GCC 4.0 Ada.Containers Cursor danger.

[Dmitry A. Kazakov]

On Mon, 11 Jul 2005 12:58:34 +0200, Georg Bauhaus wrote:

> Dmitry A. Kazakov wrote:
> 
>> An unspecified order is still an order. What could be said about that
>> unspecified order? May the order vary for a constant container?
> 
> Unspecified order can be thought of as an advantage, too.
> You don't have to worry about the concrete actual order generated
> by one iteration.

It must be defined. A concrete actual order, how long will it stay? Can it
change during one iteration? Would you worry if the order randomly changed
each 0.1 ns?

> The requirements are more flexible.

The most flexible requirement is an absent one...

> If you need order, why not just use a container that has a specified
> order?

Exactly. From which immediately follows that the compiler should not allow
me to use an unordered container as if it were ordered.

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

Re: GCC 4.0 Ada.Containers Cursor danger.

[Georg Bauhaus]

Dmitry A. Kazakov wrote:

>>Unspecified order can be thought of as an advantage, too.
>>You don't have to worry about the concrete actual order generated
>>by one iteration.
> 
> 
> It must be defined. A concrete actual order, how long will it stay? Can it
> change during one iteration?

A.18 tells you what you can expect in these cases, I'd say.

If you use Ada.Containers as bricks, you may creatively expect
to be able to build walls in all sorts of ways, using skewed
stones, stones with holes, let some stones stick out, etc.
I speculate that A.18 has not been made to protect you from this
way of using the bricks; I can't find text, though, that recommends
using the low level abstractions (bricks) in ways that I would
expect to be appropriate for higher level abstractions (walls).

>>The requirements are more flexible.
> 
> 
> The most flexible requirement is an absent one...

There are quite some requirements that an implementation of
Ada.Containers must meet.


>>If you need order, why not just use a container that has a specified
>>order?
> 
> 
> Exactly. From which immediately follows that the compiler should not allow
> me to use an unordered container as if it were ordered.

"Some order" of all elements is good enough for a set that doesn't have an ordered
flavor, in the sense of Ordered_Set. Why should compilers complain, I'm content
when I can get hold of all elements in some sequence. That's because I'm using a
set, not an ordered set.

OTOH, If you write a program using a Hashed_Set, then there might be an implementation
defined order of iteration. But it is a *big* mistake IMHO to write the program
relying on a specific iteration order using a specific version of a specific
impementation of hashed sets. You can't port it. And you have missed
an opportunity to express that you want a specific order.

Re: GCC 4.0 Ada.Containers Cursor danger.

[Randy Brukardt]

"Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> wrote in message
news:nmv39ipirsbg$.1or742g96p5km.dlg@40tude.net...
> > The abstract view of iteration is that it produces *every* element of
the
> > container, and no others, in *some* unspecified order. That applies both
the
> > the passive iterator Iterate and the cursor based routines like Next.
>
> An unspecified order is still an order. What could be said about that
> unspecified order?

Nothing. That's the meaning of "unspecified"! The implementation can use any
convinient order.

> May the order vary for a constant container?

There is no such thing as a constant container. You can declare a container
object constant, but that doesn't make the container constant.

> How does it when the container gets changed?

That's irrelevant. If the container is changed, cursor iteration may fail
(passive iteration would raise Program_Error; that's part of the contract of
all of the containers).

...
> > Of course, specific containers do require a specific order, and *then*
you
> > can rely upon it. But not in a generic algorithm.
>
> A generic algorithm is just a class-wide procedure. The problem is the
> contract of the class. If iteration is in the contract, then its behavior
> must be defined. So that the correctness of the algorithm would be
> independent on any possible implementation. If it is outside, then there
> must be no [easy] way to use it.

For a passive iterator, the contract is that each element is visited exactly
once, in an unspecified order. Signficant changes to the container during a
passive iterator are *not* allowed (they raise Program_Error). Thus, the
order is irrelevant.

                     Randy.

Re: GCC 4.0 Ada.Containers Cursor danger.

[Dmitry A. Kazakov]

On Mon, 11 Jul 2005 13:38:56 -0500, Randy Brukardt wrote:

> "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> wrote in message
> news:nmv39ipirsbg$.1or742g96p5km.dlg@40tude.net...
>>> The abstract view of iteration is that it produces *every* element of the
>>> container, and no others, in *some* unspecified order. That applies both the
>>> the passive iterator Iterate and the cursor based routines like Next.
>>
>> An unspecified order is still an order. What could be said about that
>> unspecified order?
> 
> Nothing. That's the meaning of "unspecified"! The implementation can use any
> convinient order.

What about Prev (Next (X)) /= X?

>>> Of course, specific containers do require a specific order, and *then* you
>>> can rely upon it. But not in a generic algorithm.
>>
>> A generic algorithm is just a class-wide procedure. The problem is the
>> contract of the class. If iteration is in the contract, then its behavior
>> must be defined. So that the correctness of the algorithm would be
>> independent on any possible implementation. If it is outside, then there
>> must be no [easy] way to use it.
> 
> For a passive iterator, the contract is that each element is visited exactly
> once, in an unspecified order. Signficant changes to the container during a
> passive iterator are *not* allowed (they raise Program_Error). Thus, the
> order is irrelevant.

It is not, you just have replaced "changes that preserve the iteration
order and the membership" with "insignificant changes". Then passive,
one-way iterators are more or less acceptable. Cursors are much more
questionable.

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

Re: GCC 4.0 Ada.Containers Cursor danger.

[Georg Bauhaus]

Dmitry A. Kazakov wrote:

>>Nothing. That's the meaning of "unspecified"! The implementation can use any
>>convinient order.
> 
> 
> What about Prev (Next (X)) /= X?

It is "Previous", and Previous in not an operation of
Cursor in Hashed_Sets or Hashed_Maps.

Re: GCC 4.0 Ada.Containers Cursor danger.

[Randy Brukardt]

"Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> wrote in message
news:1qm62kbb1qwnl.ywnvsfug5p88.dlg@40tude.net...
...
> It is not, you just have replaced "changes that preserve the iteration
> order and the membership" with "insignificant changes". Then passive,
> one-way iterators are more or less acceptable. Cursors are much more
> questionable.

I don't think that there is any guarantee that iteration via cursor will
actually work for an unordered (hashed) container. In practice, it usually
will work, but there is nothing in the standard that requires that (unless
"there are no intervening operations", but that would be a pretty useless
iteration!).

Cursors also have uses that have nothing to do with iteration, of course.

                         Randy.

Re: GCC 4.0 Ada.Containers Cursor danger.

[Matthew Heaney]

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

> That's easy. Enumerate all elements in the container [i.e. define an
> order there.] Location will be that number 1..n.

There is no such thing as an "unordered" container (and here we're
really talking about sets and maps), since then there would be no way to
find anything without a linear search.  That's why we have both ordered
and hashed containers.

The "position" of an element always relative to other elements in the
container.  For an "ordered" container (Ordered_Sets, Ordered_Maps), the
position is determined by the "<" operator for elements.  For a "hashed"
container (Hashed_Sets, Hashed_Maps), the position is determined from
the hash value of the element (since that determines which bucket the
element falls into).

An iterator (either passive or active) simply enumerates elements in
their order as specified by the type of container they're in (either
sort order or bucket order).

Have you ever done any COM or DirectShow programming under Windows?  A
cursor is the same as the EnumXXX class.  (If I remember correctly, I
think Java also has something it refers to as an "enumerator".)

Re: GCC 4.0 Ada.Containers Cursor danger.

[Dmitry A. Kazakov]

On Fri, 08 Jul 2005 13:15:26 GMT, Matthew Heaney wrote:

> "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> writes:
> 
>> That's easy. Enumerate all elements in the container [i.e. define an
>> order there.] Location will be that number 1..n.
> 
> There is no such thing as an "unordered" container (and here we're
> really talking about sets and maps),

But sets and maps are unordered containers. You can have a set of
incomparable things. You need only "=" defined.

> since then there would be no way to find anything without a linear search.

This is an unrelated thing. You can invent any order you wish to implement
membership test. But fundamentally yes, if the values have no identity you
can hash or compare (like memory addresses), then there is nothing better
than linear search. Why somebody might wish such thing is another question.

> That's why we have both ordered
> and hashed containers.
> 
> The "position" of an element always relative to other elements in the
> container.  For an "ordered" container (Ordered_Sets, Ordered_Maps), the
> position is determined by the "<" operator for elements.  For a "hashed"
> container (Hashed_Sets, Hashed_Maps), the position is determined from
> the hash value of the element (since that determines which bucket the
> element falls into).
> 
> An iterator (either passive or active) simply enumerates elements in
> their order as specified by the type of container they're in (either
> sort order or bucket order).

"Their order" is the problem. Depending on its definition the order may
vary in different ways when the container is mutable. What is the common
denominator across all container types? There seems to be none.

> Have you ever done any COM or DirectShow programming under Windows?  A
> cursor is the same as the EnumXXX class.  (If I remember correctly, I
> think Java also has something it refers to as an "enumerator".)

DB's cursors... Or a text editor cursor. A good example, BTW. MS Visual
Studio IDE handles text cursors surprisingly correct (most times.) AdaGIDE
does not. So browsing the compiler messages list while editing the source
code text, be prepared...

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

Re: GCC 4.0 Ada.Containers Cursor danger.

[Matthew Heaney]

Dmitry A. Kazakov wrote:
> On Fri, 08 Jul 2005 13:15:26 GMT, Matthew Heaney wrote:
>
> But sets and maps are unordered containers.

This is silly.  We are talking about the Ada 2005 standard container
library.  In that library, of course sets and maps *are* ordered.


> > since then there would be no way to find anything without a linear search.
>
> Why somebody might wish such thing is another question.

Which is exactly why they're not part of the standard library!


> > An iterator (either passive or active) simply enumerates elements in
> > their order as specified by the type of container they're in (either
> > sort order or bucket order).
>
> "Their order" is the problem. Depending on its definition the order may
> vary in different ways when the container is mutable.

No.  You're not allowed to change the key (which determimes the order)
in any way that would violate the container abstraction.  "Mutability"
is always restricted, such that only bengin changes are allowed.


> What is the common
> denominator across all container types? There seems to be none.

Vectors and lists are "sequence" containers, that allow you to
explicitly specify the position.

Sets and maps are "associative" container, that positions elements in
key order.  (A sorted order for "ordered" containers, and a hash order
for "hashed" containers.)

All containers have a consistent mechanism for iterating over elements.

Re: GCC 4.0 Ada.Containers Cursor danger.

[MMM]

Matthew Heaney wrote:

>
> Dmitry A. Kazakov wrote:
>
>> On Fri, 08 Jul 2005 13:15:26 GMT, Matthew Heaney wrote:
>>
>> But sets and maps are unordered containers.
>
>
>
> This is silly.  We are talking about the Ada 2005 standard container
> library.  In that library, of course sets and maps *are* ordered.
>
That is not silly at all. And there is not such a library as the Ada
2005 standard container library yet. There is the candidate or proposal
if you wish. And the fact that in that proposal 'of course sets and
maps *are* ordered' is silly indeed. The reason is that, if one
remember some mathematics, having an order is a fundamental property
that distinguish vectors and lists on the one side and sets and hashes
on the other. Another silliness is overgeneralization of the
'iterrator' concept and renaming it to 'cursor'. Yet another silliness
is the terminology used - Vectors, Lists, Ordered_Sets, Hashed_Sets,
Hashed_Maps, Ordered_Maps.
The problem here is that this terminology doesn't reflect the
fundamental differences between these types and mixes underlying
mathematical conncepts in some unregular way. This unnecessarily
complicates and hides underlying principles. And the principles are
very simple:

 - if a container has an order property, then it is either list or
vector, if not, then it is either set or hash.
 - if a container is a mapping, then it is either vector or hash, if
not, then it is either list or set.

Then the basic types could be:

 List - a container that provides ordering, but no mapping from it's
elements to any kind of index or position by default.

 Vector - a container that provides ordering and mapping from some kind
of index to it's elements. The only general requirement to this index
is that it should be ordered, i.e. comparison operations should be
defined for it.

 Set - a container that provides neither order nor mapping to any
index.

 Hash - a container that provides no ordering, but provides a mapping
from some kind of key to it's elements. The only general requirement to
this key is that it should be possible to calculate a hash from it's
value somehow.

These four concepts form an ortogonal normal basis for the container
types. Everything else is a specialisation or/and mixture of these
basic concepts. Of course internal implementation of all of these basic
types can use whatever ordering or indexing algorithms that could
provide reasonable implementation. Unfortunately the current proposal
uses some kind of "mixture" of these basic concepts or non ortogonal
basis. This unnecessarily distances current proposal from underlying
theory and complicates understanding of relations between different
concepts.

It would be very sad if the final standard would contain such a mixture
of concepts.

>
..... skip .....

>
>> What is the common
>> denominator across all container types? There seems to be none.
>
>
No, it is not none! If we look at these basic types, then we will see
one fundamental thing about containers. Namely, the only two elementary
operation that has common semantic among all container types are
'iteration' over their elements and membership test. Everything else is
 either has container specific semantics or has no natural semantics at
all for some container types. So, the common denominator across all
container types is:
    a) They all contain some kind of elements
    b) They all have a concept of 'iterating' over their elements
       in an unspecified order.
    c) They all have membership test.
    d) Provide similar interface with slightly differnt semantics
       for an element addition and deletion.

>
> Vectors and lists are "sequence" containers, that allow you to
> explicitly specify the position.

Not exactly. The common property of vectors and lists is that they are
"ordered" somehow and you can sort them by some criteria.
The difference is that vector elements could be directly accessed using
some kind of index and lists provide only sequential access (like
direct_io and sequential_io).

>
> Sets and maps are "associative" container, that positions elements in
> key order.  (A sorted order for "ordered" containers, and a hash order
> for "hashed" containers.)

Again, this mixture of basic properties, namely 'ordering' and
'mapping', is very unfortunate.

>
> All containers have a consistent mechanism for iterating over elements.
>
Exactly.

Mikhail

Re: GCC 4.0 Ada.Containers Cursor danger.

[Georg Bauhaus]

MMM wrote:

> The reason is that, if one
> remember some mathematics, having an order is a fundamental property
> that distinguish vectors and lists on the one side and sets and hashes
> on the other.

I think it is not too helpful to consider Ada.Containers to be
derived from some collection of mathematical notions and from
nothing else.

First, Ada.Containers is not trying to approximate some notions
from linear algebra ("orthogonal normal basis"), metaphorically
or not. ;-) You'll have justify the implication that
we should build computer libraries around some specific
choice of notions loosly derived from mathematics. Doing this
is not a matter of course, as reactive systems are not all
about mathematics.

Second, the way Ada.Containers invites you to think about the order
of elements ("containers are nothing, elements are everything").
There might be some physical/logical correspondence between the
order of elements in some container on the one hand, and their
order as implied by the user's ordering functions passed during
instantiation. Or there might not. It is more important what a
user wishes to to using the elements that happen to be elements
of some collection. I.e. while it remains advisable to choose the
proper container, Cursors are among the means to choose different
containers when the need arises, ideally without disturbing the rest of
the program.

There are a number of "orders" of elements in this discussion.
There are those on which you seem to build your correspondence, IIUC.
Elements ordered relative to one another in the list and vector abstractions,
because that is what a mathematician might assign to the notions.
But some elements are ordered relative to one another in ordered sets or maps
that are ordered by key. This order need not entail the use of a list,
and indeed requiring List/Vector <-> order will defeat several uses
of the library which is rather more flexible. If I want a set for
(a) memebership test, and (b) an ordered collection, then why should I store
the elements in some List oder Vector just because I want element
insertion to preserve order as well?
Indeed, a close correspondence of order and choice of container
will defeat some generic algorithms.

I think it is of no primary concern here that some branches of mathematics can
do without ordered sets, and that there is a natural ordering by position
in a list. The library is for programmers, not for mathematical
housekeepers. ;-)  There is a treasure trove of mathematical theory of
computation that starts from computation in computers, and not the other
way round :-)



> Another silliness is overgeneralization of the
> 'iterrator' concept and renaming it to 'cursor'.

Given the operations of Cursors, I can see clearly how I can
use Cursor operations in iteration. OTOH, iteration
means doing something again, but an STL iterator (a pointer,
really, or cursor if you wish) doesn't require that I do something
again...


> The problem here is that this terminology doesn't reflect the
> fundamental differences between these types and mixes underlying
> mathematical conncepts in some unregular way.

If the library confuses a mathematician because he/she is used
to some meanings of words, then maybe emphasising the Ada definitions,
which relate to computers, will help?


-- Georg 

Re: GCC 4.0 Ada.Containers Cursor danger.

[MMM]

Georg Bauhaus wrote:
> MMM wrote:
>
>> The reason is that, if one
>> remember some mathematics, having an order is a fundamental property
>> that distinguish vectors and lists on the one side and sets and hashes
>> on the other.
>
>
> I think it is not too helpful to consider Ada.Containers to be
> derived from some collection of mathematical notions and from
> nothing else.
>
You are right that for the person not familiar with mathematics
that will be of no help. But I suspect that people designing
computer programs in general and designing programs in Ada in
particular have some knowledge of at least simple math. Note also
that mathematics is the lingua franca not only for the science but
also for programming and computers in general. Note also that it is
not "some collection of mathematical notions", it is a well known
theory, while current proposal of container types *is* some collection
of mixed notations and it looks like it is derived from "nothing else"
only.

> First, Ada.Containers is not trying to approximate some notions
> from linear algebra ("orthogonal normal basis"), metaphorically
Note that this notion is not limited to linear algebra and I'm not
agitating
for implementation of this notion in Ada.Containers in any way!
;):);):)
What I've ment is that library should implement all commonly used and
accepted abstractions and then, if it is practical, implement all
needed
specialisations, mixtures, etc.

> or not. ;-) You'll have justify the implication that
> we should build computer libraries around some specific
> choice of notions loosly derived from mathematics. Doing this
> is not a matter of course, as reactive systems are not all
> about mathematics.
I'm not sure what you mean by "reactive systems", but anyway.
My justification is very simple. Such a generic library as
Ada.Containers, which should serve as a basis for a wide variety
of programs, should be based on a well known abstraction commonly
accepted and understood by every programmer, not only by couple of
authors. The foundations of this library should be derived from the
common experience, not from the experience of one man. For example
of what other programmers think about containers see the following
links (as well as how this abstraction is implemented in other
languages such as Java, Python etc.)

http://en.wikipedia.org/wiki/Set_%28computer_science%29
http://en.wikipedia.org/wiki/Hash_table
http://en.wikipedia.org/wiki/List_%28computer_science%29
http://en.wikipedia.org/wiki/Array

Actually current proposal have to justify the use of such a
wonderful abstractions as Ordered_Sets, Hashed_Sets, Hashed_Maps and
Ordered_Maps as a basic set of abstractions.

>
> Second, the way Ada.Containers invites you to think about the order
> of elements ("containers are nothing, elements are everything").
> There might be some physical/logical correspondence between the
> order of elements in some container on the one hand, and their
> order as implied by the user's ordering functions passed during
> instantiation. Or there might not. It is more important what a
Can't argue with that ;)

> user wishes to to using the elements that happen to be elements
> of some collection. I.e. while it remains advisable to choose the
> proper container, Cursors are among the means to choose different
> containers when the need arises, ideally without disturbing the rest of
> the program.
I can't say I understand you here, but anyway, how cursors could
help to change container type without disturbing the rest of the
program?

>
> There are a number of "orders" of elements in this discussion.
I think you overestimate a little here. Order either is present
or is not.

> There are those on which you seem to build your correspondence, IIUC.
> Elements ordered relative to one another in the list and vector
> abstractions,
> because that is what a mathematician might assign to the notions.
Yes, YUIC. But it is not because "a mathematician" created this notion.
This is how all mathematicians *and* programmers understand it.

> But some elements are ordered relative to one another in ordered sets or
> maps
> that are ordered by key. This order need not entail the use of a list,
> and indeed requiring List/Vector <-> order will defeat several uses
> of the library which is rather more flexible. If I want a set for
> (a) memebership test, and (b) an ordered collection, then why should I
> store
> the elements in some List oder Vector just because I want element
> insertion to preserve order as well?
This exaple doesn't count. Membership test is common to any collection.
If you only need ordering then you can use array/vector or list
depending
on what kind of access you need. Why would you choose a set or hash?
And if you chose to have such a specialized type as Ordered_Map then
you

> Indeed, a close correspondence of order and choice of container
> will defeat some generic algorithms.
Care to provide an example of such a generic algorithm? If your
algorithm is so generic that order and access details are not
important, then express you algorithm in terms of Abstract_Collection.
Then averyone could choose any collection type that fits the task
in question most.

>
> I think it is of no primary concern here that some branches of
> mathematics can
> do without ordered sets, and that there is a natural ordering by position
> in a list. The library is for programmers, not for mathematical
> housekeepers. ;-)  There is a treasure trove of mathematical theory of
> computation that starts from computation in computers, and not the other
> way round :-)
>
I really hope that the smiles you put here really mean something ;)
Otherwise your disregard of mathematics and computer science could led
you to reinvent a lot of weels. ;( One need to have a knowledge to
distinguish a therasure from trash :) The sad thing is that this
proposal
forces the whole Ada comunity to learn the hard way and to reinvent
collections from scratch. Take a look at others languages collections
implementations.

>
>
>> Another silliness is overgeneralization of the
>> 'iterrator' concept and renaming it to 'cursor'.
>
>
> Given the operations of Cursors, I can see clearly how I can
> use Cursor operations in iteration. OTOH, iteration
Of course you can! One can use his computer to watch TV or even to
move his lawn, but that is not a justification for renaming this
computer to TV-set or mover. Authors of this proposal stated that
they model their library on STL. So why to name the same thing
differently?

> means doing something again, but an STL iterator (a pointer,
> really, or cursor if you wish) doesn't require that I do something
> again...
So what?

>
>
>> The problem here is that this terminology doesn't reflect the
>> fundamental differences between these types and mixes underlying
>> mathematical conncepts in some unregular way.
>
>
> If the library confuses a mathematician because he/she is used
> to some meanings of words, then maybe emphasising the Ada definitions,
> which relate to computers, will help?
>
Ok, it looks like you really hate mathematicians :) Why? To soothe you
I
can tell that I'm not a mathematician. I'm a physisist by education
and a programmer for the last 20 years. This library confuses me as a
programmer. I've always loved Ada 83 and 95. I really believe that its
standard library stands out by its clarity, completeness and
correctness.
Current proposal for Ada.Containers doesn't meet these high standards
yet.
It is too raw. It looks like the authors of this proposal didn't have a
goal of creating clear and solid foundation for future library
development.
It looks like they provided just a bunch of special case algorithms and

abstractions using far from perfect terminology. To understand this one
need
no degree in mathematics, just look around - STL,Java,Python, etc.,etc.

> 
> -- Georg

Mikhail

Re: GCC 4.0 Ada.Containers Cursor danger.

[Randy Brukardt]

"MMM" <terekhov@emc.com> wrote in message
news:1121134291.379399.79460@z14g2000cwz.googlegroups.com...
> Georg Bauhaus wrote:
...
> > First, Ada.Containers is not trying to approximate some notions
> > from linear algebra ("orthogonal normal basis"), metaphorically
> Note that this notion is not limited to linear algebra and I'm not
> agitating
> for implementation of this notion in Ada.Containers in any way!
> ;):);):)
> What I've ment is that library should implement all commonly used and
> accepted abstractions and then, if it is practical, implement all
> needed specialisations, mixtures, etc.

Ada.Containers does implement the widely-used abstractions (Vectors, Lists,
Sets, Maps), and a number of flavors of each. What it doesn't try to do is
implement *every* possible abstraction; there isn't enough manpower to do
that. Especially nearly useless ones like unordered maps and sets.

If you think that unordered sets and maps are useful, go ahead and design
some (you'll find they fit it the design very well).

...
> Actually current proposal have to justify the use of such a
> wonderful abstractions as Ordered_Sets, Hashed_Sets, Hashed_Maps and
> Ordered_Maps as a basic set of abstractions.

We don't; they're not "basic" abstractions. They're *useful* abstractions.
We hope that in the future a fuller library is built around this one.

...
> > Indeed, a close correspondence of order and choice of container
> > will defeat some generic algorithms.
> Care to provide an example of such a generic algorithm? If your
> algorithm is so generic that order and access details are not
> important, then express you algorithm in terms of Abstract_Collection.
> Then averyone could choose any collection type that fits the task
> in question most.

We didn't define an abstract collection because it doesn't work with the
generic design of the libraries. And you have to know the element type in
order to do anything useful.

One idea that was considered was a number of signature generics that
provided such a generic container. But there is a problem with Ada that we
were not able to solve that prevents such generics being declared in the
containers packages. So we decided to leave that also for a future standard.

...
> The sad thing is that this proposal
> forces the whole Ada comunity to learn the hard way and to reinvent
> collections from scratch. Take a look at others languages collections
> implementations.

We did. Remember that the entire Ada community was involved with this
design; there are literally hundreds of comments on the library, many of
which caused significant changes to it.

The truly sad thing is that *you* didn't participate in that discussion
(which has been going on for years, including here). Now that the standard
is getting its final polishing, someone jumps in and says "I don't like
it!". Sorry, but we're not going to start over because one person who didn't
even pay any attention doesn't like it.

And let me make it very clear -- no one is completely happy with this
library. Everyone has something that they would do different. That's a
typical reaction to something that is understood by everyone. The benefit
here is having something standard. What exactly it is doesn't matter much.
It is very similar to the situation with Unbounded_Strings. That library is
designed about as incorrectly as possible, but it still gets wide use, and
it still is very valuable to Ada programmers. The exact details don't
matter.

> >> Another silliness is overgeneralization of the
> >> 'iterrator' concept and renaming it to 'cursor'.

We certainly don't have to repeat mistakes made in other libraries! An
iterator is something that actively moves from element to element. There is
no possible way for a piece of data alone to be an iterator. One could argue
that the combination of the cursor object and the Next function compose an
iterator, but not the separate pieces.

We selected the name "cursor" because it didn't have the baggage of
"reference" or "designator". A cursor is a designator to an element in a
container. Period. Yes, you can use it for iteration, but that is just one
of the possible uses for it (and not a particularly important one, IMHO).


> Authors of this proposal stated that
> they model their library on STL. So why to name the same thing
> differently?

Because the STL got it wrong. And, in any case, our terminology has to match
that of Ada, not that of C++. If we're just copying C++, there is no reason
to bother - we might as well just turn out the lights here in Adaville.

...
> It looks like the authors of this proposal didn't have a
> goal of creating clear and solid foundation for future library
development.

That was a secondary goal at best. I think we did a fine job of that, but
only attempts to add units to the containers library will show that for
sure.

> It looks like they provided just a bunch of special case algorithms and
> abstractions using far from perfect terminology.

No, we took a minimalist approach and defined only the containers that are
widely needed. That means some of the basic abstractions (which are not
going to be used much) are left out.

> To understand this one need
> no degree in mathematics, just look around - STL,Java,Python, etc.,etc.

Those libraries are far larger, and for the most part, far less rigourously
defined. Most are defined by an implementation rather than a standard. If we
had an unlimited budget, I'm sure that many more containers would have been
included. But we don't have an unlimited budget or unlimited time.

                          Randy Brukardt.

Re: GCC 4.0 Ada.Containers Cursor danger.

[MMM]

Randy Brukardt wrote:
>
> The truly sad thing is that *you* didn't participate in that discussion
> (which has been going on for years, including here). Now that the standard
> is getting its final polishing, someone jumps in and says "I don't like
> it!". Sorry, but we're not going to start over because one person who didn't
> even pay any attention doesn't like it.
>
>

Randy,

I'm really sorry if my postings look like a bashing of the great work
you and other people did on Ada.Containers. I didn't mean to say
"Throw it over and start anew". At the same time I believe that anyone
who has reasonable arguments may say "I don't like it because of this
and that." With all due respect of course.

Sincerely
Mikhail

Re: GCC 4.0 Ada.Containers Cursor danger.

[Georg Bauhaus]

MMM wrote:

>>Cursors are among the means to choose different
>>containers when the need arises, ideally without disturbing the rest of
>>the program.
> 
> I can't say I understand you here, but anyway, how cursors could
> help to change container type without disturbing the rest of the
> program?
> [...]
> Care to provide an example of such a generic algorithm?

Here is a silly example demonstrating a subprogram that is
independent of any specific container. That is, you can choose
any instance in place of My_Container.
 As arguments to the following function, use cursors
returned by Floor and Ceiling (to mark a range of
associations in a map.) Use First and Last of a set to express
forall. Do the same using a vector.


with My_Container;
   -- some instance of some Ada.Container ("abstract" if you wish)

function gen_find
  (first,
   last: My_Container.Cursor;
   item: My_Container.Cursor) return My_Container.Cursor

--  The first cursor of the sequence from `first` to `last` that designates
-- an elemenent equal to the element designated by `item`.
-- `No_Element` if not found.
is
   use My_Container;

   p: Cursor := first;
   off: constant Cursor := Next(last);
begin
   loop
      exit when p = off or else Element(p) = Element(item);
      next(p);
   end loop;

   if p = off then
      return No_Element;
   else
      return p;
   end if;

end gen_find;

Re: GCC 4.0 Ada.Containers Cursor danger.

[Matthew Heaney]

Georg Bauhaus <bauhaus@futureapps.de> writes:

> Here is a silly example demonstrating a subprogram that is
> independent of any specific container. That is, you can choose
> any instance in place of My_Container.
>  As arguments to the following function, use cursors
> returned by Floor and Ceiling (to mark a range of
> associations in a map.) Use First and Last of a set to express
> forall. Do the same using a vector.
> 
> 
> with My_Container;
>    -- some instance of some Ada.Container ("abstract" if you wish)

But you can make a generic algorithm that is, um, generic:

generic
   type Element_Type (<>) is limited private;
   type Cursor (<>) is private;
   with function Element (Pos : Cursor) return ET is <>;
   with procedure Next (Pos : in out Cursor) is <>;
   with function "=" (L, R : ET) return Boolean is <>;
function Generic_Find
  (Start, Stop : in Cursor;
   Item        : in Element_Type) return Cursor;

Start denotes the (inclusive) beginning of the range of items to be
tested.

Stop denotes the (exclusive) one-beyond-the-end-of-the-range of items to
be tested.

If the item isn't found, then Generic_Find returns Stop.  Otherwise it
returns the earliest cursor in the sequence that matches Item.


> function gen_find
>   (first,
>    last: My_Container.Cursor;
>    item: My_Container.Cursor) return My_Container.Cursor

This requires care, since if First and Last are both inclusive members
of the range, then there's no way to designate an empty range.  

You always need a way to specify an empty range.  Discrete subtypes work
that way, as do array types.  In those cases, if T'Last < T'First, that
means the range is empty.  But you can't do that for a cursor, so you
have to use the one-off-the-end technique instead.


> --  The first cursor of the sequence from `first` to `last` that designates
> -- an elemenent equal to the element designated by `item`.
> -- `No_Element` if not found.
> is
>    use My_Container;
> 
>    p: Cursor := first;
>    off: constant Cursor := Next(last);
> begin
>    loop
>       exit when p = off or else Element(p) = Element(item);
>       next(p);
>    end loop;
> 
>    if p = off then
>       return No_Element;
>    else
>       return p;
>    end if;
> 
> end gen_find;


I prefer to say:

function Generic_Find
  (Start, Stop : in Cursor;
   Item        : in Element_Type) return Cursor is

   C : Cursor := Start;
begin
   while C /= Stop then
     if Element (C) = Item then
        return C;
     end if;
     Next (C);
   end loop;
   return Stop;
end Generic_Find;


To make this a little more general, and possibly more efficient (you
have to be careful with value-returning functions), you could say:

generic
   type Element_Type (<>) is limited private;
   type Cursor (<>) is private;
   with function Is_Equal (C : Cursor; E : ET) return Boolean is <>;
   with procedure Next (Pos : in out Cursor) is <>;
function Generic_Find
  (Start, Stop : in Cursor;
   Item        : in Element_Type) return Cursor;


Which you can implement as:

function Generic_Find
  (Start, Stop : in Cursor;
   Item        : in Element_Type) return Cursor is

   C : Cursor := Start;
begin
   while C /= Stop then
     if Is_Equal (C, Item) then
        return C;
     end if;
     Next (C);
   end loop;
   return Stop;
end Generic_Find;


In fact, we could generalize this even more, to abstract-away the
element type:

generic
   type Cursor (<>) is private;
   with function Found (C : Cursor) return Boolean is <>;
   with procedure Next (Pos : in out Cursor) is <>;
function Generic_Find
  (Start, Stop : in Cursor) return Cursor;


So now you can say:

function Generic_Find
  (Start, Stop : in Cursor) return Cursor is

   C : Cursor := Start;
begin
   while C /= Stop then
     if Found (C) then
        return C;
     end if;
     Next (C);
   end loop;
   return Stop;
end Generic_Find;


In any event, what should be noticed is that the container isn't part of
the generic algorithm.  And that is the key to understanding iterators
(um, I mean cursors...), since they abstract-away the container.  A
generic algorithm is a "generic algorithm" precisely because it's
container-independent.

You can use the algorithm to perform a linear search of a hashed
container (using those "dangerous" map cursors), e.g.

procedure Op (M : String_Integer_Maps.Map) is

   procedure Find is
     new Generic_Find (Integer, Cursor);  -- accept defaults

   C : constant Cursor := Find (M.First, No_Element);
begin
   if Has_Element (C) then ...;
end;

Re: GCC 4.0 Ada.Containers Cursor danger.

[Mikhail Terekhov]

Georg Bauhaus wrote:
> 
> Here is a silly example demonstrating a subprogram that is
> independent of any specific container. That is, you can choose
> any instance in place of My_Container.
> As arguments to the following function, use cursors
> returned by Floor and Ceiling (to mark a range of
> associations in a map.) Use First and Last of a set to express
> forall. Do the same using a vector.
> 
> 
> with My_Container;
>   -- some instance of some Ada.Container ("abstract" if you wish)
> 
> function gen_find
>  (first,
>   last: My_Container.Cursor;
>   item: My_Container.Cursor) return My_Container.Cursor
> 
> --  The first cursor of the sequence from `first` to `last` that designates
> -- an elemenent equal to the element designated by `item`.
> -- `No_Element` if not found.
> is
>   use My_Container;
> 
>   p: Cursor := first;
>   off: constant Cursor := Next(last);
> begin
>   loop
>      exit when p = off or else Element(p) = Element(item);
>      next(p);
>   end loop;
> 
>   if p = off then
>      return No_Element;
>   else
>      return p;
>   end if;
> 
> end gen_find;

The problem with your example is that it is based on the wrong
assumptions:
	- 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. 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.
	- Second is that find/search operation makes sence only
	  for a mapping container i.e. vector or hash; in this
	  case it returns a key corresponding to the element
	  they search for (index for vectors is just a special
	  kind of key) if element has been found and some kind
	  of No_Element key or exception if there is no such
	  element. For a not mapping container i.e. set, list
	  or tree the find/search degenerates into membership test
	  because there is no sence to search for the element
	  if you already have it.
True generic operation for all container types can be membership
test not find/search.

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?

Another problem with your example is that there is no collection
per se in the gen_find function signature. This is actually a
feature of the Ada.Containers itself. Some times cursors replace
collections completely! That kind of indirect interface is very
dangerous in my view.

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

Mikhail

Re: GCC 4.0 Ada.Containers Cursor danger.

[Matthew Heaney]

Mikhail Terekhov <terekhov@emc.com> writes:

> The problem with your example is that it is based on the wrong
> assumptions:
> 	- First is that all containers have an order.
> 	  Again, sets and hashes in general are *not ordered*.

This reminds me of Galileo's famous pronouncement "Eppur si muove!"
when being confronted by the church hierarchy.  The Generic_Find
algorithm works, even if you say it doesn't!

The Generic_Find algorithm simply tests each element in the sequence as
the element is being visited, and the algorithm terminates when it
either finds a match, or has visited every element in the sequence.  It
doesn't matter in what order the elements appear in the sequence.

The Generic_Find algorithm is actually a good example, since it works
for any container.  That is, it works irrespective of the order in which
a container delivers elements via the active iterator (cursor), since
the algorithm itself doesn't depend on a specific order.

Re: GCC 4.0 Ada.Containers Cursor danger.

[Mikhail Terekhov]

Matthew Heaney wrote:
> Mikhail Terekhov <terekhov@emc.com> writes:
> 
> 
>>The problem with your example is that it is based on the wrong
>>assumptions:
>>	- First is that all containers have an order.
>>	  Again, sets and hashes in general are *not ordered*.
> 
> 
> This reminds me of Galileo's famous pronouncement "Eppur si muove!"
> when being confronted by the church hierarchy.  The Generic_Find
> algorithm works, even if you say it doesn't!

It is a great honour for me to be compared to Galileo, but wait a 
minute, may be you mean yourself? No, that can't be, Galileo wouldn't 
allow such a disregard to mathematics! ;)

> 
> The Generic_Find algorithm simply tests each element in the sequence as
> the element is being visited, and the algorithm terminates when it
> either finds a match, or has visited every element in the sequence.  It
> doesn't matter in what order the elements appear in the sequence.

That is very true. No mention about order or cusors.

> 
> The Generic_Find algorithm is actually a good example, since it works
> for any container.  That is, it works irrespective of the order in which
> a container delivers elements via the active iterator (cursor), since
> the algorithm itself doesn't depend on a specific order.

Again, that is very true. Can't believe you say it.

Re: GCC 4.0 Ada.Containers Cursor danger.

[Matthew Heaney]

Mikhail Terekhov <terekhov@emc.com> writes, in response to me:

> > The Generic_Find algorithm is actually a good example, since it
> > works for any container.  That is, it works irrespective of the
> > order in which a container delivers elements via the active iterator
> > (cursor), since the algorithm itself doesn't depend on a specific
> > order.
> 
> Again, that is very true. Can't believe you say it.


But I was referring to all of your earlier the claims:

<<  - First is that all containers have an order.
    Again, sets and hashes in general are *not ordered*.>>

As was pointed out in another post, it is helpful to distiguish between
the order of the elements themselves (the "external" order), and how the
container organizes its elements in order to satisfy time complexity
requirements (the "internal" order).

Clearly, all of the containers have some internal order; the container
itself is simply a high-level wrapper around some low-level data
structure such as a tree or a hash table.

Now of course, we're talking about the containers in the Ada 2005
standard container library.  You refer to sets and hashes "in general"
in the quoted text above, but our concern here is with sets and hashed
"in particular" (that is, in the standard container library). What is
true of sets and hashes "in general" is of no interest.

So if you are saying that containers in the standard library have no
"internal" order, then that claim is obviously false.  Lacking any
internal order, containers simply wouldn't work.  

So you must be making a statement about the "external" order of a
container.  Obviously the Ordered_Sets and Ordered_Maps do have an
(external) order, that corresponds to the element order; indeed that's
the whole point of the "ordered" container category.

That leaves the hashed containers.  The generic formal region of those
containers only requires that elements have a hash function (which is
very different from an order relation), so clearly the hashed containers
have no external order (at least one that is specified).  It would not
be meaningful to speak about the "external order" of a hashed container,
since a hash table works by scattering elements far and wide.

But that's not the same thing as saying a hashed container has no order
at all.  Of course it has an order: the internal order, that of the hash
table itself.  The difference is that the standard doesn't specify what
that internal order is.


<<  To impose an order on them standard needs to put a
    restriction on implementarion algorithms.>>

Do you mean the internal order (how the container choses to organize the
elements internally), or do you mean the external order (the order in
which elements are delivered via an iterator)?

Of course the standard does say something about the (external) order of
the Ordered_Sets and Ordered_Maps.  Vendors are free to choose any
implementation that meets the requirements.  But does that put a
restriction on implementation algorithms?  The restriction really comes
from what the generic formal region requires from its elements.
Obviously you wouldn't be able to implement an Ordered_Set using a hash
table (for example), since the generic formal region doesn't pass in a
hash function.


<<  Your example
    is completely legal generic function in the current
    Ada.Containers framework. >>

Well of course it is, because the Ada.Containers subsystem is a
framework for implementing generic algorithms!  (Hint: that's why it has
cursors.)


<<  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 sense at all.>>

This statement is false.  In the example we're talking about, the
Generic_Find algorithm works for *any* container, no matter what it's
order (internal or external, it doesn't matter).  Give it an unordered
container ("unordered" in the external sense, e.g. a hashed container),
and the algorithms works just fine.

First and Last have well-defined semantics: they define the endpoints
(half-open style) of a sequence of elements.  The algorithm works
irrespective of whether the elements of the sequence are ordered or not.


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

This statement is false.  The find operation simply tests each element
in the sequence, irrespective of its logical order.  Give it a set
container, and the algorithm works just fine.  Eppur si muove...


<<  in this case it returns a key corresponding to the element
    they search for (index for vectors is just a special
    kind of key) if element has been found and some kind
    of No_Element key or exception if there is no such
    element. >>

Well, if this is a simple membership test (to determine whether the item
is among a range of elements), then it can just return Boolean.  I
re-wrote Georg's example to return a cursor, which is more or less the
container analog of an access type.  The function returns the
distinguished cursor value No_Element (analogous to the distinguished
access value "null") if no match was found.

Certainly the algorithm doesn't have to be written that way, and if you
prefer you can return a key (or index) instead.  It is ultimately the
decision of the author of the generic algorithm.  The design of the
algorithm is orthogonal to the design of the library, which merely
provides a flexible framework that allows either possibility.


<<  For a not mapping container i.e. set, list
    or tree the find/search degenerates into membership test
    because there is no sense to search for the element
    if you already have it.>>

I don't think you understand the original algorithm.  (Indeed, I don't
think you even understand the concept of a generic algorithm.)  The
cursors passed as subprogram parameters specify the endpoints of the
range.  The container element you're looking for is (or is not) a member
of the range.

Note that it is an element *value* that is passed as a parameter, which
is then compared to the actual elements in the container.  It is not
correct to say that "you have an element" unless you have either a
cursor that designates that element, or (less efficiently) you have the
key (or index) associated with that element.  If all you have is an
element value, then you don't in any sense have a container element.
(Container elements always belong to a container, and to refer to a
container element you need some kind of handle, which means either a
cursor or a key.)

Re: GCC 4.0 Ada.Containers Cursor danger.

[Georg Bauhaus]

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 

Re: GCC 4.0 Ada.Containers Cursor danger.

[Dmitry A. Kazakov]

On Fri, 15 Jul 2005 01:03:34 +0200, 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.
> 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?".

See the well-ordering theorem and then the axiom of choice. (:-))

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)

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

Hmm, what about ring buffers?

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

And for proofs it is essential that the premises were correct. Programming
is not much different...

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

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

No. Find is more general. It searches for an element E in S having a
certain property f(E). Find is a membership test for X only when f(E) is
E=X.

[and again, sets could be searchable and not]

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

Re: GCC 4.0 Ada.Containers Cursor danger.

[Georg Bauhaus]

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


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


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


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


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


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

Re: GCC 4.0 Ada.Containers Cursor danger.

[Dmitry A. Kazakov]

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

Re: GCC 4.0 Ada.Containers Cursor danger.

[Matthew Heaney]

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

> Think about differences between:
> 
> - An unordered set of unordered elements

Does not exist in the Ada 2005 standard container library.


> - An unordered set of ordered elements

Does not exist in the Ada 2005 standard container library.


> - An ordered set of unordered elements

The Ada 2005 standard container library calls that a "hashed set."


> - An ordered set of ordered elements (and these orders are different)

The Ada 2005 standard container library calls that an "ordered set."


> Hmm, what about ring buffers?

Does not exist in the Ada 2005 standard container library.


> And for proofs it is essential that the premises were correct. Programming
> is not much different...

Yes, that's called a "reference manual."


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

Of course a container must "mix implementation and interface," since it
has to provide access to its elements.  The essential container design
problem is doing that without exposing representation details.  Cursors
are that mechanism.

There's nothing bad about this; it's simply the nature of a container
abstraction.  The container should get out of the way as much as
possible, since it's the elements we care about.


> [and again, sets could be searchable and not]

The sets in the Ada 2005 standard container library are searchable.

Re: GCC 4.0 Ada.Containers Cursor danger.

[Mikhail Terekhov]

Matthew Heaney wrote:
> 
.......
 > Does not exist in the Ada 2005 standard container library.
.......
 > Does not exist in the Ada 2005 standard container library.
.......
> 
>>And for proofs it is essential that the premises were correct. Programming
>>is not much different...
> 
> 
> Yes, that's called a "reference manual."
> 

And we are talking about Holy scripture ;)

> 
> Of course a container must "mix implementation and interface," since it
> has to provide access to its elements.  The essential container design
> problem is doing that without exposing representation details.  Cursors
> are that mechanism.
> 

This "must" is too strong. Some libraries use access types and don't 
"mix implementation and interface." If Ada.Containers exposes 
representation details (Cursors) i.e. "mixes implementation and 
interface," then it is not the essential container design then?

> There's nothing bad about this; it's simply the nature of a container

There is nothing bad about this, but it's not the nature of a container 
abstraction; it's a nature of your specific vision of a container 
abstraction.

> abstraction.  The container should get out of the way as much as
> possible, since it's the elements we care about.
> 

Yes, and Cursors are probably a part of this "as much as possible".

> 
> 
>>[and again, sets could be searchable and not]
> 
> 
> The sets in the Ada 2005 standard container library are searchable.

Then it is not the common set abstraction. In the common set abstraction 
search degenerates into membership test and the common set abstraction 
contains no such things like First, Last and Cursor.

Re: GCC 4.0 Ada.Containers Cursor danger.

[Matthew Heaney]

Mikhail Terekhov <terekhov@emc.com> writes:

> >>[and again, sets could be searchable and not]
> > The sets in the Ada 2005 standard container library are searchable.
> 
> Then it is not the common set abstraction. In the common set
> abstraction search degenerates into membership test and the common set
> abstraction contains no such things like First, Last and Cursor.

All of the containers in the standard container library have a
membership test called Contains:

  function Contains (Container : Map; Key : Key_Type) 
    return Boolean;

   function Contains (Container : Set; Item : Element_Type) 
    return Boolean;

George's generic algorithm Generic_Find does a membership test too.  The
difference is that Contains is a primitive operation of the type, and
therefore takes advantage of the container's representation: for ordered
sets and maps, Contains executes in O(log n) time, and for the hashed
containers it executes in O(1) time.

Generic_Find performs a linear search, and hence executes in O(n) time.

The other, more subtle difference is that Contains tests for
"equivalence," and Generic_Find tests for "equality."  See my tutorial
notes online at charles.tigris.org if you don't understand equivalence.

Re: GCC 4.0 Ada.Containers Cursor danger.

[Mikhail Terekhov]

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

Re: GCC 4.0 Ada.Containers Cursor danger.

[Matthew Heaney]

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.

Re: GCC 4.0 Ada.Containers Cursor danger.

[Simon Wright]

Matthew Heaney <matthewjheaney@earthlink.net> writes:

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

Is this still true in 0Y?

Re: GCC 4.0 Ada.Containers Cursor danger.

[Matthew Heaney]

Simon Wright <simon@pushface.org> writes:

> Matthew Heaney <matthewjheaney@earthlink.net> writes:
> 
> > 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).
> 
> Is this still true in 0Y?

I know Tucker and Pascal were looking at this issue, but I'm not sure
what was concluded.

Re: GCC 4.0 Ada.Containers Cursor danger.

[Randy Brukardt]

"Simon Wright" <simon@pushface.org> wrote in message
news:m2k6jmaw9n.fsf@grendel.local...
> Matthew Heaney <matthewjheaney@earthlink.net> writes:
>
> > 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).
>
> Is this still true in 0Y?

No. Virtually all of those rules were repealed; they made no sense and
didn't really fix the real problem. The better solution was to make some
access subtypes illegal instead. (If you don't even know what an access
subtype is, you're not alone. I don't think I've ever used one in 20+ years
of Ada programming.)

So we could have used access types rather than defining cursors, but we
didn't do it because access types can never be safe in this case, while
cursors can be checked. Similarly, we use a call-back procedure in
Update_Element rather than an access type, because we can check for abuse in
the routine.

                     Randy.

Re: GCC 4.0 Ada.Containers Cursor danger.

[Randy Brukardt]

"Mikhail Terekhov" <terekhov@emc.com> wrote in message
news:gb_Ce.8815$LC6.6336@fe06.lga...
....
> That is wonderful! Almost any example of using cursor doesn't really
> need cursors. Why this burden then?

Not at all true. Any algorithm that needs to modify the container during the
iteration, or needs to iterate through multiple containers in lockstep, will
need something like cursors. Ada.Containers wants Iterate to be safe, so
modifications of the container raise Program_Error (otherwise, it would be
impractical to insure that the iteration would continue safely).
...
> If you need just a set of references to some elements, then you are all
> set. Ada provides access types, why cursor?

Because access types aren't safe in Ada and cannot be made safe. If we
returned access types from functions (and we considered it), a modification
to the container could destroy the access value unpredictably -- and there
is no way for future uses of the access value to detect that. A cursor is a
higher level abstraction than an access type, and it can be checked. (I
personally think it is unfortunate that we didn't *require* it to be checked
in most cases, but at least an implementation *can* check -- which is
impossible with access types.)

                          Randy.

Re: GCC 4.0 Ada.Containers Cursor danger.

[Robert A Duff]

"Randy Brukardt" <randy@rrsoftware.com> writes:

> "Mikhail Terekhov" <terekhov@emc.com> wrote in message
> news:gb_Ce.8815$LC6.6336@fe06.lga...
> ....
> > That is wonderful! Almost any example of using cursor doesn't really
> > need cursors. Why this burden then?
> 
> Not at all true.

Consider iterating through a sequence of characters,
and producing a new, transformed sequence.
If each character is independent of the others,
then Iterate is simplest.  For example, convert each
character to upper case.

But if the characters depend on what comes before/after,
using cursors can make the code simpler.  For example,
replace all sequences of one or more blanks with a single
blank.  You can do that with Iterate, but then you have to
keep flags remembering what came before.  Using cursors,
the code is simplified.

By the way, Iterate can be implemented in terms of cursors,
and cursors can be implemented in terms of Iterate.
So in some sense they are equivalent, and any data structure
for which one makes sense, the other makes sense.

There are data structures for which neither can be supported.

- Bob

Re: GCC 4.0 Ada.Containers Cursor danger.

[MMM]

Matthew Heaney wrote:

>
> There is no such thing as an "unordered" container (and here we're
> really talking about sets and maps), since then there would be no way to
> find anything without a linear search.  That's why we have both ordered
> and hashed containers.

You contradict yourself here. So, do an "unordered" containers exist or
do they not?

>
> The "position" of an element always relative to other elements in the

That depends on the semantic. For example the Hashed_Sets in your
terminology requires no "relative position" semantic. The fact that an
implementation will use some "relative position" semantic internaly is
an implementation detail. This internal relative position can be
different for the same set in different hash implementations.

> container.  For an "ordered" container (Ordered_Sets, Ordered_Maps), the
> position is determined by the "<" operator for elements.  For a "hashed"

This is a confusion. The "<" operator defines relative order, not
position. For an ordered container position is defined by both the "<"
operator and the container contents. Think of two vectors A(a,b,c,d)
and B(a,c,d) as an simple example. Suppose they have both the same "<"
operator. The position of the 'c' element in A is 3 and in B is 2.

> container (Hashed_Sets, Hashed_Maps), the position is determined from
> the hash value of the element (since that determines which bucket the
> element falls into).
>
> An iterator (either passive or active) simply enumerates elements in
> their order as specified by the type of container they're in (either

Exactly! Note also that the natural name for this is "iterator" not
"cursor". The main and natural purpose of this thing is to iterate over
the contained elements, not to provide a pointers to arbitrary
elements.  The iterator concept is the general way to go over all
elements or some subset of then of an any container.

> sort order or bucket order).

Not quite correct. Sort order has nothing to do with a vector or list
ordering in general. One can have a vector of integers filled in
randomly, for example. In case of Hashed_Sets bucket order is an
implementation detail which can differ for different implementations.
The semantic of Hashed_Sets simpli doesn't require any particular
order.

>
> Have you ever done any COM or DirectShow programming under Windows?  A
> cursor is the same as the EnumXXX class.  (If I remember correctly, I
> think Java also has something it refers to as an "enumerator".)


MS is not always the best example to follow.

Regards,
Mikhail

Re: GCC 4.0 Ada.Containers Cursor danger.

[Matthew Heaney]

MMM wrote:
> Matthew Heaney wrote:
>
> >
> > There is no such thing as an "unordered" container (and here we're
> > really talking about sets and maps), since then there would be no way to
> > find anything without a linear search.  That's why we have both ordered
> > and hashed containers.
>
> You contradict yourself here. So, do an "unordered" containers exist or
> do they not?

Unordered containers do not exists.  The problem is nomenclature.
"Hashed" containers are of course ordered, but the order isn't
specified.


> > The "position" of an element always relative to other elements in the
>
> That depends on the semantic. For example the Hashed_Sets in your
> terminology requires no "relative position" semantic.

Not quite.  For hashed containers there is indeed a relative position,
but it's not specified.  (There must be *some* order, to deliver
elements via the iterators.)


> The fact that an
> implementation will use some "relative position" semantic internaly is
> an implementation detail. This internal relative position can be
> different for the same set in different hash implementations.

Yes.  The standard doesn't specify the order in which elements (of a
hashed container) are delivered via iterators, so different
implementations can vary.  (Among other things, implementations can
vary because the standard doesn't specify the hash table load factor.)


> > container.  For an "ordered" container (Ordered_Sets, Ordered_Maps), the
> > position is determined by the "<" operator for elements.  For a "hashed"
>
> This is a confusion. The "<" operator defines relative order, not
> position.

You say to-MAY-to, I say to-MAH-to.  It's the same.


> > An iterator (either passive or active) simply enumerates elements in
> > their order as specified by the type of container they're in (either
>
> Exactly! Note also that the natural name for this is "iterator" not
> "cursor". 

You say "chien", I say "dog".  It's the same.

Re: GCC 4.0 Ada.Containers Cursor danger.

[MMM]

"Matthew Heaney" <mheaney@on2.com> wrote in message
news:1121124248.600055.292320@f14g2000cwb.googlegroups.com...
>
> Unordered containers do not exists.  The problem is nomenclature.
> "Hashed" containers are of course ordered, but the order isn't
> specified.
>

You are mixing abstraction and implementation here. Of course during
a program run when container has been created and populated, there is
*some* order of elements. But there is no guarantee that the same order
will be provided in some other implementation. Other implementation
can use compleetely different hashing algorithm or just some different
load factor. Even in the same implementation the order could be
different (imagine an implementation where bucket is choosen using
random number). Bottom line: if an order of elements in a collection
for
the same application depends on the library implementation, or is
random, then from the API point of view - there is no order. If you
still
want to provide an order to hash implementation then API should
explicitly say what kind of order and should guarantee it across
implementations. My point is that while probably useful, this ordered
abstraction is a specialisation or extension to the basic
functionality.
See for example Java version of SortedSet.

>
>> > The "position" of an element always relative to other elements in the
>>
>> That depends on the semantic. For example the Hashed_Sets in your
>> terminology requires no "relative position" semantic.
>
> Not quite.  For hashed containers there is indeed a relative position,
> but it's not specified.  (There must be *some* order, to deliver
> elements via the iterators.)

Again, if you can't guarantee the order or do not require some order,
then
from the API point of view - there is *no* order. Of course there is
*some*
order, but this order will vary depending on the implementation or "the

phase of the moon" which can't be the base for the standard.

>
>
>> The fact that an
>> implementation will use some "relative position" semantic internaly is
>> an implementation detail. This internal relative position can be
>> different for the same set in different hash implementations.
>
> Yes.  The standard doesn't specify the order in which elements (of a
> hashed container) are delivered via iterators, so different
> implementations can vary.  (Among other things, implementations can
> vary because the standard doesn't specify the hash table load factor.)
>
>
>> > container.  For an "ordered" container (Ordered_Sets, Ordered_Maps), the
>> > position is determined by the "<" operator for elements.  For a "hashed"
>>
>> This is a confusion. The "<" operator defines relative order, not
>> position.
>
> You say to-MAY-to, I say to-MAH-to.  It's the same.
>

Yes, it is the same, while we are talking in a bar, siping beer and
bashing MS.
When we are talking about standards - there is a difference.

>
>> > An iterator (either passive or active) simply enumerates elements in
>> > their order as specified by the type of container they're in (either
>>
>> Exactly! Note also that the natural name for this is "iterator" not
>> "cursor".
>
> You say "chien", I say "dog".  It's the same.
>
Sure it is the same. So why to change? Just to be different?

Re: GCC 4.0 Ada.Containers Cursor danger.

[Simon Wright]

"MMM" <terekhov@emc.com> writes:

>>> > An iterator (either passive or active) simply enumerates elements in
>>> > their order as specified by the type of container they're in (either
>>>
>>> Exactly! Note also that the natural name for this is "iterator" not
>>> "cursor".
>>
>> You say "chien", I say "dog".  It's the same.
>>
> Sure it is the same. So why to change? Just to be different?

When the Booch Components used the word _iterator_ it was definitely
something used to deliver the elements in an order (and I for one can
remember users who did rely on an order-of-delivery when it was not at
all guaranteed, to refer up-topic; but I always thought that was
because they had had brain fade by that time ..). The STL, and now the
Ada Containers, regard a pair of _things_ as delimiting a range, and
that is most definitely something not covered by the word _iterator_.

I for one don't think that _iterator_ is at all the 'natural' name for
the concept. I don't think many other Brits would think so either. Of
course, we are in the minority now as regards use of English ...

Re: GCC 4.0 Ada.Containers Cursor danger.

[MMM]

> I for one don't think that _iterator_ is at all the 'natural' name for
> the concept. I don't think many other Brits would think so either. Of
> course, we are in the minority now as regards use of English ...

As a not native English speaker I'm guilty in this mess with the
language too. :(
I find it ironic that with regard to this thread I can feel your pain,
but in
a somewhat different way. Mathematical concepts like set and hash
used once to develop computer libraries and languages now regarded
as a "useless abstractions" and have completely different meaning.

Re: GCC 4.0 Ada.Containers Cursor danger.

[Georg Bauhaus]

MMM wrote:
> "Matthew Heaney" <mheaney@on2.com> wrote in message

>>>>An iterator (either passive or active) simply enumerates elements in
>>>>their order as specified by the type of container they're in (either

Note "enumerates", 3rd person sing. You need the operations of
the type to express iteration. However, you don't need the smae operations
of a Cursor if you just want a reference to some element. Imagine
you just want the reference, and no iteration. Is it natural then to have
the name imply iteration?

>>>Exactly! Note also that the natural name for this is "iterator" not
>>>"cursor".

Since I don't speak English, I can't decide whether an English word is
a natural name. But since I don't speak English, I feel qualified (socially)
to mention that some names were chosen by programmers whose native language
isn't English either. This includes names choses by Stepanov et al., like
"push_back".  For example the phrasal verb "to push [sth] back" has meanings
in spoken English. Its use in STL though is, uhm, novel, right? The phrasal verb
of spoken English seems to contradict the STL meaning of push_back...
(There is now a different word to be used as the name of the concept in AI 302.)

Declaring "novel" uses of English words as natural by default
(because they have become widespread) gives a new meaning to "natural"
IMHO... Natural is what some majority of non-native speakers uses ;-)

>>You say "chien", I say "dog".  It's the same.
>>
> 
> Sure it is the same. So why to change? Just to be different?

Please, be different when the difference marks the proper choice of a word.
It helps understanding. Notice the many fights over passive versus
active iteration. As far as I can tell A.18 reduces the likelyhood of this
discussion, as a side effect of using different names.

Re: GCC 4.0 Ada.Containers Cursor danger.

[Robert A Duff]

Georg Bauhaus <bauhaus@futureapps.de> writes:

> MMM wrote:
> > "Matthew Heaney" <mheaney@on2.com> wrote in message
> 
> >>>>An iterator (either passive or active) simply enumerates elements in
> >>>>their order as specified by the type of container they're in (either
> 
> Note "enumerates", 3rd person sing. You need the operations of
> the type to express iteration. However, you don't need the smae operations
> of a Cursor if you just want a reference to some element. Imagine
> you just want the reference, and no iteration. Is it natural then to have
> the name imply iteration?
> 
> >>>Exactly! Note also that the natural name for this is "iterator" not
> >>>"cursor".
> 
> Since I don't speak English,...

That's an astonishing statement!  You speak it quite well, in this
forum.

>... I can't decide whether an English word is
> a natural name. But since I don't speak English, I feel qualified (socially)
> to mention that some names were chosen by programmers whose native language
> isn't English either.

Like P and V for semaphore ops?  ;-)

Or "queue", which on this side of the pond is used only in computer
science?

Anyway, I find "cursor" preferable to "iterator", to refer to that thing
that can point at [the position of] an element, and perhaps be moved
forward or backward to point at other places.  To me, "iterator" means
"something that iterates", and I find the C++ STL usage of the term very
much unnatural.

I suppose "natural" is in the eye of the beholder.

- Bob

Re: GCC 4.0 Ada.Containers Cursor danger.

[Marc A. Criley]

MMM wrote:

> Bottom line: if an order of elements in a collection
> for
> the same application depends on the library implementation, or is
> random, then from the API point of view - there is no order. If you
> still
> want to provide an order to hash implementation then API should
> explicitly say what kind of order and should guarantee it across
> implementations. 

If the container is identified as being "unordered", e.g. set or map, 
then it is a programming error to rely on elements being produced, via 
iterator or cursor, in any particular/repeatable order.

If I needed to rely on the ordering--in the same or across 
implementations--I would utilize an "ordered" container.

-- Marc A. Criley
-- www.mckae.com
-- DTraq - XPath In Ada - XML EZ Out --

Re: GCC 4.0 Ada.Containers Cursor danger.

[MMM]

Exactly. But the original claim was that "unordered" containers do not
exist.

Re: GCC 4.0 Ada.Containers Cursor danger.

[Matthew Heaney]

MMM wrote:
> Exactly. But the original claim was that "unordered" containers do not
> exist.

It depends of course on how one defines "unordered."

I use the term "unordered" to refer to a set (or map) implemented using
some kind of sequential container (a list, say).  The only way to find
an element is by performing a linear search.

An "ordered" set is implemented using a data structure that allows you
to find an element in better than O(n) time.  Using that criterion,
then both the Hashed_Set and Ordered_Sets are "ordered."

The order isn't specified for a Hashed_Set, but its elements aren't
organized willy-nilly either (qua list).  A hashed container is
implemented using a hash table, and so its time complexity is O(1), and
it is in that sense that I refer to a hashed container as being
"ordered."

Part of the confusion stems from the fact that other languages like C++
use the term "sorted" to refer to what the Ada standard calls
Ordered_Maps and Ordered_Sets.  (My original API actually used the
terms Sorted_Maps and Sorted_Sets.)  The "sorted vs. hashed"
nomenclature probably makes it less confusing to say that the
associative containers are both "ordered," but it's not that big a deal
as long as we know we're refering to associative containers, and
understand that a hashed container has some order, but that its order
isn't specified.

Re: GCC 4.0 Ada.Containers Cursor danger.

[MMM]

Matthew Heaney wrote:
>
> MMM wrote:
>
>>Exactly. But the original claim was that "unordered" containers do not
>>exist.
>
>
> It depends of course on how one defines "unordered."
>
> I use the term "unordered" to refer to a set (or map) implemented using
> some kind of sequential container (a list, say).  The only way to find
> an element is by performing a linear search.
>
> An "ordered" set is implemented using a data structure that allows you
> to find an element in better than O(n) time.  Using that criterion,
> then both the Hashed_Set and Ordered_Sets are "ordered."
>
> The order isn't specified for a Hashed_Set, but its elements aren't
> organized willy-nilly either (qua list).  A hashed container is
> implemented using a hash table, and so its time complexity is O(1), and
> it is in that sense that I refer to a hashed container as being
> "ordered."

Ok, then you need to convince the rest of the world that your
definition
of "order" through the time complexity and big-O notation makes sense.
To understand what is wrong with you definition you could start at
http://en.wikipedia.org/wiki/Order
It could really help.

>
> Part of the confusion stems from the fact that other languages like C++
> use the term "sorted" to refer to what the Ada standard calls
> Ordered_Maps and Ordered_Sets.  (My original API actually used the
I don't think that "Sorted" vs. "Ordered" brings much confusion. What
is
confusing is that such a specialized cases as "Ordered_Maps" and
"Ordered_Sets" has been put as a foundation of the standard library.

> terms Sorted_Maps and Sorted_Sets.)  The "sorted vs. hashed"
> nomenclature probably makes it less confusing to say that the
> associative containers are both "ordered," but it's not that big a deal
> as long as we know we're refering to associative containers, and
> understand that a hashed container has some order, but that its order
> isn't specified.
>
Sorry, can't decifer this last sentence. Compating sorted vs. hashed is
like apples vs. oranges.

Re: GCC 4.0 Ada.Containers Cursor danger.

[Matthew Heaney]

MMM wrote:
> I don't think that "Sorted" vs. "Ordered" brings much confusion. What
> is confusing is that such a specialized cases as "Ordered_Maps" and
> "Ordered_Sets" has been put as a foundation of the standard library.

It can't be that confusing, since that's already the case for C++.


> Comparing sorted vs. hashed is like apples vs. oranges.

A general-purpose container library needs both.  That's why hashed
containers are being added to the C++ standard library.

Re: GCC 4.0 Ada.Containers Cursor danger.

[MMM]

> MMM wrote:
> > I don't think that "Sorted" vs. "Ordered" brings much confusion. What
> > is confusing is that such a specialized cases as "Ordered_Maps" and
> > "Ordered_Sets" has been put as a foundation of the standard library.
>
> It can't be that confusing, since that's already the case for C++.
Read it again, both my statement and the STL documentation. "Sorted
Associative Container" is a refinment of the plain vanilla "Associative
Container" that has no order.

>
> > Comparing sorted vs. hashed is like apples vs. oranges.
>
> A general-purpose container library needs both.  That's why hashed
> containers are being added to the C++ standard library.
It looks like you are not reading the message you are replying to.

Re: GCC 4.0 Ada.Containers Cursor danger.

[Georg Bauhaus]

MMM wrote:

>>>Comparing sorted vs. hashed is like apples vs. oranges.
>>
>>A general-purpose container library needs both.  That's why hashed
>>containers are being added to the C++ standard library.
> 
> It looks like you are not reading the message you are replying to.
> 

From the link you have given I can see that there are zillions
of meanings of "order". AI 302 adds clarity by selecting no more than
two I think. A meaning in the very first sentences:

 "The library
comprises sequence containers (vectors and lists), for inserting elements at
specified positions, and associative containers (sets and maps), which position
elements in order by key."

That is, positioning (a necessary implementation mechanism) is by key.
Later, the text introduces a sort order, and ordered associative
containers. So perhaps "order" is overloaded in the AI to mean
sorting and positioning depending on contenxt?

Re: GCC 4.0 Ada.Containers Cursor danger.

[MMM]

Georg Bauhaus wrote:
>
>  From the link you have given I can see that there are zillions
> of meanings of "order". AI 302 adds clarity by selecting no more than
Ok, try this one http://www.nist.gov/dads/HTML/totalorder.html

> two I think. A meaning in the very first sentences:
>
> "The library
> comprises sequence containers (vectors and lists), for inserting
> elements at
> specified positions, and associative containers (sets and maps), which
> position
> elements in order by key."
>
> That is, positioning (a necessary implementation mechanism) is by key.
Why this mechanism is necessay? From mathematical (as well as
computer science) point of view ordered set and ordered map is a
special case. From implementation point of view ordering by key is
just one possible solution.

> Later, the text introduces a sort order, and ordered associative
> containers. So perhaps "order" is overloaded in the AI to mean
> sorting and positioning depending on contenxt?
As I understand it, in mathematics "sorted" is a synonym for "ordered".
Fortunately, according to Simon, my understanding is in agreement
with English this time ;)

Mikhail

Re: GCC 4.0 Ada.Containers Cursor danger.

[Matthew Heaney]

MMM wrote:
> Read it again, both my statement and the STL documentation. "Sorted
> Associative Container" is a refinment of the plain vanilla "Associative
> Container" that has no order.

You're referring to an abstraction specification, and I was referring
to an actual container object.  There is no way to declare an
"associative container" object in C++: you can only declare a sorted
set, or a sorted map.


> It looks like you are not reading the message you are replying to.

Mostly because I have no idea what your point is.

Re: GCC 4.0 Ada.Containers Cursor danger.

[Simon Wright]

"Matthew Heaney" <mheaney@on2.com> writes:

> It depends of course on how one defines "unordered."
>
> I use the term "unordered" to refer to a set (or map) implemented using
> some kind of sequential container (a list, say).  The only way to find
> an element is by performing a linear search.
>
> An "ordered" set is implemented using a data structure that allows you
> to find an element in better than O(n) time.  Using that criterion,
> then both the Hashed_Set and Ordered_Sets are "ordered."

These seem very unnatural and misleading usages to me.

Re: GCC 4.0 Ada.Containers Cursor danger.

[Marc A. Criley]

MMM wrote:

<forContext>
I wrote:
 >> If the container is identified as being "unordered", e.g. set or map,
 >> then it is a programming error to rely on elements being produced,
 >> via iterator or cursor, in any particular/repeatable order.
 >>
 >> If I needed to rely on the ordering--in the same or across
 >> implementations--I would utilize an "ordered" container.

</forContext>

> Exactly. But the original claim was that "unordered" containers do not
> exist.

Unordered vs ordered vs sorted is part of the abstraction.  A plain 
vanilla "set" is unordered, even though any implementor knows there's 
going to be an internal ordering that is used for iterating and such.

 From the point of view of my application utilizing an unordered set 
container, there can be no expected ordering of the elements, and 
relying upon (or even expecting) one when sequentially processing the 
container's contents would be a programming error.

-- Marc A. Criley
-- www.mckae.com
-- DTraq - XPath In Ada - XML EZ Out --

Re: GCC 4.0 Ada.Containers Cursor danger.

[MMM]

I agree with you completely. The problem is that Matthew insist that
there is no need for plain
vanilla unordered set and/or plain vanilla unordered hash, they do not
even exist in computer science
and the basis of the Ada.Containers library should form Ordered_Set and
Ordered_Hash.

Re: GCC 4.0 Ada.Containers Cursor danger.

[Matthew Heaney]

MMM wrote:
> The problem is that Matthew insists that
> there is no need for a plain
> vanilla unordered set and/or plain vanilla unordered hash...

Because unordered sets and maps would have O(n) time complexity, which
makes them useless for real programs.  You might as well just use a
list.


> ...they do not
> even exist in computer science
> and the basis of the Ada.Containers library should form Ordered_Set and
> Ordered_Hash.

But ordered (sorted) sets and maps are the basis of the C++ container
library, and no one has complained so far...

Re: GCC 4.0 Ada.Containers Cursor danger.

[Georg Bauhaus]

Matthew Heaney wrote:
> 
> MMM wrote:
> 
>>The problem is that Matthew insists that
>>there is no need for a plain
>>vanilla unordered set and/or plain vanilla unordered hash...
> 
> 
> Because unordered sets and maps would have O(n) time complexity, which
> makes them useless for real programs.  You might as well just use a
> list.

My lists can find an element in O(log N). Depends on how
I implement a list. E.g. use a skip list for plain list
purposes. So is it a set then? No. But it happens to be
sorted (ordered by values, and maybe ordered by links).

I remember RBKD mentioning the As-If-Rule. With this rule in
mind, should user level container properties other than running time
expectations be defined in terms of O(f(n))?


-- Georg 

Re: GCC 4.0 Ada.Containers Cursor danger.

[Matthew Heaney]

Georg Bauhaus <bauhaus@futureapps.de> writes:

> My lists can find an element in O(log N). Depends on how I implement a
> list. E.g. use a skip list for plain list purposes.

Unfortunately, we have yet more name overloading.  When I refer to a
"list" container, I'm referring to the data structure comprising a
doubly-linked list of nodes, i.e. the container named
Doubly_Linked_Lists in the standard library.

As you point out, the list you have is really a "skip list."

Re: GCC 4.0 Ada.Containers Cursor danger.

[MMM]

> MMM wrote:
> > The problem is that Matthew insists that
> > there is no need for a plain
> > vanilla unordered set and/or plain vanilla unordered hash...
>
> Because unordered sets and maps would have O(n) time complexity, which
> makes them useless for real programs.  You might as well just use a
> list.
How did you get this estimate (O(n))? Lookup and insertion time is O(1)
for a hash implementation.
Check for example http://www.nist.gov/dads/HTML/hashtab.html

Re: GCC 4.0 Ada.Containers Cursor danger.

[Georg Bauhaus]

MMM wrote:

> How did you get this estimate (O(n))? Lookup and insertion time is O(1)
> for a hash implementation.
> Check for example http://www.nist.gov/dads/HTML/hashtab.html
> 

Mikhail, what do you think about
http://charles.tigris.org/source/browse/charles/src/ai302/a-cohase.ads?view=markup


Georg 

Re: GCC 4.0 Ada.Containers Cursor danger.

[Matthew Heaney]

MMM wrote:
> How did you get this estimate (O(n))? Lookup and insertion time is O(1)
> for a hash implementation.

Because you said "unordered," not "hashed."

Re: GCC 4.0 Ada.Containers Cursor danger.

[Randy Brukardt]

"MMM" <terekhov@emc.com> wrote in message
news:1121198441.766238.303580@o13g2000cwo.googlegroups.com...
> > Because unordered sets and maps would have O(n) time complexity, which
> > makes them useless for real programs.  You might as well just use a
> > list.
> How did you get this estimate (O(n))? Lookup and insertion time is O(1)
> for a hash implementation.
> Check for example http://www.nist.gov/dads/HTML/hashtab.html

Because a hash implementation is impossible for Ada unless you make it
visible to the user (by passing a hash function as a generic parameter). At
which point it is no longer unordered, it has turned into an "unspecified
ordered" container. As a practical matter, a hashed container is much harder
for the user to use than an ordered one. (An ordered one always will work
with reasonable time complexity; a hashed one is very sensitive to the
quality of the hash function. Writing a good hash function is an art, not a
science, and often the best answer is not obvious. I always run tests for
various hash functions on sample data, and that is not practical for the Q&D
uses that containers are best suited for.)

                   Randy.

Re: GCC 4.0 Ada.Containers Cursor danger.

[MMM]

Randy Brukardt wrote:
>
> Because a hash implementation is impossible for Ada unless you make it
> visible to the user (by passing a hash function as a generic parameter). At
> which point it is no longer unordered, it has turned into an "unspecified
That is not correct in general. That is correct if you explicitly
require order preserving hash function. See for example
http://www.nist.gov/dads/HTML/orderpresmph.html
In general order is implementation dependent and in some cases depends
on insertion order.
> ordered" container. As a practical matter, a hashed container is much harder
> for the user to use than an ordered one. (An ordered one always will work
Use an ordered one then - list or vector.
> with reasonable time complexity; a hashed one is very sensitive to the
That depends on the task at hand of course.
> quality of the hash function. Writing a good hash function is an art, not a
> science, and often the best answer is not obvious. I always run tests for
> various hash functions on sample data, and that is not practical for the Q&D
> uses that containers are best suited for.)
> 
>                    Randy.
> 
Mikhail

Re: GCC 4.0 Ada.Containers Cursor danger.

[Randy Brukardt]

"MMM" <terekhov@emc.com> wrote in message
news:1121228160.445437.171480@g47g2000cwa.googlegroups.com...
> Randy Brukardt wrote:
> >
...
> > ordered" container. As a practical matter, a hashed container is much
harder
> > for the user to use than an ordered one. (An ordered one always will
work
> Use an ordered one then - list or vector.

Those are O(N) containers, and obviously aren't going to be acceptable as a
replacement for an O(1) hashed_map or O(log N) ordered_map.

Obviously, you care more about mathematics than time performance. One of the
things we learned from listening to the Ada community about containers is
that time performance is *very* important. We had to specify it, or the
containers couldn't be used portably. (If code that works on a O(log N)
implementation is moved to an O(N) one, it may simply be too slow to be able
to be used.) Programming is about a mix of mathematics and practical
concerns, and a standard library has to balance those.

                     Randy.

Re: GCC 4.0 Ada.Containers Cursor danger.

[Simon Wright]

"Matthew Heaney" <mheaney@on2.com> writes:

> But ordered (sorted) sets and maps are the basis of the C++
> container library, and no one has complained so far...

The BCs have (only) hash-based sets & maps; if you iterate over them
you will get the elements back in an order that is not going to be a
lot of use to you. In fact it will look pretty random (depends on how
good your hash function is, of course).

Seems there's a fundamental problem with the words here. On one side,
folk like me think that 'ordered' and 'sorted' are very close in
meaning and 'unordered' and 'unsorted' ditto. On the other, folk like
you (and the ARG?) think that 'ordered' means something like 'having
an internal mechanism that can be relied on to support efficient
access'. We really don't see how this meaning can be supported!
Of course, we are all in favour of efficient implementations ...

Re: GCC 4.0 Ada.Containers Cursor danger.

[Randy Brukardt]

"MMM" <terekhov@emc.com> wrote in message
news:1121194262.036046.38230@g49g2000cwa.googlegroups.com...
> I agree with you completely. The problem is that Matthew insist that
> there is no need for plain
> vanilla unordered set and/or plain vanilla unordered hash, they do not
> even exist in computer science
> and the basis of the Ada.Containers library should form Ordered_Set and
> Ordered_Hash.

You seem to be confused about the purpose of the Ada.Containers library. It
is provide the most useful containers in the standard fashion. It's not to
be complete in any way. The names and design of containers was specifically
selected to make it easy to add other containers in the future, like
unordered sets and maps, bounded forms, protected forms, and the like.

One of the first things that we did was to discard pure unordered sets and
maps to reduce the size of the library. (It's now about the maximum size
that we could define.) The reason has that for virtually all needs, an
ordered set or map will suffice. The performance characteristics are
similar, the overhead is not significant in most applications, the
operations are a superset, so they are good enough. The reverse is clearly
not true (if you need ordering, it can't reasonably be simulated with an
unordered set or map).

Clearly, the library could have lots of other kinds of containers, but these
are going to be used much less often than the ones defined. We hope that a
secondary standard is created down the road for such containers;
Ada.Containers just provides a foundation and vision for future work. And I
hope that it focuses future work so that we have more similar components
rather than a plethora of different designs. It's not going to be the
perfect design for everyone (probably, in fact, no one will think it to be
perfect), but as a standard, it will always be available to Ada users.

                           Randy.

Re: GCC 4.0 Ada.Containers Cursor danger.

[Mikhail Terekhov]

Randy Brukardt wrote:
> "MMM" <terekhov@emc.com> wrote in message
> news:1121194262.036046.38230@g49g2000cwa.googlegroups.com...
> 
>>I agree with you completely. The problem is that Matthew insist that
>>there is no need for plain
>>vanilla unordered set and/or plain vanilla unordered hash, they do not
>>even exist in computer science
>>and the basis of the Ada.Containers library should form Ordered_Set and
>>Ordered_Hash.
> 
> 
> You seem to be confused about the purpose of the Ada.Containers library. It
> is provide the most useful containers in the standard fashion. It's not to
> be complete in any way. The names and design of containers was specifically
> selected to make it easy to add other containers in the future, like
> unordered sets and maps, bounded forms, protected forms, and the like.

That is not completely true. Current proposal explicitly oriented on
some special case - ordered containers. The point that sorted containers
are the most useful is questionable. There are a lot of applications
where order is not relevant.
> 
> One of the first things that we did was to discard pure unordered sets and
> maps to reduce the size of the library. (It's now about the maximum size
> that we could define.) The reason has that for virtually all needs, an
> ordered set or map will suffice. The performance characteristics are
> similar, the overhead is not significant in most applications, the
> operations are a superset, so they are good enough. The reverse is clearly
> not true (if you need ordering, it can't reasonably be simulated with an
> unordered set or map).

The problem is that ordered sets and maps are so special that when you
need them in your application it instantly brings a question - is this
application is really so special or is there some kind of deficiency in
design.

> 
> Clearly, the library could have lots of other kinds of containers, but these
> are going to be used much less often than the ones defined. We hope that a
> secondary standard is created down the road for such containers;

Of course the missing containers will never be used :)

> Ada.Containers just provides a foundation and vision for future work. And I

That is exactly why it concerns me! Foundation and vision based on some
biased concepts is not the best one. Ada was created to replace hundreds
of home grown special case languages with one unified, scientifically
well-founded language. Current Ada.Containers library overemphasize
significance of order and efficiency over clarity.

> hope that it focuses future work so that we have more similar components
> rather than a plethora of different designs. It's not going to be the
> perfect design for everyone (probably, in fact, no one will think it to be
> perfect), but as a standard, it will always be available to Ada users.
> 
Somewhat agree.

Mikhail

Re: GCC 4.0 Ada.Containers Cursor danger.

[Randy Brukardt]

"Mikhail Terekhov" <terekhov@emc.com> wrote in message
news:CkmBe.7957$rX7.329@fe06.lga...
...
> > Ada.Containers just provides a foundation and vision for future work.
And I
>
> That is exactly why it concerns me! Foundation and vision based on some
> biased concepts is not the best one. Ada was created to replace hundreds
> of home grown special case languages with one unified, scientifically
> well-founded language. Current Ada.Containers library overemphasize
> significance of order and efficiency over clarity.

Fair enough, but you're very much in the minority. Specifying the efficiency
was considered very important by most of the people involved with the
design. So your "unordered sets" would have to have an efficiency
requirement attached.

Now, there seem to be two practical implementations for an unordered set, as
a list or as a tree (like an ordered set). The list implementation has much
worse efficiency requirements than the ordered set for all of the complex
operations. So why would anyone use such a container? The only possible
reason is that they don't need the complex operations - in which case using
a list directly works just as well. And if we specify a tree implementation,
the unordered set is identical to the ordered set. So it's just duplication,
making it harder for users to choose the appropriate container.

You may not care about these issues, but we had to. And that is why we
choose the set of containers that we did.

                              Randy.

Re: GCC 4.0 Ada.Containers Cursor danger.

[Matthew Heaney]

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

> The problem with cursors is that they are quite difficult to get right
> for mutable containers. I tend to believe that cursor is a wrong
> abstraction there.

What does this mean?  "Difficult to get right" for whom?  What is a
"mutable" container?

I suggest you peruse the !examples secton of the AI:

<http://www.ada-auth.org/cgi-bin/cvsweb.cgi/AIs/AI-20302.TXT?rev=1.21>

You might also read my original API proposal, which has more !examples:

<http://home.earthlink.net/~matthewjheaney/charles/ai302.txt>

You should also peruse the actual code examples here:

<http://charles.tigris.org/source/browse/charles/src/ai302/examples/>

I just gave a tutorial in York a couple of weeks ago.  The teaching
material is here:

<http://charles.tigris.org/ai302_tutorial.ppt>
<http://charles.tigris.org/ai302_tutorial.pdf>

You might also want to pick up a book about the STL.

Perhaps if you tell us what problem you're trying to solve, then we can
show the best way to solve it using the container library.

-Matt

Re: GCC 4.0 Ada.Containers Cursor danger.

[Dmitriy Anisimkov]

<< No. A raw access type could never be checked, while a Cursor can
(and IMHO,
should) be checked for problems. >>

The checking of the cursors could take considerable size and
performance. It is why i propose to have cursors implementation without
cursors. Who need a cursors would pay by size and performance.

I'm sure that it is possibe to build project without cursors and with
the same performance as with "unchecked_cursors", I did one, and do not
"hash one element repeatable." and do not iterate over container by
repeatable search.

Re: GCC 4.0 Ada.Containers Cursor danger.

[Georg Bauhaus]

Dmitriy Anisimkov wrote:


> The checking of the cursors could take considerable size and
> performance. It is why i propose to have cursors implementation without
> cursors. Who need a cursors would pay by size and performance.

Could you give a real example, of some generality,
that shows why we don't need Cursors because Key-based
access is just as fast? Notice that it should be
of a general kind, see below.

> I'm sure that it is possibe to build project without cursors and with
> the same performance as with "unchecked_cursors", I did one, and do not
> "hash one element repeatable." and do not iterate over container by
> repeatable search.

But this argument, as it stands, ins't valid: You say that in a
special case you have been able to solve a problem
without repeated hasing and with one-time iteration for
searching. And based on this special case you say that
the general case can be solved in a similar way, without
loss in performance?

Re: GCC 4.0 Ada.Containers Cursor danger.

[Dmitriy Anisimkov]

My typo here.

<<The checking of the cursors could take considerable size and
performance. It is why i propose to have cursors  implementation
without
cursors. Who need a cursors would pay by size and performance. >>

have to be

<<The checking of the cursors could take considerable size and
performance. It is why i propose to have containers implementation
without
cursors. Who need a cursors would pay by size and performance. >>

Re: GCC 4.0 Ada.Containers Cursor danger.

[Matthew Heaney]

Dmitriy Anisimkov wrote:
>
> <<The checking of the cursors could take considerable size and
> performance. It is why i propose to have containers implementation
> without cursors. Who need a cursors would pay by size and
> performance.>>

A couple of points.  The ARG solicited proposals for a container API
over three years ago.  (Work on the design of the library began in
earnest at a workshop during the Ada-Europe 2002 meeting in Vienna, and
work on the library hasn't stopped since.)  If you had wanted a
container API sans cursors, then you should have submitted an API two
years ago.  It is pointless to be arguing for major changes to the
draft API on the eve of its standardization.

The other issue is that there is no cost in size or performance to have
cursors.  Implementations don't have to do anything special to
implement cursors.  Even without cursors, it's doubtful implementations
would change at all.

The only cost in size or performance is the overhead necessary to
detect dangling cursor references (and not, as you suggest above, to
merely provide cursors).

Re: GCC 4.0 Ada.Containers Cursor danger.

[Craig Carey]

On 7 Jul 2005 11:35:35 -0700, "Matthew Heaney" <mheaney@on2.com> wrote:

>
>
>Dmitriy Anisimkov wrote:
>>
>> <<The checking of the cursors could take considerable size and
>> performance. It is why i propose to have containers implementation
>> without cursors. Who need a cursors would pay by size and
>> performance.>>
>
>A couple of points.  The ARG solicited proposals for a container API
>over three years ago.

The ARG is composed of namable individuals.

Certainly not Mr Brukardt's ARG, since he anonymizes (so freely) the
names of men like Tucker Taft, when voting at ARG meetings.

The reward of anonymity is all part of the provided view. There was
a global resource shortage, e.g. of the mere names of American individuals
who are personally devoted to the success of (under the curiously
effective 50% idealism that Mr Brukardt gives us a view of).

Both Taft and Leroy created the total secrecy of AG discussions in about
October 2002. Suppose Brukardt personally desired to maintain the hold
over the ARG. He could create a rubbishy containers proposal using you
as a pawn, and the old IBM/360 seemed to get the correct answers, so
it would all adore secrecy.

Also I got an all-false e-mail from Tucker Taft dated "Tue, 05 Apr 2005
 22:15:23 -0400", that explained the secrecy of having all
discussions at the covert arg@ada-auth.org mailing list, was absent,
which is extremely untrue. I presented evidence here by ranking the
ARG members by their secretiveness.

Mr Brukardt is very more due attention than Mr Taft. In fact, Taft didn't
seem to be lying but more imagining that any story goes so long as it
can't be shot up or contradicted.

AI-302 is a pretext, a vessel named 'wrong purpose' that carries the
world to the shores of the Ada language.

Who solicited proposals?; or better still, what was the precise purpose
the Brukardtian anonymizing of the ARG.

I ask my readers to check for the unasked for and inescapable awarding of
anonymity (or less reliably, secrecy instead). It suggests an abuse of
power. Ada is for powerful people.

...

>The other issue is that there is no cost in size or performance to have
>cursors.  Implementations don't have to do anything special to
>implement cursors.  Even without cursors, it's doubtful implementations
>would change at all.
>
>The only cost in size or performance is the overhead necessary to
>detect dangling cursor references (and not, as you suggest above, to
>merely provide cursors).

Also check for strange views.
Maybe Matt render more services of value to the hierarchy (oh, that
view was missing: a little mistake but beginners would learn...)


Craig Carey
The old ranking of names by secretiveness: http://www.ijs.co.nz/ada_95.htm

Re: GCC 4.0 Ada.Containers Cursor danger.

[Dmitriy Anisimkov]

My typo here.

<<The checking of the cursors could take considerable size and
performance. It is why i propose to have *cursors*  implementation
without
cursors. Who need a cursors would pay by size and performance. >>

have to be

<<The checking of the cursors could take considerable size and
performance. It is why i propose to have *containers* implementation
without
cursors. Who need a cursors would pay by size and performance. >>

Re: GCC 4.0 Ada.Containers Cursor danger.

[Randy Brukardt]

"Dmitriy Anisimkov" <anisimkov@yahoo.com> wrote in message
news:1120740766.343393.168420@g14g2000cwa.googlegroups.com...
> << No. A raw access type could never be checked, while a Cursor can
> (and IMHO,
> should) be checked for problems. >>
>
> The checking of the cursors could take considerable size and
> performance.

Only if you insist upon perfect checking. If you are willing to miss 0.01%
of the errors, the cost is quite small. Note that to allow a 99.9% checking
system, we have to officially say that access to invalid cursors is
erroneous.

If you had used the RRS implementation of cursors, you would have gotten
Program_Error when you used the bad cursor. End of issue. I think that such
checking should be part of every implementation of the containers. (Perhaps
a way to turn off checking needs to be provided as well, but I'm unconvinced
that the performance loss from the checking would matter to any real
applications.)

                      Randy.

Re: GCC 4.0 Ada.Containers Cursor danger.

[Dmitriy Anisimkov]

<<
> The checking of the cursors could take considerable size and
> performance.

Only if you insist upon perfect checking.
>>

Me, not. 99.9 would be enought. If you sure thar cursors would be
checked in the coming Ada 200X, i'm quiet. Are you have an authority to
force Ada.Containers checking in Ada 200X ?

<<If you had used the RRS implementation of cursors,>>
Where could I see it ? Is it open source ?

Re: GCC 4.0 Ada.Containers Cursor danger.

[Matthew Heaney]

"Dmitriy Anisimkov" <anisimkov@yahoo.com> writes:

> Me, not. 99.9 would be enought. If you sure thar cursors would be
> checked in the coming Ada 200X, i'm quiet.

I'm working on the lists right now, so I modified your original example
as follows:

procedure Test_Dangling is
   package Integer_Lists is
      new Ada.Containers.Doubly_Linked_Lists (Integer);
   use Integer_Lists;

   L : List;
   C, C2 : Cursor;
begin
   L.Append (1);
   L.Insert (No_Element, 2, C);
   L.Append (3);

   C2 := L.Find (2);
   L.Delete (C2);

   Replace_Element (C, By => -2);  -- dangling reference
end;

I added some logic to detect dangling cursors, and when I run the
program above I get this output:

raised SYSTEM.ASSERTIONS.ASSERT_FAILURE : bad cursor in Replace_Element

The extra check is inside a pragma Assert, so you can choose to enable
it or not.

To make this work, I set the Next and Prev pointers of the internal
storage node to point to the node itself, just before the node is
deallocated.  In the GCC implementation, a linked list node never points
to itself, so I know that if a node pointer of a node has the node as
its value, then something must be wrong.

For the indefinite list, the element is designated by a pointer, which
can never be null.  When a node is deallocated, I set the element
pointer to null (that's sort of true anyway, since I must also
deallocate the element), and then check for a null element pointer
during cursor manipulation.

-Matt

Re: GCC 4.0 Ada.Containers Cursor danger.

[Randy Brukardt]

"Dmitriy Anisimkov" <anisimkov@yahoo.com> wrote in message
news:1120789712.389559.11090@g49g2000cwa.googlegroups.com...
> <<
> > The checking of the cursors could take considerable size and
> > performance.
>
> Only if you insist upon perfect checking.
> >>
>
> Me, not. 99.9 would be enought. If you sure thar cursors would be
> checked in the coming Ada 200X, i'm quiet. Are you have an authority to
> force Ada.Containers checking in Ada 200X ?

I'm afraid its a quality-of-implementation issue, and that will require
pressure from user like you on vendors. Note that Matt is trying to improve
the checking in the "reference" containers implementation, so that should
help.

> <<If you had used the RRS implementation of cursors,>>
> Where could I see it ?

Unfortunately, its mostly in my head at this point. I have this language
standard to finish, you see, and its already late... (In case you don't
know, I'm the editor of upcoming Amendment, meaning I'm the one that takes
all of the scattered bits and puts them together into a hopefully coherent
language standard.)

> Is it open source ?

Not at this point. It's part of the Janus/Ada compiler, which is not open
source today. Maybe at some point in the future.

                      Randy Brukardt

Re: GCC 4.0 Ada.Containers Cursor danger.

[Craig Carey]

   The Lion, the Wolf, and the Fox

   A Lion, sickly, weak, and full of years,
   Desired a remedy against old age
   (_Impossible's_ a word no monarch hears
     Without directly flying [into] a rage).
   He sent for doctros - men of draughts and pills;
     From far and near, obedient to the call,
   Came makers-up of recipes and pills:
     The Fox alone declined to come at all.
   At court the Wolf malignantly referred
     To Reynard's absence, whereupon the King --
   Whose anger was aroused at what he heard --
     Decided on a rather cruel thing.
   He sent a force to smoke sly Reynaud out,
     And bring him, willy nilly. When he came,
   The Fox could scarcely entertain a doubt
     As to whose toungue had put him thus to shame.
   "I greatly fear, your Majesty," said he,
     "You think me rude; you wrong me, if you do:
   For I was on a pilgramage, you see,
     And went to offer up my vows for _you_.
   I scarcely need inform you I have met
     Expert physicians whilst I was away,
   And hope to cure you of your sickness yet,
     Which comes from coldness of the blood, they say
   You must, sire, skin a Wolf, and wrap the skin
     About you close, to get the body warmed;
   And when the heat has kindled up within
     The fires of life again, the cure's performed.
   Our friend. I'm sure, will take immense delight
     In lending you his coat; so take it, sire."
   The Lion supped on the Wolf that night,
     And made the skin a part of his attire.
   Courtiers, discretion is your safest plan:
     Malice is sure to find its source again;
   And, while you do yourself what good you can,
     Reflect that slander others is in vain.


   [La Fontaine (1621-...), "popular with everyone in
      Paris, except [Louis XIV]".
    Quoted from the Thornury's book of La Fontaine's
      fables of Aesop).]


French may need a reminding about monarchism...


On Sat, 9 Jul 2005 20:51:44 -0500, "Randy Brukardt" wrote:
>On Sat, 09 Jul 2005 14:20:50 GMT, Matthew Heaney wrote:
>>On 7 Jul 2005 19:28:32 -0700, "Dmitriy Anisimkov" <anisimkov@yahoo.com> wrote:
>> >> The checking of the cursors could take considerable size and
>> >> performance.
>> >
>> >Only if you insist upon perfect checking.
>> >>>
>> >
>> >Me, not. 99.9 would be enought. If you sure thar cursors would be
>> >checked in the coming Ada 200X, i'm quiet. Are you have an authority to
>> >force Ada.Containers checking in Ada 200X ?
>
>I'm afraid its a quality-of-implementation issue, and that will require
>pressure from user like you on vendors. Note that Matt is trying to improve
>the checking in the "reference" containers implementation, so that should
>help.
>
>> ><<If you had used the RRS implementation of cursors,>>
>> >Where could I see it ? Is it open source ?
>
>Unfortunately, its mostly in my head at this point. I have this language
>standard to finish, you see, and its already late... (In case you don't



>Not at this point. It's part of the Janus/Ada compiler,

                       

>which is not open source today. Maybe at some point in the future.

Another lie.

>
>                      Randy Brukardt
>
>

Re: GCC 4.0 Ada.Containers Cursor danger.

[Craig Carey]

   The Sculptor and the Statue of Jupiter

    A Block of marble shone so white,
    A Sculptor bought it, and, that night,
    Said, "Now, my chisel, let's decree:
    God, tank, or table, shall it be?

   "We'll have a god - the dream I clasp;
    His hand a thunderbolt shall grasp.
    Tremble ye monarchs, ere it's hurled!
    Behold the master of the world!"

    So well the patient workman wrought
    In stone the vision of his thought,
    ...

(Ibid)

On Sun, 10 Jul 2005 17:46:37 +1200, Craig Carey wrote:

>   The Lion, the Wolf, and the Fox
>
...
>     Reflect that slander others is in vain.
>

A correction is noted: The word "slander" was is wrong.
It can be corrected with use of the word, "slandering".

>   [La Fontaine (1621-...), "popular with everyone in
       1621-1695.


Craig Carey
research@ijs.co.nz, Auckland

OT: Greg and Colin? (was Re: GCC 4.0 Ada.Containers Cursor danger.)

[Marc A. Criley]

Craig Carey wrote in various postings:
> 
>    The Lion, the Wolf, and the Fox
> 
> 
> Another lie.
> 
 >   The Sculptor and the Statue of Jupiter
 >
 >
 > AI-302 is a pretext, a vessel named 'wrong purpose' that carries the
 > world to the shores of the Ada language.
 >
 > The reward of anonymity is all part of the provided view.
 >
 > Also I got an all-false e-mail from...
 >
 > I ask my readers to check for the unasked for and inescapable awarding
 > of anonymity (or less reliably, secrecy instead). It suggests an abuse
 > of power. Ada is for powerful people.

Mr Aharonian?  Colin E. James III?  Party of three, your table's ready.

Re: GCC 4.0 Ada.Containers Cursor danger.

[Randy Brukardt]

"Dmitriy Anisimkov" <anisimkov@yahoo.com> wrote in message
news:1120583470.429264.325450@g43g2000cwa.googlegroups.com...
> I know that code have an error. I'm saying that the errors like this is
> easy to create, and hard to find. Neither compiler not runtime check
> for this errors.

Then, you're using the wrong implementation of Containers. IMHO, all
implementations of containers should at least do minimal checks to detect
the obvious cases like the one in your example.

At this point, Containers implementations are immature, so it's really
incorrect to draw any conclusions from them. And, Matt seems to have a
strong aversion to checks of any kind. Every check that we mandated in the
containers library was over his objections. So I don't find it surprising
that his implementation of the containers doesn't include much checking.

This state isn't surprising; we're still polishing the words and the
specifications of the containers libraries. So no one is putting a lot of
effort into implementations yet. It's unfortunate that the initial
implementation has minimal checking, but I expect other implementations to
be available that have more checking.

One of the advantages of GNAT is that it is relatively easy to replace parts
of the provided libraries. So using a debug Containers library instead of a
mostly unchecked one is something that should be easy to do.

                             Randy.

Re: GCC 4.0 Ada.Containers Cursor danger.

[Matthew Heaney]

"Randy Brukardt" <randy@rrsoftware.com> writes:

> At this point, Containers implementations are immature, so it's really
> incorrect to draw any conclusions from them. And, Matt seems to have a
> strong aversion to checks of any kind. Every check that we mandated in the
> containers library was over his objections. So I don't find it surprising
> that his implementation of the containers doesn't include much checking.

I had originally included checks that didn't require any extra storage
overhead, controlled by the use of pragma Assert.  However, it turns out
that even if you compile with assertion checks on, whether assertions
are enabled is decided at the time of compilation of the generic.  And
in the GNAT runtime, all checks (including constraint checks -- gulp!
I'm still fixing that...) are turned off.  I wanted additional checks to
be controlled by the user (at the point of instantiation), but I still
haven't figured out how to do that.

To make things absolutely bullet-proof, I think you'd need at least a
per-element reference count.  (That, or have the container maintain a
list of extant cursors, which you would then have to search.)  If you
attempt to delete a node for which the ref count is greater than 0, then
you could raise an exception.  (This might actually produce a false
positive, since the real error is attempting to dereference the cursor,
not merely delete the node to which it is bound.  But to solve that,
you'd have to move the node onto a free list, and during the dereference
check to see whether the node is on the free list or not.)

So yes, there are some extra checks that can be performed, but I still
prefer to let the user control whether they're enabled.

You are also correct about immaturity of implementations.  I'm still
developing a set of unit tests for the containers.  (In fact, I found a
bug this morning in the Merge operation of the list container.)  So
there's still lots of work to do, especially with the post-York API
coming down the pipe...

-Matt

Re: GCC 4.0 Ada.Containers Cursor danger.

[Randy Brukardt]

"Matthew Heaney" <matthewjheaney@earthlink.net> wrote in message
news:uslyrv50w.fsf@earthlink.net...
...
> I had originally included checks that didn't require any extra storage
> overhead, controlled by the use of pragma Assert.  However, it turns out
> that even if you compile with assertion checks on, whether assertions
> are enabled is decided at the time of compilation of the generic.  And
> in the GNAT runtime, all checks (including constraint checks -- gulp!
> I'm still fixing that...) are turned off.  I wanted additional checks to
> be controlled by the user (at the point of instantiation), but I still
> haven't figured out how to do that.

Yuck. I agree that being able to control the checking somehow would be a
good thing. That probably will require some cooperation with the compiler
vendor, so it is up to the users to put the pressure on the vendors.

Using Assert to do that seems like a good idea. (But it wouldn't have any
effect on our code-shared implementation of generics, for the obvious
reason.)

> To make things absolutely bullet-proof, I think you'd need at least a
> per-element reference count.  (That, or have the container maintain a
> list of extant cursors, which you would then have to search.)  If you
> attempt to delete a node for which the ref count is greater than 0, then
> you could raise an exception.  (This might actually produce a false
> positive, since the real error is attempting to dereference the cursor,
> not merely delete the node to which it is bound.  But to solve that,
> you'd have to move the node onto a free list, and during the dereference
> check to see whether the node is on the free list or not.)

Yes, and I agree that is too much overhead. I'm planning to use a serial
number scheme. It won't detect every possible error (if the memory for the
element or container as a whole is reused, there would be a very small
chance that it would fail to detect an error), but it would catch the vast
majority of them.

> So yes, there are some extra checks that can be performed, but I still
> prefer to let the user control whether they're enabled.
>
> You are also correct about immaturity of implementations.  I'm still
> developing a set of unit tests for the containers.  (In fact, I found a
> bug this morning in the Merge operation of the list container.)  So
> there's still lots of work to do, especially with the post-York API
> coming down the pipe...

That's one of the things (other than pure lack of time) that's kept me from
starting an implementation. Some ACATS-style tests would be very welcome.

                           Randy.

Re: GCC 4.0 Ada.Containers Cursor danger.

[Jeffrey Carter]

Randy Brukardt wrote:
> 
> Yes, and I agree that is too much overhead. I'm planning to use a serial
> number scheme. It won't detect every possible error (if the memory for the
> element or container as a whole is reused, there would be a very small
> chance that it would fail to detect an error), but it would catch the vast
> majority of them.

Is that like the scheme used by the PragmARC lists? Each list has a 
unique ID, each node contains the ID of the list it's in, and each 
Position has the ID of the list it's a Position for. All three IDs must 
match for an operation to be valid. On deletion, the ID in the node and 
in the Position are made invalid. It won't catch everything, but it 
catches most errors.

-- 
Jeff Carter
"Crucifixion's a doddle."
Monty Python's Life of Brian
82

Re: GCC 4.0 Ada.Containers Cursor danger.

[Randy Brukardt]

"Jeffrey Carter" <spam@spam.com> wrote in message
news:3goze.305$dU3.190@newsread2.news.pas.earthlink.net...
> Randy Brukardt wrote:
> >
> > Yes, and I agree that is too much overhead. I'm planning to use a serial
> > number scheme. It won't detect every possible error (if the memory for
the
> > element or container as a whole is reused, there would be a very small
> > chance that it would fail to detect an error), but it would catch the
vast
> > majority of them.
>
> Is that like the scheme used by the PragmARC lists? Each list has a
> unique ID, each node contains the ID of the list it's in, and each
> Position has the ID of the list it's a Position for. All three IDs must
> match for an operation to be valid. On deletion, the ID in the node and
> in the Position are made invalid. It won't catch everything, but it
> catches most errors.

Sounds like it. Hope it isn't patented. :-)

                       Randy.

Re: GCC 4.0 Ada.Containers Cursor danger.

[Jeffrey Carter]

Randy Brukardt wrote:
> "Jeffrey Carter" <spam@spam.com> wrote in message
> news:3goze.305$dU3.190@newsread2.news.pas.earthlink.net...
> 
>>Is that like the scheme used by the PragmARC lists? Each list has a
>>unique ID, each node contains the ID of the list it's in, and each
>>Position has the ID of the list it's a Position for. All three IDs must
>>match for an operation to be valid. On deletion, the ID in the node and
>>in the Position are made invalid. It won't catch everything, but it
>>catches most errors.
> 
> Sounds like it. Hope it isn't patented. :-)

Well, of course it is. It's not like it's an obvious idea that anyone 
could come up with. Besides, if it were obvious, the Patent Office would 
never grant a patent for it, right?

:)

Don't worry. I'm sure PragmAda grant RR a license to its non-patent for 
very reasonable terms.

-- 
Jeff Carter
"Mr. President, we must not allow a mine-shaft gap!"
Dr. Strangelove
33

Re: GCC 4.0 Ada.Containers Cursor danger.

[Randy Brukardt]

"Matthew Heaney" <matthewjheaney@earthlink.net> wrote in message
news:uslyrv50w.fsf@earthlink.net...
> To make things absolutely bullet-proof, I think you'd need at least a
> per-element reference count.  (That, or have the container maintain a
> list of extant cursors, which you would then have to search.)  If you
> attempt to delete a node for which the ref count is greater than 0, then
> you could raise an exception.  (This might actually produce a false
> positive, since the real error is attempting to dereference the cursor,
> not merely delete the node to which it is bound.  But to solve that,
> you'd have to move the node onto a free list, and during the dereference
> check to see whether the node is on the free list or not.)

It just struck me that this implementation would be wrong. The execution
doesn't become erroneous until the programmer uses the dangling cursor.
Raising some exception before the execution becomes erroneous wouldn't be
right.

I think that a scheme where the cursors were all linked to the container (or
element) would be needed to be completely bullet-proof (and correct). Then
the cursors could be marked as deleted when the element deleted or the
container is finalized. But that could have a lot of overhead.

                       Randy.

Re: GCC 4.0 Ada.Containers Cursor danger.

[Matthew Heaney]

"Dmitriy Anisimkov" <anisimkov@yahoo.com> writes:

> IMHO the cursors in the Ada.Containers implemented in GCC 4.0
> dangerouse like pointers in C/C++.
> 
> Look at the code below.

Here is a simplified version of your example:

with Ada.Containers.Indefinite_Hashed_Maps;  use Ada.Containers;
with Ada.Strings.Hash;                       use Ada.Strings;

procedure Test_HM is
   package Map_Types is
      new Indefinite_Hashed_Maps (String, Integer, Hash, "=");
   use Map_Types;

   M     : Map;
   C, C2 : Cursor;
   B     : Boolean;

begin

   M.Insert ("one", 1);

   M.Insert ("two", 2, C, B);
   pragma Assert (B);

   M.Insert ("three", 3);

   pragma Assert (Has_Element (C));
   pragma Assert (Key (C) = "two");
   pragma Assert (Element (C) = 2);

   C2 := M.Find ("two");
   pragma Assert (Has_Element (C2));
   pragma Assert (Key (C) = "two");
   pragma Assert (Element (C) = 2);

   M.Delete (C2);
   pragma Assert (not Has_Element (C2));
   pragma Assert (not M.Contains ("two"));

   Replace_Element (C, -2);  -- dangling cursor

end Test_HM;


When I compile it as follows (on WinXP):

gnatmake -gnata -g -gnat05 test_hm

and then run it, I get this output:

raised SYSTEM.ASSERTIONS.ASSERT_FAILURE : bad cursor in Replace_Element


Does this behavior adequately satisfy your needs?

Re: GCC 4.0 Ada.Containers Cursor danger.

[Dmitriy Anisimkov]

   M.Delete (C2);
   pragma Assert (not Has_Element (C2));
   pragma Assert (not M.Contains ("two"));
--  double hash overhead.

   Replace_Element (C, -2);  -- dangling cursor

<< Does this behavior adequately satisfy your needs? >>

No, this checking is too overhead. And my need is not in the cursors
aria.

I would use the

   procedure Include
     (Container : in out Map;
      Key       : Key_Type;
      New_Item  : Element_Type);

in this cases. (this sample was based in AI302 without Include
routine.)
But I need some more routines without cursors. For example

   procedure Iterate
     (Container : Map;
      Process   : not null access procedure (Key : Key_Type; Element :
Element_Type; Stop : out Boolean));

analog of

   procedure Iterate
     (Container : Map;
      Process   : not null access procedure (Position : Cursor));

but without cursor.
And for every access routine with cursor there should be analog without
cursors IMHO.

Re: GCC 4.0 Ada.Containers Cursor danger.

[Matthew Heaney]

"Dmitriy Anisimkov" <anisimkov@yahoo.com> writes:

> << Does this behavior adequately satisfy your needs? >>
> 
> No, this checking is too much overhead. 

Too much overhead, compared to what?


> And my need is not in the cursors area.

Then don't use them...

 
> I would use the
> 
>    procedure Include
>      (Container : in out Map;
>       Key       : Key_Type;
>       New_Item  : Element_Type);
> 
> in this cases. (this sample was based in AI302 without Include
> routine.)

Use Include instead of ... what?

This is not equivalent to Replace_Element, for example, since Include
must look up the key.  And if the key is already in the map, then
Include replaces both the key and the element.



> But I need some more routines without cursors. For example
> 
>    procedure Iterate
>      (Container : Map;
>       Process   : not null access 
>         procedure (Key : Key_Type; 
>                    Element : Element_Type; 
>                    Stop : out Boolean));
> 
> analog of
> 
>    procedure Iterate
>      (Container : Map;
>       Process   : not null access procedure (Position : Cursor));
>
> but without cursor.


The reason that Iterate passes a cursor is to avoid a combinatorial
explosion of parameters (e.g. your example doesn't provide a way to
modify the element).

The passive iterator is designed for the common case, which is to visit
every item in the container.  Your example requires the Process
procedure to pass an additional Stop parameter, to indicate termination.
You can achieve the same effect using a cursor.

(It also incorrectly passes the Stop parameter using in-mode, instead of
in-out mode, thus forcing the actual subprogram to set the Stop
parameter each time, if even you don't want to Stop.)

I have showed in a previous post how to implement your example using the
existing primitives.


> And for every access routine with cursor there should be analog without
> cursors IMHO.

That's fine, but you should have stated your opinion 2 years ago, by
submitting your own library design proposal.

Re: GCC 4.0 Ada.Containers Cursor danger.

[Dmitriy Anisimkov]

<<
>No, this checking is too much overhead.
Too much overhead, compared to what?
>>

Ok. I thought that you told about checking in
   pragma Assert (not Has_Element (C2));
   pragma Assert (not M.Contains ("two"));

if you told about new checking inside of

   Replace_Element (C, -2);  -- dangling cursor

it is not "too much".

<< This is a false analogy, since the name of the operations are
To_Pointer
and To_Address.  Nary an "unchecked" in site... >>

Isn't To_Pointer equivalent to Unchecked_Conversion from Address to
Access ?

Re: GCC 4.0 Ada.Containers Cursor danger.

[Matthew Heaney]

"Dmitriy Anisimkov" <anisimkov@yahoo.com> writes:

> <<
> >No, this checking is too much overhead.
> Too much overhead, compared to what?
> >>
> 
> Ok. I thought that you told about checking in
>    pragma Assert (not Has_Element (C2));
>    pragma Assert (not M.Contains ("two"));

No, I was referring to the checking in the implementation of the map
container itself.  The checks above are part of the example, and exist
for informational purposes only.


> if you told about new checking inside of
> 
>    Replace_Element (C, -2);  -- dangling cursor
> 
> it is not "too much".

Yes, that's the checking to which I was referring.  I'm glad to hear you
don't think it's too much.  (However, to check for dangling cursors,
you'll have to enable assertion checks when you compile.)

Did you try compiling your original example with assertions enabled?
What happens when you do?  (I have been modifying the GCC sources to be
more thorough in my use of assertion checks and cursor vetting, but you
still have an older version.  If you're having an emergency, I can
update the sources at tigris too, so you can have the improved checking
right away.)


> << This is a false analogy, since the name of the operations are
> To_Pointer
> and To_Address.  Nary an "unchecked" in site... >>
> 
> Isn't To_Pointer equivalent to Unchecked_Conversion from Address to
> Access ?

Yes, but since these conversions are provided by the language, they're
not outside the type system anymore, and hence don't require any scary
"unchecked" names.  "Unchecked" conversions imply that you're leaving
the type system, and that's never the case for the containers.

Re: GCC 4.0 Ada.Containers Cursor danger.

[Dmitriy Anisimkov]

<<Did you try compiling your original example with assertions enabled?
What happens when you do?>>

I did not, but i believe it is checked.

<< If you're having an emergency, >>

Not at all. I care about comming Ada standard.

Re: GCC 4.0 Ada.Containers Cursor danger.

[Matthew Heaney]

"Dmitriy Anisimkov" <anisimkov@yahoo.com> writes:

> << If you're having an emergency, >>
> 
> Not at all. I care about coming Ada standard.

Then you need to be actively involved in the review of the standard,
otherwise your opinions don't count.  Randy posts the revised drafts as
they become available at ada-auth, so you should review them and then
post your comments on ada-comment.  CLA is not the proper forum for
debating the finer points of drafts of the standard container library.

Re: GCC 4.0 Ada.Containers Cursor danger.

[Dmitriy Anisimkov]

<<(It also incorrectly passes the Stop parameter using in-mode,
>>

It was in "out" mode in my example

   procedure Iterate
     (Container : Map;
      Process   : not null access procedure (Key : Key_Type; Element :
Element_Type; Stop : out Boolean));

<< instead of
in-out mode, thus forcing the actual subprogram to set the Stop
parameter each time, if even you don't want to Stop.)>>

We could have one more Iterate procedure without Stop parameter in
Process procedure.

<<You can achieve the same effect using a cursor.>>

I understand that using of cursors allows to reduce the number of
routines in the Ada.Cursors. But i'm sure that using a much more
routines without cursors would reduce a potential errors at design
time. Using the *checking* cursors would move error detection into the
run time.
So, I know that i could build whatever i need on top of routines with a
cursors.
But I think that Ada standard should try to move design process into
the way where the errors would be avoided at the design time.

Re: GCC 4.0 Ada.Containers Cursor danger.

[Dmitriy Anisimkov]

<<I understand that using of cursors allows to reduce the number of
routines in the Ada.Cursors.>>

typo - should be Ada.Containers.

Re: GCC 4.0 Ada.Containers Cursor danger.

[Matthew Heaney]

"Dmitriy Anisimkov" <anisimkov@yahoo.com> writes:

> I understand that using of cursors allows to reduce the number of
> routines in the Ada.Cursors. But i'm sure that using a much more
> routines without cursors would reduce a potential errors at design
> time.

You must adduce evidence for this claim.  Otherwise we're just debating
religion.


> Using the *checking* cursors would move error detection into the run
> time.

Yes, but in your original example, you were complaining about a run-time
error.  That error is detectable.


> So, I know that i could build whatever i need on top of routines with a
> cursors.

Yes, but that's the point.  A general-purpose library must be flexible
enough to meet the needs of disparate applications.  If you want the
library to be strictly key-based (sans cursors), then it's far less
flexible, and no longer a general-purpose library.


> But I think that Ada standard should try to move design process into
> the way where the errors would be avoided at the design time.

You want to legislate behavior for everyone.  This is wrong.  You should
only be concerned with your own behavior.

If you want only key-based operations, then you can just write a layered
abstraction once, and you can use it everywhere.

One way is:

generic
   type Key_Type (<>) is limited private;
   type Element_Type (<>) is limited private;
   type Container_Type (<>) is limited private;
   type Cursor_Type is private;
   with function First (C : CT) return Cursor_Type is <>;
   with procedure Next (C : in out Cursor_Type) is <>;
   ...
package Generic_Map_Operations is 

   generic
      with procedure Process 
        (K : KT; E : ET; Stop : in out Boolean) is <>;
   procedure Generic_Iteration
     (Container : Container_Type);

...
end Generic_Map_Operations;

Re: GCC 4.0 Ada.Containers Cursor danger.

[Mikhail Terekhov]

Matthew Heaney wrote:
> "Dmitriy Anisimkov" <anisimkov@yahoo.com> writes:
> 
> 
>>I understand that using of cursors allows to reduce the number of
>>routines in the Ada.Cursors. But i'm sure that using a much more
>>routines without cursors would reduce a potential errors at design
>>time.
> 
> 
> You must adduce evidence for this claim.  Otherwise we're just debating
> religion.
> 

The evidence is pretty obvious. Ada.Containers contains a set of 
abstractions some of which are very specialized (ordered sets and 
hashes), mix abstraction and implementation (hashed sets) and mix 
everything in one place (cursors; they even replace container 
abstraction itself in a number of operation). May be the implementation 
of these abstractions is perfect, but using such a "non rectangular 
briks" to design a program will be prone to abstractions misuse and 
hence to design errors.

> 
> 
>>Using the *checking* cursors would move error detection into the run
>>time.
> 
> 
> Yes, but in your original example, you were complaining about a run-time
> error.  That error is detectable.
> 

Not using this special case abstraction (Cursor) in general part of the 
library would exclude this kind of errors completely.

> 
> 
>>So, I know that i could build whatever i need on top of routines with a
>>cursors.
> 
> 
> Yes, but that's the point.  A general-purpose library must be flexible
> enough to meet the needs of disparate applications.  If you want the

Great, to satisfy a common need, users should build a layer on top of 
such a "general library".

> library to be strictly key-based (sans cursors), then it's far less
> flexible, and no longer a general-purpose library.

That depends on the definition of "general-purpose" of course.

>>But I think that Ada standard should try to move design process into
>>the way where the errors would be avoided at the design time.

Exactly.

> 
> You want to legislate behavior for everyone.  This is wrong.  You should
> only be concerned with your own behavior.

I unerstand this as "shut up and go away". This is not polite. Try to 
apply the above three sentences to yourself.

> 
> If you want only key-based operations, then you can just write a layered
> abstraction once, and you can use it everywhere.
> 
That means do it youself. So much for a "generic" library - if you need 
some generic case - do it yourself.

Re: GCC 4.0 Ada.Containers Cursor danger.

[Matthew Heaney]

Mikhail Terekhov <terekhov@emc.com> writes:

> > Yes, but in your original example, you were complaining about a
> > run-time error.  That error is detectable.
> 
> Not using this special case abstraction (Cursor) in general part of
> the library would exclude this kind of errors completely.

But if you recall, the original example used Replace_Element to replace
the element designated by a (dangling) cursor.  The OP played with fire
and he got burned.  If you want to produce the same effect sans cursors,
then just use Include (which is key-based).


> Great, to satisfy a common need, users should build a layer on top of
> such a "general library".

The common need is satisfied by other, key-based operations such as
Include and Replace.



> > You want to legislate behavior for everyone.  This is wrong.  You
> > should only be concerned with your own behavior.
> 
> I unerstand this as "shut up and go away". This is not polite. Try to
> apply the above three sentences to yourself.

It simply reflects the realities of library design.  The designer must
strike a balance among flexibility, efficiency, and safety, and those
goals are often in conflict.


> > If you want only key-based operations, then you can just write a
> > layered abstraction once, and you can use it everywhere.
> >
> That means do it youself. So much for a "generic" library - if you need
> some generic case - do it yourself.

Again, the library is optimized for flexibility and efficiency.  You're
advocating an interface that is less general, less flexible, and less
efficient, so you have the burden of proving why that's better.  Saying
that "cursors don't make sense" is not a very convincing argument.

Re: GCC 4.0 Ada.Containers Cursor danger.

[Pascal Obry]

Matthew,

> But if you recall, the original example used Replace_Element to replace
> the element designated by a (dangling) cursor.  The OP played with fire
> and he got burned.  If you want to produce the same effect sans cursors,
> then just use Include (which is key-based).

I'm not an Ada beginner and the OP (Dmitriy Anisimkov) did found this problem
in AWS. I did this wrong when I moved AWS from another set of containers to
Ada.Containers.

What does this mean ?

That such problem could occur again. We must ensure that at least the
documentation is clear (very clear) about the semantics here.

I'm not saying that Ada.Containers or Cursor are bad, I already like this
library much (this is not the case for Dmitriy :), what I'm saying is that
this problem could happen to others and it is dangerous enough for us to take
great care about it :)

Just my 2 cents!

Pascal.

-- 

--|------------------------------------------------------
--| Pascal Obry                           Team-Ada Member
--| 45, rue Gabriel Peri - 78114 Magny Les Hameaux FRANCE
--|------------------------------------------------------
--|              http://www.obry.net
--| "The best way to travel is by means of imagination"
--|
--| gpg --keyserver wwwkeys.pgp.net --recv-key C1082595

Re: GCC 4.0 Ada.Containers Cursor danger.

[Matthew Heaney]

Pascal Obry wrote:
>
> That such problem could occur again. We must ensure that at least the
> documentation is clear (very clear) about the semantics here.

Cursors confer no greater safety than you get with named access types.
If this isn't clear, then yes, we need to better job of advertising
this feature.

In general, don't keep cursors around unless you have a good reason.
And if you have a key (this is a map, say), then you can always use
key-based operations instead of cursor-based ones.  (In Dmitriy's case,
he should have been using Include or Replace, not Replace_Element.)


> I'm not saying that Ada.Containers or Cursor are bad, I already like this
> library much (this is not the case for Dmitriy :), what I'm saying is that
> this problem could happen to others and it is dangerous enough for us to take
> great care about it :)

I took Dmitriy's complaint seriously enough that I've been adding
assertion checks that can detect dangling cursors.  (When you build his
original example with assertions enabled, the program now fails with a
nice error message.)

Re: GCC 4.0 Ada.Containers Cursor danger.

[Pascal Obry]

"Matthew Heaney" <mheaney@on2.com> writes:

> I took Dmitriy's complaint seriously enough that I've been adding
> assertion checks that can detect dangling cursors.  (When you build his
> original example with assertions enabled, the program now fails with a
> nice error message.)

I know, indeed this is a nice addition.

Pascal.

-- 

--|------------------------------------------------------
--| Pascal Obry                           Team-Ada Member
--| 45, rue Gabriel Peri - 78114 Magny Les Hameaux FRANCE
--|------------------------------------------------------
--|              http://www.obry.net
--| "The best way to travel is by means of imagination"
--|
--| gpg --keyserver wwwkeys.pgp.net --recv-key C1082595

Re: GCC 4.0 Ada.Containers Cursor danger.

[Pascal Obry]

"Matthew Heaney" <mheaney@on2.com> writes:

> Cursors confer no greater safety than you get with named access types.
> If this isn't clear, then yes, we need to better job of advertising
> this feature.

I think so.

Pascal.

-- 

--|------------------------------------------------------
--| Pascal Obry                           Team-Ada Member
--| 45, rue Gabriel Peri - 78114 Magny Les Hameaux FRANCE
--|------------------------------------------------------
--|              http://www.obry.net
--| "The best way to travel is by means of imagination"
--|
--| gpg --keyserver wwwkeys.pgp.net --recv-key C1082595

Re: GCC 4.0 Ada.Containers Cursor danger.

[Randy Brukardt]

"Matthew Heaney" <mheaney@on2.com> wrote in message
news:1121870089.752445.108320@g49g2000cwa.googlegroups.com...
...
> Cursors confer no greater safety than you get with named access types.
> If this isn't clear, then yes, we need to better job of advertising
> this feature.

I don't agree with this statement. That fact that it is *possible* to check
for dangling cursors shows that. It's completely impractical to do useful
dangling access type checks (we tried to do so in Janus/Ada, but they almost
never detect anything, and break some common Ada 83 idioms).

Since I agree with your assertion that cursors shouldn't be kept around for
long periods, its clear that a bit of additional space/time overhead is
acceptable to get decent checking. As long as the checking is there, there
is not going to be a problem. (Like all Ada checking, it should default to
ON, of course, and be turned off only if critical.)

                                 Randy.

Re: GCC 4.0 Ada.Containers Cursor danger.

[Robert I. Eachus]

Mikhail Terekhov wrote:

> That means do it youself. So much for a "generic" library - if you need 
> some generic case - do it yourself.

No, what you are asking for is many more standard packages.  As Randy 
discribed in another part of this thread, the ARG worked to reduce the 
number of container variations that were part of the standard.  In doing 
this there are cases where one variant supports several different 
abstractions.  If you use the standard containers with any of those 
views, the packages are safe and efficient.  If you mix abstractions, 
you either have to choose a more expensive implementation, or risk 
erroneousness.

But it would be silly to provide half-a-dozen versions of some of the 
packages, one without Delete, one without cursors, one with a single 
cursor, and one with cursors that are always checked for validity, etc. 
  In practice if you need these abstractions materialized, it is less 
than an hour's work.  But most programmers don't even do that--they 
instantiate the package and document with a comment about how callers 
are expected to use the instance.

Yes, violations of those comments should be treated as programming 
errors.  It is one of the strengths of Ada that 1) you often can choose 
between compile time and run-time checking, and 2) you can use tools, 
such as SPARK, that pay attention to those comments, and validate them 
at compile time.

To summarize this long discussion, you say you know how to program badly 
in Ada.  I, and a lot of other people say, so do we, but we would rather 
not.  Years, ago I remember Robert Dewar, when talking about Spitbol I 
think, saying that there were two possible philosophies to use when 
creating programming languages:  Try to make it hard to do it wrong, or 
to try to make it easy to do things right.  In Ada we aim for both, but 
with a third caveat, which is that it should be possible to do anything. 
  Of course, to the maximum extent possible, we try to make doing 
something wrong and writing ugly code synonymous, and the same for 
elegant code and doing things right--from a software engineering 
perspective.  I think this is why you keep not getting it.  When someone 
says, this is a cleaner way to write that, and doesn't have the flaw you 
are worried about, they are really thinking that answers you.  But you 
would prefer not to be allowed to write erroneous programs in Ada. 
Sorry, see above. It is often not easy, but it can be done.  (At this 
point I should send you off to read G�del's Proof...)

Re: GCC 4.0 Ada.Containers Cursor danger.

[Craig Carey]

On Tue, 19 Jul 2005 22:37:46 -0400, "Robert I. Eachus"
<rieachus@comcast.net> wrote:

>Mikhail Terekhov wrote:
>
>> That means do it youself. So much for a "generic" library - if you need 
>> some generic case - do it yourself.
>
>No, what you are asking for is many more standard packages.  As Randy 
>discribed in another part of this thread, the ARG worked to reduce the 
>number of container variations that were part of the standard.  In doing 
>this there are cases where one variant supports several different 
>abstractions.  If you use the standard containers with any of those 
>views, the packages are safe and efficient.  If you mix abstractions, 
>you either have to choose a more expensive implementation, or risk 
>erroneousness.
>
>But it would be silly to provide half-a-dozen versions of some of the 
>packages,


Suppose it is almost-mathematically impossible for agreement to arise?.

The ARG has an improper purpose (eg stupidity) and that is why the
intelligent discussions occur out here.

What did I learn so far: 
 * Matt Heany wrote on how USA has been getting on top of its mobster
   problem. Gee, we certainly would not AI-302 to be a protection
   racket defending, with knee buster AdaCore sucking into its FSF

   repository of C++ catechisms

   the *.d[bs] files by Mr Heaney.
  
Comp.lang.ada perhaps has the detail for one of the ARG "Mitigator
 Supreme", i.e. the standards-lowerer: a nonresolvable dispute.

Mr Burkardt can't get mention the existence of his personal and secret
"arg@ada-auth.org" mailing list, to the public ARG list named Ada-Comment.

What's the chance that Brukardt would mouth out the words,
    arg@ada-auth.org"
to Comp.lang.ada.

If a person revelled in lowering standards, then what can he do?. If we 
are not careful, Ada could (especially when one of the silent few in
France is in charge) become a programming language better than others.
That is where a mob man can help: led by desires.

Great stuff for Mr Terekhov to write. But what Brukardt desires, is less
and less transparency: it is not really true that he can win his arguments
by using logic and truth alone.

Creating a garbage AI would eliminate transparency. 


Craig Carye

Re: GCC 4.0 Ada.Containers Cursor danger.

[Simon Wright]

Craig Carey <research@ijs.co.nz> writes:

*plonk*

Re: GCC 4.0 Ada.Containers Cursor danger.

[Georg Bauhaus]

Mikhail Terekhov wrote:
> Matthew Heaney wrote:

>> You want to legislate behavior for everyone.  This is wrong.  You should
>> only be concerned with your own behavior.
> 
> 
> I unerstand this as "shut up and go away". This is not polite. Try to 
> apply the above three sentences to yourself.

I think you misunderstood. "You should only be concerned with
your own behavior" is also a technical argument.
You can use a language like SETL2, APL, or Haskell and then notice
that it is hard, if possible, to get anywhere near the
machine. For Ada.Containers, there is a machine model that
Matt has been mentioning many times. A machine model blends
rather well with Ada IMHO.

These VHL languages are not Ada (perhaps the response by Robert
Eachus illustrates?), and you don't necessarily expect pointers
or bit fiddling to be available in a very high level language
like SETL2 etc. Programmers writing programs in these languages
are not primarily concerned with the machine and that's why
these languages are not concerned with the behavior of programmers
even though they don't usually provide pointers and bits.

Using SETL2 you can write

 procedure quicksort(s);  -- a sorted list of the elements in set s
 begin
    if #s = 0 then
      return [];
    end if;
    pivot := arb s;
    return quicksort({e: e in s | e < pivot})
      + [pivot]
      + quicksort({e: e in s | e > pivot});
 end quicksort;

That's fine in the absense of time and when s is not a large set.[*]
But absence of timing and memory usage requirements is unlikely a typical
Ada situation? So in Ada, I'm comfortable with element related algorithms
working at a less higher level of abstraction, as I'm trying to control
a machine.

 [*] So I guess is't fine for non-temporal mathematics.

-- Georg 

Re: GCC 4.0 Ada.Containers Cursor danger.

[Georg Bauhaus]

Dmitriy Anisimkov wrote:
>    M.Delete (C2);
>    pragma Assert (not Has_Element (C2));
>    pragma Assert (not M.Contains ("two"));
> --  double hash overhead.
> 
>    Replace_Element (C, -2);  -- dangling cursor

I thought the Replace_Element line was the source of an
undetected dangling cursor in your initial example.
Supposedly the new checking is inside Replace_Element,
which now fails with "bad cursor in Replace_Element".

The two asserts above look like "informative" assertions
to me, expressing what Delete has done. They are not in
the library, they are in a client program, and therefore
don't add overhead to library subprograms at all. They
also don't check C.


-- Georg

Re: GCC 4.0 Ada.Containers Cursor danger.

[Matthew Heaney]

Georg Bauhaus <bauhaus@futureapps.de> writes:

> Dmitriy Anisimkov wrote:
> >    M.Delete (C2);
> >    pragma Assert (not Has_Element (C2));
> >    pragma Assert (not M.Contains ("two"));
> > --  double hash overhead.
> >    Replace_Element (C, -2);  -- dangling cursor
> 
> I thought the Replace_Element line was the source of an
> undetected dangling cursor in your initial example.

Yes, that's my understanding too.


> Supposedly the new checking is inside Replace_Element, which now fails
> with "bad cursor in Replace_Element".

Some of that checking was already in place for the hashed map.  Did the
OP compile with assertions enabled?

What I find baffling is that the OP complained that the cursors were
dangerous, since the library failed to detect a dangling cursor
reference.  But when the dangling reference *is* detected, the OP
complains that the library still isn't good enough, either because
cursors have "too much overhead," or aren't "safe enough."  (If the
library can detect dangling cursors, then what other safety issues are
there?)  

His main complaint seems to be that cursors exist at all.  Yes, cursors
are tied to the iteration mechanism (a compromise of sorts, since the
language itself doesn't have support for "real" iterators), but cursors
have uses beyond mere iteration.


> The two asserts above look like "informative" assertions
> to me, expressing what Delete has done. 

Yes, exactly.


> They are not in the library, they are in a client program, and
> therefore don't add overhead to library subprograms at all. They also
> don't check C.

Note that if I had checked cursor C (by calling Has_Element, say), then
that would have just raised the assertion error sooner.