CVS difference for ais/ai-30302.txt

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

--- ais/ai-30302.txt	2004/11/17 00:53:02	1.14
+++ ais/ai-30302.txt	2005/01/07 03:07:48	1.15
@@ -26,10 +26,1113 @@
 
 !appendix
 
-[Editor's note: For mail earlier than February 8, 2004, see AI-302-3.]
+[Editor's note: For mail earlier than February 6, 2004, see AI-302-3.]
 
 ****************************************************************
 
+From: Randy Brukardt
+Sent: Thursday, February 5, 2004  3:48 PM
+
+Jeffrey Carter wrote:
+
+...
+> > I personally consider an extensible array (i.e. a vector) a useful and
+> > important standard container.  I don't feel the same way about a linked
+> > list, because it is so easy to implement what you want, and there
+> > are so many options when it comes to how to link the objects
+> > together that having a standard container for that hardly
+> > seems worthwhile (IMHO).
+>
+> I have no objections to an extensible array, provided it's clearly
+> identified as such. I think it should look different from the proposal,
+> but that's mainly a taste issue. I'd want direct analogs to indexing,
+> both LHS and RHS (Put and Get?); slices, both LHS and RHS (Replace_Slice
+> and Slice?); and 'First, 'Last, and 'Length (though 'First is a constant
+> for an EA). An equivalent to 'range would be nice, but impossible. The
+> only difference to a normal array would be that Put and Replace_Slice
+> can accept indices not in First .. Last. I haven't given it a great deal
+> of thought, so I'm sure I'm missing some subtleties, but I don't see a
+> need for Front, Back, Insert, Delete, and so on.
+
+Let's see:
+- direct analogs to indexing, both LHS and RHS (Element, Replace_Element);
+- slices (nope);
+- 'First (First), 'Last (Last), 'Length (Length);
+
+Looks like pretty much everything is in there. And slicing will be expensive
+if the implementation is not a straight array, so it's somewhat dubious.
+Insert and Delete provide easier ways of adding or removing items than
+slices - and how often do you use a slice of a non-string type for something
+other than inserting or deleting elements anyway??
+
+Ada doesn't (and isn't) going to support user-defined indexing or
+user-defined attributes, so this is about the best you can do. So what's the
+complaint (other than the name)??
+
+> The proposal says that containers "that are relatively easy to code,
+> redundant, or rarely used are omitted". It also says that lists are
+> difficult to implement correctly.
+
+I think that's a mistake; only very rare operations are difficult to code.
+We didn't update every piece of the original text, and that one is
+misleading.
+
+> Given a list, structures such as
+> deques, stacks, and especially queues are easy to implement. Since
+> queues are common structures and not redundant (none of the proposed
+> containers provides an efficient implementation of a queue), the
+> proposal itself seems to argue that lists should be provided, since they
+> are not easy to code correctly, and provide a basis for the user to
+> easily code queues.
+
+The user can easily code a queue in terms of a Vector (that's one of the
+uses of Insert!). We dropped the list component because it had an identical
+interface to the Vector component, but was less flexible (no computed O(1)
+access).
+
+In any case efficiency is not a goal of the standard containers. It would be
+incorrect for the standard to specify performance to the point that only a
+single implementation would be possible. Moreover, we anticipate a secondary
+standard that *does* try to provide more control over performance (by adding
+lists, bounded forms, etc.)
+
+In my view, it is a mistake for projects to depend on standard containers
+where there are critical performance requirements (not just time, but also
+space as well). In that case, you really have to have control of the
+implementation -- you really need *all* of the source code. You can't trust
+something provided by the standard (or your compiler vendor) in those cases.
+
+In any case, the purpose of these containers is to provide a seed and a
+standard direction. I would hope that they would reduce the tower of babel
+that Ada containers are nowdays - by providing a style for other containers
+to follow. No one is suggesting that these are sufficient to solve all
+programming problems - just 80% of them, especially in prototypes and in Q&D
+programs.
+
+****************************************************************
+
+From: Martin Dowie
+Sent: Thursday, February 5, 2004  5:50 PM
+
+> Dowie, Martin (UK) wrote:
+> > I could but wasn't part of the purpose of the library to allow us to
+> > do common things more easily? And I'd have to say I'd use a 'Quit'
+> > version a _lot_ more than the current process everything,
+> > every time one.
+>
+> It would be helpful if you could be specific about what kind of
+> container you were using.
+
+I was thinking, primarily, of a project that used single (bounded) lists to
+hold commands (a basic, domain-specific, scripting language I guess),
+one of which was 'stop this sequence of commands'.
+
+This pattern has since shown itself to be quite common in embedded
+systems - for either domain-specific scripting languages or graphics.
+
+There is the other idiom where one is processing an iteration of items
+and an external event occurs that stops the processing - e.g. the 'stop'
+button is pushed on a GUI-search window, but it could equally be a
+50Hz message over a 1553.
+
+****************************************************************
+
+From: Randy Brukardt
+Sent: Thursday, February 5, 2004  6:14 PM
+
+> I was thinking, primarily, of a project that used single (bounded) lists to
+> hold commands (a basic, domain-specific, scripting language I guess),
+> one of which was 'stop this sequence of commands'.
+
+My understanding of the model is that passive iterators are only for cases
+where you want to iterate over the entire container. Thus, this is clearly a
+use for an active iterator. Indeed, given the iteration model of packages,
+there's hardly any reason to use a passive iterator. They're harder to write
+(a subprogram and instantiation are required), and (especially if a Quit
+parameter is provided), harder to understand.
+
+We dropped the passive iterator from the Ada.Directories package precisely
+because even ARG members were confused about how it worked. Even though it
+was a classic passive iterator with a Quit parameter. Perhaps the confusion
+really was the Quit parameter (I thought it was the whole idea), but in any
+case, you've got to keep them simple.
+
+> This pattern has since shown itself to be quite common in embedded
+> systems - for either domain-specific scripting languages or graphics.
+>
+> There is the other idiom where one is processing an iteration of items
+> and an external event occurs that stops the processing - e.g. the 'stop'
+> button is pushed on a GUI-search window, but it could equally be a
+> 50Hz message over a 1553.
+
+It seems to me that an abort situation is best handled by propagating an
+exception. Otherwise, you end up distributing termination code/flags
+everywhere in the application. But YMMV.
+
+****************************************************************
+
+From: Jeffery Carter
+Sent: Thursday, February 5, 2004  6:39 PM
+
+Matthew Heaney wrote:
+
+> Alexandre K. and Jeff C. are both incorrect.  The container is not a
+>  list, not a Java_Vector, not an Extensible_Array, and not a
+> Flexible_Array.
+
+Matthew H. is incorrect. The data structure is not a vector.
+
+I am at least as qualified as Matthew H. to make such pronouncements.
+
+****************************************************************
+
+From: Jeffery Carter
+Sent: Friday, February 6, 2004  1:05 PM
+
+A comment on type names.
+
+Ada 83, with the unfortunate* exception of File_Type, did not use
+"_Type" on the end of predefined type names. We have Address and Count,
+not Address_Type and Count_Type. Ada 95 adhered to this principle, so we
+have Storage_Element and Unbounded_String, not Storage_Element_Type and
+Unbounded_String_Type.
+
+For consistency, I think the Ada-0X process should also adhere to this
+principle. The use of "_Type" on type names in the proposal should be
+eliminated. This takes some time and thought to do well; I am willing to
+volunteer for the effort if the Committee cannot spare the time and
+cannot find anyone preferable.
+
+This is a matter of consistently. While it is not my style, and not
+recommended by the Quality and Style Guide, I have used libraries that
+use the "_Type" convention without problem. I am concerned that the ARM
+be consistent far more than I am about what convention the ARM uses.
+
+*"Unfortunate" because it is inconsistent.
+
+****************************************************************
+
+From: Matthew Heaney
+Sent: Friday, February 6, 2004  9:33 AM
+
+I have updated the reference implementation, which now has the sorted
+set container, too.
+
+There's also a test_sets.adb, so you have something to run.  You can
+pass a seed on the command line.
+
+<http://home.earthlink.net/~matthewjheaney/charles/ai302-20040206.zip>
+
+I'll take care of the hashed map containers this weekend, and post Mon AM.
+
+****************************************************************
+
+From: Matthew Heaney
+Sent: Friday, February 6, 2004  3:36 PM
+
+Martin Dowie wrote:
+
+> I was thinking, primarily, of a project that used single (bounded) lists to
+> hold commands (a basic, domain-specific, scripting language I guess),
+> one of which was 'stop this sequence of commands'.
+
+It sounds like you have a sequence container, that you traverse from
+front to back.
+
+The only sequence container in the proposal is a vector, which doesn't
+have a passive iterator.  Again, I recommend just using a loop:
+
+    for Index in First (V) .. Last (V) loop
+       declare
+          Command : Command_Type := Element (V, Index);
+       begin
+          exit when Is_Stop (Command);
+          -- process command
+       end;
+    end loop;
+
+
+If these are commands that have an order (say, each command has a
+timestamp, and commands are executed in timestamp order), then you can
+use the sorted set.  Again, an explicit loop is appropriate:
+
+declare
+    I : Cursor_Type := First (S);
+    J : constant Cursor_Type := Back (S);
+begin
+    while I /= J loop
+       declare
+          Command : Command_Type := Element (I);
+       begin
+          exit when Is_Stop (Command);
+          -- process command
+       end;
+
+       Increment (I);
+    end loop;
+end;
+
+****************************************************************
+
+From: Alexandre E. Kopilovitch
+Sent: Friday, February 6, 2004  4:24 PM
+
+> The only sequence container in the proposal is a vector,
+
+Ah, yes, it's Sequence - quite right name for that container (and not Vector).
+
+****************************************************************
+
+From: Jeffrey Carter
+Sent: Friday, February 6, 2004  7:17 PM
+
+Randy Brukardt wrote:
+
+> Let's see:
+> - direct analogs to indexing, both LHS and RHS (Element, Replace_Element);
+> - slices (nope);
+> - 'First (First), 'Last (Last), 'Length (Length);
+>
+> Looks like pretty much everything is in there. And slicing will be expensive
+> if the implementation is not a straight array, so it's somewhat dubious.
+> Insert and Delete provide easier ways of adding or removing items than
+> slices - and how often do you use a slice of a non-string type for something
+> other than inserting or deleting elements anyway??
+
+Slicing isn't included because C++ doesn't have slices, so it's a
+foreign concept to its library and users. If we want to attract users of
+inferior languages to Ada, it should be because Ada is better. Ada's
+slices are a way that Ada is better; Ada's standard extensible array
+component should be better than its competition by also offering them. I
+do not see mimicking C++'s shortcomings as advisable.
+
+Insertion and deletion are basic operations of lists, but not of arrays.
+That's why the list and vector components had the same set of
+operations: they both specify lists with different implementations.
+
+Since String is an array, and [Un]Bounded_String is an extensible array,
+and we're now told the correct name is Vector, shouldn't these be
+renamed to something like Character_Vector?
+
+> Ada doesn't (and isn't) going to support user-defined indexing or
+> user-defined attributes, so this is about the best you can do. So what's the
+> complaint (other than the name)??
+
+I don't expect user-defined indexing, slices, or attributes, which is
+why I talked about "analogs" to them. Missing slices is one complaint.
+And, yes, the name is unarguably wrong.
+
+In the C family of languages, users are accustomed to having to look at
+implementations in order to understand how to use something. Subprogram
+"prototypes" (yet another misused term to add to the collection) are
+generally insufficient, and appropriate comments are often lacking. So
+it comes as no surprise to me that C++ expects newcomers to its library,
+looking for an extensible array, and not finding anothing with an
+appropriate name, to have to look at the operations of the components to
+find that the inappropriately named "vector" is really an extensible array.
+
+However, this is not the Ada way, and I think it completely
+inappropriate to mimick this mistake. Looking at other languages'
+library to select useful components is fine; insisting that an Ada
+version must be identical to that of another language, including
+mistakes, is not.
+
+> The user can easily code a queue in terms of a Vector (that's one of the
+> uses of Insert!). We dropped the list component because it had an identical
+> interface to the Vector component, but was less flexible (no computed O(1)
+> access).
+
+The perfomance of a queue based on an extensible array is likely to be
+just as objectionable as extracting an element from an extensible array
+based on a list. That the vector and list components both had the same
+interface is further evidence that mimicking the STL is a bad idea.
+Insert and delete are as foreign to an extensible array as indexing and
+slicing should be to a list.
+
+> In my view, it is a mistake for projects to depend on standard containers
+> where there are critical performance requirements (not just time, but also
+> space as well). In that case, you really have to have control of the
+> implementation -- you really need *all* of the source code. You can't trust
+> something provided by the standard (or your compiler vendor) in those cases.
+
+I agree. That doesn't mean that the standard shouldn't provide a basis
+for queues with performance characteristics suitable for performance
+non-critical applications, which an extensible array does not provide.
+
+****************************************************************
+
+From: Randy Brukardt
+Sent: Friday, February 6, 2004  8:24 PM
+
+Jeff Carter wrote:
+
+...
+> I agree. That doesn't mean that the standard shouldn't provide a basis
+> for queues with performance characteristics suitable for performance
+> non-critical applications, which an extensible array does not provide.
+
+Huh? You've said, in effect, that the performance isn't good enough for
+applications where the performance doesn't matter. That's a pretty goofy
+statement!
+
+My opinion has not changed: if you care about performance *at all*, you
+*cannot* depend on *any* standard containers. But usually the performance
+does not matter at all (or so little as to be equivalent to not at all): the
+number of elements in the container is small (which would be true for
+virtually all queues), and/or it is used infrequently, and/or the
+application is a throw-away.
+
+Otherwise, if you are writing portable code, you shouldn't use a predefined
+container library at all -- the performance is likely to vary much more
+across implementations than code you write yourself. For instance, on
+Janus/Ada, any generic list container is going run 2-5 times slower than the
+same list created yourself -- that's just the effect of the extra call
+overhead and the shared body (which means the elements will be dynamically
+allocated - separately - in any case - at least doubling the allocation
+overhead). I'd expeect that effect to be much less on GNAT, for example,
+because they don't share generic bodies and thus don't have the double
+allocation overhead.
+
+If your application doesn't care about the component being 5 times slower,
+then it is highly unlikely that it is going to care about whether the
+Vector/Sequence/List component is implemented as an array, as a list, as a
+tree, as a hash table, or as something else.
+
+My preference with these components would be to say absolutely nothing about
+performance or implementation (because anything said is as meaningless as
+real-time metrics are). But others believe that that would cause real
+portability problems, and I'm willing to go along with that.
+
+The problem I see is a lot of people are looking far too closely at tiny
+pieces of abstractions.  You might have a queue or a list as part of a large
+abstraction, but they're pretty much useless by themselves. And given that
+creating a queue or stack (both of which have only two operations, both
+trivial!) would take 3 minutes max, it makes no sense to use a complex (and
+necessarily slow) container library for just that -- indeed, it probably
+would be more work to use a container than the 3 minutes.
+
+I much prefer the vision of this containers library, where the only
+containers included are those that are large, complex, multi-purpose, and
+have a clear abstraction.
+
+****************************************************************
+
+From: Jeffrey Carter
+Sent: Friday, February 6, 2004  7:39 PM
+
+Matthew Heaney wrote:
+
+> No.  Vector iterators are fragile, and hence very error prone.
+
+Modifying a structure from an iterator should be a bounded error.
+
+> They are fragile because the (logical) internal array gets thrown away
+> during expansion, which invalidates the iterator.  It's too hard to keep
+> track of whether a vector iterator is still valid, and most of the time
+> you end up with a dangling reference.
+
+You can only talk about what happens internally during an operation if a
+specific implementation is required, which Randy assures us is not the case.
+
+> A "set" is really any sorted sequence of items.  If you want set
+> intersection, symmetric difference, etc, then just use a generic
+> algorithm.  See the Charles library for such algorithms.
+
+I've used sets for decades, in discrete math, in specification languages
+such as Z, and in programming. A set is an unordered collection of
+elements from a universe that provides operations such as membership,
+union, intersection, and the like, represented by mathematical symbols
+that I can't reliably represent in an e-mail.
+
+An implementation of a set may be sorted to speed up operations, but
+that's a feature of the implementation, not of the concept implemented.
+That's a distinction that many users of C-family languages seem unable
+to make, but that I expect from those who embrace Ada.
+
+> The name for Delete_Sans_Increment comes from Emacs lisp, which has the
+> functions file-name-sans-extension and file-name-sans-versions.
+
+Yet another case of mimicking others' errors.
+
+> It was also in homage to Ada's French history, given that her original
+> designer was French, and worked for a French company.
+>
+> Why do you think "rendevous" was named that way?
+
+"Rendezvous" is not a predefined indentifier in the ARM. It was chosen
+because no English word has the precise meaning intended, and Ada's
+designers understood the importance of precise terminology.
+
+> If you don't immediately grok how vectors and sets and maps work, then I
+> suggest familiarizing yourself with the STL. There are lots of tutorials
+> on the WWW.
+
+I've been using arrays, including extensible arrays, sets, and maps for
+decades. I've also been using vectors for decades, having done a lot of
+scientific programming that required matrix math. I doubt that a study
+of C++ mistakes would have any effect besides raising my blood pressure.
+
+****************************************************************
+
+From: Jeffrey Carter
+Sent: Friday, February 6, 2004  7:22 PM
+
+Randy Brukardt wrote:
+
+> Precisely my point. That is intended to say that there is a logical array in
+> the container, but not necessarly an actual one. Matt's descriptions were
+> too implementation-specific, and we moved most of that. But I'm not
+> surprised that some was missed.
+
+On closer inspection, the Size and Resize operations certainly imply an
+array implementation; they are meaningless otherwise.
+
+****************************************************************
+
+From: Randy Brukardt
+Sent: Friday, February 6, 2004  9:09 PM
+
+Huh? Resize tells the container a reasonable size to use; what the container
+does with that information is up to it. Size simply returns that
+information.
+
+That's no different than many of the attributes in Ada, which (if set),
+always return the values that they were set to. But what the compiler does
+with those values is (almost) completely implementation-defined.
+
+The only real requirement here is O(1) element access (which prevents the
+use of a straight linked list).
+
+Janus/Ada will probably use an array of pointers (or possibly array of
+arrays of pointers); we're going to be (implicitly) allocating the elements
+anyway, we might as well do it explicitly and take advantage of that to make
+Insert/Delete/Sort (and any expansions) much cheaper (presuming the elements
+are bigger than scalar types). An array of arrays of pointers is even
+better, because insertion cost is bounded by the maximum size of an array
+chunk -- but there is more overhead and complexity, so I'd like to see some
+real uses before deciding on an implementation.
+
+Note that a pure list component has no real opportunity for "better"
+implementations, and indeed, any implementation on Janus/Ada would suffer
+from "double" allocation.
+
+****************************************************************
+
+From: Martin Dowie
+Sent: Saturday, February 7, 2004  4:02 AM
+
+> We dropped the passive iterator from the Ada.Directories package precisely
+> because even ARG members were confused about how it worked. Even though it
+> was a classic passive iterator with a Quit parameter. Perhaps the confusion
+> really was the Quit parameter (I thought it was the whole idea), but in any
+> case, you've got to keep them simple.
+
+I didn't find it confusing so I provided an extra child
+Ada.Directories.Iterate - and I've used it repeatedly!
+
+> > This pattern has since shown itself to be quite common in embedded
+> > systems - for either domain-specific scripting languages or graphics.
+> >
+> > There is the other idiom where one is processing an iteration of items
+> > and an external event occurs that stops the processing - e.g. the 'stop'
+> > button is pushed on a GUI-search window, but it could equally be a
+> > 50Hz message over a 1553.
+>
+> It seems to me that an abort situation is best handled by propagating an
+> exception. Otherwise, you end up distributing termination code/flags
+> everywhere in the application. But YMMV.
+
+I have tended to work in deeply enbedded systems, where exceptions (in
+any language!) are at best frowned upon and quite often forbidden! :-(
+
+****************************************************************
+
+From: Martin Dowie
+Sent: Saturday, February 7, 2004  4:25 AM
+
+> > I was thinking, primarily, of a project that used single (bounded) lists to
+> > hold commands (a basic, domain-specific, scripting language I guess),
+> > one of which was 'stop this sequence of commands'.
+>
+> It sounds like you have a sequence container, that you traverse from
+> front to back.
+
+Pretty much, although we also read in where each 'First' is as the whole
+contained many 'subroutines'.
+
+
+> The only sequence container in the proposal is a vector, which doesn't
+> have a passive iterator.  Again, I recommend just using a loop:
+
+I suspect the first thing I will do is add an extra child generic subprogram
+Ada.Containers.Vectors.Iterate! :-)
+
+****************************************************************
+
+From: Martin Krischik
+Sent: Saturday, February 7, 2004  6:16 AM
+
+> I suspect the first thing I will do is add an extra child generic
+> subprogram Ada.Containers.Vectors.Iterate! :-)
+
+Well, guess don't use GNAT. GNAT gets quite upset if you try to add something
+to the Ada packages.
+
+****************************************************************
+
+From: Marius Amado Alves
+Sent: Saturday, February 7, 2004  7:45 PM
+
+I'd expect *any* compiler to get really upset with this ;-)
+
+****************************************************************
+
+From: Martin Dowie
+Sent: Sunday, February 8, 2004  2:08 AM
+
+"gcc -gnatg" or "gnatmake -a" will stop any warnings :-)
+
+****************************************************************
+
+From: Martin Krischik
+Sent: Saturday, February 7, 2004  5:09 AM
+
+> Jeffrey Carter wrote:
+
+> > Given a list, structures such as
+> > deques, stacks, and especially queues are easy to implement. Since
+> > queues are common structures and not redundant (none of the proposed
+> > containers provides an efficient implementation of a queue), the
+> > proposal itself seems to argue that lists should be provided, since they
+> > are not easy to code correctly, and provide a basis for the user to
+> > easily code queues.
+
+> The user can easily code a queue in terms of a Vector (that's one of the
+> uses of Insert!). We dropped the list component because it had an identical
+> interface to the Vector component, but was less flexible (no computed O(1)
+> access).
+
+True enough. But if you wanted a build generic queue on top of the vector the
+tag should not be hidden from view. Otherwise one need to repeat all the
+access methods instead of just renaming the one provided from the parent
+package.
+
+In fact the hidden tag is the one feature which I realey dislike in charles.
+
+****************************************************************
+
+From: Stephen Leake
+Sent: Saturday, February 7, 2004  8:40 AM
+
+"Randy Brukardt" <randy@rrsoftware.com> writes:
+
+> Report of the ARG Select Committee on Containers
+> February 3, 2004
+
+Thanks for the committee's hard work on this.
+
+What is the rationale for making the Map Key_Type definite, as opposed
+to indefinite? Since an indefinite Key_Type is required for
+Containers.Maps.Strings, why not make that capability available to the
+users?
+
+I don't see a discussion of this in AI-302-03/01.
+
+
+Another point: Containers.Vectors.Size should return Index_Type'Base,
+and the Size parameter in Resize should also be Index_Type'Base. It's
+confusing to have different types for Size and Index.
+
+There's also a problem if Natural'Last < Index_Type'Last; you
+can't have a vector that contains every index!
+
+****************************************************************
+
+From: Randy Brukardt
+Sent: Saturday, February 7, 2004  6:03 PM
+
+> What is the rationale for making the Map Key_Type definite, as opposed
+> to indefinite?
+
+The 'committee' primarily adopted the existing proposal submitted by Matt
+Heaney. We decided not to change any of the major design decisions of that
+proposal - because no package will suit everyone or every need, and we felt
+it was more important to standardize something coherently designed for most
+needs than to fiddle endlessly with it and risk introducing serious bugs.
+
+Which is to say, I don't know. :-)
+
+> Since an indefinite Key_Type is required for
+> Containers.Maps.Strings, why not make that capability available to the
+> users?
+
+We definitely expect that the strings container will use a purpose-built
+data structure for storing strings, not some general indefinite item
+capability. Ways to compactly and efficiently store sets of varying size
+strings are well known and commonly used.
+
+Such algorithms could be extended to a general "unconstrained array of
+elementary", but that hardly seems to be a worthwhile definition for keys.
+
+...
+> Another point: Containers.Vectors.Size should return Index_Type'Base,
+> and the Size parameter in Resize should also be Index_Type'Base. It's
+> confusing to have different types for Size and Index.
+>
+> There's also a problem if Natural'Last < Index_Type'Last; you
+> can't have a vector that contains every index!
+
+Yes, that's a serious problem on Janus/Ada (Integer is 16-bit). However, you
+want the Size and Resize operations to take a numeric type that contains
+zero -- and certainly Index_Type is not that. Index_Type could be a subtype
+of an enumeration type or a subtype of a modular type (neither of which can
+contain zero) or a subtype of an integer type not containing zero.
+
+We had a short, inconclusive discussion about whether the index type ought
+to be range <> rather than (<>) (because enumeration and modular types fail
+the assertion and thus aren't directly usable), but that still doesn't
+guarantee a zero. Moreover, if the integer type has negative numbers, then
+the Length of the vector could be larger than Index_Type'Last.
+
+So I don't see a great solution. I wondered about using "Hash_Type" here (it
+has the correct properties), but that seems like a misuse of the type (and a
+bad idea in a library that most Ada programmers will read - you want to show
+them good style in standard libraries).
+
+****************************************************************
+
+From: Martin Krischik
+Sent: Saturday, February 7, 2004  5:15 AM
+
+> The perfomance of a queue based on an extensible array is likely to be
+> just as objectionable as extracting an element from an extensible array
+> based on a list. That the vector and list components both had the same
+> interface is further evidence that mimicking the STL is a bad idea.
+> Insert and delete are as foreign to an extensible array as indexing and
+> slicing should be to a list.
+
+Well, depends. Most queues are not supposed to grow indefinetly so an using a
+vector with an modular type as index will give you good perfomace. Every Ada
+tutorial contains a expample on how to do it.
+
+****************************************************************
+
+From: Martin Krischik
+Sent: Saturday, February 7, 2004  6:14 AM
+
+> The committee selected the second proposal as a starting point for a
+> standard containers library, with a number of simple changes. The
+> changes were simple enough that we produced a version of the library with
+> the changes made (AI-00302-3/01).
+
+Any place where I can actualy read the draft?
+
+Anyway, looking at the reference impementation vom Matthew Heaney (thanks for
+the quick responce) I have an improvements to suggest:
+
+type Element_Type is private;
+
+I said this bevore that is too limiting. With that signature you can't even
+store strings. And more important you cant store Element'Class. In fact I
+predict that with that signature 80% of all data stored will be "access to
+something".
+
+I have often heard Ada does not need garbage collection since a good container
+library should take care of memory management - and now I ready to follow
+that point. But taking that argument, vector is not a good container.
+
+Since vector will need heap storrage anyway and performace is only a minor
+issue I suggest:
+
+type Element_Type (<>) is private;
+
+****************************************************************
+
+From: Randy Brukardt
+Sent: Saturday, February 7, 2004  6:05 PM
+
+> Any place where I can actualy read the draft?
+
+The same place that you can read any other AI: www.ada-auth.org.
+
+****************************************************************
+
+From: Martin Krischik
+Sent: Sunday, February 8, 2004  4:58 AM
+
+I looked there but I only found a very long discussion but not the
+actual concluding decision.
+
+****************************************************************
+
+From: Randy Brukardt
+Sent: Monday, February 9, 2004  6:03 PM
+
+Don't know what you're looking for, but certainly the entire AI is posted
+there. As with all AIs, the !wording section is what goes into the standard.
+
+****************************************************************
+
+From: Martin Krischik
+Sent: Saturday, February 7, 2004  6:24 AM
+
+> > The only sequence container in the proposal is a vector,
+>
+> Ah, yes, it's Sequence - quite right name for that container (and not
+> Vector).
+
+No, in my book elements in a Sequence have only a relative positions, or at
+least the relative position is the primary position and absolut position is
+only the secondary.
+
+That is: Get_Next (V); is faster or as fast as Get (V, 5);
+
+****************************************************************
+
+From: Martin Krischik
+Sent: Saturday, February 7, 2004  6:32 AM
+
+> My understanding of the model is that passive iterators are only for cases
+> where you want to iterate over the entire container.
+
+Yes.
+
+> Indeed, given the iteration model of packages,
+> there's hardly any reason to use a passive iterator.
+
+Passive Iterators should allways provide the fastes mean to iterate over the
+hole container. They should do so by knowing the internals of the container.
+
+Of course it only matters in advanced container with B-Trees or AVL-Trees as
+as internal structure. But I have only seen those in IBM's Open Class Library
+(which is far better the the STL).
+
+But there are no advanced containers in AI 302.
+
+****************************************************************
+
+From: Randy Brukardt
+Sent: Saturday, February 7, 2004  6:21 PM
+
+> Passive Iterators should allways provide the fastes mean to iterate over the
+> hole container. They should do so by knowing the internals of the
+> container.
+
+That might be true in a language with a built-in iterator construct, but it
+is certainly not true in Ada because of the overhead of calling the generic
+formal subprogram for each element. In Janus/Ada, the overhead of calling a
+formal subprogram is at least double of a normal subprogram (we have to save
+and restore display information, because you could be calling into a more
+nested scope than the generic body -- something that normally isn't possible
+in Ada).
+
+Other compilers may not have that overhead, but they'll certainly have call
+overhead. Whereas, the explicit loop iterator for Vectors only needs to call
+Element. So the call overhead is at best a wash, and at worst much worse for
+the passive iterator. Moreover, the compiler is a lot more likely to be able
+to in-line the call to Element (which likely has a pretty simple
+implementation and thus will meet the in-lining qualifications), than the
+bunch of arbitrary code in the Process formal routine.
+
+So, a passive iterator will only be faster in complex containers (where you
+have to separate the  Element and Successor functions). For a Vector (where
+the language already has the needed iteration mechanism built-in), it's
+going to be slower (or, if you're really lucky, the same speed) and it
+certainly is a lot harder to write.
+
+So I think having it on Vector would simply be for consistency; you'd never
+actually use it if you know you're dealing with a Vector.
+
+****************************************************************
+
+From: Robert A. Duff
+Sent: Saturday, February 7, 2004  7:22 PM
+
+> Other compilers may not have that overhead, but they'll certainly have call
+> overhead. Whereas, the explicit loop iterator for Vectors only needs to call
+> Element. So the call overhead is at best a wash, and at worst much worse for
+> the passive iterator. Moreover, the compiler is a lot more likely to be able
+> to in-line the call to Element (which likely has a pretty simple
+> implementation and thus will meet the in-lining qualifications), than the
+> bunch of arbitrary code in the Process formal routine.
+
+I don't see why the compiler shouldn't inline the Process routine,
+assuming the compiler isn't doing shared generics.  They're usually
+small, but anyway, the Process routine is typically called exactly
+once, so it shouldn't matter how big it is.
+
+****************************************************************
+
+From: Randy Brukardt
+Sent: Saturday, February 7, 2004  7:33 PM
+
+Most compilers have limitations on what can be inlined; Process (which
+contains arbitrary code) is far more likely to violate one of those
+limitations than Element (which never changes and is likely to be very
+simple). In addition, many compilers only inline when you give pragma
+Inline, and you can't do that on a generic formal.
+
+****************************************************************
+
+From: Robert A. Duff
+Sent: Saturday, February 7, 2004  7:43 PM
+
+If Process violates whatever these arbitrary restrictions are, then
+sure, you can't get it inlined.  But typically Process is very simple --
+often just one line of code that calls some other procedure to do the
+real work, passing some additional parameters.  Process isn't a "real"
+procedure, conceptually -- it's just the body of a loop.
+
+In my current project, we make heavy use of the generic iterator
+pattern, and I think that in many many cases, Process is just
+a line or two of code.  (And if it's more, inlining is relatively
+less important.)
+
+>... In addition, many compilers only inline when you give pragma
+> Inline, and you can't do that on a generic formal.
+
+You give the inline on the actual.  In non-sharing implementations,
+that should apply inside the instance.  And the iterator procedure
+itself can be inlined, too.
+
+****************************************************************
+
+From: Randy Brukardt
+Sent: Saturday, February 7, 2004  8:04 PM
+
+Certainly it's not real (which is one thing I dislike about passive
+iterators in Ada - but we've discussed that before), but if it is very short
+(or the bodies of your loops are typically very short), then you're
+programming style must be very different from mine. The only loops that I
+write that are very short are those that I probably shouldn't have written
+in the first place (like the one finding the last '.' in a string) --
+there's a routine somewhere in Ada.Strings that will do the job, but looking
+it up is more work than writing the loop. (And a lot of them would be
+replaced by a Vector/List/Sequence container if I had one.)
+
+But just looking at the spam filter I'm working on at this moment: The
+average loop length is about 25 lines, the mean is around 8 lines. (There
+are more short loops than I would have guessed. But most of them wouldn't
+exist if I had a container to use instead - most of them are insert-at-end
+or delete-specific-item from a list.)
+
+...
+> You give the inline on the actual.  In non-sharing implementations,
+> that should apply inside the instance.  And the iterator procedure
+> itself can be inlined, too.
+
+At which point, you *equal* the performance of the active iterator. And only
+if *everything* goes right. The OP claimed that the passive iterator would
+always have better performance, and that's certainly not true for the vector
+container. I doubt that it would be true for the Map container, either. It
+could be true for a complex container, but those aren't commonly used.
+
+****************************************************************
+
+From: Alexandre E. Kopilovitch
+Sent: Saturday, February 7, 2004  7:55 PM
+
+Martin Krischik wrote:
+
+> > > The only sequence container in the proposal is a vector,
+> >
+> > Ah, yes, it's Sequence - quite right name for that container (and not Vector).
+>
+> No, in my book elements in a Sequence have only a relative positions, or at
+> least the relative position is the primary position and absolut position is
+> only the secondary.
+
+I don't know in which domain your book was grown up, but I can assure you that
+in mathematics (and by extension in physics and other natural sciences as they
+use mathematical apparatus) elements of a sequence are commonly indexed, and
+those indices are always treated as absolute position (which may be zero or
+even negative). By the way, your book is also certainly not from Biology/Genetics,
+where term "sequence" is used heavily, and they often speak about both absolute
+and relative positions in sequences.
+
+We have clearly different usage of terms "vector" and "sequence": substantial
+part of today's software engineering (tools and books) use them one way, while
+mathematics (and all natural sciences that use it heavily) always use them another
+way.
+
+So all the argument here about Vector/Sequence here is about Ada's choice of
+preference: will Ada choose software engineering (effectively, Java and C++
+libraries) side or mathematical/scientific side on this issue.
+
+I suppose (or hope) that the thesis "Ada is for problem space, not for solution
+space" implies the latter.
+
+****************************************************************
+
+From: Martin Krischik
+Sent: Sunday, February 8, 2004  11:40 AM
+
+> I don't know in which domain your book was grown up, but I can assure you
+
+It's the english dictornary: "Aufeinanderfolge, Reihenfolge, Szene,
+Zeitfolge". Ah, you don't speak german. Well let's look for "Reihenfolge" in
+a rushian dictornary (and have a fight with my wives rushian keyboard):
+"???????????".
+
+Asking my wives what it means she said "one after the other, queue".
+
+> that in mathematics (and by extension in physics and other natural sciences
+> as they use mathematical apparatus) elements of a sequence are commonly
+> indexed, and those indices are always treated as absolute position (which
+> may be zero or even negative). By the way, your book is also certainly not
+> from Biology/Genetics, where term "sequence" is used heavily, and they
+> often speak about both absolute and relative positions in sequences.
+
+I have spend 4 years in Great Britain I am shure if I ask anyone on the street
+there "what is a sequence" he or she will answer somthing like "one after the
+other" - and that is relativ positioning.
+
+> We have clearly different usage of terms "vector" and "sequence":
+> substantial part of today's software engineering (tools and books) use them
+> one way, while mathematics (and all natural sciences that use it heavily)
+> always use them another way.
+
+Even when it comes done to software engineering: IBM's Open Class Library has
+a Sequence - for relativ positioning  getFirst, getNext, insertAfter. Usualy
+used to fill listboxes.
+
+> So all the argument here about Vector/Sequence here is about Ada's choice
+> of preference: will Ada choose software engineering (effectively, Java and
+> C++ libraries) side or mathematical/scientific side on this issue.
+
+I don't like the STL that much. So I am not realy defending "vector".
+
+> I suppose (or hope) that the thesis "Ada is for problem space, not for
+> solution space" implies the latter.
+
+I agree with you on that too.
+
+But I think we are off topic here.
+
+****************************************************************
+
+From: Marius Amado Alves
+Sent: Saturday, February 7, 2004  8:41 PM
+
+Randy Brukardt wrote:
+
+>The 'committee' primarily adopted the existing proposal submitted by Matt
+>Heaney. We decided not to change any of the major design decisions of that
+>proposal - because no package will suit everyone or every need, and we felt
+>it was more important to standardize something coherently designed for most
+>needs than to fiddle endlessly with it and risk introducing serious bugs.
+>
+>Which is to say, I don't know. :-)
+
+I do: there is none (except perhaps the implicit one: ease of
+implementation). On the other hand, there is a rationale for indefinite
+elements. This requirement has been largely felt and voiced since ever,
+and I included it in my Bases document (I think stored in alternative
+1), and even formulated it as an Annex (stored in alternative 2 but
+applicable to any alternative). But I've always seemed to feel some
+resistance from Matt and the ARG. Which resistance I find inexplicable.
+I really don't see how making the element type indefinite may
+"compromise coherence" or "introduce bugs". Sure it complicates the
+implementation. But the increase in power for the user is a quantum
+leap, as it frees him from doing tricky memory management in many
+situations. In my proposed Annex I included this passage from someone
+who should be dear to at least one person in that group--perhaps in the
+hope of making those strange walls of resistance just shiver a bit:
+
+<<If I ask a student whether her design is as good as Chartres, she often smiles tolerantly
+at me as if to say, "Of course not, that isnt't what I am trying to do.... I could never do
+that." Then, I express my disagreement, and tell her: "That standard *must* be our
+standard. If you are going to be a builder, no other standard is worthwhile.">>
+  -- Cristopher Alexander, Foreword to [Gabriel 1996]
+
+****************************************************************
+
+From: Randy Brukardt
+Sent: Saturday, February 7, 2004  9:20 PM
+
+> I do: there is none (except perhaps the implicit one: ease of
+> implementation). On the other hand, there is a rationale for indefinite
+> elements.
+
+Perhaps. But that wasn't the question. The question was why aren't there
+indefinite *keys*.
+
+...
+> But I've always seemed to feel some
+> resistance from Matt and the ARG.
+
+Given that the "ARG" (other than the subcommittee) has not yet looked at
+these proposals, that's a pretty bizarre statement.
+
+...
+> I really don't see how making the element type indefinite may
+> "compromise coherence" or "introduce bugs". Sure it complicates the
+> implementation.
+
+And, on most implementations, I would expect it to make it *many* times
+slower. (It wouldn't have any effect on Janus/Ada, I don't think, because we
+already have to allocate an element at a time anyway.) I would guess that it
+is that efficiency concern that Matt is responding to. But I'll let him
+respond himself...
+
+****************************************************************
+
+From: Marius Amado Alves
+Sent: Sunday, February 8, 2004  6:26 AM
+
+>... that wasn't the question. The question was why aren't there
+>indefinite *keys*.
+>
+Oops... sorry.
+
+Curiously enough if you have indefinite elements the requirement for
+indefinite keys looses strength: you can then use elementary containers
+or indefinite element positions as keys.
+
+>...
+>
+>>But I've always seemed to feel some
+>>resistance from Matt and the ARG.
+>
+>Given that the "ARG" (other than the subcommittee) has not yet looked at
+>these proposals, that's a pretty bizarre statement.
+
+Just a feeling. The proposals are there in the AI, and there was some
+discussion.
+
+>>I really don't see how making the element type indefinite may
+>>"compromise coherence" or "introduce bugs". Sure it complicates the
+>>implementation.
+>
+>And, on most implementations, I would expect it to make it *many* times
+>slower....
+
+No. The system should chose at compile time a specific body according to
+the 'Definite attribute of the actual element type.
+
+Aside. Of course there is still no standard means to do this, but it
+would be a nice extension. Conditional compilation of generic bodies
+based on instantiation properties. Variant units :-)
+  generic
+    type T is private;
+    ...
+  package G is
+    when T'Definite =>
+      ...;
+    when others =>
+      ...;
+  end;
+(On the subject of conditional compilation, see also the recent Ada
+Preprocessor thread on CLA.)
+In the meanwhile, there is no requirement that Ada.Containers be
+implemented strictly in Ada, is there? I doubt any Ada 95 container
+(arrays, files) is.
+End of aside.
+
+So no coherence problem, nor bugs, nor efficiency problem :-)
+
+****************************************************************
+
 From: Tucker Taft
 Sent: Sunday, February 8, 2004  7:33 AM
 
@@ -25134,72 +26237,4 @@
 
 ****************************************************************
 
-From: Matthew Heaney
-Sent: Friday, September 2, 2004  9:31 AM
-
-****************************************************************
-
-From: Matthew Heaney
-Sent: Friday, September 2, 2004  9:31 AM
 
-****************************************************************
-
-From: Matthew Heaney
-Sent: Friday, September 2, 2004  9:31 AM
-
-****************************************************************
-
-From: Matthew Heaney
-Sent: Friday, September 2, 2004  9:31 AM
-
-****************************************************************
-
-From: Matthew Heaney
-Sent: Friday, September 2, 2004  9:31 AM
-
-****************************************************************
-
-From: Matthew Heaney
-Sent: Friday, September 2, 2004  9:31 AM
-
-****************************************************************
-
-From: Matthew Heaney
-Sent: Friday, September 2, 2004  9:31 AM
-
-****************************************************************
-
-From: Matthew Heaney
-Sent: Friday, September 2, 2004  9:31 AM
-
-****************************************************************
-
-From: Matthew Heaney
-Sent: Friday, September 2, 2004  9:31 AM
-
-****************************************************************
-
-From: Matthew Heaney
-Sent: Friday, September 2, 2004  9:31 AM
-
-****************************************************************
-
-From: Matthew Heaney
-Sent: Friday, September 2, 2004  9:31 AM
-
-****************************************************************
-
-From: Matthew Heaney
-Sent: Friday, September 2, 2004  9:31 AM
-
-****************************************************************
-
-From: Matthew Heaney
-Sent: Friday, September 2, 2004  9:31 AM
-
-****************************************************************
-
-From: Matthew Heaney
-Sent: Friday, September 2, 2004  9:31 AM
-
-****************************************************************

Questions? Ask the ACAA Technical Agent