!standard A.18.3(92/2) 11-07-28 AI05-0257-1/02 !standard A.18.3(94/2) !standard A.18.10(0) !class binding interpretation 11-06-16 !status Amendment 2012 11-07-28 !status ARG Approved 12-0-0 11-06-25 !status work item 11-06-16 !status received 11-04-13 !priority Low !difficulty Easy !subject Insert returning a Position !summary If Count = 0 for a container Insert subprogram that has a Position parameter, the Position parameter is set to the value of the Before parameter by the call. !question 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. !recommendation (See Summary.) !wording Add an AARM Ramification after A.18.2(162/2): If Count equals 0, Position will designate the element designated by Before, rather than a newly inserted element. Otherwise, Position will designate the first newly inserted element. Modify part of A.18.3(92/2), A.18.10(143/3), and A.18.10(145/3): Position designates the first newly-inserted element{, or if Count equals 0, then Position is assigned the value of Before}. Add to A.18.3(94/2): Position designates the first newly-inserted element, or if Count equals 0, then Position is assigned the value of Before. Remove AARM note A.18.10(143.a/3). !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. The description of the other routines is more likely to be what the caller expects (in that following operations are likely to treat Position as a new node). Removing the Count parameter altogether from the Insert routines that return a Position would be the best solution (it is much less error-prone). A code survey shows that virtually every use of this call uses Count = 1, either by default or explicitly. Still, that is considered too incompatible for about 2/3rds of the ARG members. Thus we defined Position to equal Before when Count equals 0. Any other solution would either make the vector case inconsistent in behavior with other containers, or potentially change the behavior of existing programs without any indication of a change (there probably are no such programs, but no one likes the "probably" in that statement). !corrigendum A.18.3(92/2) @drepl @xindent @dby @xindent !corrigendum A.18.3(94/2) @drepl @xindent @dby @xindent !corrigendum A.18.10(0) @dinsc Force a conflict; real text found in the conflict file. !ACATS test None needed. !ASIS No ASIS impact. !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 discovered, 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. **************************************************************** From: Randy Brukardt Sent: Saturday, June 25, 2011 8:51 AM A.18.2(156) and (162) do not need any change. Add a Ramification after 162: “Thus, if Count equals 0, Position will equal old value of Before.” A.18.3(92) and (94) should say: “Position designates the first newly-inserted element{, or if Count equals 0, then Position is assigned the value of Before}.” A.18.10(143/3) and (145/3) also should use this. Remove A.18.10(143.a/3). ****************************************************************