Re: Overridability of _private_ predefined "=" [was Re: list strawman]

Re: Overridability of _private_ predefined "=" [was Re: list strawman]

[Christoph Grein]

Please, before going into further discussions about reemergence of predefined 
operations and thinking about changing the language, read the corresponding 
chapters in the AARM (the Annotated Ada Reference Manual), e.g. AARM 
4.5.2(24a-c).

With respect to "block compare", this is not possible for tagged types, floating 
point types if there are signed zeros, and who knows for which other cases.

Thus it is generally a bad idea to override predefined operators for non-tagged 
types. If this is really necessary, then utmost care has to be applied 
everywhere such a type is used (e.g. as components of an array).

Reemergence has been introduced in the first place to avoid incompatibilities 
with Ada83.

Christoph Grein

> Its even worse than just that.  Now a "block compare" of any composite
> type
> that has a nontagged private type as a componant is questional because
> that
> comparison will utilize the predefined "=" of the private type even
> though
> the creator of the private type may have seen it proper to overridden
> it.
> 
> There was a thread, gosh, I guess less than two years ago where I was
> trying to
> argue that this was a disaster wrt generics and that reemergence of "="
> seemed
> to be a special case wrt the whole reemergence issue.   I now feel that
> the
> situation is very bad in general as opposed to being bad only wrt
> generics.
> 
> Does anyone think that it would be good for there to be a change in the
> language such that for private types, if a primative "=" returning
> boolean exists then it
> should be the "=" used as part of block compares and that the predefined
> one
> should not reemerge in generics?  This would not have been incompatible
> with
> Ada83, right?
> 
> I hope that the above is not perceved as rehashing old arguments - I do
> not
> remember the issues having been discussed exactly as above.
> 
> Vincent Marciante

RE: RE: list strawman

[Steven Deller]

> -----Original Message-----
> From: comp.lang.ada-admin@ada.eu.org 
> [mailto:comp.lang.ada-admin@ada.eu.org] On Behalf Of Ted Dennison
> Sent: Tuesday, January 08, 2002 10:32 AM
> To: comp.lang.ada@ada.eu.org
> Subject: Re: RE: list strawman
> 
> Since we have a "Splice", I can't really sit here and argue 
> that its inverse function has no business being there. But 
> I'd like to hear a few concurrances that it needs to be in 
> there before changing things.

Ted,
Actually, a "split" is not necessary if there is a way to compare two
iterators to see if they are pointing to the same item -- in that case,
the left and right partitions can simply be the list portions before,
and after a given iterator.

Of course that means the algorithm will need O(lnN) iterators, which is
another difficulty in the current interface.  I'm not sure why there
needs to be a limit on the number of iterators.  For any operation that
has to check consistency across all iterators, just traverse a "list" of
the iterators (such a list being a locally defined and used list).

>From my "usability" view, the interface now has 3 flaws:
  1. No "split" list into two lists
  2. No "compare iterators" (at least not that I recall)
  3. Limited number of iterators

Regards,
Steve

Re: RE: RE: list strawman

[Ted Dennison]

In article <mailman.1010519822.5637.comp.lang.ada@ada.eu.org>, Steven Deller
says...
>
>Actually, a "split" is not necessary if there is a way to compare two
>iterators to see if they are pointing to the same item -- in that case,
>the left and right partitions can simply be the list portions before,
>and after a given iterator.

This isn't explicit from the current strawman I'm afraid, so it bears publicly
stating:

The current implementation implies that "=" is available for both lists and
iterators (they are not limited types). Given this, we can either take steps to
make "=" no loger available (which was not done), or we can make it do sensible
things.

"Sensible things" to me would imply that for lists, it returns True if they have
the same number of elements, and each element in one list returns True for "="
with the element in the same position in the other list. For an iterator, it
implies that both iterators refer to the same element in the same position on
the same list.

Therefore, unless there is general disagreement with the above, "=" on iterators
should fit your requirement.


>Of course that means the algorithm will need O(lnN) iterators, which is
>another difficulty in the current interface.  I'm not sure why there
>needs to be a limit on the number of iterators.  For any operation that
>has to check consistency across all iterators, just traverse a "list" of
>the iterators (such a list being a locally defined and used list).

There is no limit on iterators in the current. You can make as many iterators as
you like. The implementation I'm working on doesn't even use dynamic allocation
for them or when working with them, so such an algorithm shouldn't be a big
efficiency problem either. But I'd have no big problem with adding a Split
either.

>From my "usability" view, the interface now has 3 flaws:
>  1. No "split" list into two lists
Again: this can be taken care of, if there is support for it.

>  2. No "compare iterators" (at least not that I recall)
Its there, it just hasn't been very well advertised.

>  3. Limited number of iterators
Nope. Never was such a limit in any of the strawmen. (This was a feature of some
of Nick's examples. Are you perhaps thinking of that?)

---
T.E.D.    homepage   - http://www.telepath.com/dennison/Ted/TED.html

No trees were killed in the sending of this message. 
However a large number of electrons were terribly inconvenienced.

Re: list strawman

[Stephen Leake]

Ted Dennison<dennison@telepath.com> writes:

> In article <mailman.1010519822.5637.comp.lang.ada@ada.eu.org>, Steven Deller
> says...
> <snip> 
> >From my "usability" view, the interface now has 3 flaws:
> >  1. No "split" list into two lists
> Again: this can be taken care of, if there is support for it.

I vote for adding 'split'; it nicely compliments 'splice'.

> >  2. No "compare iterators" (at least not that I recall)
> Its there, it just hasn't been very well advertised.

We need to add a explicit visible "=" to make it do what you want; in
my implementation, the default "=" does not.

-- 
-- Stephe

Re: list strawman

[Ted Dennison]

In article <uwuys1qun.fsf@gsfc.nasa.gov>, Stephen Leake says...
>
>Ted Dennison<dennison@telepath.com> writes:
>> Its there, it just hasn't been very well advertised.
>
>We need to add a explicit visible "=" to make it do what you want; in
>my implementation, the default "=" does not.

You don't have to override "=" in the public part of a spec, so I usually don't.
With the strawmen I took the principle that only the public part of the spec was
presented, along with some extra stuff in the private part to get it to compile.
Perhaps in this case I took the principle too far...

I should shoulder the blame for any confusion this "implicit requirement" has
caused, since I left it implicit. But nits aside, it should be clear that "=" is
available, for Lists and Iterators, and thus implementors must make them both do
the sensible thing. Leaving them available but doing useless things is obviously
not good design. I might accept it for a package internal to a project, but
certianly not for something that is supposed to be standard.

Looking back at it now, what I should have done is what was done in the LRM for
the built-in operators in package Standard: put them in the public part
commented out.

---
T.E.D.    homepage   - http://www.telepath.com/dennison/Ted/TED.html

No trees were killed in the sending of this message. 
However a large number of electrons were terribly inconvenienced.

Re: list strawman

[Thomas Wolf]

dennison@telepath.com wrote:
> In article <uwuys1qun.fsf@gsfc.nasa.gov>, Stephen Leake says...
> >
> >Ted Dennison<dennison@telepath.com> writes:
> >> Its there, it just hasn't been very well advertised.
> >
> >We need to add a explicit visible "=" to make it do what you want; in
> >my implementation, the default "=" does not.
> 
> You don't have to override "=" in the public part of a spec, so I usually don't.
> With the strawmen I took the principle that only the public part of the spec was
> presented, along with some extra stuff in the private part to get it to compile.
> Perhaps in this case I took the principle too far...
> 
> I should shoulder the blame for any confusion this "implicit requirement" has
> caused, since I left it implicit. But nits aside, it should be clear that "=" is
> available, for Lists and Iterators, and thus implementors must make them both do
> the sensible thing. Leaving them available but doing useless things is obviously
> not good design. I might accept it for a package internal to a project, but
> certianly not for something that is supposed to be standard.

Some comments on that Strawman 1.4 interface:

1. Generic formals
------------------

   generic
      type Element is private;
   package Containers.Lists.Unbounded is

I'd prefer

   generic
      type Element is private;
      with function "=" (Left, Right : Element) return Boolean is <>;
   package Containers.Lists.Unbounded is

This allows users who have unconventional ideas of equality to provide
their own routine, without requiring "normal" users to specify the
equality function explicitly.

2. Element Arrays
-----------------

      type Element_Array is array (Natural range <>) of Element;
      
Why "Natural range <>"? I'd prefer "Positive range <>" similar to the
string packages. Note that you can still return an empty array for an
empty list by returning Element_Array (2 .. 1).

3. Naming issues
----------------

      function To   (Source : Element_Array) return List;
      function From (Source : List) return Element_Array;

I'd call these 'To_List' and 'To_Array', respectively. Maybe provide
these as renamings?

      function Singleton (Initial_Element : Element) return List;

I realize there's already been quite some discussion on that name. I
side with the "don't like" camp; I'd call this 'To_List', too.

4. Removing from a list end
---------------------------

      procedure Remove
        (Target      : in out List;
         Old_Element :    out Element;
         List_End    : in     Direction);

You don't always want to get the old element when you remove an item
from the list. Hence I'd add the following:

      procedure Remove
        (Target   : in out List;
         List_End : in     Direction);

5. Generic iterator
-------------------

      generic
         with procedure Operation (Target : in out Element; 
                                   Quit   :    out Boolean);
      procedure Passive_Iterator (Target : in out List);

Two things: first, 'Quit' must be an "in out"-parameter, and second,
in *my* terminology, this is an *active* iterator. After all, it
iterates on its own, so it's active, whereas the positions provided
by the type 'Iterator' do not move by themselves but have to be
advanced explicitly by the client code. Or did I get my nomenclature
mixed up?

Oh yes, and another thing: the list is an "in out" parameter, probably
to indicate that 'Operation' may change the elements (although the list
structure, i.e. the node chain, remains unchanged). A second variant

      generic
         with procedure Inspect (Target : in     Element; 
                                 Quit   : in out Boolean);
      procedure Read_Only_Iterator (Target : in List);

might be useful, too.

6. Inserting at a given location
--------------------------------

      procedure Insert (New_Item : in Element;
                        Location : in Iterator;
                        Side     : in Direction := Head);
      procedure Insert (New_Items : in List;
                        Location  : in Iterator;
                        Side      : in Direction := Head);

For completeness, the following is missing:

      procedure Insert (New_Items : in Element_Array;
                        Location  : in Iterator;
                        Side      : in Direction := Head);

In the two latter cases, nothing happens if 'New_Items' is empty.

7. Modifying an element at a given location
-------------------------------------------

      procedure Modify (Subject   : in out List; 
                        Location  : in     Iterator;
                        New_Value : in     Element);

Why is the subject list passed along? To be consistent with the
other operations on locations, it should be omitted.

8. Operations requiring a "<" on elements
-----------------------------------------

      generic
         with function Reverse_Order (First, Second : in Element)
                 return Boolean;
         From : in Direction;
      package Sorting is

Why this somewhat unusual (at least in my perception) interface?
Why not simply

      generic
         with function "<" (Left, Right : Element) return Boolean is <>;
      package Ordered is

and define e.g. Sort to sort the list into ascending order according to
the given "<" routine. (Or if you like, replace "<" by ">", it doesn't
matter.)

If you still want the ability to do both ascending and descending sorts
with the same instantiation, change 'Sort' to something like

         procedure Sort (Subject   : in out List;
                         Ascending : in     Boolean := True);

Furthermore, you could also provide lexicographical comparisons in this
nested package.

9. Equality
-----------

Both lists and iterators need meaningful equality operations. For lists,
return True if they both contain equal elements in the same order; for
iterators, return True if they both are null or else both point to the
same list node.

Is there any harm done by putting them explicitly in the public part?
This would make it absolutely clear for anybody that sensible 
implementations have to be provided for these operations. Furthermore,
it'd define a convenient place to put a comment explaining under what
conditions these operators return True.

10. Stream Attributes
---------------------

There's no need at all to make 'Stream_Read' and 'Stream_Write' public.
I'd put them into the private part.

-- 
-----------------------------------------------------------------
Thomas Wolf                          e-mail: t_wolf@angelfire.com

Re: list strawman

[Mark Lundquist]

"Thomas Wolf" <t_wolf@angelfire.com> wrote in message
news:MPG.16a629ebab6a7b63989682@news.ip-plus.net...
> Some comments on that Strawman 1.4 interface:
>
> 1. Generic formals
> ------------------
>
>    generic
>       type Element is private;
>    package Containers.Lists.Unbounded is
>
> I'd prefer
>
>    generic
>       type Element is private;
>       with function "=" (Left, Right : Element) return Boolean is <>;
>    package Containers.Lists.Unbounded is
>
> This allows users who have unconventional ideas of equality to provide
> their own routine, without requiring "normal" users to specify the
> equality function explicitly.

Indeed it's a bug in Ada95 if the generic uses "=" without importing it
explicitly.  Otherwise, an overridden "=" is not visible to the generic, and
predefined equality "reemerges".

Don't know if that's been fixedin Ted's latest, it may have...

-- mark

Overridability of _private_ predefined "=" [was Re: list strawman]

[Vincent Marciante]

Mark Lundquist wrote:
> 
> "Thomas Wolf" <t_wolf@angelfire.com> wrote in message
> news:MPG.16a629ebab6a7b63989682@news.ip-plus.net...
> > Some comments on that Strawman 1.4 interface:
> >
> > 1. Generic formals
> > ------------------
> >
> >    generic
> >       type Element is private;
> >    package Containers.Lists.Unbounded is
> >
> > I'd prefer
> >
> >    generic
> >       type Element is private;
> >       with function "=" (Left, Right : Element) return Boolean is <>;
> >    package Containers.Lists.Unbounded is
> >
> > This allows users who have unconventional ideas of equality to provide
> > their own routine, without requiring "normal" users to specify the
> > equality function explicitly.
> 
> Indeed it's a bug in Ada95 if the generic uses "=" without importing it
> explicitly.  Otherwise, an overridden "=" is not visible to the generic, and
> predefined equality "reemerges".

Its even worse than just that.  Now a "block compare" of any composite
type
that has a nontagged private type as a componant is questional because
that
comparison will utilize the predefined "=" of the private type even
though
the creator of the private type may have seen it proper to overridden
it.

There was a thread, gosh, I guess less than two years ago where I was
trying to
argue that this was a disaster wrt generics and that reemergence of "="
seemed
to be a special case wrt the whole reemergence issue.   I now feel that
the
situation is very bad in general as opposed to being bad only wrt
generics.

Does anyone think that it would be good for there to be a change in the
language such that for private types, if a primative "=" returning
boolean exists then it
should be the "=" used as part of block compares and that the predefined
one
should not reemerge in generics?  This would not have been incompatible
with
Ada83, right?

I hope that the above is not perceved as rehashing old arguments - I do
not
remember the issues having been discussed exactly as above.

Vincent Marciante

Re: Overridability of _private_ predefined "=" [was Re: list strawman]

[Vincent Marciante]

> Christoph Grein wrote:
> Please, before going into further discussions about reemergence of predefined 
> operations and thinking about changing the language, read the corresponding 
> chapters in the AARM (the Annotated Ada Reference Manual), e.g. 
> AARM 4.5.2(24a-c).

I have read that.  
 
> With respect to "block compare",

I'm sorry, I think that I should have said 'usage of predefined "=" 
for composite types that have componants of a private type'.

> this is not possible for tagged types, floating 
> point types if there are signed zeros, and who knows for which other cases.

So, in addition to what Mark Lundquist wrote:

Mark Lundquist wrote:
> 
> >
> >    generic
> >       type Element is private;
> >       with function "=" (Left, Right : Element) return Boolean is <>;
> >    package Containers.Lists.Unbounded is
> >
> > This allows users who have unconventional ideas of equality to provide
> > their own routine, without requiring "normal" users to specify the
> > equality function explicitly.
> 
> Indeed it's a bug in Ada95 if the generic uses "=" without importing it
> explicitly.  Otherwise, an overridden "=" is not visible to the generic, and
> predefined equality "reemerges".

it seems to also be a bug in Ada95 if the generic uses predefined "=" of 
any composite types that have componants whose type is that of an
imported
private type. Right?
 
> Thus it is generally a bad idea to override predefined operators for non-tagged 
> types. If this is really necessary, then utmost care has to be applied 
> everywhere such a type is used (e.g. as components of an array).

This is why I find the situation to be so bad now.  A generic written
for Ada 83 that only imports a private type can not be made into a valid
Ada 95 one by simply transforming its spec by adding the importation of
"=" for that type;  Its body must also be analyzed and possibly changed
so as to use componant by componant comparison for any composite types
having the private type as a componant (or predefined "=" has to be
overridden for those composite types _and_ any other composite types the
have those composite types as componants.)

What was impossible (?) to do wrong in Ada 83 has now become a pitfall
in Ada 95. were by we have to dilligently follow the verbal guideline
that you just suggested. 

> Reemergence has been introduced in the first place to avoid incompatibilities 
> with Ada83.

I have read this but I have not seen the statement of the
incompatibilities that were avoided.  Can someone point me to that
information?

I must really be missing something (and I do want to understand what it
is if I am.)

>
>Christoph Grein
>
> Vincent Marciante wrote:
>> Its even worse than just that.  Now a "block compare" of any composite
>> type
>> that has a nontagged private type as a componant is questional because
>> that
>> comparison will utilize the predefined "=" of the private type even
>> though
>> the creator of the private type may have seen it proper to overridden
>> it.
>> 
>> There was a thread, gosh, I guess less than two years ago where I was
>> trying to
>> argue that this was a disaster wrt generics and that reemergence of "="
>> seemed
>> to be a special case wrt the whole reemergence issue.   I now feel that
>> the
>> situation is very bad in general as opposed to being bad only wrt
>> generics.
>> 
>> Does anyone think that it would be good for there to be a change in the
>> language such that for private types, if a primative "=" returning
>> boolean exists then it
>> should be the "=" used as part of block compares and that the predefined
>> one
>> should not reemerge in generics?  This would not have been incompatible
>> with
>> Ada83, right?
>> 
>> I hope that the above is not perceved as rehashing old arguments - I do
>> not
>> remember the issues having been discussed exactly as above.
>> 
>> Vincent Marciante

Re: Overridability of _private_ predefined "=" [was Re: list strawman]

[Nick Roberts]

"Vincent Marciante" <marciant_remove@li.net> wrote in message
news:3C49A5C4.51D6@li.net...

> ...
> This is why I find the situation to be so bad now.  A generic written
> for Ada 83 that only imports a private type can not be made into a valid
> Ada 95 one by simply transforming its spec by adding the importation of
> "=" for that type;  Its body must also be analyzed and possibly changed
> so as to use componant by componant comparison for any composite types
> having the private type as a componant (or predefined "=" has to be
> overridden for those composite types _and_ any other composite types the
> have those composite types as componants.)
>
> What was impossible (?) to do wrong in Ada 83 has now become a pitfall
> in Ada 95. were by we have to dilligently follow the verbal guideline
> that you just suggested.

AI-123 discusses this in some detail, and results (rev 12) in a corrigendum
which specifically compels language-defined types to be composable with
respect to equality (thus forcing them to be implemented either without
redefined equality or as tagged types). I smell a hint of hypocrisy here.

Personally, I completely agree with Vincent. Damn Ada 83 compatibility, and
damn implementation complexities: equality should always be composable; the
current state is plainly a potential source of 'nasty surprises'; the
language is purportedly supposed to avoid nasty surprises. But I am a small
voice.

--
Best wishes,
Nick Roberts