From mboxrd@z Thu Jan 1 00:00:00 1970 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me X-Spam-Level: X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00,LOTS_OF_MONEY autolearn=ham autolearn_force=no version=3.4.4 X-Google-Language: ENGLISH,ASCII-7-bit X-Google-Thread: 103376,fed2e7871ca258cd X-Google-Attributes: gid103376,public X-Google-ArrivalTime: 2001-12-14 17:22:06 PST Path: archiver1.google.com!news1.google.com!newsfeed.stanford.edu!news.ems.psu.edu!news.cis.ohio-state.edu!news.maxwell.syr.edu!newsfeed00.sul.t-online.de!newsfeed01.sul.t-online.de!t-online.de!fu-berlin.de!uni-berlin.de!ppp-1-78.cvx5.telinco.NET!not-for-mail From: "Nick Roberts" Newsgroups: comp.lang.ada Subject: Re: List Container Strawman 1.4 Date: Sat, 15 Dec 2001 01:20:49 -0000 Message-ID: <9ve8jn$esilp$1@ID-25716.news.dfncis.de> References: <9vbc89$eb6li$2@ID-25716.news.dfncis.de> NNTP-Posting-Host: ppp-1-78.cvx5.telinco.net (212.1.152.78) X-Trace: fu-berlin.de 1008379321 15616697 212.1.152.78 (16 [25716]) X-Priority: 3 X-MSMail-Priority: Normal X-Newsreader: Microsoft Outlook Express 5.50.4133.2400 X-MimeOLE: Produced By Microsoft MimeOLE V5.50.4133.2400 Xref: archiver1.google.com comp.lang.ada:17937 Date: 2001-12-15T01:20:49+00:00 List-Id: "Ted Dennison" wrote in message news:pMoS7.61491$xS6.100531@www.newsranger.com... > However, there are some very good ideas in there, most notably the unconstrained > array conversions and the Direction type, that have made their way into the > Strawman. Ironically, I want to remove the Forward parameters (of type Direction) from all the operations (and replace the functionality with a 'smart reverse' operation). "Ted Dennison" wrote in message news:z9aN7.41127$xS6.69040@www.newsranger.com... > On the other hand, I'm not a big fan of the iterator approach used. In an > "unbounded" package, I don't think the user should have to worry about running > out of resources like iterators. That sort of breaks the whole "unbounded" > philosophy. I've fixed that. For unbounded lists, the user can have up to 255 cursors (iterators), dynamically allocated, which can be dynamically varied. The limit of 255 is arbitrary, and could be increased if you think it necessary. > Also I think there are too many operations in there. The package spec is huge. > It has (by my count) 79 subprograms. The current strawman has 34, which to some > people it seems is annoyingly small, as we keep seeing suggestions for > additions. Perhaps in between there somewhere the truth lies. Ada.Strings.Unbounded has 62. Ada.Text_IO has 113. I would submit that 79 is not huge, and (like lines or semicolons) is not a very good measure (of complexity?) anyway. The number of really conceptually different operations is around 20-30, and most of the concepts not too difficult. > A large culprit here seems to be the unbounded-array support, which is probably > taken a bit too far. Its OK to convert between them, but anything much more > should probably be accomplished by first converting the array to a list. If we > take Ada.Strings.Unbounded as a model, only the infix operators should have > unbounded array equivalents. The fact that an array version is included for each operation that has a secondary data parameter is not just nice, it is necessary for the sake of efficiency. Consider the extra work done by converting the array to a list, and then applying that list. "Ted Dennison" wrote in message news:pMoS7.61491$xS6.100531@www.newsranger.com... > Excepting the stuff I have raised issues about, is there anything else in there > that you think really needs to be in the Strawman before we proceed? I'm afraid I've got quite a few comments on your straw man as it is currently. Here goes. [1] I would prefer the name 'Element_Type' to 'Element' for the generic parameter, since 'Element_Type' is what Ada.Sequential_IO and Ada.Direct_IO use. [2] I would prefer a name other than 'List' for the list type, since 'List' seems to be such a natural name for parameters and objects of a list type (not necessarily in the list package spec, but elsewhere). If the unbounded list package is going to be named 'x.Lists.Unbounded', it would seem natural to use the name 'Unbounded_List' (by analogy to Ada.Strings.Unbounded.Unbounded_List). I do feel that the need for consistency outweighs any complaint of wordiness. [3] Why is Element_Array declared with a Natural index subtype? Wouldn't Positive be more appropriate? [4] If you consider their usage, the functions 'To' and 'From' are surely confusingly named. What is wrong with 'To_List' and 'To_Array' (or similar)? [5] Analogous to the Ada.Strings.Maps.To_Set function, the function 'Singleton' should be named more like 'To_List' with a parameter named 'Singleton'. [6] I think it would probably (but not necessarily) be better to have the list exceptions gathered into the x.Lists parent package, so that there is only one of each exception (rather than one for each instantiation of x.Lists.[Unb|B]ounded). [7] As mentioned, I actually want to remove directional parameters. Instead, all that is required is a 'smart reverse' operation. This merely switches an 'effective forwardness' flip-flop between actually forward and actually backward. All the operations must be programmed to behave according to the effective forwardness (not difficult). [8] I would much prefer the 'Size' function to be named 'Length'. This would be much more consistent with the use of the term size in the RM95 (and the Size attribute), as well as the use of the term length, the Length attribute of arrays, and the Length functions for Bounded and Unbounded strings. [9] It would also be more consistent with Ada.Strings.* to use the parameter name 'Source' rather than 'Subject'. [10] Similarly 'New_Item' rather than 'New_Element' (or 'New_Items'), and [11] 'Is_Null' for the function 'Is_Empty'. [12] I like the Remove procedure combining retrieval and deletion. This is an omission from my own proposal. [13] Maybe 'Old_Element' should be 'Old_Item'. ([14] Also, I would prefer the name 'Extract' for the subprogram.) Now we come to the vexed issue of iterators. [13] I have a problem with passive iterators. Texts say that they should be provided in addition to active iterators, but I rather feel this is like providing cars with propellors and sails. Passive iterators have various limitations that active iterators do not: an algorithm that has multiple (significantly different) behaviour paths between iterations is much easier to program with an active iterator; an algorithm that works with two or more read-iterators is in general impossible to program with a passive iterator; passive iterators do not permit arbitrary restarting; a passive iterator cannot be a write-iterator. Passive iterators tend to break up the source code associated with a particular algorithm or work chunk. Finally, a passive iterator generic procedure can always be (very easily) constructed from an active iterator. In computer science generally, arguments still rage about this issue, but I'd give it the chop. [14] I feel that the term 'iterator' should be reserved for a construct that is applicable to all container types (and which is therefore monodirectional and not repositionable, since reverse movement or repositioning would not be appropriate to most containers), as this is the general use of the term (for both Ada and other languages). This is why I chose the term 'cursor' (taken from SQL) instead. [15] The reason why I made cursors internal to list objects (rather than providing a separate cursor type) is because an operation on one cursor (active on a certain list object) must be able to interrogate and possibly update any other cursors (also active on the same list object). With separate cursor objects, the only way to do this is for each cursor to contain a pointer to the list it is active on, and for each list to contain pointers (perhaps in a linked list) to all the cursors active on it. This would require the user to declare all list and cursor objects aliased, and to somehow make the connection between cursor object and list object before using a cursor. By having its cursors internal to the list object, all of these inconveniences are removed. [16] By making my cursors point inbetween items in the list, rather than at items, various conceptual complications are clarified regarding deletion and positioning at the end of the list. You do not appear to have adopted this approach. [17] My proposal provides a complete set of cursor operations. These include element and array secondary data parameters. As mentioned, it is necessary to provide all these operations, since they could not in general (depending on the details of the implementation) be efficiently implemented otherwise. [18] I also provide a complete set of absolute operations; I had thought that it was agreed these were justified (if only just) on the grounds of convenience. [19] I don't think it would be desirable for any of these operations to be put into an inner package, because then they wouldn't be inherited on derivatation of the list type (which is admittedly an unlikely requirement, but possible). [18] I have not published it yet, but I am going to add a child package which provides an active iterator for lists. This iterator is of a type derived from a container-wide iterator class, and forms part of an iteration scheme that permits container-independent algorithms. This container-independence is (according to texts on the subject) supposed to be an essential aspect of (the advantage of using) iterators (and I agree). [19] I'm also going to add a child package for sorting. The advantage (not necessaily overwhelming) of using one of the predefined relative comparison operators ("<", "<=", ">", ">=") for the ordering function is that you can declare it "is <>" and save the instantiator having to specify this function every time. [20] What does Splice do? Is it useful? [21] Why do you provide list serialisation (stream read and write) procedures in public, rather than overriding the Read and Write attributes of the list type in private? Your proposal apparently omits the following vital operations: [22] testing lists for equality; [23] exchanging lists; [24] exchanging two slices of a list; [25] exchanging two elements of a list; [26] retrieval of a slice; [27] deletion of a slice; [28] splitting a list into two (especially destructively for a linked-list implementation). [29] Although you have put some documentation into the spec as comments, it is not quite as clear or complete as would be ideal. I think it might be helpful if this documentation were separated out into a text (or HTML) file. I must admit, the documentation file (HTML) that I cooked up for my own proposal needs revision, simplification, and examples. These points doubtless vary in importance, between 'not at all' to (I think) 'very'. Also, it has been demonstrated that I am not infallible :-) on numerous occasions :-o ;-) However, I do feel that we are not quite yet at the stage of going to a sample implementation. I'm not concerned about whose proposal is developed, and I concede that consensus means compromise, but I do feel that there are good reasons behind the design of my proposal. What am I missing? (Apart, that is of course, from charm, wit, courage, physique, generosity, humour, artistic sensitivity, any kind of social grace whatsoever, ... ;-) I really mean it when I say that I feel your input, as well as that of Jeff, Mark, Stephe, and others, has prevented me from making an almighty cock-up of the library I was going to (attempt to) build for AdaOS. For that I owe you immense gratitude anyway. But I'm hoping that we can continue to make progress together, Ted. After lists, I think we have sets, contars (or whatever you want to call them), and probably many other things, to tackle. I'd rather not do this alone. Any more thoughts on a (better) name for the project? (Does 'Tenet' tickle you at all?) -- Best wishes, Nick Roberts