CVS difference for ais/ai-30302.txt
--- ais/ai-30302.txt 2005/08/12 05:11:04 1.18
+++ ais/ai-30302.txt 2005/10/31 05:18:52 1.19
@@ -31266,398 +31266,1299 @@
****************************************************************
-From: Matthew Heaney
-Sent: Friday, April 2, 2005 9:31 AM
+From: Christoph Grein
+Sent: Wednesday, September 21, 2005 2:11 AM
-****************************************************************
+A.18.7(3/2..5/2) contain a lot of redundant wording. This has to be
+completely reworked.
+---
+A.18.7(18/2) The predefined "=" operator for type Cursor should return
+True if both cursors {designate}[or] No_Element, or designate the same
+element in the same container.
-From: Matthew Heaney
-Sent: Friday, April 2, 2005 9:31 AM
+Why does the wording use "should" and not "shall"?
****************************************************************
-From: Matthew Heaney
-Sent: Friday, April 2, 2005 9:31 AM
+From: Randy Brukardt
+Sent: Wednesday, September 21, 2005 10:21 PM
-****************************************************************
+> A.18.7(3/2..5/2) contain a lot of redundant wording. This has to be
+> completely reworked.
-From: Matthew Heaney
-Sent: Friday, April 2, 2005 9:31 AM
+John Barnes noticed that; the first paragragh (3) is correct; the others are
+previous attempts at the wording that got left behind for some reason.
-****************************************************************
+> ---
+> A.18.7(18/2) The predefined "=" operator for type Cursor should return
+> True if both cursors {designate}[or] No_Element, or designate the same
+> element in the same container.
-From: Matthew Heaney
-Sent: Friday, April 2, 2005 9:31 AM
+John Barnes had noticed this, too. (He found about two dozen typos in the
+Containers packages.) He had suggested "are" No_Element, as No_Element is a
+value and not something that can be designated. (It's similar to null).
-****************************************************************
+> Why does the wording use "should" and not "shall"?
-From: Matthew Heaney
-Sent: Friday, April 2, 2005 9:31 AM
+Excellent question. Most likely, it's a brain freeze caused by too many
+hours of reading/editing the definitions of functions. But "shall" is wrong,
+too; it's used for legality rules and this certainly isn't one. The rule
+should just be stated declaratively:
-****************************************************************
+The predefined "=" operator for type Cursor returns True if both cursors are
+No_Element, or designate the same element in the same container.
-From: Matthew Heaney
-Sent: Friday, April 2, 2005 9:31 AM
+That rule occurs in a number of places (for every package).
****************************************************************
From: Matthew Heaney
-Sent: Friday, April 2, 2005 9:31 AM
+Sent: Thursday, April 28, 2005 7:01 PM
-****************************************************************
+I think the name of the function for computing the hash value of a wide
+unbounded string is:
-From: Matthew Heaney
-Sent: Friday, April 2, 2005 9:31 AM
+ada.strings.wide_unbounded.wide_hash
+
+but I wasn't sure. Can someone confirm that this is indeed the name? It's
+not ada.strings.wide_unbounded.hash, right?
****************************************************************
From: Matthew Heaney
-Sent: Friday, April 2, 2005 9:31 AM
+Sent: Thursday, April 28, 2005 9:32 PM
-****************************************************************
+The operation Replace, declared like this
-From: Matthew Heaney
-Sent: Friday, April 2, 2005 9:31 AM
+procedure Replace
+ (Container : in out Set;
+ Key : in Key_Type;
+ New_Item : in Element_Type);
-****************************************************************
+in the nested package Generic_Keys of the sets containers packages, is
+superfluous, confusing, and unsafe. It should be removed from the container
+API.
-From: Matthew Heaney
-Sent: Friday, April 2, 2005 9:31 AM
+The issue is that the set already has a Replace operation, declared like
+this:
-****************************************************************
+procedure Replace
+ (Container : in out Set;
+ New_Item : in Element_Type);
-From: Matthew Heaney
-Sent: Friday, April 2, 2005 9:31 AM
+An element has all the information necessary for it to be inserted into the
+set. The additional Key parameter for Generic_Keys.Replace confers no
+benefit, since the New_Item parameter already has a key (really, key-part).
+There would never be a reason to call Generic_Keys.Replace, since
+Sets.Replace does everything you would ever need.
-****************************************************************
+What makes Generic_Keys.Replace so pernicious is that the Key parameter can
+have a key value different from the key-part of New_Item.
-From: Matthew Heaney
-Sent: Friday, April 2, 2005 9:31 AM
+For example, if I have an element with an integer key-part, like this:
-****************************************************************
+ type ET is record
+ Key : Integer;
+ Payload : Payload_Type;
+ end record;
-From: Matthew Heaney
-Sent: Friday, April 2, 2005 9:31 AM
+then it would be possible for one to say:
-****************************************************************
+ Replace
+ (Container => My_Set,
+ Key => 42,
+ New_Item => ET'(Key => 1776, Payload));
-From: Matthew Heaney
-Sent: Friday, April 2, 2005 9:31 AM
+But this doesn't make any sense, since Replace.Key (42) is different from
+Replace.New_Item.Key (1776).
-****************************************************************
+What's even more wacky is that Replace searches according to the Key,
+instead of according to the New_Item. What it then does is call the equally
+evil Replace_Element operation with the cursor it finds, and attempts to
+replace the element at that node with New_Item. But since New_Item.Key is
+different from the element with Key, this means you get all the semantic
+headaches associated with attempting to change the equivalence class of an
+element.
-From: Matthew Heaney
-Sent: Friday, April 2, 2005 9:31 AM
+The operation Generic_Keys.Replace is confusing, error-prone, and
+superfluous. Please, please get rid of it...
****************************************************************
-From: Matthew Heaney
-Sent: Friday, April 2, 2005 9:31 AM
+From: Pascal Leroy
+Sent: Friday, April 29, 2005 8:00 AM
-****************************************************************
+I agree with you. This is very strange semantics. Even assuming that it
+can come handy sometimes (I can't think of any example at the moment) it
+would still be a good idea to remove it from the API, because the weird
+semantics is likely to cause bugs.
-From: Matthew Heaney
-Sent: Friday, April 2, 2005 9:31 AM
+At any rate, it's defined by a 1-line equivalence in the RM, so users who
+need this behavior can easily program it themselves.
****************************************************************
From: Matthew Heaney
-Sent: Friday, April 2, 2005 9:31 AM
+Sent: Thursday, April 28, 2005 10:08 PM
-****************************************************************
+The description of Update_Element_Preserving_Key says:
-From: Matthew Heaney
-Sent: Friday, April 2, 2005 9:31 AM
+START OF QUOTE:
-****************************************************************
+After Process.all returns, Update_Element_Preserving_Key checks if K
+determines the same equivalence class as that for the new element; if not,
+the element is removed from the set and Program_Error is propagated.
-From: Matthew Heaney
-Sent: Friday, April 2, 2005 9:31 AM
+END OF QUOTE.
-****************************************************************
+MJH:
-From: Matthew Heaney
-Sent: Friday, April 2, 2005 9:31 AM
+What exactly does it mean for the element to be "removed from the set"?
+Does this mean that it gets deallocated? Or that it must not get
+deallocated?
-****************************************************************
+I don't think we can simply deallocate the element, since we can't know what
+the consequences are. It would be bad enough for an object to simply
+disappear, but suppose the element type is controlled? Controlled finalize
+might do all kinds of unpleasent things, if it is called unexpectedly.
-From: Matthew Heaney
-Sent: Friday, April 2, 2005 9:31 AM
+So I think the description above is telling me, literally, that the element
+is removed from the set, but without being deallocated. This will leak
+memory however, since once a node has been unlinked from there's no way to
+deallocate it. (Actually, it might be possible to mark the node as having
+been unlinked from the set, and then liberalize Delete to handle these
+special nodes. But that would depend on the user to Delete the node in
+response to the Program_Error exception.)
-****************************************************************
+I've been doing this:
-From: Matthew Heaney
-Sent: Friday, April 2, 2005 9:31 AM
+ if K < E
+ or else K > E
+ then
+ ... --remove node from set
+ else
+ return;
+ end if;
-****************************************************************
+I think I'm being too pessimistic in the error case. Even if E (its new
+value) is not in the same equivalence class as K (its old value), it doesn't
+necessarily mean that E is the same equivalence class as another element.
-From: Matthew Heaney
-Sent: Friday, April 2, 2005 9:31 AM
+Maybe the correct way to handle this is:
-****************************************************************
+ if K < E
+ or else K > E
+ then
-From: Matthew Heaney
-Sent: Friday, April 2, 2005 9:31 AM
+ if Find (Container, E) = null then
+ return; -- E is dif't from K, but also from its neighbors
+ end if;
-****************************************************************
+ ... --remove E from set, since new value is already in set
-From: Matthew Heaney
-Sent: Friday, April 2, 2005 9:31 AM
+ else
+ return;
+ end if;
-****************************************************************
+Even if E does change its key, it's a benign change, since it's in a
+equivalence class that is different from any other element.
-From: Matthew Heaney
-Sent: Friday, April 2, 2005 9:31 AM
+BTW: Are you still sure you want to name this operation
+Update_Element_Preserving_Key? Besides being really verbose, we can see
+above that it's not strictly necessary to preserve the key. The thing we
+really want to preserve is for the element to remain in a unique equivalence
+class.
-****************************************************************
+As an aside, I wrote a little word-frequency counter with a set, and used
+Update_Element_Preserving_Key:
-From: Matthew Heaney
-Sent: Friday, April 2, 2005 9:31 AM
+<http://charles.tigris.org/source/browse/charles/src/ai302/examples/wordfreq
+2/wordfreq_types.adb?rev=1.1&view=markup>
****************************************************************
-From: Matthew Heaney
-Sent: Friday, April 2, 2005 9:31 AM
+From: Pascal Leroy
+Sent: Friday, April 29, 2005 7:42 AM
-****************************************************************
+> I don't think we can simply deallocate the element, since we
+> can't know what the consequences are. It would be bad enough
+> for an object to simply disappear, but suppose the element
+> type is controlled? Controlled finalize might do all kinds
+> of unpleasent things, if it is called unexpectedly.
-From: Matthew Heaney
-Sent: Friday, April 2, 2005 9:31 AM
+The phrase "remove from the set" is used all over the place, not only in
+Update_Element_Preserving_Key, and yes, the element is finalized.
+Consider the (simpler) case of Delete, which also says "remove from the
+set". When you first called Insert to put an element in the set, a *copy*
+of the value passed in was stored in the set. When Delete is called, that
+*copy* is finalized. If the element is controlled, Finalize will be
+called, and it should do the right thing, but I don't see this as an
+"unexpected" call, and I don't see why Finalize would do "unpleasant
+things".
-****************************************************************
+Obviously leaking memory is not an option, so Dewar's rule applies.
-From: Matthew Heaney
-Sent: Friday, April 2, 2005 9:31 AM
+> I've been doing this:
+>
+> if K < E
+> or else K > E
+> then
+> ... --remove node from set
+> else
+> return;
+> end if;
+>
+> I think I'm being too pessimistic in the error case. Even if
+> E (its new
+> value) is not in the same equivalence class as K (its old
+> value), it doesn't necessarily mean that E is the same
+> equivalence class as another element.
-****************************************************************
+You are not being pessimistic, you are implementing exactly the wording of
+the RM, and the purpose of this operation is to update the element without
+touching the key. This has been discussed ad nauseam for many meetings, I
+see no point in trying to change the semantics now.
-From: Matthew Heaney
-Sent: Friday, April 2, 2005 9:31 AM
+> BTW: Are you still sure you want to name this operation
+> Update_Element_Preserving_Key?
+
+Yes, because that's what it does.
****************************************************************
From: Matthew Heaney
-Sent: Friday, April 2, 2005 9:31 AM
+Sent: Friday, April 29, 2005 8:05 AM
-****************************************************************
+> The phrase "remove from the set" is used all over the place,
+> not only in Update_Element_Preserving_Key, and yes, the
+> element is finalized.
-From: Matthew Heaney
-Sent: Friday, April 2, 2005 9:31 AM
+OK, that clears things up. I just wanted to make sure I was interpreting
+the AI correctly.
****************************************************************
From: Matthew Heaney
-Sent: Friday, April 2, 2005 9:31 AM
+Sent: Thursday, April 28, 2005 10:21 PM
-****************************************************************
+The operation Sets.Replace_Element is declared like this:
-From: Matthew Heaney
-Sent: Friday, April 2, 2005 9:31 AM
+procedure Replace_Element
+ (Container : in Set;
+ Position : in Cursor;
+ By : in Element_Type);
-****************************************************************
+Just a quick note to bring up a potential issue with the formal Element_Type
+parameter named "By". I had originally used that name in order to match the
+similar operation Replace_Element in Ada.Strings.*, but for every other
+container operation we either use Item or New_Item.
-From: Matthew Heaney
-Sent: Friday, April 2, 2005 9:31 AM
+I just wanted the ARG to affirm the decision to name the Replace_Element
+formal parameter "By" instead of something else (say, "New_Item").
****************************************************************
-From: Matthew Heaney
-Sent: Friday, April 2, 2005 9:31 AM
+From: Pascal Leroy
+Sent: Friday, April 29, 2005 8:03 AM
+
+Consistency with Ada.Strings is of dubious value, but consistency of the
+various operations on sets is important, so yes, I'd prefer New_Item.
****************************************************************
-From: Matthew Heaney
-Sent: Friday, April 2, 2005 9:31 AM
+From: Marius Amado Alves
+Sent: Friday, June 17, 2005 9:52 AM
-****************************************************************
+How about this "simple thing" then?
-From: Matthew Heaney
-Sent: Friday, April 2, 2005 9:31 AM
+Include my "An Index to Ada.Containers" as an informative Note or Annex.
-****************************************************************
+http://www.softdevelcoop.org/software/ada_containers/
-From: Matthew Heaney
-Sent: Friday, April 2, 2005 9:31 AM
+At least one other person on this list backs me up:
-****************************************************************
+"Very nice table. It's certainly something one might expect to come
+with a library, given Stroustrup's similar tables in TC++PL."
+(Georg Bauhaus, 21 April 2005)
-From: Matthew Heaney
-Sent: Friday, April 2, 2005 9:31 AM
+The Index is programmatically generated from the AI text, so its
+production is really "simple," its correction guaranteed, and I'd be
+more than glad to offer the material under any required conditions.
****************************************************************
From: Matthew Heaney
-Sent: Friday, April 2, 2005 9:31 AM
+Sent: Friday, June 17, 2005 10:11 AM
-****************************************************************
+This is a specious argument. TC++PL is a textbook, not an ISO standard
+reference manual. It does not have the same constraints (e.g. page
+count) that the RM does.
-From: Matthew Heaney
-Sent: Friday, April 2, 2005 9:31 AM
+(Actually, the pages of my expensive, hard-bound "special edition"
+TC++PL are falling out, yet my copy of the Ada95 Consilidated RM is just
+fine. An analog of the languages, perhaps?)
****************************************************************
-From: Matthew Heaney
-Sent: Friday, April 2, 2005 9:31 AM
+From: Marius Amado Alves
+Sent: Friday, June 17, 2005 10:41 AM
-****************************************************************
+Isn't TC++PL, like K&R, the original RM of the respective language
+(something that Ada did not have)? Have the TC++PL tables not made
+their way into the ISO text?
-From: Matthew Heaney
-Sent: Friday, April 2, 2005 9:31 AM
+I mean, C programmers are very likely to use K&R *and* the respective
+ISO text, C++ programmers are very likely to use TC++PL *and* the
+respective ISO text, but, as has been reported, typical Ada programmers
+go only for their sole existing RM, the ISO text.
+Page constraints. The Index is roughly 10-page long. On the one hand,
+it's 10 pages. On the other hand, it reveals how Ada.Containers is long
+and complex enough to warrant it.
+
****************************************************************
-From: Matthew Heaney
-Sent: Friday, April 2, 2005 9:31 AM
+From: George Bauhaus
+Sent: Friday, June 17, 2005 11:46 AM
-****************************************************************
+> Include my "An Index to Ada.Containers" as an informative Note or Annex.
+> At least one other person on this list backs me up:
+> "Very nice table. It's certainly something one might expect to come
+> with a library, given Stroustrup's similar tables in TC++PL."
-From: Matthew Heaney
-Sent: Friday, April 2, 2005 9:31 AM
+Indeed TC++PL is a text book, not the C++ standard. Also,
+there would be more opportunities for overview tables than
+just for Ada.Containers...
+ They'd make a nice addition to a text book a la Josuttis,
+or Musser/Derge/Saini, wouldn't they?
****************************************************************
-From: Matthew Heaney
-Sent: Friday, April 2, 2005 9:31 AM
+From: Randy Brukardt
+Sent: Friday, June 17, 2005 12:04 PM
-****************************************************************
+> Isn't TC++PL, like K&R, the original RM of the respective language
+> (something that Ada did not have)? Have the TC++PL tables not made
+> their way into the ISO text?
-From: Matthew Heaney
-Sent: Friday, April 2, 2005 9:31 AM
+The matching document for Ada is the Rationale, not the Standard. Not enough
+Ada people read the Rationale...
-****************************************************************
+I believe that John is planning to include a table of operations in the
+Rationale chapter on containers. (He's still writing that chapter, so it's
+still in flux.)
-From: Matthew Heaney
-Sent: Friday, April 2, 2005 9:31 AM
+BTW, the first part of the Rationale should be posted on AdaIC fairly soon.
****************************************************************
-From: Matthew Heaney
-Sent: Friday, April 2, 2005 9:31 AM
+From: Dirk Craeynest
+Sent: Friday, June 17, 2005 12:14 PM
-****************************************************************
+= BTW, the first part of the Rationale should be posted on AdaIC
+= fairly soon.
-From: Matthew Heaney
-Sent: Friday, April 2, 2005 9:31 AM
+The Introduction and Part 1 (Object oriented model) were also published
+in the December 2004 and March 2005 issues of the Ada User Journal (*)
+resp. (AUJ 25-4 & 26-1).
+
+(*) http://www.ada-europe.org/journal.html
****************************************************************
-From: Matthew Heaney
-Sent: Friday, April 2, 2005 9:31 AM
+From: Marius Amado Alves
+Sent: Saturday, June 18, 2005 9:00 AM
-****************************************************************
+> The matching document for Ada is the Rationale, not the Standard.
-From: Matthew Heaney
-Sent: Friday, April 2, 2005 9:31 AM
+Very fuzzy matching :-)
+
+> Not enough Ada people read the Rationale...
+
+Exactly.
+But somehow this coming into scene of the Rationale (I had forgotten
+about it, how "typical" an Ada programmer am I) gave me second thoughts
+regarding the best place for the Index (RM, Rationale, text books, the
+Web). Personally I still tend to the RM, but I've stated my case and
+will now shut up and leave it to you ARG et alii.
+
****************************************************************
-From: Matthew Heaney
-Sent: Friday, April 2, 2005 9:31 AM
+From: Duncan Sands
+Sent: Friday, June 17, 2005 10:31 AM
+Talking about Ada.Containers, one thing I would like to
+see is a singleton function for sets (a singleton set is
+a set with only one element). I mean a function something
+like this:
+
+ function Singleton (Item : Element_Type) return Set;
+
+That way you can write expressions like this (assuming
+Singleton has been renamed to "+"):
+
+ My_Set : Set := +An_Element or +Another_Element;
+
+Right now there's no way to create a non-empty set without
+doing a procedure call. That's a pity, because expressions
+like the above are quite expressive (if inefficient).
+
+PS: An alternative is to introduce a bunch of extra functions
+such as:
+ function Union (Left, Right : Element_Type) return Set;
+ function Union (Left : Set; Right : Element_Type) return Set;
+But there would need to be a lot of such functions, too many in my
+opinion.
+
****************************************************************
From: Matthew Heaney
-Sent: Friday, April 2, 2005 9:31 AM
+Sent: Friday, June 17, 2005 12:28 PM
+
+Duncan Sands wrote:
+> Talking about Ada.Containers, one thing I would like to
+> see is a singleton function for sets (a singleton set is
+> a set with only one element). I mean a function something
+> like this:
+>
+> function Singleton (Item : Element_Type) return Set;
+
+This exact function isn't there, but you can do something like:
+
+ function Singleton (Item : ET) return Set is
+ S : Set;
+ begin
+ S.Insert (Item);
+ return S;
+ end;
+
+> That way you can write expressions like this (assuming
+> Singleton has been renamed to "+"):
+>
+> My_Set : Set := +An_Element or +Another_Element;
+
+You might as well do it this way:
+
+ function "or" (L, R : ET) return Set is
+ S : Set;
+ C : Cursor;
+ B : Boolean;
+ begin
+ S.Insert (L);
+ S.Insert (R, C, B);
+ return S;
+ end;
+
+
+> Right now there's no way to create a non-empty set without
+> doing a procedure call. That's a pity, because expressions
+> like the above are quite expressive (if inefficient).
+
+You can always write that function yourself, in terms of the
+procedure-based primitives.
+
+
+> PS: An alternative is to introduce a bunch of extra functions
+> such as:
+> function Union (Left, Right : Element_Type) return Set;
+> function Union (Left : Set; Right : Element_Type) return Set;
+> But there would need to be a lot of such functions, too many in my
+> opinion.
+
+These could be written easily enough in terms of existing primitives.
+They might not be quite as efficient as an operation that is properly
+primitive (since these are controlled types, a temporary will most
+likely get created, a situation I am careful to avoid in the reference
+implementation), but if you're really desperate then you could always
+write a child package.
+
****************************************************************
-From: Matthew Heaney
-Sent: Friday, April 2, 2005 9:31 AM
+From: Duncan Sands
+Sent: Saturday, June 18, 2005 4:46 PM
+> This exact function isn't there, but you can do something like:
+
+[snip example of how to write your own]
+
+the point is not whether you can write it yourself (of course you
+can), but whether set creation is fundamental enough to get its
+own function in the sets packages. Compare with operations like
+union (i.e. set manipulation rather than set creation): they have
+both procedural and functional forms. There is no logical need
+for the functional forms: they too can be implemented using the
+procedure versions. So why are they there? Presumably for
+convenience in writing expressive code (doubtless not for efficiency,
+since anyone using these functions rather than the procedures is taking
+a performance hit from the word go - a temporary being created on
+function return [is that still true in Ada 05?]). It would also be
+convenient to be able to create non-empty sets on the fly in such
+expressions. I appreciate that deciding what goes into the spec is a
+matter of taste and judgement, so I'm not going to pester you any more
+about this. I can't make a decisive argument for a function that isn't
+logically necessary. However I do remember someone saying that a
+container library "should stay out of the programmer's way" (low blow)...
+
****************************************************************
From: Matthew Heaney
-Sent: Friday, April 2, 2005 9:31 AM
+Sent: Tuesday, June 28, 2005 7:30 PM
+
+> the point is not whether you can write it yourself (of course
+> you can), but whether set creation is fundamental enough to
+> get its own function in the sets packages.
+
+It does seem like the To_Set ctor is missing from the API. Certainly I
+would be in favor of adding it.
+> I appreciate that deciding what goes into
+> the spec is a matter of taste and judgement, so I'm not going
+> to pester you any more about this.
+
+I think we just missed it, that's all. It's not as if we discussed it, and
+then decided not to include it. I can't see any harm about adding To_Set to
+the API (we have To_Vector, after all), but it's up to the ARG.
+
+> I can't make a decisive
+> argument for a function that isn't logically necessary.
+> However I do remember someone saying that a container library
+> "should stay out of the programmer's way" (low blow)...
+
+I agree that To_Set is a missing function, that should be included in the API.
+
****************************************************************
From: Matthew Heaney
-Sent: Friday, April 2, 2005 9:31 AM
+Sent: Tuesday, June 28, 2005 3:34 PM
+
+Phillip (from Eurocontrol) brought up a question during the AI-302
+tutorial last Friday.
+
+AI-302 says:
+
+"Library packages must be reentrant - multiple tasks can use the
+packages as long as they operate on separate containers. Thus, it is
+only necessary for a user to protect a container if a single container
+needs to be used by multiple tasks."
+
+His question is, How do you define "protect a container"? Does it mean
+that the container must be wrapped inside a protected object, and all
+access to the container (by multiple tasks) must be via protected
+operations? Or is there some other protection scheme that is acceptable
+by the standard?
+
+Phillip's issue was that he wants multiple tasks to be able to
+simultaneously iterate over the container, but without having to call a
+protected operation for every container operation invocation.
+
+The discussion came up wrt the algorithm on slide #11 of the tutorial:
+
+procedure Op (Container : Container_Type) is
+ C : Cursor := Container.First;
+ E : Element_Type;
+begin
+ while Has_Element (C) loop
+ E := Element (C);
+ Do_Something (E);
+ Next (C);
+ end loop;
+end Op;
+
+The standard says that "multiple tasks can use the packages as long as
+they operate on separate containers," but there appears to be ambiguity,
+since it's not absolutely clear whether "separate containers" means only
+calling operations that take a container parameter directly, or whether
+it also includes the case of using cursors too (which don't take a
+container parameter).
+
+For example, in the executable region of the procedure above, the
+container object isn't a parameter of any of the operations. So one
+interpretation of the standard is that if clients protect access to the
+First operation (called in the declarative region), then it's OK to
+simultaneously invoke the loop that follows, even if the cursors
+designate elements in the same container.
+
+The other interpretation is that no, multiple tasks are not allowed to
+invoke the iteration operation above, if the tasks are iterating over
+the same container.
+
+Phillip's question is, what task synchronization scheme is allowed by
+the standard, for multiple tasks to invoke the operation above, on the
+same container object?
+I don't think you can wrap the entire loop above in a protected
+operation (protected operations must execute for only a "short time,"
+right?), which means that every operation in the loop above, including
+Has_Element and Next, must be individually wrapped in a protected
+operation. That's what Phillip objects to. Is there an alternative?
+
****************************************************************
-From: Matthew Heaney
-Sent: Friday, April 2, 2005 9:31 AM
+From: Randy Brukardt
+Sent: Wednesday, July 6, 2005 10:11 PM
+
+Matt Heaney writes:
+
+> AI-302 says:
+>
+> "Library packages must be reentrant - multiple tasks can use the
+> packages as long as they operate on separate containers. Thus, it is
+> only necessary for a user to protect a container if a single container
+> needs to be used by multiple tasks."
+
+AARM Draft 12 says this in A.18(4.o) as well.
+
+> His question is, How do you define "protect a container"?
+
+This is not normative wording; it follows from the rules in A(3) [that is,
+paragraph 3 of the introduction to Annex A].
+
+So it's informal wording, don't read too much into it.
+
+> Does it mean
+> that the container must be wrapped inside a protected object, and all
+> access to the container (by multiple tasks) must be via protected
+> operations? Or is there some other protection scheme that is acceptable
+> by the standard?
+
+The wording probably should be "synchronize access to" rather than
+"protect". Any synchronization mechanism that prevents more than one task to
+be simultaneously accessing the same container is acceptable. You have to
+meet the requirements of A(3) for non-overlapping objects (both cursors and
+containers are passed by reference, so the rule clearly requires that).
+
+> Phillip's issue was that he wants multiple tasks to be able to
+> simultaneously iterate over the container, but without having to call a
+> protected operation for every container operation invocation.
+
+I don't think he can do that. I'd expect a protected operation to be more
+lightweight than any other synchronization mechanism.
+
+...
+> The standard says that "multiple tasks can use the packages as long as
+> they operate on separate containers," but there appears to be ambiguity,
+> since it's not absolutely clear whether "separate containers" means only
+> calling operations that take a container parameter directly, or whether
+> it also includes the case of using cursors too (which don't take a
+> container parameter).
+
+The *Standard* says no such thing. There are some AARM notes that say that.
+
+The normative wording is A(3). It would appear that it would allow reading
+from separate cursors accessing the same object as long as the cursor
+objects are non-overlapping. Of course, any operation with a container
+parameter couldn't be called without synchronization.
+
+I detest the bare cursor operations of the containers library, precisely
+because they hide the container and thus cause all kinds of anomolies. But
+that isn't going to be changed.
+
+It does seem like some slightly more restrictive wording is needed. Probably
+an AARM note would be enough (presuming that we have agreement). The term
+"non-overlapping" is intentionally vague in A(3), so we just need to mention
+that it applies to the containers containing the element designated by a
+cursor. Something like, "A cursor referencing an element in a container is
+considered to be overlapping with the container object itself." Otherwise, a
+cursor operation reading from a container would not necessarily be
+considered "overlapping" with the container itself, meaning that such a read
+would have to work in parallel with an operation writing the container. I
+don't think anyone expects *that* to work.
+
+It would be OK for cursor-only operations to not be considered overlapping
+with each other. That would mean that cursor-only operations shouldn't
+modify the container in any way, but that is pretty much the case anyway. So
+I'd expect such operations to work in practice, even if the letter of the
+standard didn't require that they work.
+
+...
+> Phillip's question is, what task synchronization scheme is allowed by
+> the standard, for multiple tasks to invoke the operation above, on the
+> same container object?
+>
+> I don't think you can wrap the entire loop above in a protected
+> operation (protected operations must execute for only a "short time,"
+> right?), which means that every operation in the loop above, including
+> Has_Element and Next, must be individually wrapped in a protected
+> operation. That's what Phillip objects to. Is there an alternative?
+Any synchronization that would prevent multiple access would work. One could
+use a lock (that's what we do in Claw for similar issues); the lock could be
+locked by the declaration of a controlled object that frees the lock then it
+is finalized. (That's safe in the face of exceptions and aborts, so is much
+preferable to bare semaphore operations.) If the lock is locked when a
+locking object is declared, the task is blocked until the lock is freed. The
+lock object would be declared in a block (or the local scope) surrounding
+the loop. A pretty standard idiom.
+
****************************************************************
-From: Matthew Heaney
-Sent: Friday, April 2, 2005 9:31 AM
+From: Pascal Leroy
+Sent: Thursday, July 7, 2005 3:10 AM
+
+> Something like, "A cursor referencing
+> an element in a container is considered to be overlapping
+> with the container object itself."
+I agree that this is needed, and I would put it in normative wording, at
+the end of A.18(2/2) where we introduce cursors.
+
****************************************************************
From: Matthew Heaney
-Sent: Friday, April 2, 2005 9:31 AM
+Sent: Saturday, July 2, 2005 12:33 PM
+
+What follows is my review of sections A.18 and A.18.2 (vectors) of the
+latest AI-302 draft.
+
+The full draft is described here:
+
+http://www.ada-auth.org/cgi-bin/cvsweb.cgi/AIs/AI-20302.TXT?rev=1.21
+
+The first line of that file says:
+
+!standard A.18 (00) 05-05-13 AI95-00302-03/13
+
+My comments immediately followed the text to which they refer, and each
+comment is demarcated using "MJH:" and "ENDMJH." pairs.
+
+-Matt
+
+
+
+A.18 Containers
+...
+Note that the language already includes several requirements that are
+important to the use of containers. These requirements include:
+
+* Library packages must be reentrant - multiple tasks can use the packages
+as
+ long as they operate on separate containers. Thus, it is only necessary
+for a
+ user to protect a container if a single container needs to be used by
+ multiple tasks.
+
+MJH:
+
+The issue here is defining exactly what it means to "protect a
+container." Does this mean wrapping the container inside a
+protected object? Is there any other task synchronization scheme that
+is permitted by this standard? If so, what is it?
+
+ENDMJH.
+
+
+A.18.2 The Package Containers.Vectors
+
+ function To_Vector
+ (New_Item : Element_Type;
+ Length : Count_Type) return Vector;
+
+MJH:
+
+Did we get these params backwards? We declare arrays this way:
+
+declare
+ A := Array_Subtype (1 .. Length) := (others => New_Item);
+begin ...;
+
+By analogy, a vector would be declared like this:
+
+declare
+ V : Vector := To_Vector (Length, New_Item);
+begin ...;
+
+Yet, we have the params in the opposite order. I always have to think about
+param order when using To_Vector.
+
+ENDMJH.
+
+
+ function "&" (Left, Right : Element_Type) return Vector;
+
+MJH:
+
+Do we really want this operation? I always get a little antsy when
+adding operations to a formal type. The issue is that when you overload
+merely on the return type, this can introduce ambiguities when calling
+an operation that accepts the return type as a parameter. The other
+operators, that have at least one Vector parameter, don't have this problem.
+
+ENDMJH.
+
+
+ procedure Replace_Element (Container : in Vector;
+ Index : in Index_Type;
+ By : in Element_Type);
+
+MJH:
+
+I had mentioned a few weeks ago about possibly renaming the "By"
+parameter to "New_Item". The parameter was originally named "By" in
+order to conform to the similarly-named operation in
+Ada.Strings.Unbounded, but the container API has matured a lot since
+then, and today the parameter name "By" makes less sense.
+
+ENDMJH.
+
+
+Some operations are assumed to work on a constant set of elements. For such
+an operation, a subprogram is said to *tamper with cursors* of a vector
+object V if:
+ * it inserts or deletes elements of V, that is, it calls the Insert,
+ Insert_Space, Clear, Delete, or Set_Length procedures with V
+ as a parameter; or
+
+ AARM To Be Honest: Operations which are defined to be equivalent to
+ a call on one of these operations also are included. Similarly,
+operations
+ which call one of these as part of their definition are included.
+
+ * it finalizes V; or
+ * it calls the Move procedure with V as a parameter.
+
+ AARM Note:
+ Swap, Sort, and Merge copy elements rather than reordering them, so
+ they do not tamper with cursors.
+
+Some operations are assumed to not replace elements. For such an operation,
+a
+subprogram is said to *tamper with elements* of a vector object V if:
+
+MJH:
+
+Is the sense of that first sentence correct? Shouldn't it say
+"...assumed to replace elements"? The second bullet below says "it
+replaces ... elements of V".
+
+ENDMJH.
+
+ * it tampers with cursors of V; or
+ * it replaces one or more elements of V, that is, it calls the
+ Replace_Element or Swap procedures or the Sort or Merge procedures of
+an
+ instance of Generic_Sorting with V as a parameter.
+
+ AARM Note: Complete replacement of an element can cause its
+ memory to be deallocated while another operation is holding onto a
+reference
+ to it. That can't be allowed. However, a simple modification of (part of)
+an
+ element is not a problem, so Update_Element does not cause a problem.
+
+MJH:
+
+Just so I understand these semantics, can you clarify the behavior in
+the following cases?
+
+I think it's true that if Replace_Element is called from within
+Process.all during a call to Query_Element or Update_Element, then
+Program_Error is raised. Is this correct?
+
+What happens if Generic_Sorting.Sort is called from within Process.all
+during a call to Query_Element or Update_Element? Is this allowed, or
+is Program_Error raised?
+
+What about Swap? Can you call Swap from within Process.all during a
+call to Query_Element or Update_Element?
+
+What about Merge?
+
+Are there are any other operations besides Replace_Element (and possibly
+Sort, Swap, and Merge) that raise Program_Error if called from within
+Process.all during a call to Query_Element or Update_Element?
+
+ENDMJH.
+
+
+procedure Move (Target : in out Vector;
+ Source : in out Vector);
+
+If Target denotes the same object as Source, then Move has no effect.
+Otherwise, Move first calls Clear (Target); then, each element from Source
+is removed from Source and inserted into Target in the original order. The
+length of Source is 0 after a successful call to Move.
+
+AARM Note:
+
+The idea is that the internal array is removed from Source and moved to
+Target.
+(See the Implementation Advice for Move).
+If Capacity (Target) /= 0, the previous internal array may need to be
+deallocated. We don't mention this explicitly, because it is covered by the
+"no memory loss" Implementation Requirement.
+
+MJH:
+
+In the reference implementation, I give Target's previous array to
+Source, since we might as well reuse it, instead of throwing it away.
+Such behavior is allowed by this standard, since the paragraph above
+doesn't specify how the vectors' capacities are affected by Move.
+
+ENDMJH.
+
+
+Implementation Advice
+
+Containers.Vectors should be implemented similarly to an array. In
+particular,
+if the length of a vector is *N*, then
+ * the worst-case time complexity of Append with Count=1 and Element
+should
+ be O(log N); and
+ * the worst-case time complexity of Prepend with Count=1 and
+Delete_First
+ with Count=1 should be O(N log N).
+
+MJH:
+
+Is that second bullet correct? Shouldn't the worst-case time complexity
+for Prepend be O(N)? Isn't N * log N < N? How can an array-based
+implementation of vector do any better than O(N) for Prepend?
+
+ENDMJH.
+
****************************************************************
-From: Matthew Heaney
-Sent: Friday, April 2, 2005 9:31 AM
+From: Randy Brukardt
+Sent: Saturday, July 2, 2005 4:41 PM
+
+Matt writes:
+
+> What follows is my review of sections A.18 and A.18.2 (vectors) of the
+> latest AI-302 draft.
+
+A general comment: the ARG approved a number of changes to this, based on
+comments from you, John Barnes, and others, at the meeting in York. So I'd
+suggest holding off on reviewing this further until those changes (some of
+which are pretty extensive, although mainly cosmetic) are handled.
+
+----
+
+> function "&" (Left, Right : Element_Type) return Vector;
+>
+>MJH:
+>Do we really want this operation? I always get a little antsy when
+>adding operations to a formal type. The issue is that when you overload
+>merely on the return type, this can introduce ambiguities when calling
+>an operation that accepts the return type as a parameter. The other
+>operators, that have at least one Vector parameter, don't have this
+problem.
+>ENDMJH.
+
+Yes, of course. This is the standard way that "&" is defined in Ada (look at
+4.5.3(4)),
+and we should always follow that pattern in packages.
+
+The only way for this operator to cause a problem is to have a use type on
+both the element and the vector type, and have "&" defined on the element
+type, *and* a complex expression where there might be confusion. Unless
+Element_Type is String or Character, I don't see any chance of a problem;
+and you can always use prefix notation to specify the right operation. (Bob
+thinks that is too ugly, but its better than eliminating useful operations.)
****************************************************************
-From: Matthew Heaney
-Sent: Friday, April 2, 2005 9:31 AM
+From: Dan Eilers
+Sent: Wednesday, October 19, 2005 7:52 PM
+
+In Annex A, all the occurrences of "asymmetric" should be "antisymmetric".
****************************************************************
-From: Matthew Heaney
-Sent: Friday, April 2, 2005 9:31 AM
+From: Randy Brukardt
+Sent: Wednesday, October 19, 2005 10:12 PM
+Huh? Would you care to explain that further? I've never even seen the word
+"antisymmetric" before. In any case, what rules are you talking about, as
+Annex A is huge.
+
****************************************************************
-From: Matthew Heaney
-Sent: Friday, April 2, 2005 9:31 AM
+From: Robert Dewar
+Sent: Wednesday, October 19, 2005 10:40 PM
+asymmetric simply says the two opposing halves are different
+
+antisymmetric (a perfectly good and standard word) says that the two
+opposing halves are in some well defined sense the opposite of
+one another.
+
****************************************************************
-From: Matthew Heaney
-Sent: Friday, April 2, 2005 9:31 AM
+From: Pascal Leroy
+Sent: Thursday, October 20, 2005 1:33 AM
+
+> Huh? Would you care to explain that further? I've never even
+> seen the word "antisymmetric" before. In any case, what rules
+> are you talking about, as Annex A is huge.
+
+I think Dan is talking about rules like the one in A.18.2(230) which say:
+"It should define a strict ordering relationship, that is, be irreflexive,
+asymmetric, and transitive;"
+
+This is a mathematical definition, and as such it complies with the
+reference document mentioned in 1.3(1), which gives the following
+definitions:
+
+- Irreflexive: a R a does not hold for any a
+
+- Asymmetric: if a R b, then b R a does not hold.
+
+- Antisymmetric: a R b and b R a together imply a = b.
+
+- Transitive: a R b and b R c implies a R c.
+
+Note that the mathematical meanings of asymmetric and antisymmetric are
+significantly different, and that they are actually consistent with the
+general meanings mentioned by Robert.
+
+Also note that a strict order (that is, "<") is *never* antisymmetric,
+although it certainly is asymmetric. It is a nonstrict order (that is,
+"<=") that is antisymmetric.
+
+In the case at hand, the operators must be implement a strict order, a
+nonstrict order would lead to unspecified behavior, so the wording is
+correct as is.
+
****************************************************************
-From: Matthew Heaney
-Sent: Friday, April 2, 2005 9:31 AM
+From: Dan Eilers
+Sent: Thursday, October 20, 2005 12:01 PM
+ Pascal correctly noted that I was referring to the mathematical
+definition, and that I was mistaken and that asymmetric is correct
+for this usage. ("<=" is antisymmetric, but the generic formal
+is "<".)
+
+> In any case, what rules are you talking about, as Annex A is huge.
+
+I wasn't trying to be obscure, I thought they would be easier to
+find using online search than looking them up by paragraph number.
+Anyways, there should probably be an index entry for asymmetric.
+
****************************************************************
-From: Matthew Heaney
-Sent: Friday, April 2, 2005 9:31 AM
+From: Randy Brukardt
+Sent: Thursday, October 20, 2005 5:02 PM
+
+> I wasn't trying to be obscure, I thought they would be easier to
+> find using online search than looking them up by paragraph number.
+OK, but I guess I would have expected a bit more specificity (as Pascal
+gave). Something like "The container rules of the form ....".
+
+> Anyways, there should probably be an index entry for asymmetric.
+
+Generally, the index only includes the definitions, not the uses of terms.
+And in this case, the term is used in its mathmatical sense, so there is no
+definition in the RM. Thus it doesn't appear in the index. (Mathematical
+terms are defined by a particular reference and (in the AARM) by a website,
+so its best to go there for the definition.)
+
****************************************************************
From: Matthew Heaney
-Sent: Friday, April 2, 2005 9:31 AM
+Sent: Sunday, October 30, 2005 3:53 PM
+
+The first line of my copy of the draft says:
+
+!standard A.18 (00) 05-07-26 AI95-00302-03/14
+
+As usual, my comments follow the text to which they refer, and are bracketed
+by "MJH:" and "ENDMJH." pairs.
+
+
+A.18.2 The Package Containers.Vectors
+
+ function To_Vector
+ (New_Item : Element_Type;
+ Length : Count_Type) return Vector;
+
+MJH:
+
+The ARG should rule on whether this parameter order is correct. The reason
+is that we declare array objects this way:
+
+procedure Op (N : Positive) is
+ A : Array_Type (1 .. N) := (others => E);
+begin
+
+In the array declaration, the order is: length then element.
+
+In the vector declaration above, the parameter order is: element then
+length.
+
+ENDMJH.
+
+From A.18.2:
+
+procedure Delete (Container : in out Vector;
+ Position : in out Cursor;
+ Count : in Count_Type := 1);
+
+...Otherwise, Delete (Container, To_Index (Position), Count) is called, and
+then Position is set to No_Element.
+
+
+and from A.18.3:
+
+procedure Delete (Container : in out List;
+ Position : in out Cursor;
+ Count : in Count_Type := 1);
+
+...Finally, Position is set to No_Element.
+
+
+MJH:
+
+The equivalent STL member function is declared this way:
+
+iterator erase(iterator);
+
+The issue with the new, post-York semantics is that if you specify a Count >
+1, then there's no way to discover what the first element of the remainder
+of the sequence is, without using some kind of loop -- but that undermines
+the reason for having a count parameter in the first place.
+
+Yes, I realize that this makes Delete consistent across all containers, but
+all containers are not equal. Vectors and lists not called a "sequence
+container" for nothing.
+
+Note that sets and maps don't even have a count parameter in the Delete
+operation, so we already know they're not equivalent. Also, we don't return
+the position of the "next" element for sets and maps because there's a cost
+to compute it. In the case of vectors and lists, there is no cost.
+
+It's also reasonable to assume that iterative algorithms involving deletion
+of elements are applied to sequence containers. But those algorithms are
+unnecessarily awkward (indeed, arguably more error-prone) when the position
+value returned is always No_Element.
+
+These semantics also seem strange when Count = 0, which we've been treating
+as a no-op.
+
+ENDMJH.
+
+
+MJH:
+
+A.18.7 Sets: Shouldn't we have a To_Set factory function, that takes an
+element returns a set?
+
+ENDMJH.
+
****************************************************************
-From: Matthew Heaney
-Sent: Friday, April 2, 2005 9:31 AM
+From: Randy Brukardt
+Sent: Sunday, October 30, 2005 5:05 PM
+
+...
+> A.18.2 The Package Containers.Vectors
+>
+> function To_Vector
+> (New_Item : Element_Type;
+> Length : Count_Type) return Vector;
+>
+> MJH:
+>
+> The ARG should rule on whether this parameter order is correct.
+
+It's too late for this sort of noodling around. We're only looking to fix
+errors or significant omissions at this point. The order of parameters
+clearly can be neither.
+
+...
+> From A.18.2:
+>
+> procedure Delete (Container : in out Vector;
+> Position : in out Cursor;
+> Count : in Count_Type := 1);
+>
+> ...Otherwise, Delete (Container, To_Index (Position), Count) is
+> called, and then Position is set to No_Element.
+...
+
+> The equivalent STL member function is declared this way:
+>
+> iterator erase(iterator);
+
+This is clearly a different function; it returns something. The reason for
+clearing the cursor passed in is that it no longer designates the element
+that it originally did.
+
+> The issue with the new, post-York semantics is that if you specify a Count
+>
+> 1, then there's no way to discover what the first element of the remainder
+> of the sequence is, without using some kind of loop -- but that undermines
+> the reason for having a count parameter in the first place.
+
+You seem to want "Delete_and_Return_First_Undeleted_Item", which is clearly
+not what Delete does.
+We talked about this sort of semantics in the context of Splice (should we
+make Splice update the cursor so it can be used in a loop), and we decided
+that we didn't want "tricky" semantics that was just as likely to be wrong
+as right. Surely that conclusion applies to Delete as well.
+
+...
+> A.18.7 Sets: Shouldn't we have a To_Set factory function, that takes an
+> element returns a set?
+
+I was supposed to add that to draft 13, and I forgot. It's in draft 14 (to
+be posted RSN). Of course, the ARG still will have to approve the addition.
+
****************************************************************
From: Matthew Heaney
-Sent: Friday, April 2, 2005 9:31 AM
+Sent: Sunday, October 30, 2005 6:42 PM
+
+> > The equivalent STL member function is declared this way:
+> >
+> > iterator erase(iterator);
+>
+> This is clearly a different function; it returns something.
+> The reason for clearing the cursor passed in is that it no
+> longer designates the element that it originally did.
+
+The syntax is obviously different, but the original semantics were the same.
+
+The STL erase function doesn't manipulate the value of the iterator object
+passed in, as it's intended to be used as follows:
+
+ i = list_container.erase(i);
+
+The equivalent Ada operation can't be declared as a function, so it has to
+be a procedure. That, and the original semantics were intended to duplicate
+the behavior of the C++ statement above.
+
+It's no big deal, but when you're writing an iterative algorithm that
+deletes elements, then you have to save the next position and create a
+temporary, simply to do the deletion.
****************************************************************
From: Matthew Heaney
-Sent: Friday, April 2, 2005 9:31 AM
+Sent: Friday, June 17, 2005 9:31 AM
****************************************************************
From: Matthew Heaney
-Sent: Friday, April 2, 2005 9:31 AM
+Sent: Friday, June 17, 2005 9:31 AM
****************************************************************
From: Matthew Heaney
-Sent: Friday, April 2, 2005 9:31 AM
+Sent: Friday, June 17, 2005 9:31 AM
****************************************************************
From: Matthew Heaney
-Sent: Friday, April 2, 2005 9:31 AM
+Sent: Friday, June 17, 2005 9:31 AM
****************************************************************
Questions? Ask the ACAA Technical Agent