CVS difference for ais/ai-30302.txt

Differences between 1.18 and version 1.19
Log of other versions for file 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