Version 1.3 of ai12s/ai12-0391-1.txt

Unformatted version of ai12s/ai12-0391-1.txt version 1.3
Other versions for file ai12s/ai12-0391-1.txt

!standard A.18.3(6/5)          20-09-10 AI12-0391-1/02
!standard A.18.3(23/5)
!standard A.18.3(50.2/5)
!standard A.18.3(96/5)
!class Amendment 20-08-31
!status Amendment 1-2012 20-09-10
!status ARG Approved 8-0-6 20-09-09
!status work item 20-08-31
!status received 20-06-16
!priority Low
!difficulty Easy
!subject List containers need Append_One
!summary
Add an Append_One operation to Ada.Containers.Doubly_Linked_Lists, and use it for Add_Unnamed in the Aggregate aspect.
!problem
The Aggregate aspect for Ada.Containers.Doubly_Linked_Lists has Add_Unnamed defined to be the existing Append operation. However, the existing Append operation includes a Count parameter which does not meet the profile of the required operation. Fix this? (Yes.)
!proposal
(See Summary.)
!wording
In A.18.3(6/5) and A.18.3(50.2/5), replace "Append" with "Append_One".
Add after A.18.3(23/5):
procedure Append_One (Container : in out List; New_Item : in Element_Type) with Pre => (not Tampering_With_Cursors_Prohibited (Container) or else raise Program_Error) and then (Length (Container) <= Count_Type'Last - 1 or else raise Constraint_Error), Post => Length (Container)'Old + 1 = Length (Container);
Add after A.18.3(96/5):
procedure Append_One (Container : in out List; New_Item : in Element_Type) with Pre => (not Tampering_With_Cursors_Prohibited (Container) or else raise Program_Error) and then (Length (Container) <= Count_Type'Last - 1 or else raise Constraint_Error), Post => Length (Container)'Old + 1 = Length (Container);
Equivalent to Insert (Container, No_Element, New_Item, 1).
!discussion
As in Vectors, this operation cannot be named Append, as any call to Append without the Count parameter would be ambiguous if that was the case.
!corrigendum A.18.3(6/5)
Replace the paragraph:
type List is tagged private with Constant_Indexing => Constant_Reference, Variable_Indexing => Reference, Default_Iterator => Iterate, Iterator_Element => Element_Type, Iterator_View => Stable.List, Aggregate => (Empty => Empty, Add_Unnamed => Append), Stable_Properties => (Length, Tampering_With_Cursors_Prohibited, Tampering_With_Elements_Prohibited), Default_Initial_Condition => Length (List) = 0 and then (not Tampering_With_Cursors_Prohibited (List)) and then (not Tampering_With_Elements_Prohibited (List)); pragma Preelaborable_Initialization(List);
by:
type List is tagged private with Constant_Indexing => Constant_Reference, Variable_Indexing => Reference, Default_Iterator => Iterate, Iterator_Element => Element_Type, Iterator_View => Stable.List, Aggregate => (Empty => Empty, Add_Unnamed => Append_One), Stable_Properties => (Length, Tampering_With_Cursors_Prohibited, Tampering_With_Elements_Prohibited), Default_Initial_Condition => Length (List) = 0 and then (not Tampering_With_Cursors_Prohibited (List)) and then (not Tampering_With_Elements_Prohibited (List)); pragma Preelaborable_Initialization(List);
!corrigendum A.18.3(23/5)
Insert after the paragraph:
procedure Append (Container : in out List; New_Item : in Element_Type; Count : in Count_Type := 1) with Pre => (not Tampering_With_Cursors_Prohibited (Container) or else raise Program_Error) and then (Length (Container) <= Count_Type'Last - Count or else raise Constraint_Error), Post => Length (Container)'Old + Count = Length (Container);
the new paragraph:
procedure Append_One (Container : in out List; New_Item : in Element_Type) with Pre => (not Tampering_With_Cursors_Prohibited (Container) or else raise Program_Error) and then (Length (Container) <= Count_Type'Last - 1 or else raise Constraint_Error), Post => Length (Container)'Old + 1 = Length (Container);
!comment A.18.3(50.2/5) not in corrigendum text.
!comment A.18.3(96/5) not in corrigendum text.
!ASIS
No ACATS effect.
!ACATS test
An ACATS C-Test is needed to check that the new procedure exists and works as expected. (This is a low priority test, as container aggregates will use the procedure, and thus the aggregate tests will check this functionality indirectly.)
!appendix

From: Ed Schonberg
Sent: Tuesday, June 16, 2020  3:29 PM

The modification to Ada/Containers.Doubly_Linked_Lists (A.18.3) indicates that 
the aspect Aggregate uses the existing Append operation fort Add_Unnamed. 
However the existing Append operation includes a Count parameter which does 
not meet the profile of the required operation.  An operation Append_One should 
be mentioned, as is already done for the Vector container.

****************************************************************

From: Tucker Taft
Sent: Tuesday, June 16, 2020  3:38 PM

Good point!

****************************************************************

From: Brad Moore
Sent: Monday, September 7, 2020  12:47 PM

Not sure if Ada comment or the ARG list is more appropriate for this. 
Ordinarily I would have gone with Ada-comment, but I chose the ARG list here, 
since this AI is being voted on this week.

I am wondering if there might be better choices for names for the Append_One 
procedure being added to the containers.

In my view, the containers and vectors, in particular, are missing a few 
convenience routines, to the extent that I ended up feeling the need to derive 
my own containers from the standard ones, to get the missing functionality.

One missing set of functions are ones to extract the first or last element. 
One can do this currently, by issuing two calls. One to get the desired 
element, and one to remove the element from the container. I believe this 
is a common usage, and its annoying that two calls are needed, when one 
could have been provided.

Other languages (e.g Python and C++) use the verb Pop, to describe this 
functionality, and similarly Push to append an item to the front (or back) 
of the container. If we were to decide down the road to provide routines, 
named such as Pop_First, and Pop_Last, it would be desirable to also provide 
the other side of the analogy, Push_First, and Push_Last.

Is it worth considering using, say, Push_Last rather than Append_One?

Append_One feels like a bandaid to fix a mistake to me. (i.e. if designing 
the containers from Scratch, I think it would have made sense to have "Append" 
be the routine that appends one element, and named the other one that we have 
currently, Append_Multiple (or even better not had a defaulted parameter for 
the call, and used overloading instead).

Push and Pop semantics on the otherhand provide a different mental model that 
many might be familiar with, which might better complement the existing 
container primitives, in the same way that Include and Insert for the Set 
containers provide similar semantics, where one call fits better when thinking 
of Sets, and the other fits when thinking more generically of containers.

Otherwise, I dont see the Append_One call being used much in user code. I 
think most would continue to use Append with the Defaulted count parameter,
because it is a shorter name, and more succinctly conveys to the reader the
intended semantics.

****************************************************************

From: Tucker Taft
Sent: Monday, September 7, 2020  2:59 PM

One important problem that "Append_One" is solving is related to having too 
much overloading.  Now that aggregates are permitted for containers, having 
two "Append" routines creates ambiguity, one which takes an element, and one 
which takes another container.  Append_One avoids that ambiguity, and avoids 
the need to qualify an aggregate that appears as the second parameter.

I could see adding a rename of Append_One for Push, and a Remove_Last function 
that returned and removed the last element, with a rename of Pop.  But 
providing only a Push and a Pop presumes that the container is being used as 
a stack, and that is frequently not the case.

****************************************************************

From: Brad Moore
Sent: Tuesday, September 8, 2020  2:43 PM

> One important problem that "Append_One" is solving is related to 
> having too much overloading.  Now that aggregates are permitted for 
> containers, having two "Append" routines creates ambiguity, one which 
> takes an element, and one which takes another container.  Append_One 
> avoids that ambiguity, and avoids the need to qualify an aggregate that 
> appears as the second parameter.

Understood.

> I could see adding a rename of Append_One for Push, and a Remove_Last 
> function that returned and removed the last element, with a rename of 
> Pop.  But providing only a Push and a Pop presumes that the container 
> is being used as a stack, and that is frequently not the case.

I would prefer to not see "Remove" used to describe that operation, because 
Remove suggests only a deletion, but not otherwise obtaining the element 
that was removed. Really no different semantics suggested than the current
"Delete" routines (i.e Delete_First, Delete_Last, etc).

Ideally a verb would be chosen that suggests both removal and retrieval.
The only two that immediately come to mind are "Pop" and "Extract".
Perhaps Extract would be a better fit for Ada as it is more formal an 
English word than Pop (i.e Less slangy). But I could see Pop as well, and 
has perhaps a more familiar association with general container usage.

Though Push and Pop are associated with stacks, it seems the semantics of 
these operations generally fit other types of containers as well,  which 
may be why other languages made the same choice, even though those containers 
are most often not used to represent stacks.

Anyway, I agree that if we decided down the road to provide a Push and a 
Pop, we could make those renames of existing routines.

****************************************************************

From: Tucker Taft
Sent: Tuesday, September 8, 2020  3:24 PM

At this point, I believe consistency between Vectors and Doubly_Linked_Lists 
argues for using the name Append_One.  From my own experience (e.g. in Java),
I find the use of Push and Pop always a bit confusing when it is *not* a stack
I am dealing with.

...
>> I could see adding a rename of Append_One for Push, and a Remove_Last 
>> function that returned and removed the last element, with a rename of 
>> Pop.  But providing only a Push and a Pop presumes that the container 
>> is being used as a stack, and that is frequently not the case.
> 
> I would prefer to not see "Remove" used to describe that operation, 
> because Remove suggests only a deletion, but not otherwise obtaining the 
> element that was removed. Really no different semantics suggested than the
> current "Delete" routines (i.e Delete_First, Delete_Last, etc).

Remove and Delete have different meanings to me (despite Unix' use of "rm" for 
deleting a file ;-).  But another choice is "Retrieve_Last" though as you 
argue, that could have the same ambiguity as "Get".  "Remove" has just the 
right intuition to me.  You don't destroy something when you remove it.  You
take it out, and you have to then decide what to do with it (e.g. destroy it,
give it away, etc.).

In any case, this seems like a discussion for the next revision of Ada! ;-) ...

****************************************************************

From: Randy Brukardt
Sent: Tuesday, September 8, 2020  6:25 PM

I vaguely remember talking about Push and Pop as possible operations back in 
the day, and deciding that they didn't match most of the uses of the 
containers. (That is, some containers are used as stacks, but most aren't.)

It's easy enough to write Push and Pop routines, so it doesn't seem that 
critical to have them.

I share Brad's unease about the name Append_One, though. It looks like a hack 
- there's nothing else named similarly in the packages. But that's because it 
*is* a hack, existing mainly because default parameters are inconsistently 
treated in Ada - they disappear in calls, but not when renaming/'Access/other 
profile matching.

But I've tried for many months now to find a better name. And there isn't one 
- there's no good name for a hack. ;-)

I don't think the overloading problem is real, in the sense that it comes from 
an Ada decision to not make resolution "too smart". This is one of the cases 
where that decision bites us in the ass. That's going to happen in a large 
language, and the usual answer is to suck it up and move on. (Having *one* of
the four routines involved in this problem having a hack that side-steps the 
problem doesn't appear to be much of a fix to me - we'd need Insert_One and 
Prepend_One to mostly fix it, and no fix is possible for "&" -- and the 
problem already occurs for Strings and other arrays anyway.)

****************************************************************

From: Tucker Taft
Sent: Tuesday, September 8, 2020  7:38 PM

Pragmatically speaking, we have found "Append" to be the main culprit in our 
code bases and with our (few) customers who have been experimenting with 2020
features, and Append_One seems to solve the problem pretty well.

****************************************************************

From: Brad Moore
Sent: Wednesday, September 9, 2020  8:44 AM

Append_One leaves a bad taste in my mouth, because appending a single item to 
a container is not a special variant of Append. It should be the main usage 
for Append, worthy of the name "Append". If anything, adding multiple items 
should be the special varianted name.

Having an Insert_First and Insert_Last would be a better choice in my view, 
as these could be considered as special variants of Insert. We do have 
Delete_First and Delete_Last for example.

But it seems to me that the ambiguity problem we have is because Append has a 
defaulted parameter for Count. It is ambiguous whether a call to a new variant
Append with no Count parameter was intended, vs a call to the existing Append 
but with Count being defaulted.

It also seems to me that this could be addressed by replacing the existing 
Append call with one that has a non-defaulted Count parameter. And then add 
a new Append procedure with the needed profile that does not have a Count 
parameter. That shouldn't be an incompatibility, I would think, since previous
calls using the Count default would now get mapped to the new procedure, and 
others with the Count parameter specified explicitly would get mapped to the 
replaced procedure.

****************************************************************

From: Tucker Taft
Sent: Wednesday, September 9, 2020  8:51 AM

You are still not addressing the ambiguity, which was the main purpose of 
having a different name.  The change you have suggested would be essentially 
invisible, but unfortunately, not fix the problem.

****************************************************************

From: Brad Moore
Sent: Wednesday, September 9, 2020  9:06 AM

How so?

I presume it has something to do with the new Add_Unnamed aspect, having to 
resolve which call to Append to make?

But for example, in the Vectors container, we specify Replace_Element for the 
Assign_Indexed aspect, and there are multiple Replace_Element calls to choose 
from.

****************************************************************


From: Tucker Taft
Sent: Monday, September 7, 2020  12:47 PM

****************************************************************


Questions? Ask the ACAA Technical Agent