Version 1.2 of ai05s/ai05-0257-1.txt

Unformatted version of ai05s/ai05-0257-1.txt version 1.2
Other versions for file ai05s/ai05-0257-1.txt

!standard A.18.2(167/2)          11-06-16 AI05-0257-1/01
!standard A.18.3(92/2)
!standard A.18.3(94/2)
!standard A.18.10(0)
!class Amendment 11-06-16
!status work item 11-06-16
!status received 11-04-13
!priority Low
!difficulty Easy
!subject Insert returning a Position
!summary
!proposal
A.18.3(92/2), A.18.10(143/3), and A.18.10(145/3) say "Position designates the first newly-inserted node." What happens if Count = 0 and there are no newly-inserted nodes??
A.18.3(94/2) doesn't say anything at all about the value of Position. That's clearly wrong.
!wording
!discussion
A.18.2(167/2) doesn't explicitly address this question, but since it is defined in terms of indexes, it effectively returns the insertion position when Count = 0.
This result seems broken, in that it almost never is what you would want. The description of the other routines is more likely to be correct (in that following operations are likely to treat Position as a new node). Indeed, Count /= 1 almost never makes sense when returning a position. As such, one possibility would be simply to raise Program_Error if Count = 0 when returning a position (as there is no newly inserted node).
Removing the Count parameter altogether from Inserts returning Positions would be the best solution (it much less error-prone), but that might be too incompatible (even though the vast majority of code that use the parameter would simply need to remove Count => 1, from the calls).
!ACATS test
None needed.
!appendix

From: Matthew Heaney
Sent: Monday, April 11, 2011  9:31 PM

[The relevant part of this message - Editor.]

The description of:

    procedure Insert_Child (Container : in out Tree;
                            Parent    : in     Cursor;
                            Before    : in     Cursor;
                            New_Item  : in     Element_Type;
                            Position  :    out Cursor;
                            Count     : in     Count_Type := 1);

states that:

(quote)

Position designates the first newly-inserted node.

(end quote)

The issue here is what value does Position have when Count is 0.  I think it
should have the value No_Element, which is what we decided in York about the
behavior of Delete for the doubly-linked list.

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

From: Randy Brukardt
Sent: Saturday, April 30, 2011  1:02 AM

[The relevant part of this message - Editor.]

> The description of:
>
>     procedure Insert_Child (Container : in out Tree;
>                             Parent    : in     Cursor;
>                             Before    : in     Cursor;
>                             New_Item  : in     Element_Type;
>                             Position  :    out Cursor;
>                             Count     : in     Count_Type := 1);
>
> states that:
>
> (quote)
>
> Position designates the first newly-inserted node.
>
> (end quote)
>
> The issue here is what value does Position have when Count is 0.  I
> think it should have the value No_Element, which is what we decided in
> York about the behavior of Delete for the doubly-linked list.

I don't see what Delete has to do with anything; it always sets the Position to
No_Element (the Count is irrelevant).

And there is no answer to this question in the linked list Inserts that have out
Position parameters, either (the wording for these Tree routines was lifted
directly from the linked list wording). (There is an answer for the vector, at
least, and neither Maps nor Sets have these Count parameters.)

My preference for the semantics of this is to raise Constraint_Error. It doesn't
make sense to ask to insert no elements and at the same time expect to get a
cursor back of the inserted element. (As you would say, any other result would
violate the postcondition of the routine that Position points at the first
inserted element - that seems bad.)

(I'm surprised that any of these Count parameters allow zero, but it is too late
to change that.)

So I added "; if Count is zero, Constraint_Error is propagated." to each of
these. (We could also define a Positive_Count_Type subtype, but that seems to be
overkill for this very isolated case, and it would be [slightly] incompatible
for the existing List routines.)

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

From: Matthew Heaney
Sent: Saturday, April 30, 2011  9:36 AM

>> Issue 3/3:
>>
>> The description of:
>>
>>      procedure Insert_Child (Container : in out Tree;
>>                              Parent    : in     Cursor;
>>                              Before    : in     Cursor;
>>                              New_Item  : in     Element_Type;
>>                              Position  :    out Cursor;
>>                              Count     : in     Count_Type := 1);
>>
>> states that:
>>
>> (quote)
>>
>> Position designates the first newly-inserted node.
>>
>> (end quote)
>>
>> The issue here is what value does Position have when Count is 0.  I
>> think it should have the value No_Element, which is what we decided
>> in York about the behavior of Delete for the doubly-linked list.
>
> I don't see what Delete has to do with anything; it always sets the
> Position to No_Element (the Count is irrelevant).

That was my mistake -- I meant to compare Insert_Splice to the Insert operation
of the other containers.

> My preference for the semantics of this is to raise Constraint_Error.

I think this argument is wrong -- all the containers "do nothing"
(meaning specifically "do not raise any exceptions") when the Count
parameter is 0 for insertion (and deletion) operations.  The multiway
tree should not behave any differently from the other containsers.

 > It doesn't make sense to ask to insert no elements and at the
 > same time expect to get a cursor back of the inserted element.

The this works for the other containers is the Position points to the
next element in sequence.  When the Count parameter is 0, then Position
designates an element that happens to have already existed in the
container (Position = Before).  This is how it works for all the containers.

> (As you would say, any other
> result would violate the postcondition of the routine that Position points
> at the first inserted element - that seems bad.)

The spec should say explicitly that when Count is 0, then Position
equals Before.  (It should not raise CE or any other exception.)

> (I'm surprised that any of these Count parameters allow zero, but it is too
> late to change that.)

This was deliberate - the insertion (and deletion) operations were
designed to "do nothing gracefully" when the Count parameter is 0.

There's nothing new here, except that the behavior when Count is 0 was
not specified explicitly.  The multiway tree spec just needs to say that
it does exactly what the other containers do, which is set Position =
Before when the Count is 0.

> So I added "; if Count is zero, Constraint_Error is propagated." to each of
> these. (We could also define a Positive_Count_Type subtype, but that seems
> to be overkill for this very isolated case, and it would be [slightly]
> incompatible for the existing List routines.)

I don't think this is what you want.  Insertion (and deletion)
operations are always idempotent, for all the containers, including the
multiway tree.

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

From: Randy Brukardt
Sent: Saturday, April 30, 2011  5:10 PM

...
> > My preference for the semantics of this is to raise
> Constraint_Error.
>
> I think this argument is wrong -- all the containers "do nothing"
> (meaning specifically "do not raise any exceptions") when the Count
> parameter is 0 for insertion (and deletion) operations.  The multiway
> tree should not behave any differently from the other containsers.

I agree that the multiway trees should act the same, and in fact they do; I made
the change to ALL of the containers except the vectors since the behavior was
unspecifed for all of them. I could easily be convinced to make the change to
Vectors as well.

>  > It doesn't make sense to ask to insert no elements and at the  >
> same time expect to get a cursor back of the inserted element.
>
> The this works for the other containers is the Position points to the
> next element in sequence.  When the Count parameter is 0, then
> Position designates an element that happens to have already existed in
> the container (Position = Before).  This is how it works for all the
> containers.

Bull. It happens to work that way for the Vectors, but there is no evidence that
this was intended behavior. For the Lists, it is completely unspecified; the
wording says that Position is set to the "first newly inserted element" and
there is no indication of what happens otherwise. Maps and Sets don't have Count
parameters. The Multiway_Tree is just a copy of the list.

> > (As you would say, any other
> > result would violate the postcondition of the routine that Position points
> > at the first inserted element - that seems bad.)
>
> The spec should say explicitly that when Count is 0, then Position
> equals Before.  (It should not raise CE or any other exception.)

Why? This seems like useless semantics; if you intend to do additional
initialization after the insertion (which seems to be the best reason for
returning the Position parameter), this would cause you to initialize an old
element or require extra testing. Neither seems good.

And it definitely does not match the defined "postcondition" for the routine
(that Position points at the first NEWLY INSERTED element). If you want to
change that, you need to explain a clear alternative postcondition and why it
would be useful.

Indeed, I think the Count parameter itself on these routines is junk; if you
want a pointer to the element back, you want each such cursor back, not an
arbitrary one. (Meaning you have to use Count = 1.) Having this parameter is
just consistency run amok. (Not going to change it, of course, but worrying
about it's usefulness is rather silly.)

> > (I'm surprised that any of these Count parameters allow zero, but it
> > is too late to change that.)
>
> This was deliberate - the insertion (and deletion) operations were
> designed to "do nothing gracefully" when the Count parameter is 0.

This doesn't seem to be very Ada-like. We don't allow calling New_Line to write
zero lines. This seems like something that comes from languages that don't have
subranges and thus can't prevent passing silly values.

Moreover this is junk semantics, it doesn't provide any real benefit. If the
counter is calculated, it still has to be pretested as converting to Count_Type
will raise Constraint_Error if the calculated value is negative. When Ada does
allow zero of something (as for loops), it ensures that it doesn't matter what
the expressions are. That's not true here.

To give a specific example, when you write:
    Flop : Integer := 1;
    for I in 3 .. Flop loop
the loop runs zero times.

But if you wrote:
     Insert (List, ..., Count => Count_Type (3 - Flop + 1)); you'd get
Constraint_Error from the conversion (or the parameter passing, if the
expression is calculated in Count_Type).

So allowing zero only helps in the unusual case that you can prove that the
expression can never be negative but can be zero.

In any case, we're not going to change this now; we're *only* talking about the
routines that return a Position parameter.

> There's nothing new here, except that the behavior when Count is 0 was
> not specified explicitly.  The multiway tree spec just needs to say
> that it does exactly what the other containers do, which is set
> Position = Before when the Count is 0.

It is not specified for the Lists or any other containers, either. I don't know
why you seem to think otherwise. For the Vectors, it accidentally has the
semantics you suggest, but that's it.

> > So I added "; if Count is zero, Constraint_Error is propagated." to
> > each of
> > these. (We could also define a Positive_Count_Type subtype, but that seems
> > to be overkill for this very isolated case, and it would be
> > [slightly] incompatible for the existing List routines.)
>
> I don't think this is what you want.

It's definitely what *I* want. Whether others agree or disagree remains to be
seen...

> Insertion (and deletion) operations are always idempotent, for all the containers,
> including the multiway tree.

Definitely not true for the Position returning one, and when I said *all of
these* above, I meant for all containers with an Insert with a Count parameter
-- other than Vectors. (I left out Vectors because it was previously specified
to do something, even though it was by accident, so I couldn't justify inserting
an inconsistency. For the others, the behavior was unspecified, so any
inconsistency is an accident of a random implementation choice, and the
parameter is virtually useless anyway, meaning it won't show up in real code. I
wouldn't mind changing the Vector ones as well, if the consistency of the
operations is more important than the consistency with unlikely to exist code.)

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

From: Bob Duff
Sent: Saturday, April 30, 2011  6:42 PM

> It's definitely what *I* want. Whether others agree or disagree
> remains to be seen...

I don't know much about multi-way trees, but I think I agree with
Matt: It makes sense to insert zero things into a sequence (Vector or List).
And if a Position is returned, and zero things were inserted, it makes sense for
Position to be Before (so a subsequent call to Insert using that Position
works).

Negative counts don't make sense, and should raise an exception.

> So allowing zero only helps in the unusual case that you can prove
> that the expression can never be negative but can be zero.

I don't think that's unusual.  You say:

    X : Count_Type := 0;

Then you say "X := X + 1;" some number of times (possibly zero).
Then you say "Insert(..., Count => X)".  There's no need to worry about negative
X, here.  And it would be annoying to require "if X /= 0 then Insert...".

How this relates to trees, I don't know.

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

From: Randy Brukardt
Sent: Saturday, April 30, 2011  8:06 PM

> > It's definitely what *I* want. Whether others agree or disagree
> > remains to be seen...
>
> I don't know much about multi-way trees, but I think I agree with
> Matt: It makes sense to insert zero things into a sequence (Vector or
> List).  And if a Position is returned, and zero things were inserted,
> it makes sense for Position to be Before (so a subsequent call to
> Insert using that Position works).

Why would anyone do that? It doesn't make sense to me.

Any that is definitely not the description of the result of this parameter for
these routines; I have no idea what the description should be. (The description
that you and Matt have given sounds like junk to me; it makes the meaning of the
parameter conditional on the Count, which requires a test (at least logically)
and defeats the purpose of adding zero.)

If you (or anyone) wants this meaning, please suggest some wording to describe
it. And explain what the hell this parameter means after the call (so John and
other authors can explain it).

> Negative counts don't make sense, and should raise an exception.
>
> > So allowing zero only helps in the unusual case that you can prove
> > that the expression can never be negative but can be zero.
>
> I don't think that's unusual.  You say:
>
>     X : Count_Type := 0;
>
> Then you say "X := X + 1;" some number of times (possibly zero).
> Then you say "Insert(..., Count => X)".  There's no need to worry
> about negative X, here.  And it would be annoying to require "if X /=
> 0 then Insert...".

Maybe it would be annoying, but it would be much more obvious what you are
doing. This is very much like testing for null before calling
Unchecked_Deallocation: that's something that should explicitly be in the code
even though the routine (mistakenly) allows null to be passed to it.

I suppose the fact that I consider Count = 0 to be junk in all circumstances
makes me not the best person to decide on the semantics here. Indeed, I think
calling either of these routines that return a Position with Count other than =
1 to be a mistake -- you need the cursor for each new item, not some random
element that might not even be new.

> How this relates to trees, I don't know.

This has nothing to do with Trees specifically; only Matt seems to think this is
currently defined at all (it's not). This is a question about how these routines
should work for all containers -- the behavior is currently unspecified, and any
result here will be potentially inconsistent with implementations (specifying a
result of any sort is inconsistent with unspecified).

Anyway, it's clear this requires a full discussion, so this will not be answered
in Ada 2012. We'll have to make a Ada 2012 BI to deal with this case. (That's
OK, it's unspecified now, it can stay that way for a while longer; it would be
worse to specify junk semantics that has to be changed.)

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

From: Matthew Heaney
Sent: Saturday, April 30, 2011  10:38 PM

> I agree that the multiway trees should act the same, and in fact they
> do; I made the change to ALL of the containers except the vectors
> since the behavior was unspecifed for all of them. I could easily be
> convinced to make the change to Vectors as well.

Well this is a *far* more radical change to the container library semantics.

It has always been the case, even in the Charles library, that insertion operations should "do nothing gracefully" when attempting to insert 0 items in the container.  (The same, mutatis mutandis, for deletion
operations.)

My thinking on this matter was directly influenced by Dijkstra, in his review of the Red language (IIRC), which didn't allow you to declare a zero-length array.  He thought this was ridiculous, arguing that it took thousands of years for number 0 to be dis
covered, only to be forgotten again by certain language designers.

Certainly it has been this way, ab initio, in the GNAT implementation of the container library.


> Bull. It happens to work that way for the Vectors, but there is no evidence
> that this was intended behavior.

Well it certainly was intended from me!  (Oh, you're going to make dig
through my archives, aren't you...)


> For the Lists, it is completely
> unspecified; the wording says that Position is set to the "first newly
> inserted element" and there is no indication of what happens otherwise. Maps
> and Sets don't have Count parameters. The Multiway_Tree is just a copy of
> the list.

Well perhaps we should invoke the Dewar rule.  The fact that the spec
doesn't explicitly say what happens when the Count is 0 does not mean
that raising CE is the intended behavior!


> Why? This seems like useless semantics; if you intend to do additional
> initialization after the insertion (which seems to be the best reason for
> returning the Position parameter), this would cause you to initialize an old
> element or require extra testing. Neither seems good.

No.  The intent is that the return value indicate what the new insertion
position is.  If the number of items inserted is 0, then the new
insertion position is simply the old insertion position (the value of
the Before parameter).


> And it definitely does not match the defined "postcondition" for the routine
> (that Position points at the first NEWLY INSERTED element).

But that's precisely the issue we're debating!  We can either change the
wording (e.g. say "new insertion position" or some such instead) or
preserve the "newly inserted" wording but define it mean what we say it
means.

Words are our servants, not our masters.  What Humpty Dumpty said and
all that.


 > If you want to
> change that, you need to explain a clear alternative postcondition and why
> it would be useful.

Well now, I could argue that you're just shifting the burden of proof.
I could easily argue, with equal merit, that "If you want to change the
semantics of container insertion (to raise CE when 0 elements are
inserted, instead of doing nothing), you need to explain why such a
change would be useful."

If all you want is some new, unambiguous wording, then I'll be happy to
provide it.


> Indeed, I think the Count parameter itself on these routines is junk; if you
> want a pointer to the element back, you want each such cursor back, not an
> arbitrary one. (Meaning you have to use Count = 1.) Having this parameter is
> just consistency run amok. (Not going to change it, of course, but worrying
> about it's usefulness is rather silly.)

Well if you remember the meeting in Phoenix, I lobbied to have separate
operations: one that takes an explicit (non-defaulted) count, and
another with no count parameter at all.  Tucker likes default
parameters, so I lost that battle.

In any case, this takes us away from the issue at hand, which is an
unambiguous specification of the behavior when the Count value is 0.  I
have always argued (and you know I am never timid about such things),
and always assumed the RM meant, that when the Count is 0, the insertion
operation does nothing, and returns the value of Before as the return
value of Position.

Call this behavior "having Dijkstra semantics" if you wish (with
apologies to Ben, and anyone else associated with Red).


> This doesn't seem to be very Ada-like. We don't allow calling New_Line to
> write zero lines. This seems like something that comes from languages that
> don't have subranges and thus can't prevent passing silly values.

There is nothing silly about 0!  In fact it is one of mankind's most
important discoveries.


> But if you wrote:
>       Insert (List, ..., Count =>  Count_Type (3 - Flop + 1));
> you'd get Constraint_Error from the conversion (or the parameter passing, if
> the expression is calculated in Count_Type).

Well I'd be happy to accept Count_Type'Base as the type of that
parameter (and I probably argued for that).  However, Pascal was fond of
explicit testing for "extreme values that might indicate an error" and
raising an exception (I lobbied to accept them, and do nothing), so I
lost that battle too.

In any event, you are attempting to move the goalposts, since we are
debating the semantics when count has the value 0, not when the count is
negative, so your argument above doesn't, er, count.


> So allowing zero only helps in the unusual case that you can prove that the
> expression can never be negative but can be zero.

Well that's a debate you should have with Pascal.  That (putative)
problem is easily solved by making the Count parameter have type
Count_Type'Base.


> In any case, we're not going to change this now; we're *only* talking about
> the routines that return a Position parameter.

Right, and, what should happen when the Count value is 0.


> It is not specified for the Lists or any other containers, either. I don't
> know why you seem to think otherwise. For the Vectors, it accidentally has
> the semantics you suggest, but that's it.

But that's an essential, not accidental, characteristic!  Those
containers were designed precisely to be inter-changeable.  That's why
we spent months getting the vector just right (even giving it a
supernumerary Cursor, when it already has a perfectly-good index).


> It's definitely what *I* want. Whether others agree or disagree remains to
> be seen...

You always need to handle the zero case, by doing nothing.  (Handling
Count values that are negative is an interesting, but separate, discussion.)


> Definitely not true for the Position returning one, and when I said *all of
> these* above, I meant for all containers with an Insert with a Count
> parameter -- other than Vectors. (I left out Vectors because it was
> previously specified to do something, even though it was by accident, so I
> couldn't justify inserting an inconsistency. For the others, the behavior
> was unspecified, so any inconsistency is an accident of a random
> implementation choice, and the parameter is virtually useless anyway,
> meaning it won't show up in real code. I wouldn't mind changing the Vector
> ones as well, if the consistency of the operations is more important than
> the consistency with unlikely to exist code.)

Consistency is precisely why the vector was specified that way.  If the
List container is described differently, then that's a bug in the spec,
not a bug in the semantics, which should exactly match those for vector.
  Mutatis mutandis, for the multiway tree.

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

From: Matthew Heaney
Sent: Saturday, April 30, 2011  11:14 PM

> Why would anyone do that? It doesn't make sense to me.

This is called "the argument from personal incredulity".  Just because it
doesn't make sense to you does not mean that it doesn't make sense!

> Any that is definitely not the description of the result of this parameter
> for these routines; I have no idea what the description should be. (The
> description that you and Matt have given sounds like junk to me; it makes
> the meaning of the parameter conditional on the Count, which requires a test
> (at least logically) and defeats the purpose of adding zero.)

Position returns the new insertion position.  The return value
designates the first element of what was inserted, and in the limit,
when what was inserted happens to be an empty sequence, the return value
is the same as Before.

You definitely do not want to require that users handle the limiting
case themselves to avoid an exception: that was the cause of endless
headaches for Ada83 users when concatenating arrays (a problem that was
thankfully solved in Ada95).

> If you (or anyone) wants this meaning, please suggest some wording to
> describe it. And explain what the hell this parameter means after the call
> (so John and other authors can explain it).

"On return, Position designates the new insertion position, defined as
the position of the first newly-inserted element when the Count is
non-zero, or the value Before when the Count is zero."

> This has nothing to do with Trees specifically; only Matt seems to think
> this is currently defined at all (it's not). This is a question about how
> these routines should work for all containers -- the behavior is currently
> unspecified, and any result here will be potentially inconsistent with
> implementations (specifying a result of any sort is inconsistent with
> unspecified).

Well the behavior certainly is implied.  In syllogistic form:

(p) the vector says to return Before when Count is 0
(p) lists were designed to behave like a vector
----
(c) a list returns Before when Count is 0

Likewise for the multiway tree.

> Anyway, it's clear this requires a full discussion, so this will not be
> answered in Ada 2012. We'll have to make a Ada 2012 BI to deal with this
> case. (That's OK, it's unspecified now, it can stay that way for a while
> longer; it would be worse to specify junk semantics that has to be changed.)

Well the "junk semantics" are what GNAT has been doing for several years
now.  If there is an ambiguity in the specification (yes this happens,
and that's why we have an ARG to resolve such things), then I think the
burden is advocates of the interpretation "raise an exception when the
Count is 0" to justify why existing code should be modified to now
handle an exception in the limiting case when Count is 0.

It goes without saying, but I'll say it anyway: the purpose of an
exception is either to indicate that an precondition has not been
satisfied, or to indicate that the operation cannot satisfy its
postcondition.  In general (per Dijkstra and Hoare), you want to weaken
the precondition and strengthen the postcondition.  For example,
Unchecked_Deallocation does nothing when the X parameter has the value
null; this is an example of weakening the precondition.  Likewise for
container insertion and deletion, when the Count is 0, the operation
should do nothing.  It certainly should not raise exception.  I thought
Ada95 settled such debates.

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

From: Bob Duff
Sent: Sunday, May  1, 2011  7:39 AM

> Anyway, it's clear this requires a full discussion, so this will not
> be answered in Ada 2012. We'll have to make a Ada 2012 BI to deal with
> this case. (That's OK, it's unspecified now, it can stay that way for
> a while longer; it would be worse to specify junk semantics that has
> to be changed.)

Yes, of course!

That should be the general policy for all new bugs anybody finds in Ada 2005.
It's too late to fix them now.  We can chat about how to fix them, but we're not
going to fix them until Ada 2012 is done. Otherwise, we'll be stuck in an
infinite loop.

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

From: Bob Duff
Sent: Sunday, May  1, 2011  11:16 AM

> That should be the general policy for all new bugs anybody finds in
> Ada 2005.  It's too late to fix them now.  We can chat about how to
> fix them, but we're not going to fix them until Ada 2012 is done.
> Otherwise, we'll be stuck in an infinite loop.

Let's make sure to clarify this for reviewers:  When somebody reviews the new
Ada 2012 RM, they should be looking for bugs in the the new text.  Old text that
got broken by new text is also fair game.

But old text containing old bugs should be left alone.  If you find such a
thing, ignore it, unless it's important.  "Important" means "will have some
affect on the behavior of some implementers or programmers".  And even if it's
important, the only action ARG should take is to open an Ada 2012 AI, for
far-future consideration.

Otherwise, we (especially Randy) are going to spend a lot of time arguing about
where to put the commas that were inherited from Ada 83/95/2005.

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

From: Randy Brukardt
Sent: Sunday, May  1, 2011  10:11 PM

To be fair, it wasn't clear where this bug lies. Matt noticed it in new text; I
pointed out that it is identical to *old* text. So it is really an old bug, but
Matt couldn't have been expected to know that.

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

From: Bob Duff
Sent: Sunday, May  1, 2011  11:15 AM

>...  In general (per Dijkstra and Hoare), you want to weaken  the
>precondition and strengthen the postcondition.

I agree with your position with respect to allowing count = 0, but I think the
above claim is not true.  Or maybe "only sometimes true".

Weakening a precondition increases the burden on the callee, while reducing the
burden on the caller.  Whether that's a good thing depends on the situation.
For example, we could weaken the precondition on String indexing, so that
out-of-bounds indexing is allowed, and returns a blank.  But that wouldn't be a
good idea.

>...For example,
> Unchecked_Deallocation does nothing when the X parameter has the value
>null; this is an example of weakening the precondition.

That's not an effective argument, because (1) "null" is not at all analogous to
"0", and (2) not everybody agrees that U_D should null-out its parameter.

>...Likewise for
> container insertion and deletion, when the Count is 0, the operation
>should do nothing.

I agree, if you remove "Likewise".  ;-)

By the way, I did a couple of experiments: changed all the Insert operations
that take a Count, and raise an exception if the count is 0, or (separate
experiment) if the count is not 1.

Tests run: 15005
Tests that fail when Count must be >= 1: 2 Tests that fail when Count must be
exactly = 1: 3

All 3 failures are purpose-written tests, not "real code".

I also ran 3787 ACATS tests, and got zero failures in both experiments.

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

From: Randy Brukardt
Sent: Sunday, May  1, 2011  10:13 PM

> I also ran 3787 ACATS tests, and got zero failures in both
> experiments.

Sadly, there aren't any container tests in the ACATS, so I wouldn't expecy any
results from any such test. (You'd have gotten the same results if you made
declaring a Vector raise Tasking_Error. :-)

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

From: Randy Brukardt
Sent: Sunday, May  1, 2011  10:39 PM

...
> > Anyway, it's clear this requires a full discussion, so this will not
> > be answered in Ada 2012. We'll have to make a Ada 2012 BI to deal
> > with this case. (That's OK, it's unspecified now, it can stay that
> > way for a while longer; it would be worse to specify junk semantics
> > that has to be
changed.)
>
> Well the "junk semantics" are what GNAT has been doing for several
> years now.

Really? I was talking about raising an exception when I wrote that! :-)

It doesn't matter what semantics you think is right, or I think is right, we
need a wider decision. And we're not doing any more such decisions for Ada 2012.
Choosing *anything* here is potentially "junk" because it is adding a constraint
that currently does not exist.

> If there is an ambiguity in the specification (yes this happens, and
> that's why we have an ARG to resolve such things), then I think the
> burden is advocates of the interpretation "raise an exception when the
> Count is 0" to justify why existing code should be modified to now
> handle an exception in the limiting case when Count is 0.

There is no existing code other than in tests (according to Bob) -- and I
believe that. The Count parameter is something that is rarely used, and the
Insert that returns a cursor is fairly uncommon, and the use of them together is
going to be non-existent.

> It goes without saying, but I'll say it anyway: the purpose of an
> exception is either to indicate that an precondition has not been
> satisfied, or to indicate that the operation cannot satisfy its
> postcondition.  In general (per Dijkstra and Hoare), you want to
> weaken the precondition and strengthen the postcondition.  For
> example, Unchecked_Deallocation does nothing when the X parameter has
> the value null; this is an example of weakening the precondition.
> Likewise for container insertion and deletion, when the Count is 0,
> the operation should do nothing.  It certainly should not raise exception.
> I thought Ada95 settled such debates.

This is a load of rubbish (which Bob explained better than I could). I can't
argue with the general outline, but you make it sound far more cut-and-dried
than it really is. You essentially are suggesting that any operation for which
there is anything remotely resembling possible semantics should in fact accept
that semantics and allow the operation.

But that flies in the face of strong typing (especially Ada-style strong
typing). The lesson of PL/1 was that implicitly converting everything simply is
a bad idea. For instance, Ada does not automatically convert integers to floats,
even though the result is well-defined.

You've repeatedly made this argument, and it has just as repeatedly been shot
down. Ada is not all about the widely permissive approach; it is about making a
balance between utility and error detection. If we don't get it wrong once in a
while (like the Ada 83 example you mentioned), we aren't trying hard enough!

The fact that Unchecked_Deallocation does nothing when the parameter is null is
a bug in my view; it comes about because we didn't have a way at the time to
reasonably specify that (null exclusions are far more recent), and from the
desire to null the result pointer.

You said: "Likewise for container insertion and deletion, when the Count is 0,
the operation should do nothing.  It certainly should not raise exception." But
that is not possible for the Insert with an "out" Position parameter. The
parameter has to be set to something, and that is definitely *not* doing
nothing. Doing nothing would leave the parameter uninitialized, which I hope we
all agree is not a very good idea.

Moreover, the postcondition of the existing routine is that Position designates
the newly-allocated element after the call. That is a postcondition that cannot
be met for Count = 0; thus raising an exception is the only possible solution.

Well, there is one other solution, which is changing the postcondition to
something much less useful. (I would guess that more than 95% of the Inserts
returning a Position is using it for future references to the new element.) And
this is precisely the sort of case where you are much more likely to be covering
up a bug (or creating a new one) than providing some sort of useful semantics.

In any case, the point is that this is not something that has a clear solution,
so it is too late to fix it now. And at least leaving it unspecified allows you
to keep doing what you want until we make a final decision on it.

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

From: Robert Dewar
Sent: Monday, May  2, 2011  4:44 AM

>> I also ran 3787 ACATS tests, and got zero failures in both
>> experiments.
>
> Sadly, there aren't any container tests in the ACATS, so I wouldn't
> expecy any results from any such test. (You'd have gotten the same
> results if you made declaring a Vector raise Tasking_Error. :-)

And even in our giant test suite there aren't that many container tests outside
purpose written ones, the containers are not yet in wide use.

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

From: Robert Dewar
Sent: Monday, May  2, 2011  4:48 AM

Generally I prefer to raise exceptions than ignore situations which might be
error cases. I agree for example that UD on a null pointer should obviously
raise an exception.

If you have a situation which might or might not be an error, best to err on the
side of raising an exception. it is easy enough (and good documentation) to
explicitly test for the case, or to handle the resulting exception if it is NOT
an error with an explanation of why it is not an error in this case. We are used
to things like

      begin
         Close (File);

      exception
         -- Just ignore close if it fails, we don't care in
         -- this case, since there is nothing we can do about
         -- it at this stage.

         null;
      end;

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

From: Bob Duff
Sent: Monday, May  2, 2011  8:39 AM

> There is no existing code other than in tests (according to Bob)...

Well, that's just in our test suite, which contains a whole lot of code from
customer bug reports.  You can deduce that it's rare, but you can't deduce that
there's NO such code -- maybe there were no bugs in this area (good work,
Matt!), so nobody sent bug reports.

>... -- and I
> believe that. The Count parameter is something that is rarely used,
>and the  Insert that returns a cursor is fairly uncommon, and the use
>of them  together is going to be non-existent.

Yeah, probably -- or close to it.

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

From: Matthew Heaney
Sent: Monday, May  2, 2011  8:43 AM

> Generally I prefer to raise exceptions than ignore situations which
> might be error cases. I agree for example that UD on a null pointer
> should obviously raise an exception.

But if X is null, then the post-condition is already satisfied, so it would not
make any sense to raise an exception.  (Obviously!)  The current behavior of UD
is exception correct (it has "Dijkstra semantics").

Likewise for a file Close operation: if the file is already closed, then the
Close operation should do nothing, since the post-condition is already
satisfied.  It makes little sense for the caller to duplicate a test that the
operation itself must perform (such checks at the point of call just add noise
to the text of the program), so it is perfectly appropriate to weaken the
precondition.

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

From: Bob Duff
Sent: Monday, May  2, 2011  8:50 AM

> Generally I prefer to raise exceptions than ignore situations which
> might be error cases. I agree for example that UD on a null pointer
> should obviously raise an exception.
>
> If you have a situation which might or might not be an error, best to
> err on the side of raising an exception. it is easy enough (and good
> documentation) to explicitly test for the case, or to handle the
> resulting exception if it is NOT an error with an explanation of why
> it is not an error in this case. We are used to things like
>
>       begin
>          Close (File);
>
>       exception
>          -- Just ignore close if it fails, we don't care in
>          -- this case, since there is nothing we can do about
>          -- it at this stage.
>
>          null;
>       end;

I agree with all of the above, but as I said, I don't find "null" to be
analogous to "0" in any way.  I don't find closed file handles to be analogous
to 0, either.

We don't want to forbid zero-length arrays (as C does), zero-trip loops (as
Fortran does (or did?) I think), or zero-length positional array aggregates (as
Ada does).  It's all bad language design. If you want to count how many elements
to Insert, then 0 makes sense.  Raising an exception would just be a tripping
hazard.

Anyway, Vectors work as Matt wants.  Randy thinks that's by accident, but I
doubt that.  Only List has questionable wording. (And now, Trees, but I've
mostly ignored the design of those.)

Note that you can also insert a Vector into a Vector -- I'd be surprised if
inserting a zero-length Vector was considered an error.

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

From: Bob Duff
Sent: Monday, May  2, 2011  8:54 AM

> But if X is null, then the post-condition is already satisfied, so it
> would not make any sense to raise an exception.  (Obviously!)  The
> current behavior of UD is exception correct (it has "Dijkstra semantics").
>
> Likewise for a file Close operation: if the file is already closed,
> then the Close operation should do nothing, since the post-condition
> is already satisfied.  It makes little sense for the caller to
> duplicate a test that the operation itself must perform (such checks
> at the point of call just add noise to the text of the program), so it
> is perfectly appropriate to weaken the precondition.

I disagree with both of the above, and especially the "Obviously!" part.
And yet, I agree with you about Count => 0.

Therefore, I suggest the above line of argument is unfruitful, and you should
drop it.  ;-)

Stick to arguments about how 0 makes perfect sense when counting things.

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

From: Matthew Heaney
Sent: Monday, May  2, 2011  10:41 AM

I will heed your sage advice.  &^)

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

From: Randy Brukardt
Sent: Monday, May  2, 2011  2:00 PM

...
> We don't want to forbid zero-length arrays (as C does), zero-trip
> loops (as Fortran does (or did?) I think), or zero-length positional
> array aggregates (as Ada does).  It's all bad language design.
> If you want to count how many elements to Insert, then 0 makes sense.
> Raising an exception would just be a tripping hazard.

I'm not going to argue that in terms of the other Inserts and Deletes (those
that don't return handles), because it is what it is. I can see reasons for
allowing them, and in any case, we're not changing their behavior. But this
isn't that case...

> Anyway, Vectors work as Matt wants.  Randy thinks that's by accident,
> but I doubt that.  Only List has questionable wording.
> (And now, Trees, but I've mostly ignored the design of those.)

I still disagree. The problem isn't really the zero-length insert, it is the
fact that you get a handle back from that insert that fails the postcondition
(that is, it doesn't point at a new element, or possibly an element at all).

If you intend to do anything with the result, the fact that it is not a new
element is likely to cause trouble -- most likely, you'll have to test that the
count is not zero. So how is allowing this helping?

Matt wants to "solve" this by changing the postcondition. But the problem with
that is that the new postcondition is irrelevant to 99% of the uses of this
routine - for those you want a cursor of a new element only!

You've all convinced me that this routine shouldn't have a Count parameter at
all; it does such violence to the important postcondition that it isn't worth
it, especially given that it will be used very, very rarely.

> Note that you can also insert a Vector into a Vector -- I'd be
> surprised if inserting a zero-length Vector was considered an error.

I actually find zero-length vectors a different case than inserting zero
elements. A zero-length vector is *something* (the zero-length vector) - it has
a size, bounds, etc - only the elements are empty, the data structure still
exists. (Indeed, Ada doesn't actually allow aliased zero-sized structures,
although most compilers ignore this). A count of zero is nothing at all, it has
no properties, and executing code to deal with that is misleading to the reader.

In any case, the case in point is not an argument about zero. If this routine
was doing nothing I would not be complaining; the problem is that it is
returning a value -- and that value is much more likely to be used incorrectly
(as if it is a new element) than as an insertion point [which is what Matt
claims it is]. (Very, very few applications care about insertion points after an
insertion.)

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

From: Matthew Heaney
Sent: Monday, May  2, 2011  5:12 PM

> I still disagree. The problem isn't really the zero-length insert, it
> is the fact that you get a handle back from that insert that fails the
> postcondition (that is, it doesn't point at a new element, or possibly
> an element at all).

Of course it satisfies the post-condition!  The problem is that the
*description* of the post-condition is wrong, not the post-condition itself.
(If we are debating what the post-condition is, that just proves my point.)

> If you intend to do anything with the result, the fact that it is not
> a new element is likely to cause trouble -- most likely, you'll have
> to test that the count is not zero. So how is allowing this helping?

The return value always indicates the "position of what was inserted".
It does not matter that what was inserted happened to be the empty set.

> Matt wants to "solve" this by changing the postcondition.

You can't simultaneously argue that the specification is ambiguous, but then
also argue that I want to change the post-condition!

Is it you who is advocating for a radical change in the post-condition.
  I want to preserve the existing post-condition (specifically: when Count is 0,
  the value Before is returned as the value of Position), but add wording to the
  RM to state this behavior explicitly, so that there is no ambiguity.

> But the problem
> with that is that the new postcondition is irrelevant to 99% of the
> uses of this routine - for those you want a cursor of a new element only!

The cursor return value always designates the insertion position.  It has a
well-defined value irrespective of the number of items inserted (including 0).
The problem is the wording of the RM, which does not specify explicitly (though
it does implicitly) what value is returned for Position when the number of items
inserted is 0.  Raising an exception in this case would be a radical change of
semantics.

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

From: Randy Brukardt
Sent: Monday, May  2, 2011  7:02 PM

> > I still disagree. The problem isn't really the zero-length insert,
> > it is the fact that you get a handle back from that insert that
> > fails the postcondition (that is, it doesn't point at a new element,
> > or possibly an element at all).
>
> Of course it satisfies the post-condition!  The problem is that the
> *description* of the post-condition is wrong, not the post-condition
> itself.  (If we are debating what the post-condition is, that just
> proves my point.)

It would be helpful if you actually argued from the language of the Standard and
not from what you would like it to be. At this point, more than 4 years after
the standardization of Ada 2005 completed (in 2007), the operations do what the
language says they do, not what you wished they would do, or you intended them
to do, or I wished they would do, or anything else. Got it??

The postcondition for this insertion operation is: "Position designates the
first newly-inserted element." And that's it. Making it be something else is a
change.

I'd argue that if you had tried to make it something else, people would have
objected. But we can't know that now.

> > If you intend to do anything with the result, the fact that it is
> > not a new element is likely to cause trouble -- most likely, you'll
> > have to test that the count is not zero. So how is allowing this helping?
>
> The return value always indicates the "position of what was inserted".
> It does not matter that what was inserted happened to be the empty set.

But that's between useless and actively harmful for the most common use-cases
for insertions. And this is the point that you (and Bob for that matter)
continue to ignore. So long as you do that, we cannot have a rational
discussion. (And I need to be doing other things.) But let me spell it out for
you in excruciating detail, so you can continue to ignore that.

Most likely uses for the cursor designating a newly created element (or an
insertion point, if you prefer) immediately after an Insert operation:

   (A) Nothing. [80% of uses.] (This is the case where the element is inserted in a data structure and no immediate use is needed. This is by far the most common.)
   (B) Use to finish initialization of the element. [9% of uses.]
   (C) Store in another data structure. [7% of uses.]
   (D) Use as marker after which to insert other elements. [3% of uses.]
   (E) Use as marker before which to insert other elements. [1% of uses.]
   (F) Something else. [0% of uses.]

[The percentages are based on my experience using data structures in my code.
But the exact numbers aren't that important; any use of data structures will
follow a similar pattern.]

Anyway, (A) is handled nicely by the Insert routines that don't return a
Position. That's why they exist, because that is such a common operation. We
don't need to discuss (A) further.

Similarly, there is nothing intelligent we can say about (F). I'm unconvinced
that anything actually falls into that category, but in any case we can't make
any analysis of it.

Cases (B) through (E) make use of the Insert routine with a Position parameter
to retrieve the cursor designating a newly created element. (Note that I'm not
unaware that (D) could be implemented by using the Insert without a parameter
and reusing the initial insertion point instead. I don't think most programmers
will think of that [I didn't initially] as it is backwards to common use.
Whether or not (D) is included doesn't make much difference to the final
result.]

For (B) through (E), if Count = 1, all is well. The cursor that is retrieved
through Position is directly useful (you'd have to use Next(Position) to get the
insertion position, but that is obvious and no problem.)

OTOH, when the Count greater than 1, (B) doesn't work without writing a loop
after the Insert call. Indeed, it is better to implement (B) for an unknown
count by putting an Insert with a count of 1 into a loop, as that is less
confusing.

(C) only works on rare occasions when Count is greater than 1 (it depends on
    whether individual elements need to be inserted into the other structure or
    just the head of a sublist; the latter is much more likely to be rare).

(D) only works by using an explicit loop as well. Avoiding the Insert returning
    Position is a better plan here -- if you can figure it out.

(E) works directly when the Count is greater than 1.

Now let's consider the Count = 0 cases, assuming your semantics. (B) will
attempt to initialize an element that is already initialized (or try to
initialize No_Element). To avoid that, one would need to write a conditional
testing the Count. Failure to do that causes very serious bugs.

(C) will insert some existing element (or No_Element) into some other data
    structure. No_Element might be harmless, but inserting some random other
    element into a data structure is going to be a nasty bug.

(D) will point at the wrong place unless a loop was used. Another nasty problem.

(E) will work, of course.

The net effect is only 1 out of 20 of the uses will work as expected with Count
= 0; it's only slightly better (depending on how rare (C) without a loop is).

Indeed, what this analysis shows is that Insert returning Position should not
have a Count parameter; since well over 50% of the time (and much closer to 90%
I suspect) you shouldn't use it and write a loop instead. If you don't do that,
you have a bug waiting to happen in those cases. The handful of cases that work
are so rare (using the Count parameter in any form is likely to happen in less
than 10% of the code) that there is no real value to supporting them specially.

If we had thought about this routine carefully, it would not have a Count
parameter at all. That would be my current recommendation to solve this problem
- remove the Count parameter. In the very unlikely case that it was used, it
would be detected at compile-time.

In the absence of that, I still think that Count = 0 is dangerous. It's more
dangerous that Count > 1 (because it puts incorrect items into data structures);
moreover, no one is likely to think about the consequences of it to their data
structures.

I want these containers to be as idiot-proof as possible, because all of us are
idiots from time-to-time. This Count parameter is just plain dangerous for the
common uses. And we don't want the containers full of rarely used
routines/capabilities, because those make it much harder to understand programs
using the containers.

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

From: Bob Duff
Sent: Monday, May  2, 2011  8:09 PM

> It would be helpful if you actually argued from the language of the
> Standard and not from what you would like it to be. At this point,
> more than 4 years after the standardization of Ada 2005 completed (in
> 2007), the operations do what the language says they do, not what you
> wished they would do, or you intended them to do, or I wished they would do, or anything else. Got it??
>
> The postcondition for this insertion operation is: "Position
> designates the first newly-inserted element." And that's it. Making it
> be something else is a change.

Matt is correctly stating the semantics of Vectors as stated in the RM.
Randy is correctly stating the semantics of Lists as stated in the RM.

Randy, please don't accuse Matt of ignoring the RM (for Vectors).
Matt, please don't accuse Randy of ignoring the RM (for Lists).

It would be helpful (to me anyway) if you guys mentioned the paragraph(s) you're talking about.  There are dozens of Insert procedures, and I tend to lose track.  (Sorry, I'm sure you've already done that, but it would be helpful to repeat it when you say,
 as above, "The postcondition for this insertion operation..." -- which one?!)

>...But let me spell
> it out for you in excruciating detail, so you can continue to ignore that.

I'm not ignoring you, Randy.  But I think you didn't split up the cases in the best way.  I think there are two cases:

    Count = 1 statically, and by default.  We all know what that does,
    and we all agree this is the most common case, and you said it
    should be the ONLY case, and I'd probably agree with that.
    In this case you can poke at Position.

    The program calculates the number of things to insert, N, which is
    probably dynamic.  And then Insert(..., Count => N).  In this case,
    you need to do some sort of loop, poking at Position N times,
    incrementing it each time.  If N = 17, you poke 17 things.  If
    N = 0, the loop does nothing.  Either way, you end up with a
    position after all the inserted items.  And you can insert some more
    there.  This is the way Vectors work according to the RM, and Matt
    would like Lists (and Trees?) to work the same way.

Note that the N=17 case is similar to the N=0 case, in that you cannot assume
Position points to THE (single thing) that was inserted. It points to a sequence
of them, which could be zero-length.

I snipped all your talk about A, B, C, D, E, F, but I read it and I read it
carefully.  I'm not ignoring all that, but I'm asking you to consider my two
cases above as an alternative view.

Perhaps it would have been clearer if Before and Position were a single 'in out'
parameter?

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

From: Randy Brukardt
Sent: Monday, May  2, 2011  9:00 PM

> > It would be helpful if you actually argued from the language of the
> > Standard and not from what you would like it to be. At this point,
> > more than 4 years after the standardization of Ada 2005 completed
> > (in 2007), the operations do what the language says they do, not
> > what you wished they would do, or you intended them to do, or I
> > wished they would do, or anything else. Got it??
> >
> > The postcondition for this insertion operation is: "Position
> > designates the first newly-inserted element." And that's it. Making
> > it be something else is a change.
>
> Matt is correctly stating the semantics of Vectors as stated in the RM.
> Randy is correctly stating the semantics of Lists as stated in the RM.
>
> Randy, please don't accuse Matt of ignoring the RM (for Vectors).
> Matt, please don't accuse Randy of ignoring the RM (for Lists).

Vectors is irrelevant. Matt originally asked about the multiway trees, and I
noted that it is identical to the lists. The Vectors is completely different
because it is defined in terms of a calculated index, something that makes no
sense in the context of any other container that we have.

Moreover, there is no Position parameter in the vector inserts that take
indexes, so it is impossible to see any intent from that. The Cursor version
uses a mathematical formula to figure out the result, and it appears to me to be
an accident that it happens that way.

> It would be helpful (to me anyway) if you guys mentioned the
> paragraph(s) you're talking about.  There are dozens of Insert
> procedures, and I tend to lose track.  (Sorry, I'm sure you've already
> done that, but it would be helpful to repeat it when you say, as
> above, "The postcondition for this insertion operation..." -- which
> one?!)

A.18.3(92/2) is where this quote comes from. A.18.3(94/2) should be the same,
but it doesn't even mention Position! Yikes.

> >...But let me spell
> > it out for you in excruciating detail, so you can continue to ignore that.
>
> I'm not ignoring you, Randy.  But I think you didn't split up the
> cases in the best way.  I think there are two cases:
>
>     Count = 1 statically, and by default.  We all know what that does,
>     and we all agree this is the most common case, and you said it
>     should be the ONLY case, and I'd probably agree with that.
>     In this case you can poke at Position.
>
>     The program calculates the number of things to insert, N, which is
>     probably dynamic.  And then Insert(..., Count => N).  In this case,
>     you need to do some sort of loop, poking at Position N times,
>     incrementing it each time.  If N = 17, you poke 17 things.  If
>     N = 0, the loop does nothing.  Either way, you end up with a
>     position after all the inserted items.  And you can insert some more
>     there.  This is the way Vectors work according to the RM, and Matt
>     would like Lists (and Trees?) to work the same way.
>
> Note that the N=17 case is similar to the N=0 case, in that you cannot
> assume Position points to THE (single thing) that was inserted.
> It points to a sequence of them, which could be zero-length.
>
> I snipped all your talk about A, B, C, D, E, F, but I read it and I
> read it carefully.  I'm not ignoring all that, but I'm asking you to
> consider my two cases above as an alternative view.

That is certainly an alternative view; the problem with it is that is much more
likely to be wrong that using the Count = 1 version of the routine and putting
that in the loop itself. (That's because you have an additional
point-of-failure, the call to advance the cursor between iterations -- if you
forget that, you still have a mess. It's rather like forgetting to put Ptr :=
Ptr.Next at the bottom of a loop.)

> Perhaps it would have been clearer if Before and Position were a
> single 'in out' parameter?

We think we considered that, but it would require using a variable and then
initializing it in the common case that you want to insert at the end.

Anyway, you've convinced me that I need to lobby to completely remove the Count
parameter from this routine, because it is unsafe and unnecessary. And that and
any other change has to wait until after Ada 2012, so let's drop this discussion
for now.

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

From: Bob Duff
Sent: Monday, May  2, 2011  9:31 PM

> that and any other change has to wait until after Ada 2012, so let's
> drop this discussion for now.

OK.

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

Questions? Ask the ACAA Technical Agent