CVS difference for ais/ai-30302.txt

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

--- ais/ai-30302.txt	2004/02/21 03:07:46	1.2
+++ ais/ai-30302.txt	2004/03/02 04:45:01	1.3
@@ -8791,123 +8791,601 @@
 
 ****************************************************************
 
-From: Matthew Heaney
-Sent: Tuesday, February 17, 2004  9:31 AM
+From: Nick Roberts
+Sent: Saturday, February 21, 2004  12:54 PM
+
+> "Cells" seems better to me. Short is always good!
+
+I like that name too. Splendid.
+
+> Well, a "Cell" (which is doing memory management) is not a pointer, it's
+> a controlled object containing a pointer. (Otherwise, the memory
+> wouldn't be recovered on scope exit, which is a clear no-no.) So that
+> means its size is more like 20 bytes for Janus/Ada. So I think I was
+> wrong about fragmentation problems (it is big enough to avoid those).
+> But it certainly would be a potential problem for memory use (if there
+> are lot of them), and a lot more overhead when items are copied (calls
+> to Finalize and Adjust for each item, which the directly indefinite
+> version would not have - it wouldn't need controlled elements as the
+> container itself is controlled). Of course, this doesn't matter in truly
+> low performance applications, but there are a lot of middle ground
+> applications in which that could matter.
+
+It may or may not be a problem for memory use. The size of one 'cell'
+object would, as you say, comprise in the ball park of 20 bytes (a tag and
+a linked-list 'next' access value, in addition the access value referring
+to the contained indefinite object). I reckon the overhead (the tag and the
+next pointer) is likely to be 8 bytes in most cases, although it could be
+quite a lot more. However, if the average size of each contained object is
+significantly more than this overhead, it is unlikely to be really
+significant (it may be a little annoying). If the inidefinite objects are
+relatively small on average, it matters. I'm not really sure, myself, which
+scenario will be prevalent in practice.
+
+> One more minor advantage to indefinite element containers: they only
+> require one instantiation to use. The "cell" solution requires two.
+
+The extra instantiation could be somewhat amortised away in some (perhaps
+many) realistic situations.
+
+    type Fragment_Count is range 0..2000;
+    subtype Fragment_Number is Fragment_Count range 1..Fragment_Count'Last;
+
+    package Gene_Fragments is new Ada.Containers.Cells(Gene_Array);
+    subtype Gene_Fragment is Gene_Fragments.Cell; use Gene_Fragments;
+
+    package Fragment_Gangs is
+       new Ada.Containers.Vectors(Fragment_Number,Gene_Fragment);
+    subtype Fragment_Gang is Fragment_Gangs.Vector; use Fragment_Gangs;
 
+    type Fixed_Gang is array (Fragment_Number range <>) of Gene_Fragment;
+
+    Sample: constant Fixed_Gang := Ref_Samp_1 & Ref_Samp_2;
+
+Here, the instantiation of a cell package permits us to declare an array of
+cells in addition to a vector of them. I feel that cells would quite often
+be useful for purposes other than allowing a (definite) container to
+contain indefinite objects.
+
+An advantage of definite containers over their indefinite counterparts is
+that they permit conversion to and from arrays (including the slicing of a
+linear container). The cell technique would have the extra advantage that,
+since only definite containers are used, these array operations would
+remain available. I feel that in itself could be quite a compelling argument.
+
+In my ignorance, could I ask please what the presumed (proper)
+implementation of Vectors is?
+
+In my mind forms a picture of a tree structure with the leaves containing
+(or pointing to) actual arrays which form fragments of the whole conceptual
+array. Each fragment would have a counter saying how many of its elements
+are actually used. Appending an element would require adding a leaf node if
+there was no more space in the end fragment. Random selection of an element
+would require descending the tree. Am I way off the mark?
+
+If I'm not way off the mark, I would contend that building a linked list
+and converting to an array (for subsequent random access) would be likely
+to be superior (to building a vector and selecting randomly from it by tree
+descent) in a majority of cases in practice.
+
 ****************************************************************
 
 From: Matthew Heaney
-Sent: Tuesday, February 17, 2004  9:31 AM
+Sent: Monday, February 23, 2004  6:23 PM
+
+> In my ignorance, could I ask please what the presumed (proper)
+> implementation of Vectors is?
+
+See the files
 
+ai302-containers-vectors.ad?
+ai302-containers-indefinite_vectors.ad?
+
+in the latest reference implementation for the details.
+
+<http://home.earthlink.net/~matthewjheaney/charles/ai302-20040223.zip>
+
+This implementation has a few more examples, some of which use the new
+indefinite vector container.  Look thru the anagram examples for some ideas.
+
+> In my mind forms a picture of a tree structure with the leaves containing
+> (or pointing to) actual arrays which form fragments of the whole conceptual
+> array. Each fragment would have a counter saying how many of its elements
+> are actually used. Appending an element would require adding a leaf node if
+> there was no more space in the end fragment. Random selection of an element
+> would require descending the tree. Am I way off the mark?
+
+A vector is implemented as an unconstrained array.
+
+> If I'm not way off the mark, I would contend that building a linked list
+> and converting to an array (for subsequent random access) would be likely
+> to be superior (to building a vector and selecting randomly from it by tree
+> descent) in a majority of cases in practice.
+
+To convert between container types, just use one of the iterators.
+
+The container library takes pains to give the library user easy and
+efficient access to the container elements (that means the actual
+objects).
+
+It is never the case that a container needs, say, an operation to
+convert itself to an array specifically.  A container iterator allows
+the library user himself to choose the target type, whatever makes the
+most sense for him.
+
 ****************************************************************
 
 From: Matthew Heaney
-Sent: Tuesday, February 17, 2004  9:31 AM
+Sent: Tuesday, February 24, 2004  10:27 AM
+
+
+
+Nick Roberts wrote:
+>
+> I might suggest a constant Null_Vector, obviating the need for the
+> Is_Empty function and Clear procedure, but I must admit one disadvantage
+> of such constants is that they are not inherited. I've found this a
+> small pain occasionally. On the other hand, the test V = Foo.Null_Vector
+> might be considered better (more natural, more readable) than
+> Is_Empty(V) and V := Foo.Null_Vector than Clear(V). But personally I'm
+> not sure.
+
+This won't work, because the vector type privately derives from
+Controlled, and therefore you can't declare a constant of the type in a
+package with preelaborate categorization.
+
+However, a constructor function would work.  Here are some ideas:
+
+   function Null_Vector return Vector_Type;
+
+   function Empty_Vector return Vector_Type;
+
+   function New_Vector return Vector_Type;
 
+   function To_Vector (Length : Size_Type) return Vector_Type;
+
+   function To_Vector (New_Item : Element_Type;
+                       Count    : Size_Type)
+      return Vector_Type;
+
+
+I actually had a need for something like this in one of my examples.
+
+It's kind of a pain that the language doesn't give you a default
+constructor for a type that you can pass as a parameter.  For example,
+in C++ I can say:
+
+    container.insert(T());
+
+where T() invokes the default ctor for the element type T.
+
+Ada does let you do something like this, when constructing an aggregate:
+
+    type NT is new T with record
+       I : Integer;
+    end record;
+
+    Object : constant NT := (T with I => 42);
+
+Here we're allowed to use T as the value of the parent part of NT, when
+constructing an aggregate of type NT.  But I can't use the type name as
+the value of a parameter:
+
+    Insert (Container, New_Item => T);  -- not legal Ada
+
+I have to say something like:
+
+    Insert (Container, New_Item => New_T);
+
+where New_T is a function that returns type T.
+
 ****************************************************************
 
-From: Matthew Heaney
-Sent: Tuesday, February 17, 2004  9:31 AM
+From: Randy Brukardt
+Sent: Tuesday, February 24, 2004  1:39 PM
+
+> It's kind of a pain that the language doesn't give you a default
+> constructor for a type that you can pass as a parameter.
+
+..
+> Here we're allowed to use T as the value of the parent part of NT, when
+> constructing an aggregate of type NT.  But I can't use the type name as
+> the value of a parameter:
+>
+>     Insert (Container, New_Item => T);  -- not legal Ada
+
+True, but Ada 200Y lets you say:
 
+     Insert (Container, New_Item => (<>));
+
+which is a default-initialized aggregate. Which is what you want, right??
+
+(See AI-287.)
+
+We originally tried to use the type name here, but it led to all kinds of
+problems, and it isn't providing any actual information, so we decided to
+use the box "<>" instead.
+
+So all you really want is an Ada 200Y compiler. :-)
+
 ****************************************************************
 
-From: Matthew Heaney
-Sent: Tuesday, February 17, 2004  9:31 AM
+From: Gary Dismukes
+Sent: Tuesday, February 24, 2004  3:13 PM
+
+> This won't work, because the vector type privately derives from
+> Controlled, and therefore you can't declare a constant of the type in a
+> package with preelaborate categorization.
 
+Not completely true.  In Ada 200Y you can make a private type have
+preelaborable initialization, in which case constants of the type
+can be declared in preelaborable packages (see AI-161).  Type
+Ada.Finalization.Controlled (and Limited_Controlled) are defined
+to have preelaborable initialization, though there's a restriction
+that if a user-defined controlled type overrides Initialize then
+the type doesn't have preelaborable initialization.
+
 ****************************************************************
 
 From: Matthew Heaney
-Sent: Tuesday, February 17, 2004  9:31 AM
+Sent: Tuesday, February 24, 2004  4:15 PM
+
+OK.  Thanks for the info.
 
+The vector and (hashed) map containers don't override the Initialize
+operation.
+
+The (sorted) set does override Initialize.  Let me see if I can get rid
+of that.
+
+It might not matter anyway, since we can use the new "(<>)" notation to
+construct an anonymous instance of the type.
+
 ****************************************************************
 
 From: Matthew Heaney
-Sent: Tuesday, February 17, 2004  9:31 AM
+Sent: Tuesday, February 24, 2004  4:27 PM
+
+I just got rid of the override of Initialize for the set.  The full view
+of Set_Type now looks like:
+
+    function New_Back return Node_Access;
 
+    type Set_Type is new Controlled with record
+       Tree : Tree_Type := (Back => New_Back, Length => 0);
+    end record;
+
+The function New_Back does the allocation and initialization that I was
+doing in Initialize.
+
+I'll fold this change into the next release of the reference implementation.
+
 ****************************************************************
 
 From: Matthew Heaney
-Sent: Tuesday, February 17, 2004  9:31 AM
+Sent: Friday, February 27, 2004  12:29 PM
+
+I just uploaded the latest version of the reference implementation:
 
+<http://home.earthlink.net/~matthewjheaney/charles/ai302-20040227.zip>
+
+This version includes indefinite forms for all containers.  There are
+also two more anagram examples, and a new genealogy example.
 ****************************************************************
 
-From: Matthew Heaney
-Sent: Tuesday, February 17, 2004  9:31 AM
+From: Tucker Taft
+Sent: Friday, February 27, 2004  4:07 PM
+
+I had a couple of problems compiling this.
+One problem is that you have two versions of package "String_Vectors",
+one in the top-level dir, and one in the indefinite_vectors subdirectory.
+You might want to delete the indefinite_vectors subdirectory, since it
+is redundant with the ai302-containers-indefinite_vectors stuff, and
+it is confusing because one uses "Natural" where the other uses "Size_Type."
+
+The other problem I had was with your "Control_Type" in the
+private part of indefinite_vectors/indefinite_vectors.ads.  Again,
+this is largely redundant with ai302-containers-indefinite_vectors.
+But for what it is worth, the former one doesn't compile with
+our latest compiler, because the type declaration:
+
+   type VT is new Rep_Types.Vector_Type;
+
+fails with complaints about trying to add primitive operations
+after a type is frozen.  It is a bit subtle, but this type
+declaration is in fact implicitly declaring additional operations
+on "Control_Type" *after* Control_Type has been passed to a generic.
+
+The solution I came up with was putting the declaration of
+Control_Type into a nested package ("Inner") starting at the
+declaration of Control_Type and ending after the generic
+instantiation producing Rep_Types.  Then the declaration
+of VT is outside the (inner) package, meaning that the additional
+operations it implicitly declares with parameters of type
+Control_Type don't end up as primitives of Control_Type.
+A corresponding change is needed in the body of Indefinite_Vectors.
+
+In any case, ai302-containers-indefinite_vectors.ad? doesn't
+have this problem -- you use a different approach.
+
+I'll let you know about any other problems I encounter.
+
+Very nice work, in any case!
 
 ****************************************************************
 
 From: Matthew Heaney
-Sent: Tuesday, February 17, 2004  9:31 AM
+Sent: Friday, February 27, 2004  4:43 PM
+
+I wasn't sure whether I still needed the old indefinite_xxx subdirectories.
+
+Those were originally created to show how to implement an indefinite
+container as a thin layer on top of the official definite containers.
+
+However, after I did that Randy suggested that having indefinite forms
+as an official part of the library might be acceptable, so I went ahead
+and implemented them, up in the parent directory.
+
+I can either remove them entirely from the release, or move them off
+into a deprecated subdirectory.
+
+I suppose a README couldn't hurt, either...
+
+
+> The other problem I had was with your "Control_Type" in the
+> private part of indefinite_vectors/indefinite_vectors.ads.
+...
+
+OK.  That's easy enough to fix.  (I don't really need that derived type.
+  It was only declared to effect transitivity of visibility.)
+
+
+> The solution I came up with was putting the declaration of
+> Control_Type into a nested package ("Inner") starting at the
+> declaration of Control_Type and ending after the generic
+> instantiation producing Rep_Types.  Then the declaration
+> of VT is outside the (inner) package, meaning that the additional
+> operations it implicitly declares with parameters of type
+> Control_Type don't end up as primitives of Control_Type.
+> A corresponding change is needed in the body of Indefinite_Vectors.
+
+OK.  Thanks for the tip.
+
+
+> In any case, ai302-containers-indefinite_vectors.ad? doesn't
+> have this problem -- you use a different approach.
+
+Indeed.  That version is implemented natively, not as a thin layer.
+
+The versions in the parent directory are the only ones you really care
+about.  I can move those other versions to somewhere less confusing.
+
+
+> I'll let you know about any other problems I encounter.
+
+OK, thanks.  I can fold any changes into the next release.
+
+I'll be at the meeting in Phoenix, so we can discuss any other issues
+you have.
+
+
+> Very nice work, in any case!
+
+Thanks.  I was able to build the reference implementation from the spare
+parts I had lying around for Charles, so it was a big job but not that big.
+
+I was just thinking today that it would be nice to have a functional
+insertion operation, like this:
+
+--see wordcount.adb
+declare
+    N : Natural renames Insert (Map'Access, Word, 0).all;
+begin
+    N := N + 1;
+end;
+
+or like this:
+
+--see genealogy.adb
+declare
+    Roots : Set_Type renames Insert (Map'Access, Key => "---").all;
+begin
+...
+
+This simulates what I can do in C++ using operator[]().
 
+One way to declare it is:
+
+    function Insert
+      (Map : access Map_Type;
+       Key :        String) return access Element_Type;
+
+I was thinking the cursor selectors could be declared like this:
+
+    function To_Element
+       (Cursor : Cursor_Type) return access Element_Type;
+
+    function To_Key
+      (Cursor : Cursor_Type) return access constant Key_Type;
+
+If functions could return an anonymous access type this would allow me
+to get rid of the Generic_Element and Generic_Key functions.
+
+Just some ideas...
+
 ****************************************************************
 
-From: Matthew Heaney
-Sent: Tuesday, February 17, 2004  9:31 AM
+From: Dan Eilers
+Sent: Saturday, February 28, 2004  2:14 PM
+
+  In ai302/test_sets.adb, on line 91, there is a call to
+"find" that appears to be ambiguous, matching the find
+declared in test_sets.adb on line 51, and the find
+declared in integer_vectors.
 
 ****************************************************************
 
-From: Matthew Heaney
-Sent: Tuesday, February 17, 2004  9:31 AM
+From: Adam Beneschan
+Sent: Monday, March  1, 2004  6:33 PM
+
+...
+> fails with complaints about trying to add primitive operations
+> after a type is frozen.  It is a bit subtle, but this type
+> declaration is in fact implicitly declaring additional operations
+> on "Control_Type" *after* Control_Type has been passed to a generic.
+
+Can this be right?  Essentially the source is equivalent to:
+
+   generic ...
+   package Indefinite_Vectors is
+
+   private
+
+      type Control_Type is new Controlled with record ... end record;
+
+      package Rep_Types is
+         type Vector_Type is private;
+         procedure Append (Vector   : in out Vector_Type;
+                           New_Item : in     Control_Type);
+      private ...
+      end Rep_Types;
+
+      type VT is new Rep_Types.Vector_Type;
+
+   end Indefinite_Vectors;
 
+The derived type declaration causes a new inherited subprogram to be
+declared implicitly:
+
+   procedure Append (Vector   : in out VT;
+                     New_Item : in     Control_Type);
+
+But as I read RM 3.2.3 and particularly 3.2.3(4), the derived
+subprogram Append is a primitive subprogram of type VT, but *not* a
+primitive subprogram of type Control_Type.  So there shouldn't be an
+error message about primitive subprograms being added after
+Control_Type is frozen (even if there were some declaration that froze
+Control_Type before the declaration of VT, which there isn't in my
+reduced example).
+
+Also, 3.9.2(13) makes "the explicit declaration of a primitive
+subprogram of a tagged type" illegal after the type is frozen, but
+this is not an explicit subprogram declaration.
+
+So what did I miss?
+
 ****************************************************************
 
-From: Matthew Heaney
-Sent: Tuesday, February 17, 2004  9:31 AM
+From: Randy Brukardt
+Sent: Monday, March  1, 2004  6:57 PM
+
+...
+> But as I read RM 3.2.3 and particularly 3.2.3(4), the derived
+> subprogram Append is a primitive subprogram of type VT, but *not* a
+> primitive subprogram of type Control_Type.
+
+Humm. This looks messy. Primitive subprograms have to be explicitly declared
+for initial types. But 3.2.3(4) says that inherited routines are primitive
+for derived types. It doesn't say that routines inherited *from the parent
+type* are primitive. In this case, Control_Type is derived, so inherited
+routines are primitive -- and this routine is certainly inherited.
+
+Of course, that seems to be a nonsense interpretation of the language. I
+think that 3.2.3(4) was intended to apply only to routines inherited from
+the parent. So the question is whether that can be derived from other
+language (in which case Tucker's compiler has a bug), or if there is
+actually a language hole.
 
 ****************************************************************
 
-From: Matthew Heaney
-Sent: Tuesday, February 17, 2004  9:31 AM
+From: Adam Beneschan
+Sent: Monday, March  1, 2004  7:26 PM
+
+> Humm. This looks messy. Primitive subprograms have to be explicitly declared
+> for initial types. But 3.2.3(4) says that inherited routines are primitive
+> for derived types. It doesn't say that routines inherited *from the parent
+> type* are primitive. In this case, Control_Type is derived, so inherited
+> routines are primitive -- and this routine is certainly inherited.
+
+The exact language of 3.2.3(2,4) is:
+
+   The primitive subprograms of a specific type are defined as
+   follows:
+
+   For a derived type, the inherited (see 3.4) user-defined
+   subprograms;
+
+So we refer to 3.4 to see what it says about "inherited user-defined
+subprograms".  3.4(17) says, "For each user-defined primitive
+subprogram... of the parent type that already exists at the place of
+the derived_type_definition, there exists a corresponding _inherited_
+primitive subprogram of the derived type with the same defining name".
+The primitive subprograms of the parent type that exist at the time
+Control_Type is defined are those that exist for Control_Type's parent
+type, Ada.Finalization.Controlled, namely Initialize, Finalize,
+Adjust.
+
+So to me, those are "the inherited user-defined subprograms" to which
+3.2.3(4) refers.  I've always interpreted it that way, just from the
+language of those two sections, independently of any other language in
+the RM or of any conclusion that a different interpretation would be
+nonsense.
+
+> Of course, that seems to be a nonsense interpretation of the language. I
+> think that 3.2.3(4) was intended to apply only to routines inherited from
+> the parent.
+
+I agree.  I personally think the intent is already clear from the RM.
 
 ****************************************************************
 
 From: Matthew Heaney
-Sent: Tuesday, February 17, 2004  9:31 AM
+Sent: Tuesday, February 24, 2004  9:31 AM
 
 ****************************************************************
 
 From: Matthew Heaney
-Sent: Tuesday, February 17, 2004  9:31 AM
+Sent: Tuesday, February 24, 2004  9:31 AM
 
 ****************************************************************
 
 From: Matthew Heaney
-Sent: Tuesday, February 17, 2004  9:31 AM
+Sent: Tuesday, February 24, 2004  9:31 AM
 
 ****************************************************************
 
 From: Matthew Heaney
-Sent: Tuesday, February 17, 2004  9:31 AM
+Sent: Tuesday, February 24, 2004  9:31 AM
 
 ****************************************************************
 
 From: Matthew Heaney
-Sent: Tuesday, February 17, 2004  9:31 AM
+Sent: Tuesday, February 24, 2004  9:31 AM
 
 ****************************************************************
 
 From: Matthew Heaney
-Sent: Tuesday, February 17, 2004  9:31 AM
+Sent: Tuesday, February 24, 2004  9:31 AM
 
 ****************************************************************
 
 From: Matthew Heaney
-Sent: Tuesday, February 17, 2004  9:31 AM
+Sent: Tuesday, February 24, 2004  9:31 AM
 
 ****************************************************************
 
 From: Matthew Heaney
-Sent: Tuesday, February 17, 2004  9:31 AM
+Sent: Tuesday, February 24, 2004  9:31 AM
 
 ****************************************************************
 
 From: Matthew Heaney
-Sent: Tuesday, February 17, 2004  9:31 AM
+Sent: Tuesday, February 24, 2004  9:31 AM
 
 ****************************************************************
 
 From: Matthew Heaney
-Sent: Tuesday, February 17, 2004  9:31 AM
+Sent: Tuesday, February 24, 2004  9:31 AM
 
 ****************************************************************
 

Questions? Ask the ACAA Technical Agent