CVS difference for ais/ai-30302.txt

Differences between 1.13 and version 1.14
Log of other versions for file ais/ai-30302.txt

--- ais/ai-30302.txt	2004/11/14 06:37:26	1.13
+++ ais/ai-30302.txt	2004/11/17 00:53:02	1.14
@@ -20680,8 +20680,8 @@
 
 ****************************************************************
 
-From: Matthew Heaney
-Sent: Friday, September 2, 2004  9:31 AM
+From: Randy Brukardt
+Sent: Thursday, September 30, 2004  1:42 PM
 
 > I agree if the implementation is manageable, and
 > the definition is relatively short, safety is
@@ -24724,7 +24724,393 @@
 ****************************************************************
 
 From: Matthew Heaney
-Sent: Friday, September 2, 2004  9:31 AM
+Sent: Tuesday, November 16, 2004  12:34 AM
+
+!standard A.17                      04-11-01  AI95-00302-03/08
+!class amendment 04-01-14
+!status work item 04-01-14
+!status received 04-01-14
+!priority Medium
+!difficulty Hard
+!subject Container library
+
+My review of the AI95-00302-03/08 (preatlanta) draft follows.  For issues
+that I have already discussed in previous reviews, I have only made a brief
+comment.  
+
+Each comment is bracketed with "MJH:" and "ENDMJH." pairs, and immediately
+follows the text to which it refers.
+
+-Matt
+
+
+!proposal
+
+The hashed map associative containers scatter keys in the container
+according
+to a hash function. The size of the hash table is automatically increased
+when
+the length of the container equals its capacity (which specifies the length
+before which it is guaranteed that no automatic hash table resizing occurs),
+thus preserving constant time complexity for insertions.
+
+MJH:
+
+We might want to generalize this paragraph, since we now have a hashed
+set, too.
+
+ENDMJH.
+
+
+The set associative container maintains elements in sort order. Insertions
+and searches have O(log N) time complexity even in the worst case.
+
+MJH:
+
+Similar my previous comment, we might want to generalize this, since we
+now have ordered maps, too.
+
+ENDMJH.
+
+
+All of the containers have alternate forms that accept an element type that
+is
+indefinite. The indefinite hashed maps also accept an indefinite key type,
+allowing (for example) type String to be used as the generic actual key
+type.
+
+MJH:
+
+We can probably just say "indefinite maps" here.
+
+ENDMJH.
+
+A.17 Containers
+
+The following major non-limited containers are provided:
+   * (Expandable) Vectors of any non-limited type;
+   * Doubly-linked Lists of any non-limited type;
+   * Hashed Maps keyed by any non-limited type containing any
+non-limited type;
+   * Ordered Sets of any non-limited type.
+
+MJH:
+
+As above, we should generalize what is said about maps and sets, since
+each of those containers now has both hashed and ordered forms.
+
+ENDMJH.
+
+Note that the language already includes several requirements that are
+important to the use of containers. First, 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:
+
+I have already stated my objection to this feature (an objection perhaps
+based on a misunderstanding of A(3)).
+
+ENDMJH.
+
+
+A.17.2 The Package Containers.Vectors
+
+package Ada.Containers.Vectors is
+...
+   type Vector is tagged private;
+
+MJH:
+
+As has been discussed on Ada-Comment, I have mixed feelings about making
+the container types publicly tagged.  My tentative opinion is that (as
+the language stands now) we should get rid of the tag.
+
+One justification for making the container types publicly tagged is that
+they're already privately tagged, since you need to derive from type
+Controlled to make memory management work, so you might as well expose
+the tag.  However, it turns out that it is not necessary for the
+container type itself to derive from Controlled, since the full view of
+the type can be implemented like this:
+
+   type Control_Type is new Controlled with record
+      Elements : Element_Array_Access;
+      Last     : Extended_Index := No_Index;
+   end record;
+
+   type Vector is record
+      Control : Control_Type;
+   end record;
+
+This implementation has the benefit that since the container type isn't
+tagged, then there's no vtable, which I assume means that there's less
+run-time baggage.
+
+Another reason for making the type publicly tagged is that you can
+extend the type, and use class-wide types for polymorphic programming.
+However, in practice using container types this way would probably be
+extremely rare.  Anything you'd be tempted to do to a container using
+dynamic mechanisms you can do more easily via static mechanisms such as
+cursors or iterators.
+
+I had given another reason for public taggedness during the Palma meeting, 
+and that was that tagged types are implicitly aliased.  But needing this 
+functionality is probably rare, since this API has been designed (as much 
+as possible) to give you unhindered access to elements.  Assuming we state 
+that the container type is a by-reference type, then in the rare case that 
+aliasing of a container parameter were necessary, the developer could use 
+'Address and Address_To_Access_Conversions to obtain a pointer to the 
+container object.  (Or perhaps the language has been changed in this
+area, to add something like the 'Unrestricted_Access attribute in GNAT.)
+
+I bring all this up because I and at least one other developer have run
+into the scenario of wanting to implement the full view of a private
+type as a private derivation from Vector, like this:
+
+generic
+   type ET is private;
+package P is
+   type T is private;
+   procedure Op (O : T);
+private
+   package ET_Vectors is new A.C.Vectors (Positive, ET);
+   type T is new ET_Vectors.Vector with null record;
+   --lots of tedious overridings are req'd here
+end P;
+
+The problem is that several of the primitive operations return type
+Vector, which means they must be overridden.  This is too painful, so in
+practice no one will bother, and in the example above you'll probably
+have to implement type T as a record with a vector component.  But this
+feels unnatural.  If the container type weren't tagged, no extension or
+overridings would be necessary.
+
+Another common technique is to derive from a type in order to bring its
+operations into local scope.
+
+In general the design of this API has guided by the philosophy that you
+should design around the common case.  Declaring one type as a
+derivation of another type is a nearly ubiquitous idiom in Ada.  Since
+type derivation is common, and polymorphic container programming is
+rare, we should design around the derivation case.  That probably means
+getting rid of the public tag, unless the language is modified somehow
+to allow null type extensions to inherit a default version of functions
+that return the type.
+
+ENDMH.
+
+...
+
+procedure Iterate
+   (Container : in Vector;
+    Process : not null access procedure (Position : in Cursor));
+
+Invokes Process.all with a cursor that designates each element in Container,
+in
+index order. Any exception raised by Process is propagated.
+Program_Error is propagated if:
+ * Process.all attempts to insert or delete elements from Container; or
+ * Process.all finalizes Container; or
+ * Process.all calls Move with Container as a parameter.
+
+AARM Note:
+This check takes place when the operations that insert or delete elements,
+etc.
+are called. There is no check needed if an attempt is made to insert or
+delete
+nothing (that is, Count = 0 or Length(Item) = 0).
+
+The check is easy to implement: each container needs a counter. The counter
+is incremented when Iterate is called, and decremented when Iterate
+completes.
+If the counter is nonzero when an operation that inserts or deletes is
+called,
+Finalize is called, or one of the other operations in the list occurs,
+Program_Error is raised.
+
+Swap and Generic_Sort are not included here, as they only copy elements.
+End AARM Notes.
+
+MJH:
+
+I have already stated my objection to this requirement.  Basically, we
+already have rules to handle cursors that are "invalid", so I don't see
+why those rules shouldn't also apply to Iterate too.
+
+ENDMJH.
+
+
+A.17.7 Sets
+
+function "=" (Left, Right : Set) return Boolean;
+
+If Left and Right denote the same set object, then the function returns
+True.
+If Left and Right have different lengths, then the function returns False.
+Otherwise, for each element E in Left, the function returns False if an
+element
+equivalent to E is not present in Right. If the function has not returned a
+result after checking all of the elements, it return True. Any exception
+raised
+during evaluation of element equivalence is propagated.
+
+MJH:
+
+Do you want to move this into each subsection separately?  Ordered sets
+and hashed sets implement set equality a little differently:
+
+For ordered sets, the elements are in order, so you only need to compare
+each element sequentially using element "=".
+
+For hashed sets, given an element of left, you compute the index of the
+bucket in right that corresponds to the left element's hash value, and
+then you compare the left element to each element in that bucket using
+element "=".
+
+I bring this up because the language above about returning false if
+there is no "equivalent" element is at best ambiguous (and at worse
+wrong), since for either container Equivalent_Elements isn't guaranteed
+to return the same result as "=" for elements.  This is especially the
+case since Tucker wants to add an Equivalent function for sets, that is
+implemented in terms of element equivalence instead of element equality.
+
+ENDMJH.
+
+
+procedure Replace_Element (Container : in Set;
+                           Position  : in Cursor;
+                           By        : in Element_Type);
+
+If Position equals No_Element, then Constraint_Error is propagated.
+If Position does not designate an element in Container, then Program_Error
+is propagated. Otherwise,  the element designated by Position is tested for
+equivalence to By; if equivalent Replace assigns By to the element
+designated
+by Position. Otherwise, the element designated by Position is removed from
+the
+container, then By is inserted into the container. If the insertion fails,
+Program_Error is propagated.
+
+MJH:
+
+If we decide to keep this operation, then it needs to pass the container
+as an inout parameter, not in-mode.
+
+ENDMJH.
+
+procedure Replace (Container : in out Set;
+                   Key       : in     Key_Type;
+                   New_Item  : in     Element_Type);
+
+Equivalent to Replace (Container, Find (Container, Key), New_Item).
+
+MJH:
+
+I think you meant to say that it's equivalent to Replace_Element.
+
+I have stated elsewhere that I don't agree that Generic_Keys.Replace
+should be included in this API.
+
+ENDMJH.
+
+
+procedure Checked_Update_Element
+    (Container : in out Set;
+     Position  : in     Cursor;
+     Process   : not null access procedure (Element : in out Element_Type));
+
+MJH:
+
+I have stated elsewhere that I think this operation should be named just
+Update_Element, not Checked_Update_Element.
+
+ENDMJH.
+
+A.17.8 The Package Containers.Hashed_Sets
+
+Static Semantics
+
+The package Containers.Hashed_Sets has the following declaration:
+
+generic
+
+   type Element_Type is private;
+
+   with function Hash (Element : Element_Type) return Hash_Type;
+
+   with function Equivalent_Elements (Left, Right : Element_Type)
+                 return Boolean;
+
+MJH:
+
+I have stated elsewhere that I think this formal operation should be
+named Equivalent_Keys, not Equivalent_Elements.
+
+Note that Randy's argument for including the operation
+Generic_Keys.Replace was to facilitate changing from a map to a set.
+That goal is undermined if you use a different name from
+Equivalent_Keys.
+
+This generic formal region also needs to pass element "=", since that's
+how set "=" is implemented.  See my note above.
+
+ENDMJH.
+
+
+Function Equivalent_Elements is expected to return the same value each time
+it is called with a particular pair of element values. For any two elements
+E1
+and E2, the boolean values Equivalent_Keys (E1, E2) and Equivalent_Key (E2,
+E1)
+are expected to be equal. If Equivalent_Elements behaves in some other
+manner,
+the behavior of this package is unspecified. Which subprograms of this
+package
+call Equivalent_Elements, and how many times they call it, is unspecified.
+
+MJH:
+
+In the middle sentence you refer to "Equivalent_Keys".  Is this a typo?
+(But see my comments above.)
+
+ENDMJH.
+
+
+A.17.9 The Package Containers.Ordered_Sets
+
+Static Semantics
+
+The package Containers.Ordered_Sets has the following declaration:
+
+generic
+
+   type Element_Type is private;
+
+   with function "<" (Left, Right : Element_Type) return Boolean is <>;
+
+   with function "=" (Left, Right : Element_Type) return Boolean is <>;
+
+package Ada.Containers.Ordered_Sets is
+   pragma Preelaborate (Ordered_Sets);
+
+   type Set is tagged private;
+
+   type Cursor is private;
+
+   Empty_Set : constant Set;
+
+   No_Element : constant Cursor;
+
+   function "=" (Left, Right : Set) return Boolean;
+
+MJH:
+
+Tucker wants an Equivalent function for sets, implemented in terms of
+element equivalence.  (This is different from set equality, which is
+implemented in terms of element equality.)
+
+ENDMJH.
 
 ****************************************************************
 

Questions? Ask the ACAA Technical Agent