CVS difference for 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