CVS difference for ais/ai-30302.txt

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

--- ais/ai-30302.txt	2005/04/15 04:31:25	1.16
+++ ais/ai-30302.txt	2005/05/15 23:47:03	1.17
@@ -1,5 +1,6 @@
 !standard A.17                                       04-02-13  AI95-00302-04/00
 !class amendment 04-02-13
+!status No Action (11-0-0) 05-04-16
 !status work item 04-02-13
 !status received 04-02-13
 !priority Medium
@@ -27,6 +28,528 @@
 !appendix
 
 [Editor's note: For mail earlier than February 6, 2004, see AI-302-3.]
+
+****************************************************************
+
+From: Jeffrey Carter
+Sent: Thursday, February 5, 2004  11:38 AM
+
+Tucker Taft wrote:
+
+> The term "vector" for extensible array is used in Java
+> as well.  I think we should strive to use terminology
+> that has become widely used in the programming community.
+
+I disagree, even though I know that's dangerous when discussing Ada with
+STT. An application that uses both extensible arrays and mathematical
+vectors will be very confusing if both are called vectors. Since an
+explicit design goal of Ada is to emphasize ease of reading, calling an
+extensible array a vector seems inappropriate.
+
+> 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.
+
+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. 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.
+
+> So we settled on Vector, Map, and Set as three basic yet
+> important abstractions that will help lift the level of
+> programming above arrays and records.  In my experience
+> with using languages that have large container libraries,
+> it is these three that are used more widely than all
+> the others combined.
+
+There was an article by Mills [Harlan D. Mills, Richard C. Linger: Data
+Structured Programming: Program Design without Arrays and Pointers. IEEE
+Trans. Software Eng. 12(2): 192-197 (1986)] that proposed that
+applications only use queues, stacks, and sets (real sets, with union,
+intersection, and such operations). It's an interesting concept, and I
+agree with the aim of programs using appropriate abstractions and hiding
+lower level implementation details, especially use of pointers.
+
+****************************************************************
+
+From: Alexandre E. Kopilovitch
+Sent: Thursday, February 5, 2004  9:04 AM
+
+Tucker Taft wrote:
+
+> The term "vector" for extensible array is used in Java
+> as well.  I think we should strive to use terminology
+> that has become widely used in the programming community.
+
+So call it Java_Vector - that will be at least consistent.
+
+Do you think that Java meaning for "vector" is more significant for Ada than
+mathematical meaning of this term (which never implied extensibility) ?
+
+Why not call that thing Flexible_Array (after Algol-68, I think) - this name
+will directly reflect the essense.
+
+****************************************************************
+
+From: Robert A. Duff
+Sent: Thursday, February 5, 2004  1:37 PM
+
+Bill Wulf and other professors at CMU circa late 1970's were using the
+term "vector" to mean "array" (not necessarily extensible); that's the
+first time *I* heard it.  So it's not a Java-ism.
+
+I think this meaning of "vector" derives from the maths meaning,
+even if it's not precisely the same thing.
+
+****************************************************************
+
+From: Stephen Leake
+Sent: Thursday, February 5, 2004  2:18 PM
+
+Jeffrey Carter <jrcarter@acm.org> writes:
+
+> Tucker Taft wrote:
+>
+> > The term "vector" for extensible array is used in Java
+> > as well.  I think we should strive to use terminology
+> > that has become widely used in the programming community.
+>
+> I disagree, even though I know that's dangerous when discussing Ada
+> with STT. An application that uses both extensible arrays and
+> mathematical vectors will be very confusing if both are called
+> vectors. Since an explicit design goal of Ada is to emphasize ease of
+> reading, calling an extensible array a vector seems inappropriate.
+
+I agree with Tucker. I have code that uses both Cartesian vectors and
+extensible arrays. One is SAL.Math_Double.DOF_3.Cart_Vector_Type, the
+other is SAL.Poly.Unbounded_Arrays. Obviously, I have different names
+for them, as Carter wants. But if I called them
+SAL.Math_Double.DOF_3.Vector and SAL.Poly.Vector, I would have no
+chance of confusion. That's what package hierarchies are for.
+
+Since both Java and C++ use the term "vector" for an extensible array,
+I think Ada should also. Part of the point of the OY revision is to
+make the language more attractive to current users of other languages.
+This is an easy way to do that.
+
+> (Replace_Slice and Slice?); and 'First, 'Last, and 'Length (though
+> 'First is a constant for an EA).
+
+'First is not constant for SAL.Poly.Unbounded_Arrays; I provide both
+Append and Prepend operations. I don't think I've ever used Prepend,
+though; it was really just an exercise in what was possible.
+
+> .. I don't see
+> a need for Front, Back, Insert, Delete, and so on.
+
+I use Insert and Delete in real applications.
+
+> 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. 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.
+
+I agree. A lists package would be nice.
+
+But I also agree with Tucker, that it is difficult to come up with one
+list package that really meets a wide range of needs.
+
+Perhaps one list package, that meets a narrow range of needs, would
+still be useful. It would set a style standard for other list packages.
+
+****************************************************************
+
+From: Matthew Heaney
+Sent: Thursday, February 5, 2004  2:48 PM
+
+Alexandre E. Kopilovitch wrote:
+
+> So call it Java_Vector - that will be at least consistent.
+>
+> Do you think that Java meaning for "vector" is more significant for Ada than
+> mathematical meaning of this term (which never implied extensibility) ?
+>
+> Why not call that thing Flexible_Array (after Algol-68, I think) - this name
+> will directly reflect the essense.
+
+Tucker T. and Bob D. are both correct: the container is a "vector."
+
+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.
+
+It is a vector.  It has the same semantics as the identically-named
+container in the STL.  The one named "vector."
+
+The container whose name is vector does not have array semantics.  There
+is no slicing for example.
+
+The container whose name is vector has the following important properties:
+
+o inserting at the back end is amortized constant time
+o supports random access of elements, in constant time
+
+Yes, internally a vector is implemented as an array.  The Size function
+returns the length of this internal array, and Resize can be used to
+expand its length.
+
+But it is not an array.  It is a container.  Whose name is "vector".
+Just like the one in the STL.
+
+****************************************************************
+
+From: Alexandre E. Kopilovitch
+Sent: Thursday, February 5, 2004  3:46 PM
+
+No problem with all that if another term was chosen. Now, with "vector", this
+is name squatting (well, participation in name squatting in Ada case), which
+is fully appropriate for Java, somehow understandable for C++, but seems
+(still) inappropriate for Ada, especially taking into account that the involved
+term belongs to some Ada-friendly domain.
+
+****************************************************************
+
+From: Robert A. Duff
+Sent: Thursday, February 5, 2004  3:38 PM
+
+I wrote:
+
+> Bill Wulf and other professors at CMU circa late 1970's were using the
+> term "vector" to mean "array" (not necessarily extensible); that's the
+> first time *I* heard it.  So it's not a Java-ism.
+
+Actually, the meaning was "one-dimensional array".  But there was no
+implication that they could grow.
+
+> I think this meaning of "vector" derives from the maths meaning,
+> even if it's not precisely the same thing.
+
+I mean, what's a vector in 3-space?  Basically, a one-dimensional array
+of 3 real numbers -- the X, Y, and Z coordinates.
+
+Matt wrote:
+
+> It is a vector.  It has the same semantics as the identically-named
+> container in the STL.  The one named "vector."
+
+This stuff comes from the C++ STL.  I think gratuitous differences from
+that are unhelpful.  (But I admit that I was one of the folks pushing
+for "cursor" instead of "iterator".)
+
+> The container whose name is vector does not have array semantics.  There
+> is no slicing for example.
+
+Well, "no slicing" is hardly fundamental.  It could be added, or
+programmed by the client.
+
+> The container whose name is vector has the following important properties:
+>
+> o inserting at the back end is amortized constant time
+> o supports random access of elements, in constant time
+
+I think "random access" is the essence of array semantics.  After all,
+anything you can do with an array you can do with a linked list, and
+vice versa -- the only fundamental difference is the efficiency
+properties.
+
+****************************************************************
+
+From: Matthew Heaney
+Sent: Thursday, February 5, 2004  9:31 AM
+
+Robert A Duff wrote:
+
+> This stuff comes from the C++ STL.  I think gratuitous differences from
+> that are unhelpful.  (But I admit that I was one of the folks pushing
+> for "cursor" instead of "iterator".)
+
+Yes.  The world has settled on the name "vector."  Let's use the terms
+everyone else is using, unless we have a good reason not to.
+
+(BTW, that's also why I used the name "Iterator_Type".  But I have no
+issues with the name "Cursor_Type".)
+
+
+> I think "random access" is the essence of array semantics.  After all,
+> anything you can do with an array you can do with a linked list, and
+> vice versa -- the only fundamental difference is the efficiency
+> properties.
+
+But that's the essence of the argument!
+
+Yes, it's *possible* to seek to specific elements in a linked list, but
+I would hardly call that "random access."
+
+If you need fast random access to the elements in a container, and the
+number of elements in the container is large, then you can effectively
+rule out using a linked list as the container.
+
+Of course you could make the argument the other way.  If you need
+constant-time insertion of elements at any position, then that
+effectively rules out a vector, in favor of a list.
+
+****************************************************************
+
+From: Alexandre E. Kopilovitch
+Sent: Thursday, February 5, 2004  3:21 PM
+
+Robert A Duff wrote:
+
+> Bill Wulf and other professors at CMU circa late 1970's were using the
+> term "vector" to mean "array" (not necessarily extensible); that's the
+> first time *I* heard it.
+
+Yes, CMU always was (as far as I know) primarily engineering educational
+facility, and I know well that engineers (not software engineers, but rather
+general kind of engineers) often called "vector" any column or row of numbers.
+(not bothering themselves with the question how the components of that "vector"
+transform with a change of coordinate system). But apparently they never used
+this term for arrays of any other objects, and I almost never seen a case
+(even in engineering) where "vector" was used for extensible array - except
+Java and perhaps some C++ libraries.
+
+A notable exception is APL, in which "vector" is the basic term, and that
+"vector" is extensible. But in APL that "vector" is equipped with vast
+nomenclature of functions, many of them associated with genuine mathematical
+vectors, so the entire balance for the term was acceptable.
+
+> So it's not a Java-ism.
+
+Yes, not exactly - there were other precedents of sloppy usage of this term.
+But nevertheless a strong impression remains that it is exactly Java, which
+is a real reason, ground and reference for proposing this term for extensible
+arrays *now and for Ada0Y*.
+
+> I think this meaning of "vector" derives from the maths meaning,
+> even if it's not precisely the same thing.
+
+No, not at all - it lacks the primary mathematical meaning of it, and adds
+the primary feature, which meaning is totally non-mathematical (that is, there
+is no attempt to bring any mathematical meaning to it... and it will not be
+simple, if attempted).
+
+****************************************************************
+
+From: Matthew Heaney
+Sent: Thursday, February 5, 2004  5:11 PM
+
+
+
+Jeffrey Carter wrote:
+
+> The actual algorithm produces 8-bit hash values, which may no longer be
+> considered adequate, given
+>
+>> Hash_Type'Modulus shall be at least as large as the smaller of
+>> System.Max_Binary_Modulus and 2**32.
+
+In Charles I copied the hash function from GNAT.  I figure if it's good
+enough for Robert Dewar it's good enough for me...
+
+
+
+> Vector should have an iterator, in addition to allowing the user to
+> explicitly iterate over the structure.
+
+No.  Vector iterators are fragile, and hence very error prone.
+
+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.
+
+The STL has vector iterators in order to provide the infrastructure
+necessary to support generic algorithms.
+
+In Ada they are not necessary, because you can use locally-declared
+subprograms to fit within such a framework.
+
+
+
+
+>> Open issue: This function returns a value that doesn't depend on it's
+>>  parameter. It possibility could be removed in favor of just saying
+>> Index_Type'Pred(Index_Type'First) appropriately. Committee discussion
+>>  with the original proposal's author was inconclusive.
+>
+>
+> I'd say that it should be a constant, not a function. The same seems to
+> hold for First.
+
+Front can probably go away.  First is there for consistency with other
+containers.
+
+
+
+> Given that Back is defined as Index_Type'Succ (Last (Vector) ), and Last
+> (Vector) could be Index_Type'Last, there seems to be a problem. There
+> should be an assertion that Index_Type'Base'Last > Index_Type'Last.
+
+That's not really possible for generic actual index types such as
+Natural or Positive.
+
+We could get rid of the assertion, but this would impact implementors.
+That's why it's still an open issue.
+
+In my reference implementation, I don't think the generic actual type
+has to have IT'Base'First < IT'First, since internally I use Integer
+subtypes for everything.
+
+http://home.earthlink.net/~matthewjheaney/charles/ai302-20040205.zip
+
+
+
+> All the problems with Index_Type disappear with a general list, which
+> would use a cursor.
+
+The original proposal included list containers, but they were not
+included in the subcommittee report, in order to keep the size of the
+report more manageable.
+
+
+
+> An important thing about maps is that they provide fast searching,
+> typically based on a lower-level structure such as a hash table or
+> balanced tree.
+
+My original proposal had both sorted and hashed maps, but in order to
+keep the subcommittee report small support for sorted maps was removed.
+
+
+> Such structures have uses of their own in addition to
+> creating maps, and independent of the key/value concept of a map. For
+> example, an application may collect a number of values and then need to
+> quickly determine if a value is in that collection, and a searchable
+ > structure with a Get_First operation can be used for a priority queue.
+
+That's what the sorted set is for.
+
+
+> None of these applications use key/value pairs.
+
+So use the sorted set.
+
+
+> Therefore, I think it's
+> important to provide the underlying searchable structure to users.
+
+Just use the sorted set container.  If guarantees that searches only
+take O (log N) even in the worst case.
+
+
+> (Indeed, given the ease with which a user can wrap a key/value pair in a
+> record, define comparison operations for that record that only use the
+> key part, and create a map structure, given the existence of a
+> searchable structure, it could be argued, since the proposal states that
+> easily implemented structures should not be part of the library, that
+> the library should only supply searchable structures, and not maps.)
+
+The (hashed) map stores the key and element as separate components of
+the internal node of storage.
+
+If you have a record like that, containing a key-part component, then
+use the sorted set, and instantiate the nested generic package Generic_Keys.
+
+
+> Do we really need Maps.[Wide_]Strings, given that an Unbounded_String
+> can be used for the key type, and that this library should not be used
+> for applications in which the use of Unbounded_Strings is not acceptable?
+
+Yes, we really need string-key maps.
+
+
+> The Sets package is mostly incomprehensible. Sets deal with elements,
+> and operations must include testing if an element is in a set, creating
+> a set from a list of elements (set "literals"), and set union,
+> intersection, difference, and symmetric difference. Except for the
+> membership test, these are missing from the package, so I don't see what
+> it has to do with sets. It appears to be a searchable structure, not a
+> set. This is corroborated by the package Generic_Keys, which allows the
+> structure to be used as a map.
+
+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.
+
+Of course, if you want target of a set union operation to be the set
+itself, then just use Insert to insert the items.
+
+The subcommittee report has several examples of how sets are used, and
+there's at least one example showing how to use the nested generic package.
+
+See the last two slides in my AE-2003 paper presentation for an example
+of how to take the union of a set and a (sorted) list:
+
+http://home.earthlink.net/~matthewjheaney/charles/charlesppt.htm
+
+My original proposal has the same example at the very end:
+
+http://home.earthlink.net/~matthewjheaney/charles/ai302.txt
+
+
+
+> "Sans" is a French word. Since the ARM is in English, we should use the
+> English "without" instead. "No" might also be acceptable.
+
+Je crois que non.  C'est une bonne idea.
+
+The name for Delete_Sans_Increment comes from Emacs lisp, which has the
+functions file-name-sans-extension and file-name-sans-versions.
+
+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?
+
+
+
+> I'd like to thank the select committee for their work. No library will
+> completely please everyone. I will welcome any standard container
+> library in Ada 0X.
+
+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 also recommend Stanley Lippman's little book Essential C++.  That was
+my introduction to the STL, and what originally convinced me that
+Stepanov's approach was the correct one.
+
+You might also like Accelerated C++ by Andrew Koenig and Barbara Moo,
+which uses the STL as a basis for teaching C++.
+
+****************************************************************
+
+From: Randy Brukardt
+Sent: Thursday, February 5, 2004  5:49 PM
+
+Matt's too modest. The tutorial that makes up the !example section is
+actually quite good. I learned a lot about how the packages work (and how to
+use them) from reading it carefully, and I recommend that everyone do that
+to better understand Matt's work.
 
 ****************************************************************
 

Questions? Ask the ACAA Technical Agent