* Re: List container strawman @ 2001-11-02 19:54 Mike Brenner 2001-11-02 21:04 ` Ted Dennison 0 siblings, 1 reply; 116+ messages in thread From: Mike Brenner @ 2001-11-02 19:54 UTC (permalink / raw) To: comp.lang.ada Ted Dennison <dennison@telepath.com> posted a Strawman for a List package asked for comments. Comment 1. Possibly add a new retrieval function. The ability to PEEK, that is, to read the n-th element from either side of the list without popping. To implement this, the ITEM function could possibly be split into PEEK_FRONT and PEEK_BACK. Comment 2. The lists are indexed by type natural. It might be beneficial to generically put in an indexing type to use instead? Comment 3. There is no method of putting in a garbage collector. Comment 4. The ability to delete, insert, move, swap, and copy things around might be useful. These would be fast in a double linked list and slow in a single linked list. Comment 5. I like Marin David Condic's idea of adding a load/store to put the list to streams and 'read and 'write. Adding to that, I prefer all types to have a string representation, for example: function image(list: lists) return string; Comment 6. I agree with Ehud Lamm that there is a significant difference between limited private and private. In differing circumstances, one would want both. The limited private is safer but has syntactic problems (e.g. one has to use functions instead of the assignment operator). Comment 7. I also agree that SORT should be a child package so we can substitute a faster sort for whatever is provided. Also all higher functionality should be substitutable through child packages, generic parameters, or some other method. Comment 8. On copying the list, there is a convention in Python that there is a copy that just copies the top level of pointers and a deep_copy that copies all levels of pointers. Perhaps something like that could be invented here. ^ permalink raw reply [flat|nested] 116+ messages in thread
* Re: List container strawman 2001-11-02 19:54 List container strawman Mike Brenner @ 2001-11-02 21:04 ` Ted Dennison 2001-11-03 8:09 ` Simon Wright 0 siblings, 1 reply; 116+ messages in thread From: Ted Dennison @ 2001-11-02 21:04 UTC (permalink / raw) In article <mailman.1004730907.14961.comp.lang.ada@ada.eu.org>, Mike Brenner says... > >Comment 3. There is no method of putting in a garbage collector. *That's* the other thing I forgot! I was thinking of having a storage pool be an optional parameter (the default being the default storage pool). Any problems with that? >Comment 4. The ability to delete, insert, move, swap, and copy things around might be useful. These would be fast in a double linked list and slow in a single linked list. Delete and insert are now in there. The others aren't but could be accomplished with delete and insert. Does anyone think they need their own routines anyway? > >Comment 5. I like Marin David Condic's idea of adding a load/store to put the >list to streams and 'read and 'write. Adding to that, I prefer all types to Done. >have a string representation, for example: > > function image(list: lists) return string; In my own code, I'd agree. For something meant to fit nicely into the existing Ada library, I'm not so sure. Remember that it wouldn't be too tough to do this yourself using one of the iterators. >Comment 7. I also agree that SORT should be a child package so we can >substitute a faster sort for whatever is provided. Also all higher >functionality should be substitutable through child packages, generic >parameters, or some other method. You can *still* do that (or some important information in the declaration may be deferred to the body, in which case you can't do either). All this does is provide a default algorithm which is easy to use. However, it really doesn't matter much at all syntacticly. This way just saves a "with". >Comment 8. On copying the list, there is a convention in Python that there is a copy that just copies the top level of pointers and a deep_copy that copies all levels of pointers. Perhaps something like that could be invented here. I don't think that would be feasible, since that would require client help for any pointers that are in the Element type (its opaque to the List package). I'm guessing Python doesn't have that issue? --- T.E.D. homepage - http://www.telepath.com/dennison/Ted/TED.html No trees were killed in the sending of this message. However a large number of electrons were terribly inconvenienced. ^ permalink raw reply [flat|nested] 116+ messages in thread
* Re: List container strawman 2001-11-02 21:04 ` Ted Dennison @ 2001-11-03 8:09 ` Simon Wright 2001-11-03 12:46 ` Simon Wright 0 siblings, 1 reply; 116+ messages in thread From: Simon Wright @ 2001-11-03 8:09 UTC (permalink / raw) Ted Dennison<dennison@telepath.com> writes: > In article <mailman.1004730907.14961.comp.lang.ada@ada.eu.org>, Mike Brenner > says... > > > >Comment 3. There is no method of putting in a garbage collector. > > *That's* the other thing I forgot! I was thinking of having a > storage pool be an optional parameter (the default being the default > storage pool). Any problems with that? I couldn't find a way of giving the parameter a default; the problem being that there's no standard way of getting at the standard storage pool. GNAT makes it visible, but warns you about using features that aren't "officially" supported. I guess one could go in for indirections using accesses or functions .. I have generic Storage : in out System.Storage_Pools.Root_Storage_Pool'Class; package BC.Containers.Collections.Unbounded is and you can get at the default pool using with System.Storage_Pools; package BC.Support.Standard_Storage is type T is access Integer; -- arbitrary subtype Pool : System.Storage_Pools.Root_Storage_Pool'Class renames T'Storage_Pool; end BC.Support.Standard_Storage; Aha! this compiles (GNAT 3.14a1), whether it is legal and works on other compilers is a different matter of course .. with System.Storage_Pools; package Default_Pool is type Pool_Access is access all System.Storage_Pools.Root_Storage_Pool'Class; type T is access Integer; Pool : System.Storage_Pools.Root_Storage_Pool'Class renames T'Storage_Pool; generic Storage : Pool_Access := Pool'Access; package G is end G; end Default_Pool; ^ permalink raw reply [flat|nested] 116+ messages in thread
* Re: List container strawman 2001-11-03 8:09 ` Simon Wright @ 2001-11-03 12:46 ` Simon Wright 0 siblings, 0 replies; 116+ messages in thread From: Simon Wright @ 2001-11-03 12:46 UTC (permalink / raw) Simon Wright <simon@pushface.org> writes: > Aha! this compiles (GNAT 3.14a1), whether it is legal and works on > other compilers is a different matter of course .. > > with System.Storage_Pools; > package Default_Pool is > > type Pool_Access > is access all System.Storage_Pools.Root_Storage_Pool'Class; > > type T is access Integer; > Pool : System.Storage_Pools.Root_Storage_Pool'Class > renames T'Storage_Pool; > > generic > Storage : Pool_Access := Pool'Access; > package G is > end G; > > end Default_Pool; Drat, I fear it's not legal; well, ObjectAda thinks not. Pool needs to be aliased so that Pool'Access at line 12 is permitted. Bug report sent to ACT .. ^ permalink raw reply [flat|nested] 116+ messages in thread
* List container strawman @ 2001-11-02 3:56 Ted Dennison 2001-11-02 4:20 ` James Rogers ` (7 more replies) 0 siblings, 8 replies; 116+ messages in thread From: Ted Dennison @ 2001-11-02 3:56 UTC (permalink / raw) Since we do seem to be reaching a small amount of agreement on details, I went ahead a put together a strawman package spec (sans private part) for the unbounded list container, for the purposes of keeping the dicussions rolling in a postitive direction. It is attached here, and available on my website at http://www.telepath.com/dennison/Ted/Containers-Lists-Unbounded.ads.html . If it is close enough to be worth persuing, we may be able to use it as a starting point. (Note: The htmlization there was done by a tool I'm developing as part of the next release of OpenToken. If you have comments on the job it did, I'd like them too, but email would probably be the best venue for it). --- T.E.D. homepage - http://www.telepath.com/dennison/Ted/TED.html No trees were killed in the sending of this message. However a large number of electrons were terribly inconvenienced. ^ permalink raw reply [flat|nested] 116+ messages in thread
* Re: List container strawman 2001-11-02 3:56 Ted Dennison @ 2001-11-02 4:20 ` James Rogers 2001-11-02 14:23 ` Ted Dennison 2001-11-02 4:35 ` Eric Merritt ` (6 subsequent siblings) 7 siblings, 1 reply; 116+ messages in thread From: James Rogers @ 2001-11-02 4:20 UTC (permalink / raw) My attempts to access your website result in the following message: The page that you have requested /dennison/Ted/htmlify.css was not found. Jim Rogers Colorado Springs, Colorado USA Ted Dennison wrote: > > Since we do seem to be reaching a small amount of agreement on details, I went > ahead a put together a strawman package spec (sans private part) for the > unbounded list container, for the purposes of keeping the dicussions rolling in > a postitive direction. It is attached here, and available on my website at > http://www.telepath.com/dennison/Ted/Containers-Lists-Unbounded.ads.html . If it > is close enough to be worth persuing, we may be able to use it as a starting > point. > > (Note: The htmlization there was done by a tool I'm developing as part of the > next release of OpenToken. If you have comments on the job it did, I'd like them > too, but email would probably be the best venue for it). > > --- > T.E.D. homepage - http://www.telepath.com/dennison/Ted/TED.html > > No trees were killed in the sending of this message. > However a large number of electrons were terribly inconvenienced. ^ permalink raw reply [flat|nested] 116+ messages in thread
* Re: List container strawman 2001-11-02 4:20 ` James Rogers @ 2001-11-02 14:23 ` Ted Dennison 2001-11-02 14:38 ` Preben Randhol 2001-11-02 15:15 ` Larry Kilgallen 0 siblings, 2 replies; 116+ messages in thread From: Ted Dennison @ 2001-11-02 14:23 UTC (permalink / raw) In article <3BE21F0E.49967416@worldnet.att.net>, James Rogers says... > >My attempts to access your website result in the following message: > >The page that you have requested /dennison/Ted/htmlify.css was not >found. Out of curiosity, what browser were you using? It works fine for me with IE 5 and Mozilla 0.95. However, I have had someone else report trouble with an older version of Netscape. However, I just ran the page through the CSS validator, and it reports the same error you are reporting. Basicly, I forgot to put up the style sheet that goes with it. Ooops! I'll get that up there when I get back home. --- T.E.D. homepage - http://www.telepath.com/dennison/Ted/TED.html No trees were killed in the sending of this message. However a large number of electrons were terribly inconvenienced. ^ permalink raw reply [flat|nested] 116+ messages in thread
* Re: List container strawman 2001-11-02 14:23 ` Ted Dennison @ 2001-11-02 14:38 ` Preben Randhol 2001-11-02 15:15 ` Larry Kilgallen 1 sibling, 0 replies; 116+ messages in thread From: Preben Randhol @ 2001-11-02 14:38 UTC (permalink / raw) On Fri, 02 Nov 2001 14:23:32 GMT, Ted Dennison wrote: > In article <3BE21F0E.49967416@worldnet.att.net>, James Rogers says... >> >>My attempts to access your website result in the following message: >> >>The page that you have requested /dennison/Ted/htmlify.css was not >>found. > > Out of curiosity, what browser were you using? It works fine for me > with IE 5 and Mozilla 0.95. However, I have had someone else report > trouble with an older version of Netscape. It works with: w3m, links, lynx, opera, dillo, galeon, skipstone, konqueror :-) Preben -- "Violence is the last refuge of the incompetent", Isaac Asimov ^ permalink raw reply [flat|nested] 116+ messages in thread
* Re: List container strawman 2001-11-02 14:23 ` Ted Dennison 2001-11-02 14:38 ` Preben Randhol @ 2001-11-02 15:15 ` Larry Kilgallen 1 sibling, 0 replies; 116+ messages in thread From: Larry Kilgallen @ 2001-11-02 15:15 UTC (permalink / raw) In article <E%xE7.9986$xS6.13571@www.newsranger.com>, Ted Dennison<dennison@telepath.com> writes: > However, I just ran the page through the CSS validator, and it reports the same > error you are reporting. Basicly, I forgot to put up the style sheet that goes > with it. Ooops! I'll get that up there when I get back home. CSS is a relatively new feature for browsers (and _working_ CSS is even newer). Unlike an Ada project where you pick a version (Ada95) and force everyone to use that version, World Wide Web communications must often work to people who have made different tool choices. Dreamweaver 4 has the capability to take a CSS-designed web page and create backward compatible source for actual deployment. ^ permalink raw reply [flat|nested] 116+ messages in thread
* Re: List container strawman 2001-11-02 3:56 Ted Dennison 2001-11-02 4:20 ` James Rogers @ 2001-11-02 4:35 ` Eric Merritt 2001-11-02 15:46 ` Ted Dennison 2001-11-02 7:28 ` Ehud Lamm ` (5 subsequent siblings) 7 siblings, 1 reply; 116+ messages in thread From: Eric Merritt @ 2001-11-02 4:35 UTC (permalink / raw) To: comp.lang.ada Just out of curiosity, for the iteration functions would it be more efficient/readable to provide a Has_Next and Has_Previous routines that return a boolean? I realize that you have already provided mechenisims in teh Size function and the raiseing the No_More exception. __________________________________________________ Do You Yahoo!? Find a job, post your resume. http://careers.yahoo.com ^ permalink raw reply [flat|nested] 116+ messages in thread
* Re: List container strawman 2001-11-02 4:35 ` Eric Merritt @ 2001-11-02 15:46 ` Ted Dennison 0 siblings, 0 replies; 116+ messages in thread From: Ted Dennison @ 2001-11-02 15:46 UTC (permalink / raw) In article <mailman.1004675765.27706.comp.lang.ada@ada.eu.org>, Eric Merritt says... > >Just out of curiosity, for the iteration functions >would it be more efficient/readable to provide a >Has_Next and Has_Previous routines that return a >boolean? I realize that you have already provided >mechenisims in teh Size function and the raiseing the >No_More exception. It certinaly shouldn't be tough to do, so I don't see a good reason for not doing it. However, the iterators as presented have serious problems. I have to redo them anyway, so it may be best to reserve discussion about them (other than how to redo them of course) until that is done. --- T.E.D. homepage - http://www.telepath.com/dennison/Ted/TED.html No trees were killed in the sending of this message. However a large number of electrons were terribly inconvenienced. ^ permalink raw reply [flat|nested] 116+ messages in thread
* Re: List container strawman 2001-11-02 3:56 Ted Dennison 2001-11-02 4:20 ` James Rogers 2001-11-02 4:35 ` Eric Merritt @ 2001-11-02 7:28 ` Ehud Lamm 2001-11-02 14:57 ` Marin David Condic ` (2 more replies) 2001-11-02 14:49 ` Marin David Condic ` (4 subsequent siblings) 7 siblings, 3 replies; 116+ messages in thread From: Ehud Lamm @ 2001-11-02 7:28 UTC (permalink / raw) Thanks fro the effort. Sorry I didn't have time these past week to contribute anything. A few questions/comments. I am not sure about many of these. 1. In my scheme "Element" is a generic parameter of the top package (Containers), and not of the specific implementations. (Remember, my attemp for having interface inheritance) 2. Why is List private? Shouldn't it be limited private, so we avoid possible erros caused by aliasing? We may need a private implementation, but I'd prefer this not to be the default, since it can come and bite you when you don't know what you are doing. The private version is for library builders and more advanced users, best used as part of a layered design that hides the list itself. (If the majority wants private, at least the spec should mention the possbile problems) 3. "Construct" is indeed a long name. We can, as part of the library, decide on some standard name for this like - or + 4. I've seen many implemenations that paremtrize Insert and Remove with a direction parameter, instead of having seperate routines (_Back/_Front). I am not sure I know which approach I prefer... 5. Front() and Back() raise execption on Empty List? 6. I like having a "No_More_Elements()" operation as part of the Iterator interface. It saves time compared to Size (for containers that don't keep count of size), and I don't like programming with exceptions ("exceptions for control flow"). 7. Sort should be in a child unit. Finally, a more general question: Is this a DeQueue or a Doubly-linked list? Should these be two different abstractions? (IMO: Yes, they should). Ehud ^ permalink raw reply [flat|nested] 116+ messages in thread
* Re: List container strawman 2001-11-02 7:28 ` Ehud Lamm @ 2001-11-02 14:57 ` Marin David Condic 2001-11-02 15:57 ` Francisco Javier Loma Daza 2001-11-02 15:06 ` Ted Dennison 2001-11-02 16:26 ` Ted Dennison 2 siblings, 1 reply; 116+ messages in thread From: Marin David Condic @ 2001-11-02 14:57 UTC (permalink / raw) Limited private sounds like a good idea to me - with operations to assign one list to another via duplication. One other thing: Allow me publically to display my ignorance. If Element is private, how does this play with tagged records? I know there is a "tagged private" formal type - but I've never played with it so I don't know what the implications are for that. If the Element type is "private" only and this precludes some things, that's probably O.K. for a first cut - it would let you pile up most of the basic data types and so would be useful. Just wondering how the tagged private thing works. MDC -- Marin David Condic Senior Software Engineer Pace Micro Technology Americas www.pacemicro.com Enabling the digital revolution e-Mail: marin.condic@pacemicro.com Web: http://www.mcondic.com/ "Ehud Lamm" <mslamm@mscc.huji.ac.il> wrote in message news:9rti6v$hcu$1@news.huji.ac.il... > > 2. Why is List private? Shouldn't it be limited private, so we avoid > possible erros caused by aliasing? > We may need a private implementation, but I'd prefer this not to be the > default, since it can come and bite you when you don't know what you are > doing. The private version is for library builders and more advanced users, > best used as part of a layered design that hides the list itself. > (If the majority wants private, at least the spec should mention the > possbile problems) > ^ permalink raw reply [flat|nested] 116+ messages in thread
* Re: List container strawman 2001-11-02 14:57 ` Marin David Condic @ 2001-11-02 15:57 ` Francisco Javier Loma Daza 2001-11-02 16:28 ` Marin David Condic 0 siblings, 1 reply; 116+ messages in thread From: Francisco Javier Loma Daza @ 2001-11-02 15:57 UTC (permalink / raw) To: comp.lang.ada On 2 Nov 2001, Marin David Condic wrote: > Date: 2 Nov 2001 14:57:16 GMT > To: comp.lang.ada@ada.eu.org > From: "Marin David Condic" <dont.bother.mcondic.auntie.spam@[acm.org>] > Reply-To: comp.lang.ada@ada.eu.org > Sender: comp.lang.ada-admin@ada.eu.org > Subject: Re: List container strawman > > Limited private sounds like a good idea to me - with operations to assign > one list to another via duplication. > > One other thing: Allow me publically to display my ignorance. If Element > is > private, how does this play with tagged records? I know there is a > "tagged > private" formal type - but I've never played with it so I don't know what > the implications are for that. If the formal is tagged private then you can derive a tagged type from it. generic type T is tagged private; package DD type Object is new T with null record; end DD; ^ permalink raw reply [flat|nested] 116+ messages in thread
* Re: List container strawman 2001-11-02 15:57 ` Francisco Javier Loma Daza @ 2001-11-02 16:28 ` Marin David Condic 2001-11-02 17:08 ` Ted Dennison 0 siblings, 1 reply; 116+ messages in thread From: Marin David Condic @ 2001-11-02 16:28 UTC (permalink / raw) O.K. Thanks. Now I get it. My guess is that you could still instantiate with a tagged type, so piling up tagged records should not be a problem, right? Could you instantiate with a 'Class wide type so anything of a class could be put on the list? Of course you could not do an abstract type (to a plain old private formal) since they don't exist yet, but I don't see that as a drawback. MDC -- Marin David Condic Senior Software Engineer Pace Micro Technology Americas www.pacemicro.com Enabling the digital revolution e-Mail: marin.condic@pacemicro.com Web: http://www.mcondic.com/ "Francisco Javier Loma Daza" <Francisco.Loma@isotrol.com> wrote in message news:mailman.1004716745.9697.comp.lang.ada@ada.eu.org... > > If the formal is tagged private then you can derive a tagged type from > it. > > generic > type T is tagged private; > package DD > > type Object is new T with null record; > > end DD; > > ^ permalink raw reply [flat|nested] 116+ messages in thread
* Re: List container strawman 2001-11-02 16:28 ` Marin David Condic @ 2001-11-02 17:08 ` Ted Dennison 0 siblings, 0 replies; 116+ messages in thread From: Ted Dennison @ 2001-11-02 17:08 UTC (permalink / raw) In article <9ruhig$kef$1@nh.pace.co.uk>, Marin David Condic says... >up tagged records should not be a problem, right? Could you instantiate with >a 'Class wide type so anything of a class could be put on the list? I don't believe so. However, you can't do that with an array either. In both cases you'd have to use a pointer to your tagged type. That would mean you'd have to avoid the funtional stuff ("&" routines), or at least be careful using it. --- T.E.D. homepage - http://www.telepath.com/dennison/Ted/TED.html No trees were killed in the sending of this message. However a large number of electrons were terribly inconvenienced. ^ permalink raw reply [flat|nested] 116+ messages in thread
* Re: List container strawman 2001-11-02 7:28 ` Ehud Lamm 2001-11-02 14:57 ` Marin David Condic @ 2001-11-02 15:06 ` Ted Dennison 2001-11-02 15:32 ` Marin David Condic 2001-11-02 16:26 ` Ted Dennison 2 siblings, 1 reply; 116+ messages in thread From: Ted Dennison @ 2001-11-02 15:06 UTC (permalink / raw) In article <9rti6v$hcu$1@news.huji.ac.il>, Ehud Lamm says... >1. In my scheme "Element" is a generic parameter of the top package >(Containers), and not of the specific implementations. >(Remember, my attemp for having interface inheritance) I didn't do that because that is precisely what Booch does that makes it so complicated to use. If one does that, then proper use of the package would require 3 cascading generic package instantiations. If that is OK, then in my opinion we should just bag this whole thing and use Booch. >2. Why is List private? Shouldn't it be limited private, so we avoid >possible erros caused by aliasing? First off, I'd like to note for anyone who may have missed it, that any Element passed in to be put on a list or taken off of one will be *copied*. Pointers to elements will not be used. If List were limited private, then we'd have to get rid of all those "&" routines. My thinking was that Lisp-like functional list processing would be desirable. You could indeed have aliasing problems, but only if your Element type uses pointers. Having "&" avaliable also makes list operations somewhat consistent with arrays, which also have "&". However, any use of those "&" routines will involve creating a copy of every element (much like using "&" with arrays does). That would probably be too expensive in most cases, so perhaps it really isn't all that valuable. I'm curious how others feel about this. >(If the majority wants private, at least the spec should mention the >possbile problems) I can agree with this. At the least there should be some sort of warning in there about using pointers in Element with those routines. >3. "Construct" is indeed a long name. We can, as part of the library, decide >on some standard name for this like - or + As the comment said, I seriously considered that. However, it is not (yet) a common idiom to use those for constructors. So I'm not sure if it would help or hurt readability. Again, I'm curious what people think about this. >4. I've seen many implemenations that paremtrize Insert and Remove with a >direction parameter, instead of having seperate routines (_Back/_Front). I >am not sure I know which approach I prefer... >5. Front() and Back() raise execption on Empty List? Assuming you are talking about the iterator routines "First" and "Last", that's a good point. I seem to have totally neglected that case, and thus left serious problems in there. For instance, the comment that says "For an empty list, First = Last." is clearly wrong. That would indicate a list with one element, not an empty one. I'll have to redo the iterators somehow... >6. I like having a "No_More_Elements()" operation as part of the Iterator >interface. It saves time compared to Size (for containers that don't keep >count of size), and I don't like programming with exceptions ("exceptions >for control flow"). That seems sensible. And I agree about using exceptions, which is why it is only one example of 3. That stuff is all wrong anyway though... >7. Sort should be in a child unit. Why do you feel that way? What does putting it off in a separate unit gain you? > >Finally, a more general question: >Is this a DeQueue or a Doubly-linked list? Should these be two different >abstractions? (IMO: Yes, they should). What specificly would the difference be? Clearly it would have to be doubly-linked to support all those push and pop operations, and both Next and Previous as iterators. You could implement those on a singly-linked list, but it wouldn't be very efficient. --- T.E.D. homepage - http://www.telepath.com/dennison/Ted/TED.html No trees were killed in the sending of this message. However a large number of electrons were terribly inconvenienced. ^ permalink raw reply [flat|nested] 116+ messages in thread
* Re: List container strawman 2001-11-02 15:06 ` Ted Dennison @ 2001-11-02 15:32 ` Marin David Condic 2001-11-02 16:33 ` Ted Dennison 0 siblings, 1 reply; 116+ messages in thread From: Marin David Condic @ 2001-11-02 15:32 UTC (permalink / raw) O.K. I hereby revoke my agreement with Limited Private. If the List type works kind of like the Ada.Strings.Unbounded.Unbounded_String type, then I guess we're O.K. (Lists do look an awful lot like Ada.Strings.Unbounded, don't they? You could view an unbounded string kind of as a list of characters, eh? Maybe look at A.S.U for ideas about how it should look and what sort of operations it should have?) How is assignment handled here? If you don't inherit from Ada.Finalization how do you make sure you copy the list rather than duplicate pointers to the list? (Assuming the underlying implementation relies on pointers to list elements.) MDC -- Marin David Condic Senior Software Engineer Pace Micro Technology Americas www.pacemicro.com Enabling the digital revolution e-Mail: marin.condic@pacemicro.com Web: http://www.mcondic.com/ "Ted Dennison" <dennison@telepath.com> wrote in message news:1EyE7.10050$xS6.13527@www.newsranger.com... > > First off, I'd like to note for anyone who may have missed it, that any Element > passed in to be put on a list or taken off of one will be *copied*. Pointers to > elements will not be used. > > If List were limited private, then we'd have to get rid of all those "&" > routines. My thinking was that Lisp-like functional list processing would be > desirable. You could indeed have aliasing problems, but only if your Element > type uses pointers. Having "&" avaliable also makes list operations somewhat > consistent with arrays, which also have "&". > > However, any use of those "&" routines will involve creating a copy of every > element (much like using "&" with arrays does). That would probably be too > expensive in most cases, so perhaps it really isn't all that valuable. I'm > curious how others feel about this. > ^ permalink raw reply [flat|nested] 116+ messages in thread
* Re: List container strawman 2001-11-02 15:32 ` Marin David Condic @ 2001-11-02 16:33 ` Ted Dennison 2001-11-02 16:43 ` Marin David Condic ` (2 more replies) 0 siblings, 3 replies; 116+ messages in thread From: Ted Dennison @ 2001-11-02 16:33 UTC (permalink / raw) In article <9rue9f$j4t$1@nh.pace.co.uk>, Marin David Condic says... >How is assignment handled here? If you don't inherit from Ada.Finalization >how do you make sure you copy the list rather than duplicate pointers to the >list? (Assuming the underlying implementation relies on pointers to list >elements.) Well, the honest answer is that I hadn't thought of that. :-( I guess if the funcional stuff is going to remain in there, then it will have to be a controlled type. That means that users won't be able to instantiate it from within a subprogram (yuk!). If we *do* make it limited, then another issue I just thought of is that we wouldn't be able to make lists of lists (we had already decided that we won't allow limited list components). However, I can't think of a good common use for lists of lists of the top of my head. --- T.E.D. homepage - http://www.telepath.com/dennison/Ted/TED.html No trees were killed in the sending of this message. However a large number of electrons were terribly inconvenienced. ^ permalink raw reply [flat|nested] 116+ messages in thread
* Re: List container strawman 2001-11-02 16:33 ` Ted Dennison @ 2001-11-02 16:43 ` Marin David Condic 2001-11-02 22:51 ` Jeffrey Carter 2001-11-02 18:11 ` Mark Johnson 2001-11-03 22:30 ` Nick Roberts 2 siblings, 1 reply; 116+ messages in thread From: Marin David Condic @ 2001-11-02 16:43 UTC (permalink / raw) If the List type is simply private, can it contain an element that is Controlled? In other words, is this a problem that can be covered up with just one more layer of indirection? I'm guessing that Ada.Strings.Unbounded has to do *something* fairly dynamic in its underlying implementation and it has to solve the problem of assignment along the way. That either means a) the problem can be solved from within the language or b) its done with smoke and mirrors behind the scenes. I'm guessing that A is likely to be the case, so perhaps a solution does exist? MDC -- Marin David Condic Senior Software Engineer Pace Micro Technology Americas www.pacemicro.com Enabling the digital revolution e-Mail: marin.condic@pacemicro.com Web: http://www.mcondic.com/ "Ted Dennison" <dennison@telepath.com> wrote in message news:wVzE7.10194$xS6.14029@www.newsranger.com... > > I guess if the funcional stuff is going to remain in there, then it will have to > be a controlled type. That means that users won't be able to instantiate it from > within a subprogram (yuk!). If we *do* make it limited, then another issue I > just thought of is that we wouldn't be able to make lists of lists (we had > already decided that we won't allow limited list components). However, I can't > think of a good common use for lists of lists of the top of my head. > ^ permalink raw reply [flat|nested] 116+ messages in thread
* Re: List container strawman 2001-11-02 16:43 ` Marin David Condic @ 2001-11-02 22:51 ` Jeffrey Carter 2001-11-03 0:24 ` Matthew Heaney 2001-11-05 15:10 ` Marin David Condic 0 siblings, 2 replies; 116+ messages in thread From: Jeffrey Carter @ 2001-11-02 22:51 UTC (permalink / raw) Marin David Condic wrote: > > If the List type is simply private, can it contain an element that is > Controlled? In other words, is this a problem that can be covered up with > just one more layer of indirection? There's no problem with the actual type being Controlled if the formal type is [limited] private. If there's anything about the actual type that requires finalization we would hope the client would implement it as a controlled type, since objects of this type are going to come and go as items are added and removed from the structure. > > I'm guessing that Ada.Strings.Unbounded has to do *something* fairly dynamic > in its underlying implementation and it has to solve the problem of > assignment along the way. That either means a) the problem can be solved > from within the language or b) its done with smoke and mirrors behind the > scenes. I'm guessing that A is likely to be the case, so perhaps a solution > does exist? Unbounded_String may be implemented as a controlled type. It's implementation is not defined, so compiler writers may use any tricks they think necessary, but you could write the implementation in plain Ada. Another place where some compiler writers use tricks is the interaction between a random number Generator value and the Random function. The generator holds the state data for the algorithm, which are supposed to be updated when a number is generated. You can implement Generator as a controlled type with a pointer to the state data, but again other tricks are possible from within the compiler. -- Jeffrey Carter ^ permalink raw reply [flat|nested] 116+ messages in thread
* Re: List container strawman 2001-11-02 22:51 ` Jeffrey Carter @ 2001-11-03 0:24 ` Matthew Heaney 2001-11-03 2:21 ` Jeffrey Carter 2001-11-05 15:10 ` Marin David Condic 1 sibling, 1 reply; 116+ messages in thread From: Matthew Heaney @ 2001-11-03 0:24 UTC (permalink / raw) "Jeffrey Carter" <jeffrey.carter@boeing.com> wrote in message news:3BE3235D.E292B890@boeing.com... > Another place where some compiler writers use tricks is the interaction > between a random number Generator value and the Random function. The > generator holds the state data for the algorithm, which are supposed to > be updated when a number is generated. You can implement Generator as a > controlled type with a pointer to the state data, but again other tricks > are possible from within the compiler. Why would you need to implement type Generator as a Controlled type? Generator state is allocated on the stack, so Finalization is not required. Allocating state on the heap and using Controlled Finalization would be a horribly inefficient way to implement that type. No heap allocation or compiler magic is needed to implement Generator; just use the Rosen Trick: package P is type Generator is limited private; function Random (G : Generator) return Integer; private type Handle_Type (G : access Generator) is null record; type Generator is limited record Handle : Handle_Type (G'Access); State : State_Type; --whatever end record; end P; package body P is function Random (G : Generator) return Integer is State : State_Type renames G.Handle.G.all; begin -- modify State as necessary return X; end; end P; This is all perfectly legal. ^ permalink raw reply [flat|nested] 116+ messages in thread
* Re: List container strawman 2001-11-03 0:24 ` Matthew Heaney @ 2001-11-03 2:21 ` Jeffrey Carter 2001-11-16 0:31 ` Vincent Marciante 0 siblings, 1 reply; 116+ messages in thread From: Jeffrey Carter @ 2001-11-03 2:21 UTC (permalink / raw) Matthew Heaney wrote: > > "Jeffrey Carter" <jeffrey.carter@boeing.com> wrote in message > news:3BE3235D.E292B890@boeing.com... > > Another place where some compiler writers use tricks is the interaction > > between a random number Generator value and the Random function. The > > generator holds the state data for the algorithm, which are supposed to > > be updated when a number is generated. You can implement Generator as a > > controlled type with a pointer to the state data, but again other tricks > > are possible from within the compiler. > > Why would you need to implement type Generator as a Controlled type? > Generator state is allocated on the stack, so Finalization is not required. > Allocating state on the heap and using Controlled Finalization would be a > horribly inefficient way to implement that type. The obvious way to modify an in parameter is to have it be an access value and change what it points to. You would want this to be Controlled so you could deallocate the storage when an object of the type goes out of scope. The GNAT implementation says -- The design of this spec is very awkward, as a result of Ada 95 not -- permitting in-out parameters for function formals (most naturally -- Generator values would be passed this way). In pure Ada 95, the only -- solution is to use the heap and pointers, and, to avoid memory leaks, -- controlled types. > > No heap allocation or compiler magic is needed to implement Generator; just > use the Rosen Trick: Yes, that is a trick that can be used (although your example has a couple of errors). Was it known before standardization? I somehow suspect it would have been outlawed if it were. GNAT uses type State is ... type Generator is limited record Gen_State : State; end record; Following the above quote, they add -- This is awfully heavy, so what we do is to use Unrestricted_Access to -- get a pointer to the state in the passed Generator. This works because -- Generator is a limited type and will thus always be passed by reference. type Pointer is access all State; function Random (Gen : Generator) return Uniformly_Distributed is Genp : constant Pointer := Gen.Gen_State'Unrestricted_Access; and then modify Genp.all. Since 'Unrestricted_Access is an implementation-dependent attribute, I think this qualifies as a trick, too. I wonder if there is some advantage to this trick over the Rosen trick. -- Jeff Carter "Now go away or I shall taunt you a second time." Monty Python & the Holy Grail ^ permalink raw reply [flat|nested] 116+ messages in thread
* Re: List container strawman 2001-11-03 2:21 ` Jeffrey Carter @ 2001-11-16 0:31 ` Vincent Marciante 0 siblings, 0 replies; 116+ messages in thread From: Vincent Marciante @ 2001-11-16 0:31 UTC (permalink / raw) Jeffrey Carter wrote: > > Matthew Heaney wrote: > > > > "Jeffrey Carter" <jeffrey.carter@boeing.com> wrote in message > > news:3BE3235D.E292B890@boeing.com... > > > Another place where some compiler writers use tricks is the interaction > > > between a random number Generator value and the Random function. <snip> > > No heap allocation or compiler magic is needed to implement Generator; just > > use the Rosen Trick: > > Yes, that is a trick that can be used (although your example has a > couple of errors). Was it known before standardization? I somehow > suspect it would have been outlawed if it were. > > GNAT uses <snip> > I wonder if there is some advantage to this trick over the Rosen > trick. IIRC The GNAT code was written before the Rosen Trick was first described. The GNAT code worked and there was no important reason to change it. If the Rosen Trick was known at the time, it would have been used. Vincent Marciante ^ permalink raw reply [flat|nested] 116+ messages in thread
* Re: List container strawman 2001-11-02 22:51 ` Jeffrey Carter 2001-11-03 0:24 ` Matthew Heaney @ 2001-11-05 15:10 ` Marin David Condic 2001-11-05 18:31 ` Ted Dennison 1 sibling, 1 reply; 116+ messages in thread From: Marin David Condic @ 2001-11-05 15:10 UTC (permalink / raw) "Jeffrey Carter" <jeffrey.carter@boeing.com> wrote in message news:3BE3235D.E292B890@boeing.com... > > There's no problem with the actual type being Controlled if the formal > type is [limited] private. If there's anything about the actual type > that requires finalization we would hope the client would implement it > as a controlled type, since objects of this type are going to come and > go as items are added and removed from the structure. > I think you missed it. Its the other way around. I was asking if the list type you might be exporting from the generic package can be private and contain something that is controlled. generic type Something is private ; package A_Package is type Something_Else is private ; private type Something_Else is record X : Some_Type_Derived_From_Controlled_Along_Some_With_Chain ; end record ; end A_Package ; Without having passed anything like this past a compiler, I just don't know if it is legal and gets Ted the ability to instantiate the generic from within a non-library-level scope. > > Unbounded_String may be implemented as a controlled type. It's > implementation is not defined, so compiler writers may use any tricks > they think necessary, but you could write the implementation in plain > Ada. > The spec in the appendix does not indicate a "with Ada.Finalization;" anywhere I can see, so it isn't clear how they intended for it to be done. That's why I was wondering how they dealt with assignment if, for example, one were to want Unbounded_String to be implemented with some version of dynamic allocation. MDC -- Marin David Condic Senior Software Engineer Pace Micro Technology Americas www.pacemicro.com Enabling the digital revolution e-Mail: marin.condic@pacemicro.com Web: http://www.mcondic.com/ ^ permalink raw reply [flat|nested] 116+ messages in thread
* Re: List container strawman 2001-11-05 15:10 ` Marin David Condic @ 2001-11-05 18:31 ` Ted Dennison 2001-11-05 19:09 ` Marin David Condic 0 siblings, 1 reply; 116+ messages in thread From: Ted Dennison @ 2001-11-05 18:31 UTC (permalink / raw) In article <9s6a60$a49$1@nh.pace.co.uk>, Marin David Condic says... >generic > type Something is private ; >package A_Package is > type Something_Else is private ; >private > type Something_Else is record > X : Some_Type_Derived_From_Controlled_Along_Some_With_Chain ; > end record ; >end A_Package ; > >Without having passed anything like this past a compiler, I just don't know >if it is legal and gets Ted the ability to instantiate the generic from >within a non-library-level scope. The problem with this approach is that the X field in Something_Else can have no knowledge of any of other the fields in Something_Else, and thus is unable to control it. It can control itself, but not its parent Something_Else. I think you can sometimes use tricks like this if the thing being controlled has nothing to do with any of the generic parameters (or anything dependant upon them). But in all other cases you are hosed, as near as I can tell. --- T.E.D. homepage - http://www.telepath.com/dennison/Ted/TED.html No trees were killed in the sending of this message. However a large number of electrons were terribly inconvenienced. ^ permalink raw reply [flat|nested] 116+ messages in thread
* Re: List container strawman 2001-11-05 18:31 ` Ted Dennison @ 2001-11-05 19:09 ` Marin David Condic 2001-11-05 21:23 ` Ted Dennison 2001-11-07 19:27 ` Stephen Leake 0 siblings, 2 replies; 116+ messages in thread From: Marin David Condic @ 2001-11-05 19:09 UTC (permalink / raw) Hmmmmmmm.......... So basically, you're saying that a library level generic that contained as part of it a Controlled element, you'd be able to instantiate it in a procedure (non-library level)? But if a data item in it is itself derived from Controlled, you can't? (Seems kind of strange, but I'm sure there's going to be some corner-case of the rules to explain it.) The Controlled thing clearly can't have anything to do with the generic parameters since it needs to be itself declared in some other package. You could pass the generic parameter making an instance of the Controlled thing, but this is just pushing the problem off by one package - not really a solution. So it would probably have to use something either convoluted enough to fool the compiler into doing what you want, or it would need to do something kind of "dirty" like using System.Address in the Controlled part and doing some kind of access type to the generic parameter with a conversion to address. (Kinky, but since it all remains hidden down in the bowels of the implementation, probably not a hopelessly bad idea.) MDC -- Marin David Condic Senior Software Engineer Pace Micro Technology Americas www.pacemicro.com Enabling the digital revolution e-Mail: marin.condic@pacemicro.com Web: http://www.mcondic.com/ "Ted Dennison" <dennison@telepath.com> wrote in message news:yWAF7.13454$xS6.17694@www.newsranger.com... > > The problem with this approach is that the X field in Something_Else can have no > knowledge of any of other the fields in Something_Else, and thus is unable to > control it. It can control itself, but not its parent Something_Else. > > I think you can sometimes use tricks like this if the thing being controlled has > nothing to do with any of the generic parameters (or anything dependant upon > them). But in all other cases you are hosed, as near as I can tell. > ^ permalink raw reply [flat|nested] 116+ messages in thread
* Re: List container strawman 2001-11-05 19:09 ` Marin David Condic @ 2001-11-05 21:23 ` Ted Dennison 2001-11-07 19:27 ` Stephen Leake 1 sibling, 0 replies; 116+ messages in thread From: Ted Dennison @ 2001-11-05 21:23 UTC (permalink / raw) In article <9s6o5m$fsi$1@nh.pace.co.uk>, Marin David Condic says... >So basically, you're saying that a library level generic that contained as >part of it a Controlled element, you'd be able to instantiate it in a >procedure (non-library level)? But if a data item in it is itself derived >from Controlled, you can't? (Seems kind of strange, but I'm sure there's >going to be some corner-case of the rules to explain it.) Yes. It isn't controlled per se. Its just that you can't declare a derived tagged type at a lower level than its parent, and Controlled is a tagged type. The rule goes for all tagged types. Its just that controlled was unfortunately implemented as a tagged type declared at the library level. >solution. So it would probably have to use something either convoluted >enough to fool the compiler into doing what you want, or it would need to do >something kind of "dirty" like using System.Address in the Controlled part >and doing some kind of access type to the generic parameter with a >conversion to address. (Kinky, but since it all remains hidden down in the >bowels of the implementation, probably not a hopelessly bad idea.) Any solution would have to have the library-level controlled type somehow know how to control the non-library-level type. If the controlled stuff isn't a generic parameter or dependent on one, there are (nasty) ways to do that. If it is, then you are just plain hosed (unless someone knows a neat trick I don't). --- T.E.D. homepage - http://www.telepath.com/dennison/Ted/TED.html No trees were killed in the sending of this message. However a large number of electrons were terribly inconvenienced. ^ permalink raw reply [flat|nested] 116+ messages in thread
* Re: List container strawman 2001-11-05 19:09 ` Marin David Condic 2001-11-05 21:23 ` Ted Dennison @ 2001-11-07 19:27 ` Stephen Leake 1 sibling, 0 replies; 116+ messages in thread From: Stephen Leake @ 2001-11-07 19:27 UTC (permalink / raw) "Marin David Condic" <dont.bother.mcondic.auntie.spam@[acm.org> writes: > Hmmmmmmm.......... > > > So basically, you're saying that a library level generic that contained as > part of it a Controlled element, you'd be able to instantiate it in a > procedure (non-library level)? But if a data item in it is itself derived > from Controlled, you can't? (Seems kind of strange, but I'm sure there's > going to be some corner-case of the rules to explain it.) The issue is where the Controlled _type_ is declared, not where the _object_ of that type is declared. The _type_ must be declared at library level, so pointers to it's base class are at the same level as Controlled itself. In this case, the Controlled type is still declared at library level; the generic instantiation declares another type, which happens to contain a component object of the Controlled type. > The Controlled thing clearly can't have anything to do with the You need to distinguish between declaring the type and declaring the object. "Thing" is not specific enough. -- -- Stephe ^ permalink raw reply [flat|nested] 116+ messages in thread
* Re: List container strawman 2001-11-02 16:33 ` Ted Dennison 2001-11-02 16:43 ` Marin David Condic @ 2001-11-02 18:11 ` Mark Johnson 2001-11-02 18:46 ` Marin David Condic 2001-11-02 19:21 ` Larry Kilgallen 2001-11-03 22:30 ` Nick Roberts 2 siblings, 2 replies; 116+ messages in thread From: Mark Johnson @ 2001-11-02 18:11 UTC (permalink / raw) Ted Dennison wrote: > [snip] If we *do* make it limited, then another issue I > just thought of is that we wouldn't be able to make lists of lists (we had > already decided that we won't allow limited list components). However, I can't > think of a good common use for lists of lists of the top of my head. Examples of a list (or nested) of lists... - represent the nested scope of names (e.g., A.X.3) or other items - a sparse array implementation (2d or 3d...) - associative lookups of data are a few that come off the top of my head. I kept thinking of LISP when I thought of other applications as well. Not to say there are not better algorithms to implement such capabilities, but you will likely be surprised at what people come up with. --Mark ^ permalink raw reply [flat|nested] 116+ messages in thread
* Re: List container strawman 2001-11-02 18:11 ` Mark Johnson @ 2001-11-02 18:46 ` Marin David Condic 2001-11-02 19:21 ` Larry Kilgallen 1 sibling, 0 replies; 116+ messages in thread From: Marin David Condic @ 2001-11-02 18:46 UTC (permalink / raw) Or a Unix/WinNT directory - that could be modeled as a list of lists of lists of... (Sounds like recursion to me...) Its something that would be nice to be able to do, but its not necessarily something that won't have its own drawbacks. We can't expect everything out of one little list package, so maybe we take a cut at what is possible and think about alternate designs as possible additions. Maybe thats an indication of a need for alternate list packages - or possibly other data structures like trees? MDC -- Marin David Condic Senior Software Engineer Pace Micro Technology Americas www.pacemicro.com Enabling the digital revolution e-Mail: marin.condic@pacemicro.com Web: http://www.mcondic.com/ "Mark Johnson" <Mark_H_Johnson@Raytheon.com> wrote in message news:3BE2E1DD.EE0078C7@Raytheon.com... > > Examples of a list (or nested) of lists... > - represent the nested scope of names (e.g., A.X.3) or other items > - a sparse array implementation (2d or 3d...) > - associative lookups of data > are a few that come off the top of my head. I kept thinking of LISP when I thought > of other applications as well. Not to say there are not better algorithms to > implement such capabilities, but you will likely be surprised at what people come up > with. ^ permalink raw reply [flat|nested] 116+ messages in thread
* Re: List container strawman 2001-11-02 18:11 ` Mark Johnson 2001-11-02 18:46 ` Marin David Condic @ 2001-11-02 19:21 ` Larry Kilgallen 1 sibling, 0 replies; 116+ messages in thread From: Larry Kilgallen @ 2001-11-02 19:21 UTC (permalink / raw) In article <3BE2E1DD.EE0078C7@Raytheon.com>, Mark Johnson <Mark_H_Johnson@Raytheon.com> writes: > Examples of a list (or nested) of lists... > - represent the nested scope of names (e.g., A.X.3) or other items It seems to me that would be a list inside a record, since if the list contained elements for X, Y and Z, something associated with the list would have to indicate A. ^ permalink raw reply [flat|nested] 116+ messages in thread
* Re: List container strawman 2001-11-02 16:33 ` Ted Dennison 2001-11-02 16:43 ` Marin David Condic 2001-11-02 18:11 ` Mark Johnson @ 2001-11-03 22:30 ` Nick Roberts 2 siblings, 0 replies; 116+ messages in thread From: Nick Roberts @ 2001-11-03 22:30 UTC (permalink / raw) "Ted Dennison" <dennison@telepath.com> wrote in message news:wVzE7.10194$xS6.14029@www.newsranger.com... > I guess if the funcional stuff is going to remain in there, then it will have to > be a controlled type. That means that users won't be able to instantiate it from > within a subprogram (yuk!). If we *do* make it limited, then another issue I > just thought of is that we wouldn't be able to make lists of lists (we had > already decided that we won't allow limited list components). However, I can't > think of a good common use for lists of lists of the top of my head. Lists of lists are frequently useful, but the problem you suggest is easily (and efficiently) solved by having lists of access values to lists. E.g.: package Item_Collections is new Collections(Game_Item); subtype Item_List is Item_Collections.Utility.Linked_List; type Game_Room is limited record ... Contents: Item_List; end record; type Room_Reference is access all Game_Room; package Room_Collections is new Collections(Room_Reference); and so on. -- Nick Roberts ^ permalink raw reply [flat|nested] 116+ messages in thread
* Re: List container strawman 2001-11-02 7:28 ` Ehud Lamm 2001-11-02 14:57 ` Marin David Condic 2001-11-02 15:06 ` Ted Dennison @ 2001-11-02 16:26 ` Ted Dennison 2001-11-02 16:36 ` Marin David Condic ` (2 more replies) 2 siblings, 3 replies; 116+ messages in thread From: Ted Dennison @ 2001-11-02 16:26 UTC (permalink / raw) In article <9rti6v$hcu$1@news.huji.ac.il>, Ehud Lamm says... >2. Why is List private? Shouldn't it be limited private, so we avoid >possible erros caused by aliasing? Ahh. It finally dawned on me what your objection to private was. (I'm a little slow today again.) We are talking about what happens when you do a "List1 := List2;", aren't we? Yeah, it is either going to have to be limited, or be derived from Ada.Finalization.Controlled. Limited gets rid of the ability to perform funtional operations on it; Controlled get rid of the ability to instantiate it from within a subprogram. Have I mentioned lately how much I dislike the implementation of controlled types? :-{ --- T.E.D. homepage - http://www.telepath.com/dennison/Ted/TED.html No trees were killed in the sending of this message. However a large number of electrons were terribly inconvenienced. ^ permalink raw reply [flat|nested] 116+ messages in thread
* Re: List container strawman 2001-11-02 16:26 ` Ted Dennison @ 2001-11-02 16:36 ` Marin David Condic 2001-11-02 19:31 ` Ted Dennison 2001-11-02 17:49 ` Jeffrey Carter 2001-11-08 10:34 ` Ehud Lamm 2 siblings, 1 reply; 116+ messages in thread From: Marin David Condic @ 2001-11-02 16:36 UTC (permalink / raw) I'd think that in *most* instances you aren't going to need to instantiate from within a subprogram. Hence, Controlled is probably not that much of a burden. (We don't live in a perfect world do we?) How does Ada.Strings.Unbounded handle not being limited? I didn't see an indication of it being derived from Controlled and it is doing something fairly similar to lists. Or does it rely on behind-the-scenes magic to cope with their dynamic nature? MDC -- Marin David Condic Senior Software Engineer Pace Micro Technology Americas www.pacemicro.com Enabling the digital revolution e-Mail: marin.condic@pacemicro.com Web: http://www.mcondic.com/ "Ted Dennison" <dennison@telepath.com> wrote in message news:WOzE7.10186$xS6.14012@www.newsranger.com... > > Ahh. It finally dawned on me what your objection to private was. (I'm a little > slow today again.) We are talking about what happens when you do a > "List1 := List2;", aren't we? > > Yeah, it is either going to have to be limited, or be derived from > Ada.Finalization.Controlled. Limited gets rid of the ability to perform > funtional operations on it; Controlled get rid of the ability to instantiate it > from within a subprogram. > > Have I mentioned lately how much I dislike the implementation of controlled > types? :-{ > ^ permalink raw reply [flat|nested] 116+ messages in thread
* Re: List container strawman 2001-11-02 16:36 ` Marin David Condic @ 2001-11-02 19:31 ` Ted Dennison 0 siblings, 0 replies; 116+ messages in thread From: Ted Dennison @ 2001-11-02 19:31 UTC (permalink / raw) In article <9rui2b$kku$1@nh.pace.co.uk>, Marin David Condic says... >How does Ada.Strings.Unbounded handle not being limited? I didn't see an >indication of it being derived from Controlled and it is doing something >fairly similar to lists. Or does it rely on behind-the-scenes magic to cope >with their dynamic nature? The one implementation I know about (and I haven't looked at Gnat's so I could easily make it two) does indeed use a controlled type. Since it isn't a generic, and is indeed declared at the library level, this is no problem. We have the problem here because its a generic. Remember, declaring objects of type List isn't the issue. The issue is declaring the list type itself. --- T.E.D. homepage - http://www.telepath.com/dennison/Ted/TED.html No trees were killed in the sending of this message. However a large number of electrons were terribly inconvenienced. ^ permalink raw reply [flat|nested] 116+ messages in thread
* Re: List container strawman 2001-11-02 16:26 ` Ted Dennison 2001-11-02 16:36 ` Marin David Condic @ 2001-11-02 17:49 ` Jeffrey Carter 2001-11-08 10:34 ` Ehud Lamm 2 siblings, 0 replies; 116+ messages in thread From: Jeffrey Carter @ 2001-11-02 17:49 UTC (permalink / raw) Ted Dennison wrote: > > Yeah, it is either going to have to be limited, or be derived from > Ada.Finalization.Controlled. Limited gets rid of the ability to perform > funtional operations on it; Controlled get rid of the ability to instantiate it > from within a subprogram. Functions may return limited values; the function call may be used as the actual for a parameter or renamed as a (constant) object of the type. Controlled requires instantiating at the library level, which is a pain, but I think it's required anyway for an unbounded structure, since otherwise you will have memory leaks when objects of the type go out of scope. -- Jeffrey Carter ^ permalink raw reply [flat|nested] 116+ messages in thread
* Re: List container strawman 2001-11-02 16:26 ` Ted Dennison 2001-11-02 16:36 ` Marin David Condic 2001-11-02 17:49 ` Jeffrey Carter @ 2001-11-08 10:34 ` Ehud Lamm 2001-11-09 14:49 ` Ted Dennison 2 siblings, 1 reply; 116+ messages in thread From: Ehud Lamm @ 2001-11-08 10:34 UTC (permalink / raw) Ted Dennison <dennison@telepath.com> wrote in message news:WOzE7.10186$xS6.14012@www.newsranger.com... > In article <9rti6v$hcu$1@news.huji.ac.il>, Ehud Lamm says... > >2. Why is List private? Shouldn't it be limited private, so we avoid > >possible erros caused by aliasing? > > Ahh. It finally dawned on me what your objection to private was. (I'm a little > slow today again.) We are talking about what happens when you do a > "List1 := List2;", aren't we? Yep. And to make things worse the scoping issues with Controlled are really confusing for beginners. Now I don't see any reason why newcomers shouldn't be able to reuse standard containers, but I really don't want to start explaining "controled type must be declared at library level". Amusingly, a student just asked about this problem, in my course newsgroup, trying to reuse a linked list package. They are now just learning about the basics of ADTs, and Ada packages... Are we coming to the conclusion that Ada95 approaches to memory management (Controlled and storage pools), simply aren't enough for creating reliable components, without imposing inessential restrictions? We want user created abstractions to be as much like language supplied types as possible, remember. Ehud ^ permalink raw reply [flat|nested] 116+ messages in thread
* Re: List container strawman 2001-11-08 10:34 ` Ehud Lamm @ 2001-11-09 14:49 ` Ted Dennison 2001-11-09 16:12 ` Ehud Lamm 2001-11-09 17:12 ` Marin David Condic 0 siblings, 2 replies; 116+ messages in thread From: Ted Dennison @ 2001-11-09 14:49 UTC (permalink / raw) In article <9sdnb2$dd4$1@news.huji.ac.il>, Ehud Lamm says... > >Now I don't see any reason why newcomers shouldn't be able to reuse standard >containers, but I really don't want to start explaining "controled type must >be declared at library level". To make matters worse, that isn't even where you'd have to start. You'd have to start by talking about tagged types and declaration levels, then move to the fact that controlled is a tagged type declared at the library level. :-) >Are we coming to the conclusion that Ada95 approaches to memory management >(Controlled and storage pools), simply aren't enough for creating reliable >components, without imposing inessential restrictions? I don't think there's anything horribly wrong with the rest of the language, but we can certianly come to the conclusion that the way Controlled is currently implemented blows. I've said as much to any who would listen for about the last year or so. However, I would like to agree with Nick's point that my contempt is aimed solely at the feature in its current state, not the folks who worked on the language design. I could easily see where this consequence was either not forseen, or it wasn't realised how big of a problem the restriction would be. --- T.E.D. homepage - http://www.telepath.com/dennison/Ted/TED.html No trees were killed in the sending of this message. However a large number of electrons were terribly inconvenienced. ^ permalink raw reply [flat|nested] 116+ messages in thread
* Re: List container strawman 2001-11-09 14:49 ` Ted Dennison @ 2001-11-09 16:12 ` Ehud Lamm 2001-11-09 17:12 ` Marin David Condic 1 sibling, 0 replies; 116+ messages in thread From: Ehud Lamm @ 2001-11-09 16:12 UTC (permalink / raw) Ted Dennison <dennison@telepath.com> wrote in message news:72SG7.18851$xS6.30225@www.newsranger.com... > However, I would like to agree with Nick's point that my contempt is > aimed solely at the feature in its current state, not the folks who worked on > the language design. I could easily see where this consequence was either not > forseen, or it wasn't realised how big of a problem the restriction would be. > I am sure we can all agree that no one here feels contempt for the Ada95 designers. Ehud ^ permalink raw reply [flat|nested] 116+ messages in thread
* Re: List container strawman 2001-11-09 14:49 ` Ted Dennison 2001-11-09 16:12 ` Ehud Lamm @ 2001-11-09 17:12 ` Marin David Condic 2001-11-09 18:11 ` Ted Dennison 2001-11-09 18:42 ` Matthew Heaney 1 sibling, 2 replies; 116+ messages in thread From: Marin David Condic @ 2001-11-09 17:12 UTC (permalink / raw) Aside from the restrictions, I've found it to be just plain buggy. By combining Controlled with other features, either Controlled breaks, or the other features break. Granted, the experience I have, has only been with a handful of versions of a single compiler, but because it seems to kill things in new and interesting ways in a variety of settings, I begin to wonder if the feature is just simply not reliable in its current design. We need something very much like Controlled, but perhaps it is possible to design something that is a little less restrictive and/or a little easier to make reliable? MDC -- Marin David Condic Senior Software Engineer Pace Micro Technology Americas www.pacemicro.com Enabling the digital revolution e-Mail: marin.condic@pacemicro.com Web: http://www.mcondic.com/ "Ted Dennison" <dennison@telepath.com> wrote in message news:72SG7.18851$xS6.30225@www.newsranger.com... > > I don't think there's anything horribly wrong with the rest of the language, but > we can certianly come to the conclusion that the way Controlled is currently > implemented blows. I've said as much to any who would listen for about the last > year or so. However, I would like to agree with Nick's point that my contempt is > aimed solely at the feature in its current state, not the folks who worked on > the language design. I could easily see where this consequence was either not > forseen, or it wasn't realised how big of a problem the restriction would be. > ^ permalink raw reply [flat|nested] 116+ messages in thread
* Re: List container strawman 2001-11-09 17:12 ` Marin David Condic @ 2001-11-09 18:11 ` Ted Dennison 2001-11-09 18:42 ` Matthew Heaney 1 sibling, 0 replies; 116+ messages in thread From: Ted Dennison @ 2001-11-09 18:11 UTC (permalink / raw) In article <9sh2qq$nu6$1@nh.pace.co.uk>, Marin David Condic says... > >Aside from the restrictions, I've found it to be just plain buggy. By >combining Controlled with other features, either Controlled breaks, or the >other features break. Granted, the experience I have, has only been with a >handful of versions of a single compiler, but because it seems to kill >things in new and interesting ways in a variety of settings, I begin to >wonder if the feature is just simply not reliable in its current design. I've often found trouble when doing complicated or unusual things with the language with any compiler. Perhaps what you are seeing is just a combination of the fact that, as Robert pointed out, Controlled is tricky to implement properly, and the fact that as designed it isn't as useful (and therefore as exercised in compilers) as it could be. --- T.E.D. homepage - http://www.telepath.com/dennison/Ted/TED.html No trees were killed in the sending of this message. However a large number of electrons were terribly inconvenienced. ^ permalink raw reply [flat|nested] 116+ messages in thread
* Re: List container strawman 2001-11-09 17:12 ` Marin David Condic 2001-11-09 18:11 ` Ted Dennison @ 2001-11-09 18:42 ` Matthew Heaney 2001-11-10 17:54 ` Simon Wright 1 sibling, 1 reply; 116+ messages in thread From: Matthew Heaney @ 2001-11-09 18:42 UTC (permalink / raw) "Marin David Condic" <dont.bother.mcondic.auntie.spam@[acm.org> wrote in message news:9sh2qq$nu6$1@nh.pace.co.uk... > Aside from the restrictions, I've found it to be just plain buggy. By > combining Controlled with other features, either Controlled breaks, or the > other features break. Granted, the experience I have, has only been with a > handful of versions of a single compiler, but because it seems to kill > things in new and interesting ways in a variety of settings, I begin to > wonder if the feature is just simply not reliable in its current design. Well, I can only speak from my experience (several versions of GNAT), but I have never had a problem with Controlled types. Which features "break" when you use Controlled? ^ permalink raw reply [flat|nested] 116+ messages in thread
* Re: List container strawman 2001-11-09 18:42 ` Matthew Heaney @ 2001-11-10 17:54 ` Simon Wright 0 siblings, 0 replies; 116+ messages in thread From: Simon Wright @ 2001-11-10 17:54 UTC (permalink / raw) "Matthew Heaney" <mheaney@on2.com> writes: > Well, I can only speak from my experience (several versions of > GNAT), but I have never had a problem with Controlled types. > > Which features "break" when you use Controlled? I don't remember the exact details, but I see a remark in the BC's release notes: Iterators are visibly Controlled. The Controlled bit is because of work on synchronized forms, and the visible bit is because of a GNAT 3.13 problem with finalization when using a function return value to initialize a classwide value. .. GNAT's WITH TYPE sometimes fails when you have a record which contains a field of a WITH TYPE IS ACCESS type and a field of a controlled type and you create an access type for the record and you try to use a non-standard storage pool .. .. like Ted said, it can take some poking at extreme cases to get this stuff to show! ^ permalink raw reply [flat|nested] 116+ messages in thread
* Re: List container strawman 2001-11-02 3:56 Ted Dennison ` (2 preceding siblings ...) 2001-11-02 7:28 ` Ehud Lamm @ 2001-11-02 14:49 ` Marin David Condic 2001-11-02 15:15 ` Ted Dennison 2001-11-02 17:02 ` David Botton ` (3 subsequent siblings) 7 siblings, 1 reply; 116+ messages in thread From: Marin David Condic @ 2001-11-02 14:49 UTC (permalink / raw) I just took a quick look at it & I think it would be workable. It has simplicity on its side. Without having thought about it for any real length of time I don't see anything major missing, but perhaps there might be some desirable operations to be added. For example, I think it ought to have a "Load/Store" operation to get/put the contents to a file using Streams. ("You give me a file name string and a list & I handle the I/O") It would be handy to have 'Input and 'Output working on it as well so you could get it in and out of a Stream_Element_Array. Also, I think it would be wise to have this (and any other packages) rooted at some common package with a name like "ASCL" just to make the whole thing identifiable as a conglomerate. (But that would be arguing about names and I promised I would not do that! :-) MDC -- Marin David Condic Senior Software Engineer Pace Micro Technology Americas www.pacemicro.com Enabling the digital revolution e-Mail: marin.condic@pacemicro.com Web: http://www.mcondic.com/ "Ted Dennison" <dennison@telepath.com> wrote in message news:kPoE7.9567$xS6.13287@www.newsranger.com... > Since we do seem to be reaching a small amount of agreement on details, I went > ahead a put together a strawman package spec (sans private part) for the > unbounded list container, for the purposes of keeping the dicussions rolling in > a postitive direction. It is attached here, and available on my website at > http://www.telepath.com/dennison/Ted/Containers-Lists-Unbounded.ads.html . If it > is close enough to be worth persuing, we may be able to use it as a starting > point. > > (Note: The htmlization there was done by a tool I'm developing as part of the > next release of OpenToken. If you have comments on the job it did, I'd like them > too, but email would probably be the best venue for it). > > --- > T.E.D. homepage - http://www.telepath.com/dennison/Ted/TED.html > > No trees were killed in the sending of this message. > However a large number of electrons were terribly inconvenienced. ^ permalink raw reply [flat|nested] 116+ messages in thread
* Re: List container strawman 2001-11-02 14:49 ` Marin David Condic @ 2001-11-02 15:15 ` Ted Dennison 2001-11-02 15:37 ` Marin David Condic 0 siblings, 1 reply; 116+ messages in thread From: Ted Dennison @ 2001-11-02 15:15 UTC (permalink / raw) In article <9rubqc$i1u$1@nh.pace.co.uk>, Marin David Condic says... >desirable operations to be added. For example, I think it ought to have a >"Load/Store" operation to get/put the contents to a file using Streams. >("You give me a file name string and a list & I handle the I/O") It would be >handy to have 'Input and 'Output working on it as well so you could get it >in and out of a Stream_Element_Array. Definitely. >Also, I think it would be wise to have this (and any other packages) rooted >at some common package with a name like "ASCL" just to make the whole thing >identifiable as a conglomerate. (But that would be arguing about names and I >promised I would not do that! :-) :-) Actually, that's a perfectly reasonable discussion to be having. I picked the root name of "Containers" just to have something. If it were part of the Ada standard, I'd like to see "Ada.Containers.*". Otherwise, we'd need a good root name either on top of, or instead of, "Containers". --- T.E.D. homepage - http://www.telepath.com/dennison/Ted/TED.html No trees were killed in the sending of this message. However a large number of electrons were terribly inconvenienced. ^ permalink raw reply [flat|nested] 116+ messages in thread
* Re: List container strawman 2001-11-02 15:15 ` Ted Dennison @ 2001-11-02 15:37 ` Marin David Condic 2001-11-02 16:49 ` Ted Dennison 0 siblings, 1 reply; 116+ messages in thread From: Marin David Condic @ 2001-11-02 15:37 UTC (permalink / raw) The problem with Ada.Containers is that a) it presumes we're going to get it into the standard and b) it makes it difficult for someone to modify the source since compilers are free to restrict you from manipulating things under Ada... (Try declaring Ada.Containers and see if it will compile.) Probably it is better to have it rooted as its own thing so it can be as flexible as possible until such time as The Powers That Be decide to immortalize you by including The Dennison Components into the standard. :-) It could probably be accommodated at a later date through a bunch of "renames" things... MDC -- Marin David Condic Senior Software Engineer Pace Micro Technology Americas www.pacemicro.com Enabling the digital revolution e-Mail: marin.condic@pacemicro.com Web: http://www.mcondic.com/ "Ted Dennison" <dennison@telepath.com> wrote in message news:JMyE7.10064$xS6.13823@www.newsranger.com... > Actually, that's a perfectly reasonable discussion to be having. I picked the > root name of "Containers" just to have something. If it were part of the Ada > standard, I'd like to see "Ada.Containers.*". Otherwise, we'd need a good root > name either on top of, or instead of, "Containers". ^ permalink raw reply [flat|nested] 116+ messages in thread
* Re: List container strawman 2001-11-02 15:37 ` Marin David Condic @ 2001-11-02 16:49 ` Ted Dennison 2001-11-02 17:09 ` Marin David Condic 2001-11-03 23:41 ` Nick Roberts 0 siblings, 2 replies; 116+ messages in thread From: Ted Dennison @ 2001-11-02 16:49 UTC (permalink / raw) In article <9rueje$j69$1@nh.pace.co.uk>, Marin David Condic says... > >The problem with Ada.Containers is that a) it presumes we're going to get it >into the standard and b) it makes it difficult for someone to modify the >source since compilers are free to restrict you from manipulating things >under Ada... (Try declaring Ada.Containers and see if it will compile.) All of which is why it isn't currently named that. :-) >Probably it is better to have it rooted as its own thing so it can be as >flexible as possible until such time as The Powers That Be decide to >immortalize you by including The Dennison Components into the standard. :-) Fine by me. It might be a good idea if it were something reasonably interchangable with "Ada." when/if the time comes. But then again, perhaps it would be best to have somthing that we would be comfortable with on its own for perpetuity. I know the "Dennison Components" bit was just a joke, but I'd like to make one thing perfectly clear: I don't want or need my name prominently attached to this. This has been and should contiune to be a community effort. We have just reached a point in the discussion where we really need something tangible to talk around. I'm trying to see if it is possible to synthesize our agreements into source code form. If it is possible, great. If not, it was worth a shot. If I wanted to make my *own* component library, I'd just do it rather than come up here asking for input on everything. More likely, I'd *not* do it and use Booch. :-) --- T.E.D. homepage - http://www.telepath.com/dennison/Ted/TED.html No trees were killed in the sending of this message. However a large number of electrons were terribly inconvenienced. ^ permalink raw reply [flat|nested] 116+ messages in thread
* Re: List container strawman 2001-11-02 16:49 ` Ted Dennison @ 2001-11-02 17:09 ` Marin David Condic 2001-11-04 0:10 ` Nick Roberts 2001-11-03 23:41 ` Nick Roberts 1 sibling, 1 reply; 116+ messages in thread From: Marin David Condic @ 2001-11-02 17:09 UTC (permalink / raw) I think we're clear that this is a group-consensus effort to at least see what sort of requirements people have for such a library. So far, we're at least kicking around some concrete ideas, which IMHO is a good thing. I know we've got a couple of BC fans here & if there was a consensus to accept that, I'd get on board, so maybe its still an idea worth kicking around. But I can understand and agree with the objection that it is not as simple and straightforward as one might like. Is there any way we might identify interested parties and get a straw-poll on it? Any chance the vendors would likely get on board? MDC -- Marin David Condic Senior Software Engineer Pace Micro Technology Americas www.pacemicro.com Enabling the digital revolution e-Mail: marin.condic@pacemicro.com Web: http://www.mcondic.com/ "Ted Dennison" <dennison@telepath.com> wrote in message news:j8AE7.10206$xS6.13935@www.newsranger.com... > > I know the "Dennison Components" bit was just a joke, but I'd like to make one > thing perfectly clear: I don't want or need my name prominently attached to > this. This has been and should contiune to be a community effort. We have just > reached a point in the discussion where we really need something tangible to > talk around. I'm trying to see if it is possible to synthesize our agreements > into source code form. If it is possible, great. If not, it was worth a shot. If > I wanted to make my *own* component library, I'd just do it rather than come up > here asking for input on everything. More likely, I'd *not* do it and use Booch. > :-) ^ permalink raw reply [flat|nested] 116+ messages in thread
* Re: List container strawman 2001-11-02 17:09 ` Marin David Condic @ 2001-11-04 0:10 ` Nick Roberts 0 siblings, 0 replies; 116+ messages in thread From: Nick Roberts @ 2001-11-04 0:10 UTC (permalink / raw) I tried to kick start the Ada Structured Component Library (ASCL) group more than a year ago, on eGroups, but weirdly I seemed to get a pile of interest which fizzled out as fast as it arrived. Very odd. Anyway, I am interested! -- Nick Roberts "Marin David Condic" <dont.bother.mcondic.auntie.spam@[acm.org> wrote in message news:9ruk02$lft$1@nh.pace.co.uk... > I think we're clear that this is a group-consensus effort to at least see > what sort of requirements people have for such a library. So far, we're at > least kicking around some concrete ideas, which IMHO is a good thing. > > I know we've got a couple of BC fans here & if there was a consensus to > accept that, I'd get on board, so maybe its still an idea worth kicking > around. But I can understand and agree with the objection that it is not as > simple and straightforward as one might like. Is there any way we might > identify interested parties and get a straw-poll on it? Any chance the > vendors would likely get on board? ^ permalink raw reply [flat|nested] 116+ messages in thread
* Re: List container strawman 2001-11-02 16:49 ` Ted Dennison 2001-11-02 17:09 ` Marin David Condic @ 2001-11-03 23:41 ` Nick Roberts 1 sibling, 0 replies; 116+ messages in thread From: Nick Roberts @ 2001-11-03 23:41 UTC (permalink / raw) "Ted Dennison" <dennison@telepath.com> wrote in message news:j8AE7.10206$xS6.13935@www.newsranger.com... > ... > I know the "Dennison Components" bit was just a joke, but I'd like to make one > thing perfectly clear: I don't want or need my name prominently attached to > this. This has been and should contiune to be a community effort. We have just > reached a point in the discussion where we really need something tangible to > talk around. I'm trying to see if it is possible to synthesize our agreements > into source code form. If it is possible, great. If not, it was worth a shot. If > I wanted to make my *own* component library, I'd just do it rather than come up > here asking for input on everything. More likely, I'd *not* do it and use Booch. I'm afraid I feel it ought to be named 'Iteration'. It's terribly insipid, but it seems to fit the bill, to me: generic type Element_Type is private; package Iteration is ... end Iteration; This would then be instantiated in a very clear way: package Thingy_Iteration is new Iteration(Thingy_Type); Thingy_List_1: Thingy_Iteration.Lists.Unbounded.Doubly_Linked_List; I think perhaps there should be a child package Lists, which declares an abstract List_Type with attendant common list operations. This should then have children such as Unbounded which declares concrete utility types based on List_Type. We could then have other hierarchies implementing queues, content-addressed containers, and so on. See also my other posting. -- Nick Roberts ^ permalink raw reply [flat|nested] 116+ messages in thread
* Re: List container strawman 2001-11-02 3:56 Ted Dennison ` (3 preceding siblings ...) 2001-11-02 14:49 ` Marin David Condic @ 2001-11-02 17:02 ` David Botton 2001-11-02 17:55 ` David Botton 2001-11-03 19:22 ` Nick Roberts ` (2 subsequent siblings) 7 siblings, 1 reply; 116+ messages in thread From: David Botton @ 2001-11-02 17:02 UTC (permalink / raw) Why not start with the Original (as in Ada 83) Booch http://www.adapower.com/original_booch components and just modify them (they are under the GMGPL)? They are a very close fit already. "Ted Dennison" <dennison@telepath.com> wrote > Since we do seem to be reaching a small amount of agreement on details ^ permalink raw reply [flat|nested] 116+ messages in thread
* Re: List container strawman 2001-11-02 17:02 ` David Botton @ 2001-11-02 17:55 ` David Botton 0 siblings, 0 replies; 116+ messages in thread From: David Botton @ 2001-11-02 17:55 UTC (permalink / raw) Just to clarify, I am not referring to the BC components. "David Botton" <David@Botton.com> wrote in message news:tu5kdq7ej2j3e6@corp.supernews.com... > Why not start with the Original (as in Ada 83) Booch > http://www.adapower.com/original_booch components and just modify them (they > are under the GMGPL)? They are a very close fit already. > > "Ted Dennison" <dennison@telepath.com> wrote > > Since we do seem to be reaching a small amount of agreement on details > > ^ permalink raw reply [flat|nested] 116+ messages in thread
* Re: List container strawman 2001-11-02 3:56 Ted Dennison ` (4 preceding siblings ...) 2001-11-02 17:02 ` David Botton @ 2001-11-03 19:22 ` Nick Roberts [not found] ` <3BE29AF4.80804@telepath.com> 2001-11-08 14:57 ` M. A. Alves 7 siblings, 0 replies; 116+ messages in thread From: Nick Roberts @ 2001-11-03 19:22 UTC (permalink / raw) May I make a suggestion, which, though I say it myself, I feel is rather important! Please make the type List derived from an abstract 'iterator' type. List would then inherit the iteration operations of this type. An alternative is for List to provide a function that generates or gives access to an object derived from this iterator type. For example: generic type Element_Type is private; package Containers is ... type Terminating_Producer is abstract tagged limited private; procedure Read (Producer: in out Terminating_Producer; Item: out Element_Type) is abstract; function End_of_Data (Producer: in Terminating_Producer) return Boolean is abstract; ... type Sequence_Reproducer is abstract new Terminating_Producer with private; procedure Restart (Reproducer: in out Sequence_Reproducer) is abstract; type Sequence_Recorder is abstract new Sequence_Reproducer with private; procedure Rewrite (Reproducer: in out Sequence_Reproducer) is abstract; procedure Write (Recorder: in out Sequence_Recorder; Item: in Element_Type) is abstract; function Count (Recorder: in Sequence_Recorder) return Natural is abstract; function Is_Recording (Recorder: in Sequence_Recorder) return Boolean is abstract; ... end Containers; The Restart procedure tells a sequence reproducer to start producing its data over again. The Rewrite procedure tells a sequence recorder to start recording data (at which point Write can be used and Read cannot; Is_Recording returns True). Restart than tells it to start reading again (at which point Write cannot be used; Is_Recording returns False). Count returns the number of items currently recorded. package Containers.Lists.Unbounded is type Linked_List is new Sequence_Recorder with private; -- Representing a singly-linked (forward) list type, with typical operations. function "&" (Left, Right: in Linked_List) return Linked_List is abstract; ... procedure Push (List: in out Linked_List; Item: in Element_Type); procedure Pop (List: in out Linked_List; Item: out Element_Type); ... -- etc type Doubly_Linked_List is new Sequence_Recorder with private; function "&" (Left, Right: in Linked_List) return Abstract_List is abstract; ... procedure Push (List: in out Linked_List; Item: in Element_Type); procedure Pop (List: in out Linked_List; Item: out Element_Type); procedure Reverse_Push (List: in out Linked_List; Item: in Element_Type); procedure Reverse_Pop (List: in out Linked_List; Item: out Element_Type); ... -- etc end Containers.Utility.Lists; In this way, a piece of software which only needs to iterate over a container can be passed any of the list types, or other container types. E.g.: generic with package Specific_Containers is new Containers(<>); procedure Print_a_List (List: in out Specific_Containers.Sequence_Producer'Class); ... package Thingy_Containers is new Containers(Thingy_Type); Thingies_1: Thingy_Containers.Lists.Unbounded.Linked_List; Thingies_2: Thingy_Containers.Lists.Unbounded.Doubly_Linked_List; ... package Print_Thingies is new Print_a_List(Thingy_Containers); ... Print_Thingies(Thingies_1); Print_Thingies(Thingies_2); We can call instantiations of Print_a_List with objects of type Linked_List, or Doubly_Linked_List, or anything else (i.e. other containers) derived from Sequence_Producer. My choice of identifiers, and the details of my design may not be ideal, but the basic idea is right. Please don't get this elementary aspect of the design wrong! -- Nick Roberts "Ted Dennison" <dennison@telepath.com> wrote in message news:kPoE7.9567$xS6.13287@www.newsranger.com... > Since we do seem to be reaching a small amount of agreement on details, I went > ahead a put together a strawman package spec (sans private part) for the > unbounded list container, for the purposes of keeping the dicussions rolling in > a postitive direction. It is attached here, and available on my website at > http://www.telepath.com/dennison/Ted/Containers-Lists-Unbounded.ads.html . If it > is close enough to be worth persuing, we may be able to use it as a starting > point. ^ permalink raw reply [flat|nested] 116+ messages in thread
[parent not found: <3BE29AF4.80804@telepath.com>]
* Re: List container strawman [not found] ` <3BE29AF4.80804@telepath.com> @ 2001-11-02 13:14 ` Ted Dennison 2001-11-02 13:31 ` Larry Kilgallen 2001-11-02 17:44 ` Jeffrey Carter 2001-11-05 14:00 ` Stephen Leake 1 sibling, 2 replies; 116+ messages in thread From: Ted Dennison @ 2001-11-02 13:14 UTC (permalink / raw) [-- Attachment #1: Type: text/plain, Size: 337 bytes --] Ted Dennison wrote: > Ted Dennison wrote: > >> a postitive direction. It is attached here, and available on my >> website at > > Whoops. No, it wasn't. That was probably for the best, as Newsranger > likes to hose formatting. It is attached here (posted w/ Mozilla). (sigh) My aplogies for posting HTML. Here's the text file. [-- Attachment #2: containers-lists-unbounded.ads --] [-- Type: text/plain, Size: 5343 bytes --] ------------------------------------------------------------------------------- -- This file contains a proposal for a standard Ada list package. -- -- version - Strawman 1.0 ------------------------------------------------------------------------------- generic type Element is private; package Containers.Lists.Unbounded is ----------------------------------------------------------------------------- -- The list type. I know the name's a bit redundant, but it doesn't look too -- bad, and any fully-named use will have to have a different name for the -- package anyway. ----------------------------------------------------------------------------- type List is private; ----------------------------------------------------------------------------- -- List construction operations. The returned list will contain *copies* of -- all the elements in the source lists, so these routines could get -- time-consuming. However, they should be useful for Lisp-like processing. -- -- I considered using unary minus ("-") for the "Construct" routine, but -- that's not a common idiom right now. ----------------------------------------------------------------------------- function "&" (Left, Right : Element) return List; function "&" (Left : Element; Right : List) return List; function "&" (Left : List; Right : Element) return List; function "&" (Left, Right : List) return List; function Construct (Initial_Element : Element) return List; ----------------------------------------------------------------------------- -- "push" and "pop" operations. ----------------------------------------------------------------------------- procedure Push_Front (Target : in out List; New_Element : in Element); procedure Pop_Front (Target : in out List; Old_Element : out Element); procedure Push_Back (Target : in out List; New_Element : in Element); procedure Pop_Back (Target : in out List; Old_Element : out Element); ----------------------------------------------------------------------------- -- Non-modifying query operations. ----------------------------------------------------------------------------- function Is_Empty (Subject : List) return Boolean; function Size (Subject : List) return Natural; function Front (Subject : List) return Element; function Back (Subject : List) return Element; ----------------------------------------------------------------------------- -- I'm not too sure how useful these are, since they have to work on global -- data. ----------------------------------------------------------------------------- generic with procedure Operation (Target : in out Element); procedure Closure_Operation (Target : in out List); ----------------------------------------------------------------------------- -- Iteration routines. Next and Previous raise No_More if there is no item in -- the given direction. For an empty list, First = Last. As written, a -- typical iteration idiom would look like: -- -- i := My_Lists.First (My_List); -- loop -- do stuff with My_Lists.Item(i); -- exit when i = My_Lists.Last (My_List); -- i := My_Lists.Next (i); -- end loop; -- -- Another alternative using exception handling would be: -- -- declare -- i := My_Lists.First (My_List); -- begin -- loop -- do stuff with My_Lists.Item(i); -- i := My_Lists.Next (i); -- end loop; -- exception -- when My_Lists.No_More => -- null; -- end; -- -- A third alternative using "Size" would be: -- -- i := My_Lists.First (My_List); -- for iteration_count in 1..My_Lists.Size (My_List) loop -- do stuff with My_Lists.Item (i); -- i := My_Lists.Next (i); -- end loop; -- ----------------------------------------------------------------------------- type Iterator is private; No_More : exception; function First (Subject : List) return Iterator; function Last (Subject : List) return Iterator; function Next (Location : Iterator) return Iterator; function Previous (Location : Iterator) return Iterator; function Item (Location : Iterator) return Element; -- Ideally this routine would verify that Location was issued for the Subject -- list and is still valid, but that would be tough to enforce. Better to call -- such misuse a "bounded error", or somesuch. procedure Remove (Subject : in out List; Location : Iterator); ----------------------------------------------------------------------------- -- Sorting routine. -- To sort in increasing order, use the ">" routine for the Reverse_Order -- parameter. To sort in decreasing order, substitute your "<" routine for -- the Reverse_Order parameter. :-) ----------------------------------------------------------------------------- generic with function Reverse_Order (Left, Right : in Element) return Boolean; procedure Sort (Subject : in out List); private -- Placebo entries to make the compiler happy (so I know the syntax above is correct) type List is new Boolean; type Iterator is new Boolean; end Containers.Lists.Unbounded; ^ permalink raw reply [flat|nested] 116+ messages in thread
* Re: List container strawman 2001-11-02 13:14 ` Ted Dennison @ 2001-11-02 13:31 ` Larry Kilgallen 2001-11-02 15:09 ` Ted Dennison 2001-11-02 20:48 ` David Starner 2001-11-02 17:44 ` Jeffrey Carter 1 sibling, 2 replies; 116+ messages in thread From: Larry Kilgallen @ 2001-11-02 13:31 UTC (permalink / raw) In article <3BE29BD4.10401@telepath.com>, Ted Dennison <dennison@telepath.com> writes: > This is a multi-part message in MIME format. > --------------060706040909060005070802 > Content-Type: text/plain; charset=us-ascii; format=flowed > Content-Transfer-Encoding: 7bit > > Ted Dennison wrote: > >> Ted Dennison wrote: >> >>> a postitive direction. It is attached here, and available on my >>> website at >> >> Whoops. No, it wasn't. That was probably for the best, as Newsranger >> likes to hose formatting. It is attached here (posted w/ Mozilla). > > > (sigh) > > My aplogies for posting HTML. Here's the text file. > > > > > --------------060706040909060005070802 > Content-Type: text/plain; > name="containers-lists-unbounded.ads" > Content-Transfer-Encoding: 7bit > Content-Disposition: inline; > filename="containers-lists-unbounded.ads" So why _do_ you continue to post HTML if you know it is undesired ? But thanks for _finally_ changing to a reasonable title. ^ permalink raw reply [flat|nested] 116+ messages in thread
* Re: List container strawman 2001-11-02 13:31 ` Larry Kilgallen @ 2001-11-02 15:09 ` Ted Dennison 2001-11-02 15:13 ` Preben Randhol 2001-11-02 20:48 ` David Starner 1 sibling, 1 reply; 116+ messages in thread From: Ted Dennison @ 2001-11-02 15:09 UTC (permalink / raw) In article <TOPqAssaO5$l@eisner.encompasserve.org>, Larry Kilgallen says... > >So why _do_ you continue to post HTML if you know it is undesired ? Damn. I'm sorry about that. I'm not used to posting w/ Mozilla. I thought posting it as a text attachment would make it text. I guess I should have posted it to alt.text first. --- T.E.D. homepage - http://www.telepath.com/dennison/Ted/TED.html No trees were killed in the sending of this message. However a large number of electrons were terribly inconvenienced. ^ permalink raw reply [flat|nested] 116+ messages in thread
* Re: List container strawman 2001-11-02 15:09 ` Ted Dennison @ 2001-11-02 15:13 ` Preben Randhol 0 siblings, 0 replies; 116+ messages in thread From: Preben Randhol @ 2001-11-02 15:13 UTC (permalink / raw) On Fri, 02 Nov 2001 15:09:39 GMT, Ted Dennison wrote: > Damn. I'm sorry about that. I'm not used to posting w/ Mozilla. I thought > posting it as a text attachment would make it text. I guess I should have posted > it to alt.text first. ^^^^^^^^ alt.test I hope? ;-) Preben -- "Violence is the last refuge of the incompetent", Isaac Asimov ^ permalink raw reply [flat|nested] 116+ messages in thread
* Re: List container strawman 2001-11-02 13:31 ` Larry Kilgallen 2001-11-02 15:09 ` Ted Dennison @ 2001-11-02 20:48 ` David Starner 2001-11-02 22:49 ` Larry Kilgallen 1 sibling, 1 reply; 116+ messages in thread From: David Starner @ 2001-11-02 20:48 UTC (permalink / raw) On 2 Nov 2001 07:31:02 -0600, Larry Kilgallen <Kilgallen@SpamCop.net> wrote: > In article <3BE29BD4.10401@telepath.com>, Ted Dennison <dennison@telepath.com> writes: >> --------------060706040909060005070802 >> Content-Type: text/plain; >> name="containers-lists-unbounded.ads" >> Content-Transfer-Encoding: 7bit >> Content-Disposition: inline; >> filename="containers-lists-unbounded.ads" > > So why _do_ you continue to post HTML if you know it is undesired ? That's not HTML; that's MIME. -- David Starner - dstarner98@aasaa.ofe.org Pointless website: http://dvdeug.dhis.org "I saw a daemon stare into my face, and an angel touch my breast; each one softly calls my name . . . the daemon scares me less." - "Disciple", Stuart Davis ^ permalink raw reply [flat|nested] 116+ messages in thread
* Re: List container strawman 2001-11-02 20:48 ` David Starner @ 2001-11-02 22:49 ` Larry Kilgallen 0 siblings, 0 replies; 116+ messages in thread From: Larry Kilgallen @ 2001-11-02 22:49 UTC (permalink / raw) In article <9rv0qq$8i41@news.cis.okstate.edu>, David Starner <dvdeug@x8b4e53cd.dhcp.okstate.edu> writes: > On 2 Nov 2001 07:31:02 -0600, Larry Kilgallen <Kilgallen@SpamCop.net> wrote: >> In article <3BE29BD4.10401@telepath.com>, Ted Dennison <dennison@telepath.com> writes: >>> --------------060706040909060005070802 >>> Content-Type: text/plain; >>> name="containers-lists-unbounded.ads" >>> Content-Transfer-Encoding: 7bit >>> Content-Disposition: inline; >>> filename="containers-lists-unbounded.ads" >> >> So why _do_ you continue to post HTML if you know it is undesired ? > > That's not HTML; that's MIME. Correct. ^ permalink raw reply [flat|nested] 116+ messages in thread
* Re: List container strawman 2001-11-02 13:14 ` Ted Dennison 2001-11-02 13:31 ` Larry Kilgallen @ 2001-11-02 17:44 ` Jeffrey Carter 2001-11-02 20:07 ` Ted Dennison 2001-11-03 7:42 ` Simon Wright 1 sibling, 2 replies; 116+ messages in thread From: Jeffrey Carter @ 2001-11-02 17:44 UTC (permalink / raw) Ted Dennison wrote: > > -- This file contains a proposal for a standard Ada list package. This is NOT a list. A list allows insertions at any point in the sequence. This is a dequeue. > -- > -- version - Strawman 1.0 > ------------------------------------------------------------------------------- > generic > type Element is private; This specifies that the package requires "=" for Element. I see no need for "=" in implementing a dequeue. The generic formal part is improperly specified. > package Containers.Lists.Unbounded is > > ----------------------------------------------------------------------------- > -- The list type. I know the name's a bit redundant, but it doesn't look too > -- bad, and any fully-named use will have to have a different name for the > -- package anyway. > ----------------------------------------------------------------------------- > type List is private; This either needs to be limited private or a controlled type. Since this is an unbounded dequeue, assignment of one dequeue to another will result in sharing the internal structure implementing the source dequeue. What are the time/space implications for the operations. For example, is Size O(1) or O(N)? > > ----------------------------------------------------------------------------- > -- List construction operations. The returned list will contain *copies* of > -- all the elements in the source lists, so these routines could get > -- time-consuming. However, they should be useful for Lisp-like processing. > -- > -- I considered using unary minus ("-") for the "Construct" routine, but > -- that's not a common idiom right now. > ----------------------------------------------------------------------------- > function "&" (Left, Right : Element) return List; > function "&" (Left : Element; Right : List) return List; > function "&" (Left : List; Right : Element) return List; > function "&" (Left, Right : List) return List; > function Construct (Initial_Element : Element) return List; I suggest Make rather than Construct. > > ----------------------------------------------------------------------------- > -- "push" and "pop" operations. > ----------------------------------------------------------------------------- > procedure Push_Front (Target : in out List; New_Element : in Element); > procedure Pop_Front (Target : in out List; Old_Element : out Element); > procedure Push_Back (Target : in out List; New_Element : in Element); > procedure Pop_Back (Target : in out List; Old_Element : out Element); What happens if you Pop from an empty list? > > ----------------------------------------------------------------------------- > -- Non-modifying query operations. > ----------------------------------------------------------------------------- > function Is_Empty (Subject : List) return Boolean; > function Size (Subject : List) return Natural; > function Front (Subject : List) return Element; > function Back (Subject : List) return Element; > > ----------------------------------------------------------------------------- > -- I'm not too sure how useful these are, since they have to work on global > -- data. They are global to Operation, but they are no more global to the client code than are any variables used in the "do stuff" part of your examples below. > ----------------------------------------------------------------------------- > generic > with procedure Operation (Target : in out Element); > procedure Closure_Operation (Target : in out List); This is an iterator and should be so named ("Iterate"). I recommend adding a Quit or Continue out Boolean parameter to Operation to allow the client to terminate the iteration early. > > ----------------------------------------------------------------------------- > -- Iteration routines. Next and Previous raise No_More if there is no item in > -- the given direction. For an empty list, First = Last. As written, a > -- typical iteration idiom would look like: > -- > -- i := My_Lists.First (My_List); > -- loop > -- do stuff with My_Lists.Item(i); > -- exit when i = My_Lists.Last (My_List); > -- i := My_Lists.Next (i); > -- end loop; > -- > -- Another alternative using exception handling would be: > -- > -- declare > -- i := My_Lists.First (My_List); > -- begin > -- loop > -- do stuff with My_Lists.Item(i); > -- i := My_Lists.Next (i); > -- end loop; > -- exception > -- when My_Lists.No_More => > -- null; > -- end; > -- > -- A third alternative using "Size" would be: > -- > -- i := My_Lists.First (My_List); > -- for iteration_count in 1..My_Lists.Size (My_List) loop > -- do stuff with My_Lists.Item (i); > -- i := My_Lists.Next (i); > -- end loop; > -- > ----------------------------------------------------------------------------- This is really ugly. Why should the client have to include all this framing code every time he uses an iterator? The passive iterator (generic) given above does the same thing without all this extra client code, and allows the value stored in the dequeue to be changed as well. > type Iterator is private; > No_More : exception; > > function First (Subject : List) return Iterator; > function Last (Subject : List) return Iterator; > function Next (Location : Iterator) return Iterator; > function Previous (Location : Iterator) return Iterator; > function Item (Location : Iterator) return Element; > > -- Ideally this routine would verify that Location was issued for the Subject > -- list and is still valid, but that would be tough to enforce. Better to call > -- such misuse a "bounded error", or somesuch. This is simple to enforce. See PragmARC.List_Unbounded_Unprotected for an example. > procedure Remove (Subject : in out List; Location : Iterator); Using a given Iterator value, what is the value of Next or Previous after Remove? How about Item? What about when you remove the first or last Elements in the dequeue? > > ----------------------------------------------------------------------------- > -- Sorting routine. > -- To sort in increasing order, use the ">" routine for the Reverse_Order > -- parameter. To sort in decreasing order, substitute your "<" routine for > -- the Reverse_Order parameter. :-) > ----------------------------------------------------------------------------- This seems ugly and easy to get wrong. Why not import "<" and specify that after calling Sort, the Elements in Subject will be in order according to "<"? Then the meaning of the imported function is clear without such a comment. > generic > with function Reverse_Order (Left, Right : in Element) return Boolean; > procedure Sort (Subject : in out List); > > private > -- Placebo entries to make the compiler happy (so I know the syntax above is correct) > type List is new Boolean; > type Iterator is new Boolean; > > end Containers.Lists.Unbounded; -- Jeffrey Carter ^ permalink raw reply [flat|nested] 116+ messages in thread
* Re: List container strawman 2001-11-02 17:44 ` Jeffrey Carter @ 2001-11-02 20:07 ` Ted Dennison 2001-11-02 23:19 ` Jeffrey Carter 2001-11-03 7:42 ` Simon Wright 1 sibling, 1 reply; 116+ messages in thread From: Ted Dennison @ 2001-11-02 20:07 UTC (permalink / raw) In article <3BE2DB99.B707D409@boeing.com>, Jeffrey Carter says... > >Ted Dennison wrote: >> >> -- This file contains a proposal for a standard Ada list package. > >This is NOT a list. A list allows insertions at any point in the >sequence. This is a dequeue. Ahhh. I *knew* I forgot a routine. :-) I'll add Insert next to Remove. >This either needs to be limited private or a controlled type. Since this >is an unbounded dequeue, assignment of one dequeue to another will >result in sharing the internal structure implementing the source >dequeue. Right again. >What are the time/space implications for the operations. For example, is >Size O(1) or O(N)? That's something we should most certianly discuss (for all these ops). I'd be for specifying that Size *should* be O(1), which implies that it will be kept with the main list structure rather than calculated at every Size call. >I suggest Make rather than Construct. Fair enough. I'm used to seeing "make" in terms of GNU make, but the term "Construct" has a fair bit of baggage too. Do we have a second on this motion? >What happens if you Pop from an empty list? Good catch. I'll add an exception for that. (talking about the Closure_Operation generic's Operation procedure parameter) >They are global to Operation, but they are no more global to the client >code than are any variables used in the "do stuff" part of your examples >below. True. I'm so used to avioding using globals in routines that its tough to retrain my thinking in this case. But I guess its OK, since you can instantiate this generic at any level you choose. Thus it could still be data local to the calling subroutine, but "global" to Operation. >> generic >> with procedure Operation (Target : in out Element); >> procedure Closure_Operation (Target : in out List); > >This is an iterator and should be so named ("Iterate"). I recommend >adding a Quit or Continue out Boolean parameter to Operation to allow >the client to terminate the iteration early. Both seem like good suggestions. I'll work on it. >> -- Iteration routines. Next and Previous raise No_More if there is no >This is really ugly. Why should the client have to include all this >framing code every time he uses an iterator? The passive iterator >(generic) given above does the same thing without all this extra client >code, and allows the value stored in the dequeue to be changed as well. I messed that interface up a bit, so I'd appreciate it if you would look over the next version and reconsider your comment. It does clean it up a bit. Also note that to use the passive iterator, you need a generic instantiation and a custom Operation routine, both of which this solution does not require. I think most folks would at least find it a wash. Even if it isn't as nice as the passive iterator, I think it is still needed, as that is how Insert and Remove (your middle of the list operations) are performed. >This is simple to enforce. See PragmARC.List_Unbounded_Unprotected for >an example. Hmmm. Yeah, I guess one could keep a copy of the address of the list around, assuming that it is implemented in a way in which that makes sense. That still doesn't prevent further operations from invalidating your iterator. To detect that, you'd need to somehow keep track of every iterator issued along with the list (in a little mini-list inside it) %-( . > >> procedure Remove (Subject : in out List; Location : Iterator); > >Using a given Iterator value, what is the value of Next or Previous >after Remove? How about Item? What about when you remove the first or >last Elements in the dequeue? Yet another good catch (one would think you've done this before ;-) ). I'd say that: o The mode for "Location" should be "in out" so it won't be invalid afterwards. o If Location=First, then Location will be set to the new First. o If Location=Last, then Location will be set to Done_Iterating. o If Location=Done_Iterating, then No_Item will be raised. o otherwise, Location will be set to what Next was previously (the next element after the removal). > >> >> ----------------------------------------------------------------------------- >> -- Sorting routine. >> -- To sort in increasing order, use the ">" routine for the Reverse_Order >> -- parameter. To sort in decreasing order, substitute your "<" routine for >> -- the Reverse_Order parameter. :-) >> ----------------------------------------------------------------------------- > >This seems ugly and easy to get wrong. Why not import "<" and specify >that after calling Sort, the Elements in Subject will be in order >according to "<"? Then the meaning of the imported function is clear >without such a comment. I started with that, but it wasn't clear to *me* when I read it back to myself. (Hint: which end of the list is on the "left"?) Admittedly, I'm not always the perfect judge of such things though. Does anyone else think that would be clearer? --- T.E.D. homepage - http://www.telepath.com/dennison/Ted/TED.html No trees were killed in the sending of this message. However a large number of electrons were terribly inconvenienced. ^ permalink raw reply [flat|nested] 116+ messages in thread
* Re: List container strawman 2001-11-02 20:07 ` Ted Dennison @ 2001-11-02 23:19 ` Jeffrey Carter 2001-11-03 6:56 ` Ted Dennison 0 siblings, 1 reply; 116+ messages in thread From: Jeffrey Carter @ 2001-11-02 23:19 UTC (permalink / raw) Ted Dennison wrote: > > Even if it isn't as nice as the passive iterator, I think it is still needed, as > that is how Insert and Remove (your middle of the list operations) are > performed. OK. Then this isn't really an iterator type; it's the "Position" type that indicates where in the list you're operating. Now this is starting to look like a list, except I expect to see the general operations (obtain a Position for a list and operate on a specific Position within a list) first, with the bells and whistles later. > > >This is simple to enforce. See PragmARC.List_Unbounded_Unprotected for > >an example. > > Hmmm. Yeah, I guess one could keep a copy of the address of the list around, > assuming that it is implemented in a way in which that makes sense. That still > doesn't prevent further operations from invalidating your iterator. To detect > that, you'd need to somehow keep track of every iterator issued along with the > list (in a little mini-list inside it) %-( . The technique used by PragmARC.List_Unbounded_Unprotected is that the list object contains a pointer to a "mini-node" (a node with no data stored in it). This makes insertions and deletions at the beginning and end of the list look exactly the same as insertions and deletions in the middle, but it also follows that the value of this pointer is unique to the list object. Call this value the list ID. Every node in the list contains a copy of this ID, as does every Position value generated for the list. An operation is not permitted unless the IDs for the list, position, and node match. When a node is deleted, its ID is invalidated (set to null), and the position used to delete the node is similarly invalidated (both its ID and pointer are set to null). If a client makes a copy of a Position and uses one to delete a node, he cannot then manipulate the deallocated node through the other since it has an invalid ID. Easy to implement and fairly foolproof. > > > > >> procedure Remove (Subject : in out List; Location : Iterator); > > > >Using a given Iterator value, what is the value of Next or Previous > >after Remove? How about Item? What about when you remove the first or > >last Elements in the dequeue? > > Yet another good catch (one would think you've done this before ;-) ). I'd say > that: > > o The mode for "Location" should be "in out" so it won't be invalid afterwards. > o If Location=First, then Location will be set to the new First. > o If Location=Last, then Location will be set to Done_Iterating. > o If Location=Done_Iterating, then No_Item will be raised. > o otherwise, Location will be set to what Next was previously (the next element > after the removal). Now that I know that this is standard list manipulation, not iteration, I'd recommend calling it Delete. It's also a lot simpler to make Location in out and invalidate it. There should probably be an Update procedure that changes the Element stored at a location. > >> ----------------------------------------------------------------------------- > >> -- Sorting routine. > >> -- To sort in increasing order, use the ">" routine for the Reverse_Order > >> -- parameter. To sort in decreasing order, substitute your "<" routine for > >> -- the Reverse_Order parameter. :-) > >> ----------------------------------------------------------------------------- > > > >This seems ugly and easy to get wrong. Why not import "<" and specify > >that after calling Sort, the Elements in Subject will be in order > >according to "<"? Then the meaning of the imported function is clear > >without such a comment. > > I started with that, but it wasn't clear to *me* when I read it back to myself. > (Hint: which end of the list is on the "left"?) Admittedly, I'm not always the > perfect judge of such things though. Does anyone else think that would be > clearer? A list is a sequence; it has a first Element, a second Element, and so on. The postcondition here is that for any 2 valid locations L1 and L2 such that L1 /= L2 and L2 = Next (L1), not (Item (L2) < Item (L1) ). -- Jeffrey Carter ^ permalink raw reply [flat|nested] 116+ messages in thread
* Re: List container strawman 2001-11-02 23:19 ` Jeffrey Carter @ 2001-11-03 6:56 ` Ted Dennison 2001-11-03 19:22 ` Jeffrey Carter 0 siblings, 1 reply; 116+ messages in thread From: Ted Dennison @ 2001-11-03 6:56 UTC (permalink / raw) In article <3BE32A18.18404AD1@boeing.com>, Jeffrey Carter says... >The technique used by PragmARC.List_Unbounded_Unprotected is that the >list object contains a pointer to a "mini-node" (a node with no data >stored in it). This makes insertions and deletions at the beginning and >end of the list look exactly the same as insertions and deletions in the >middle, but it also follows that the value of this pointer is unique to >the list object. Call this value the list ID. Every node in the list >contains a copy of this ID, as does every Position value generated for >the list. An operation is not permitted unless the IDs for the list, >position, and node match. When a node is deleted, its ID is invalidated >(set to null), and the position used to delete the node is similarly >invalidated (both its ID and pointer are set to null). If a client makes >a copy of a Position and uses one to delete a node, he cannot then >manipulate the deallocated node through the other since it has an >invalid ID. Easy to implement and fairly foolproof. So you are saying that you are placing values into the memory before it is deallocated, in the hopes that any code trying to access it through a stale pointer will still find that value there (telling it not to use this)? What if: a) The memory at that location gets reallocated to something else in the meantime, which then puts what looks like a valid value in there. b) The OS marks that location as not allocated, and issues a segfault (or whatever) when you try to access it. >Now that I know that this is standard list manipulation, not iteration, >I'd recommend calling it Delete. It's also a lot simpler to make >Location in out and invalidate it. That could be done. "Delete" would also be a natural name for toasting a list, but then I guess in the current scheme "-" would make more sense for that. >There should probably be an Update procedure that changes the Element >stored at a location. That sounds right. --- T.E.D. homepage - http://www.telepath.com/dennison/Ted/TED.html No trees were killed in the sending of this message. However a large number of electrons were terribly inconvenienced. ^ permalink raw reply [flat|nested] 116+ messages in thread
* Re: List container strawman 2001-11-03 6:56 ` Ted Dennison @ 2001-11-03 19:22 ` Jeffrey Carter 2001-11-04 18:58 ` Darren New 0 siblings, 1 reply; 116+ messages in thread From: Jeffrey Carter @ 2001-11-03 19:22 UTC (permalink / raw) Ted Dennison wrote: > > In article <3BE32A18.18404AD1@boeing.com>, Jeffrey Carter says... > >The technique used by PragmARC.List_Unbounded_Unprotected is that the > >list object contains a pointer to a "mini-node" (a node with no data > >stored in it). This makes insertions and deletions at the beginning and > >end of the list look exactly the same as insertions and deletions in the > >middle, but it also follows that the value of this pointer is unique to > >the list object. Call this value the list ID. Every node in the list > >contains a copy of this ID, as does every Position value generated for > >the list. An operation is not permitted unless the IDs for the list, > >position, and node match. When a node is deleted, its ID is invalidated > >(set to null), and the position used to delete the node is similarly > >invalidated (both its ID and pointer are set to null). If a client makes > >a copy of a Position and uses one to delete a node, he cannot then > >manipulate the deallocated node through the other since it has an > >invalid ID. Easy to implement and fairly foolproof. > > So you are saying that you are placing values into the memory before it is > deallocated, in the hopes that any code trying to access it through a stale > pointer will still find that value there (telling it not to use this)? That's right. You don't get 100% confidence, but it's better than the nothing that most lists provide. > > What if: > a) The memory at that location gets reallocated to something else in the > meantime, which then puts what looks like a valid value in there. It's certainly possible that the memory could be reallocated to the same list, so the dangling reference becomes valid again. I did say *fairly* foolproof. :) > > b) The OS marks that location as not allocated, and issues a segfault (or > whatever) when you try to access it. Then you're no worse off than without the check. > That could be done. "Delete" would also be a natural name for toasting a list, > but then I guess in the current scheme "-" would make more sense for that. Let me record my vote against unary operators as primary names. I probably won't object if they're renames of other subprograms. I suggest Clear for deleting all Elements in a List; Make_Empty might also be acceptable. Finally, what you're calling an iterator is what is usually called a "position within a list" in discussing lists as an abstraction, and the manipulation of a list is usually defined in terms of positions. I think it would make the package easier to understand if it adheres to this convention: call the type Position and present the operations for obtaining positions and using them to manipulate a list before the dequeue- and string-like operations. -- Jeff Carter "I fart in your general direction." Monty Python & the Holy Grail ^ permalink raw reply [flat|nested] 116+ messages in thread
* Re: List container strawman 2001-11-03 19:22 ` Jeffrey Carter @ 2001-11-04 18:58 ` Darren New 2001-11-04 19:40 ` Larry Kilgallen 2001-11-05 19:28 ` Ted Dennison 0 siblings, 2 replies; 116+ messages in thread From: Darren New @ 2001-11-04 18:58 UTC (permalink / raw) Jeffrey Carter wrote: > > a) The memory at that location gets reallocated to something else in the > > meantime, which then puts what looks like a valid value in there. > > It's certainly possible that the memory could be reallocated to the same > list, so the dangling reference becomes valid again. I did say *fairly* > foolproof. :) If you really want it to be foolproof, then for each "Location" pointer, you keep a pointer to the list, a pointer to the element being indexed, and a list number counter. In each list head, you keep a list number counter, a counter of the number of Location pointers outstanding, and the head and tail of the list. Creating a Location copies the list number counter into the Location record and otherwise initializes it. It also increments the reference count in the List head. Deleting a Location decrements the ref count in the list head. Deleting the list is defered (via finalization) until the reference count goes to zero. Each access to the pointer in the Location can run thru the linked list that the Location claims it points to, to make sure the node it points to is still on the list. This makes indirection become O(N) instead of O(1), but it's also the kind of check that would be easy to turn on and off at runtime, let alone compile time. Did this for a Pascal compiler, so students using dangling pointers would be told that instead of just dumping core. -- Darren New San Diego, CA, USA (PST). Cryptokeys on demand. Sore feet from standing in line at airport security checkpoints: Jet Leg. ^ permalink raw reply [flat|nested] 116+ messages in thread
* Re: List container strawman 2001-11-04 18:58 ` Darren New @ 2001-11-04 19:40 ` Larry Kilgallen 2001-11-04 20:49 ` Darren New 2001-11-07 19:07 ` ramatthews 2001-11-05 19:28 ` Ted Dennison 1 sibling, 2 replies; 116+ messages in thread From: Larry Kilgallen @ 2001-11-04 19:40 UTC (permalink / raw) In article <3BE58FDD.E1FB1815@san.rr.com>, Darren New <dnew@san.rr.com> writes: > If you really want it to be foolproof, Yes please. ^ permalink raw reply [flat|nested] 116+ messages in thread
* Re: List container strawman 2001-11-04 19:40 ` Larry Kilgallen @ 2001-11-04 20:49 ` Darren New 2001-11-07 19:07 ` ramatthews 1 sibling, 0 replies; 116+ messages in thread From: Darren New @ 2001-11-04 20:49 UTC (permalink / raw) > > If you really want it to be foolproof, > Yes please. Well, yes. However, the performance overhead can be significant. There are ways of reducing it (see, for example, some of the fields in the private structures in my offering) but to be 100% bullet-proof, you'd at least need to have O(N) access times. Given user-programmable and multiple storage pools, this would be harder than in Pascal. The trick is to make it so you can turn it on and off at runtime, or for only a particular type of list (i.e., particular instantiations) so you can narrow down the problem. Actually, I never really thought of it with user-definable storage pools. There may be a much more efficient way of working it. A couple other points: 1) Does Ada even ensure there's only one default storage pool? I would think that perhaps the storage pool for Integers might be different than the storage pool for big records.... perhaps a different storage pool for each size item being stored or some such? Hence, I'm not surprised that it's difficult to find out what the "default" storage pool is. Or am I wrong in this? 2) Perhaps using terms from Unbounded_String might be wise? I.e., stuff that treats an unbounded string as an array of elements that happen to be characters rather than relying on the fact that they're characters. Ie., calling the routines Element(), Replace_Element(), Slice(), Overwrite(), Delete(), "*", etc? This isn't what I think of as the best naming convention, but it's at least going to be familiar to other Ada programmers. -- Darren New San Diego, CA, USA (PST). Cryptokeys on demand. Sore feet from standing in line at airport security checkpoints: Jet Leg. ^ permalink raw reply [flat|nested] 116+ messages in thread
* Re: List container strawman 2001-11-04 19:40 ` Larry Kilgallen 2001-11-04 20:49 ` Darren New @ 2001-11-07 19:07 ` ramatthews 2001-11-08 0:04 ` Darren New ` (2 more replies) 1 sibling, 3 replies; 116+ messages in thread From: ramatthews @ 2001-11-07 19:07 UTC (permalink / raw) In article <bgR13FMw5mIK@eisner.encompasserve.org>, Kilgallen@SpamCop.net (Larry Kilgallen) wrote: > In article <3BE58FDD.E1FB1815@san.rr.com>, Darren New <dnew@san.rr.com> writes: > >> If you really want it to be foolproof, > > Yes please. While I see a foolproof list does not have universal appeal I have been successfully using one for some time so I thought its specification would help discussions. Robert Matthews ----------------------------------------------------- with Ada.Finalization; with Ada.IO_Exceptions; with Ada.Streams; with Ada.Tags; generic type Data_Type (<>) is private; package Containers.Lists.Unbounded is -- This package provides facilities for manipulating simple list structures. -- -- A list is an ordered sequence of data elements. It can also be empty, -- containing no data elements. -- -- Client software creates an empty list by declaring a variable of type -- List_Type. Data elements can then be added to the list via the subprograms -- Prepend and Append. Note that data is copied into the list - pointers are not -- retained to the original data. -- -- All data elements can be removed from a list via subprogram Delete_All. -- Applying this subprogram to an already empty list will have no effect. -- -- When applied to an empty list, Is_Empty will return True, otherwise it will -- return False. -- -- A list can be assigned to another. The target list will be emptied then loaded with -- a copy of each data element in the source list. The copying will be done such that -- the ordering of the data elements in each list will be the same. -- Note that if the source list is empty, then the target will be set empty. -- -- Two lists can be compared for equality. To be equal they must have equal data elements -- at corresponding positions. Two empty lists are considered equal. -- -- The elements in a list can be accessed via an enumerator: the client software -- declares a variable of type Enumerator_Type which it then attaches to a list via -- the function New_Enumerator. -- -- At any one time an enumerator denotes a single element in its associated list. This -- element is termed the "current" element. Initially current will be set to the first -- element in the list; the following subprograms allow current to move to a different -- element: Goto_Next, Goto_Previous, Goto_First, Goto_Last. -- -- The following subprograms allow an enumerator's current element to be retrieved, -- changed, or deleted: Current, Update, Delete. Note that after Delete, current -- still denotes the same point in the list, even though the associated data -- element no longer exists. -- -- The subprogram Insert allows a new data element to be added to the list either -- before or after the current element. Note that if the list is empty then this -- subprogram will still insert the data even though current does not exist. -- Alternatively if current has been deleted then Insert will insert the data at -- the point in the list from which current was deleted. -- After the insertion, current will be set to the new data element. -- -- When current is at the start of a list, Is_First will return True, -- otherwise it will return False. -- When current is at the end of a list, Is_Last will return True, -- otherwise it will return False. -- -- If current exists Current_Exists will return True, otherwise it will return False -- (current will not exist if the element denoted by current has been deleted, or if -- the associated list is empty). -- -- If the list associated with an enumerator exists List_Exists will return True, otherwise -- it will return False (a list can cease to exist if the list's variable goes out of scope). -- -- An enumerator can be assigned to another enumerator. The target enumerator will then -- be associated with the same list and denote the same current element. Note that -- if the source enumerator's list and/or current do not exist then these characteristics -- will be transferred to the target enumerator. -- -- Two enumerators can be compared for equality. They must be associated with the same -- list and their current elements must be the same element. Note that two enumerators whose -- lists do not exist are deemed equal. Also two enumerators whose lists exist but whose current -- elements do not, are deemed equal if: -- 1) the lists are the same and empty; or -- 2) the lists are the same and non-empty, and each current denotes the same point in the list. -- -- Note that two or more enumerators can change the same list; changes made via one enumerator -- will be visible to the other enumerators. Similarly changes made directly to a list will be -- visible to its enumerators. However, concurrent access from more than one task is not supported; -- concurrent access may well lead to list and enumerator corruption. -- -- Note also that the storage associated with lists and enumerators is automatically deallocated -- when their variables go out of scope. -- -- Stream input/output can be used with lists via the stream oriented attributes List_Type'Write -- and List_Type'Read. -- For the Write attribute, each data element in the list is sent to the stream via -- Data_Type'Output. -- For the Read attribute, data elements are extracted from the stream (via Data_Type'Input) -- and inserted into the list. Note that any data elements previously in the list will be deleted. -- Note also that an empty list will be suitably flagged in the stream data, and so will be -- correctly handled when read back in. -- -- -- When applied to an empty list, the following will raise No_Data: -- Goto_First, Goto_Last, Goto_Next, Goto_Previous, Is_First, Is_Last. -- -- When current is the last data element in a list, Goto_Next will raise No_Data. -- When current is the first data element in a list, Goto_Previous will raise No_Data. -- -- When current does not exist, the following will raise No_Data: -- Delete, Current, Update. -- -- When an enumerator's list does not exist, the following will raise No_List: -- Insert, Delete, Current, Update, Goto_First, Goto_Last, Goto_Next, Goto_Previous, -- Is_First, Is_Last, Current_Exists, Is_Empty[Enumerator_Type]. -- -- When the stream I/O attributes are used, the following exceptions may be raised: -- Device_Error, Data_Error, Constraint_Error, Tag_Error, End_Error and Mode_Error. -- See the Ada Reference Manual for details. -- ------------------------------------------------------------------------------------------------ type List_Type is tagged private; type Enumerator_Type is private; -- Subprograms for directly dealing with lists... procedure Prepend (List : in out List_Type; Data : in Data_Type); -- Insert data at start of list. procedure Append (List : in out List_Type; Data : in Data_Type); -- Insert data at end of list. procedure Delete_All (List : in out List_Type); -- Delete all data from list. function Is_Empty (List : in List_Type) return Boolean; function "=" (Left : in List_Type; -- Check lists have equal. Right : in List_Type) return Boolean; -- elements at matching positions. function New_Enumerator (List : in List_Type'Class) return Enumerator_Type; -- Enumerator will denote the list and its current will be the first in the list. -- Note: can also assign list to list: target list will contain a copy of all the elements in the source -- list, with each element and its copy having the same position in their respective lists. ---------------------------------------------------------------------- -- Subprograms for dealing with the current element of an enumerator... type Position_Type is (Before_Current, After_Current); procedure Insert (Enumerator : in out Enumerator_Type; Data : in Data_Type; Position : in Position_Type); procedure Delete (Enumerator : in Enumerator_Type); function Current (Enumerator : in Enumerator_Type) return Data_Type; procedure Update (Enumerator : in out Enumerator_Type; Data : in Data_Type); -- Update current element. -- Note that if new data is larger, then new data will be loaded into a new element that replaces -- the old in the list. The location in the list will not have changed but current will now denote -- that new data element - hence the in out mode. procedure Goto_First (Enumerator : in out Enumerator_Type); procedure Goto_Last (Enumerator : in out Enumerator_Type); procedure Goto_Next (Enumerator : in out Enumerator_Type); procedure Goto_Previous (Enumerator : in out Enumerator_Type); function Is_First (Enumerator : in Enumerator_Type) return Boolean; function Is_Last (Enumerator : in Enumerator_Type) return Boolean; function Current_Exists (Enumerator : in Enumerator_Type) return Boolean; function List_Exists (Enumerator : in Enumerator_Type) return Boolean; function Is_Empty (Enumerator : in Enumerator_Type) return Boolean; -- Is the associated list empty. function "=" (Left : in Enumerator_Type; Right : in Enumerator_Type) return Boolean; -- Note: can also assign enumerator to enumerator: target will denote same list -- and have same current as source. -------------------------------------------------------- -- The subprograms can raise the following exceptions: No_Data : exception; No_List : exception; -- And for stream I/O... Device_Error : exception renames Ada.IO_Exceptions.Device_Error; Data_Error : exception renames Ada.IO_Exceptions.Data_Error; End_Error : exception renames Ada.IO_Exceptions.End_Error; Mode_Error : exception renames Ada.IO_Exceptions.Mode_Error; Tag_Error : exception renames Ada.Tags.Tag_Error; -- Also Constraint_Error may be raised. --------------------------------------------------- private type Data_Access_Type is access Data_Type; type Data_Envelope_Type; type Data_Envelope_Access_Type is access Data_Envelope_Type; type Enumerator_Envelope_Type; type Enumerator_Envelope_Access_Type is access Enumerator_Envelope_Type; type List_Header_Type; type List_Header_Access_Type is access List_Header_Type; type Data_Envelope_Type is record Data : Data_Access_Type; Next : Data_Envelope_Access_Type; Previous : Data_Envelope_Access_Type; end record; type List_Header_Type is record First : Data_Envelope_Access_Type; Last : Data_Envelope_Access_Type; Enumerators : Enumerator_Envelope_Access_Type; -- Sub-list of enumerators attached to this List. end record; type List_Type is new Ada.Finalization.Controlled with record Header : List_Header_Access_Type; end record; procedure Initialize (List : in out List_Type); procedure Adjust (List : in out List_Type); procedure Finalize (List : in out List_Type); procedure List_Write (Stream : access Ada.Streams.Root_Stream_Type'Class; Item : in List_Type); for List_Type'Write use List_Write; procedure List_Read (Stream : access Ada.Streams.Root_Stream_Type'Class; Item : out List_Type); for List_Type'Read use List_Read; type Enumerator_Envelope_Type is record List_Header : List_Header_Access_Type; -- List that Enumerator applies to. Current : Data_Envelope_Access_Type; -- List element that Enumerator denotes. Next_Enumerator : Enumerator_Envelope_Access_Type; -- Enumerators are linked in their own sub-list, Previous_Enumerator : Enumerator_Envelope_Access_Type; -- within the relevant List. Next_Data : Data_Envelope_Access_Type; -- List element that follows current. Previous_Data : Data_Envelope_Access_Type; -- List element that precedes current. end record; -- Note that in the above record, components Next_Data and Previous_Data duplicate the Next and Previous -- components of the record referenced by Current. This duplication is necessary for the case when Current -- is Null (ie. the corresponding data element has been deleted), Next_Data and Previous_Data then indicate -- where in the list the enumerator is. type Enumerator_Type is new Ada.Finalization.Controlled with record Header : Enumerator_Envelope_Access_Type; end record; procedure Initialize (Enumerator : in out Enumerator_Type); procedure Adjust (Enumerator : in out Enumerator_Type); procedure Finalize (Enumerator : in out Enumerator_Type); end Containers.Lists.Unbounded; ------------------------------------------------------------- ^ permalink raw reply [flat|nested] 116+ messages in thread
* Re: List container strawman 2001-11-07 19:07 ` ramatthews @ 2001-11-08 0:04 ` Darren New 2001-11-08 4:50 ` Jeffrey Carter 2001-11-09 18:00 ` Ted Dennison 2 siblings, 0 replies; 116+ messages in thread From: Darren New @ 2001-11-08 0:04 UTC (permalink / raw) ramatthews@tinuviel.com wrote: > While I see a foolproof list does not have universal appeal I have > been successfully using one for some time so I thought its > specification would help discussions. Heh. This looks almost exactly like what I came up with and posted earlier. :-) Except you've actually written it. ;-) -- Darren New San Diego, CA, USA (PST). Cryptokeys on demand. Sore feet from standing in line at airport security checkpoints: Jet Leg. ^ permalink raw reply [flat|nested] 116+ messages in thread
* Re: List container strawman 2001-11-07 19:07 ` ramatthews 2001-11-08 0:04 ` Darren New @ 2001-11-08 4:50 ` Jeffrey Carter 2001-11-08 23:26 ` ramatthews 2001-11-09 18:00 ` Ted Dennison 2 siblings, 1 reply; 116+ messages in thread From: Jeffrey Carter @ 2001-11-08 4:50 UTC (permalink / raw) ramatthews@tinuviel.com wrote: > > While I see a foolproof list does not have universal appeal I have > been successfully using one for some time so I thought its > specification would help discussions. How does this extra complexity ensure that the list is foolproof? It is not clear, for example, how this prevents updating a node through one Position (which you call Enumerator_Type) that has been deleted through another. The initial block of comments is rather a lot to digest all at once, and might be better distributed among the type and subprogram declarations it refers to. The use of "current" by itself is a bit confusing; it sounds as if it is a global property of a list, when actually it is a property of a position within a list. Overall, the package looks quite usable. I might suggest a default of Before_Current in the Insert procedure. -- Jeff Carter "Sons of a silly person." Monty Python & the Holy Grail ^ permalink raw reply [flat|nested] 116+ messages in thread
* Re: List container strawman 2001-11-08 4:50 ` Jeffrey Carter @ 2001-11-08 23:26 ` ramatthews 0 siblings, 0 replies; 116+ messages in thread From: ramatthews @ 2001-11-08 23:26 UTC (permalink / raw) In article <3BEA0F08.AD9AB7C1@acm.org>, Jeffrey Carter <jrcarter@acm.org> wrote: > > How does this extra complexity ensure that the list is foolproof? It is > not clear, for example, how this prevents updating a node through one > Position (which you call Enumerator_Type) that has been deleted through > another. > > If two Positions (of Enumerator_Type) are denoting the same element in a list and one is used to delete the element then BOTH will return False to 'Current_Exists' and BOTH will raise 'No_Data' on using 'Update'. This is ensured by the (behind the scenes) two-way linkage between the list and all of its Positions. As an aside, if I were re-implementing this I would use the term 'Cursor' in place of 'Enumerator' - but then arguments over names can go on for ever! Robert Matthews. ^ permalink raw reply [flat|nested] 116+ messages in thread
* Re: List container strawman 2001-11-07 19:07 ` ramatthews 2001-11-08 0:04 ` Darren New 2001-11-08 4:50 ` Jeffrey Carter @ 2001-11-09 18:00 ` Ted Dennison 2001-11-09 18:13 ` Jean-Marc Bourguet ` (3 more replies) 2 siblings, 4 replies; 116+ messages in thread From: Ted Dennison @ 2001-11-09 18:00 UTC (permalink / raw) In article <po0cs9.dt.ln@127.0.0.1>, ramatthews@tinuviel.com says... > >In article <bgR13FMw5mIK@eisner.encompasserve.org>, Kilgallen@SpamCop.net (Larry Kilgallen) wrote: >> In article <3BE58FDD.E1FB1815@san.rr.com>, Darren New <dnew@san.rr.com> writes: >> >>> If you really want it to be foolproof, >> >> Yes please. > > >While I see a foolproof list does not have universal appeal I have >been successfully using one for some time so I thought its >specification would help discussions. Yup. That does exactly what is needed to make it safe. I never said it was impossible, just that its a lot of work, inculding some extra runtime work that might not endear the facility to real-time users. One problem is that creating an iterator with this facility involves dynamic allocation and linked-list traversal. That violates our general principle of avoiding runtime vs. setup overhead, but that could probably(?) be fixed or at least avoided by the user if noted. Another issue is that it puts a controlled type in the generic package, which I was trying to avoid so that it was instantiateable at lower levels. However, it turned out that List has to be controlled anyway, so perahps this isn't so bad. I'm interested in what the general consensus is here. Should we do the extra work to make iterators safe, given that this will have at least the following effects: o Add extra dynamic memory operations to any list modification (there were some there already). o Add a (usually small) internal list traversal to any element deletion. o Add a small validity check (or possibly two) to every iterator operation. o Possibly make iterator creation non-determistic (time-wise). o Possibly make iterator assignment non-deterministic. Note that functions are currently used for iterating, so that would make just about any use of iterators non-determinstic, unless procedure variants are introduced. If there's a way to get rid of the last two "possibly"s (which there probably is, but I don't know), I think I'd vote in favor of it. Otherwise I'd lean against it just on the basis that I don't generaly go for one small "nice-to-have" feature accounting for large amounts of the implmentation's code and complexity, which is what would happen here. --- T.E.D. homepage - http://www.telepath.com/dennison/Ted/TED.html No trees were killed in the sending of this message. However a large number of electrons were terribly inconvenienced. ^ permalink raw reply [flat|nested] 116+ messages in thread
* Re: List container strawman 2001-11-09 18:00 ` Ted Dennison @ 2001-11-09 18:13 ` Jean-Marc Bourguet 2001-11-09 18:55 ` Ted Dennison 2001-11-09 19:27 ` Larry Kilgallen ` (2 subsequent siblings) 3 siblings, 1 reply; 116+ messages in thread From: Jean-Marc Bourguet @ 2001-11-09 18:13 UTC (permalink / raw) Ted Dennison<dennison@telepath.com> writes: > In article <po0cs9.dt.ln@127.0.0.1>, ramatthews@tinuviel.com says... > > In article <bgR13FMw5mIK@eisner.encompasserve.org>, Kilgallen@SpamCop.net > >(Larry Kilgallen) wrote: > >> In article <3BE58FDD.E1FB1815@san.rr.com>, Darren New <dnew@san.rr.com> > >>writes: > >> > >>> If you really want it to be foolproof, > >> Yes please. > > > > > >While I see a foolproof list does not have universal appeal I have been > >successfully using one for some time so I thought its specification would > >help discussions. > > Yup. That does exactly what is needed to make it safe. I never said it was > impossible, just that its a lot of work, inculding some extra runtime work > that might not endear the facility to real-time users. One problem is that > creating an iterator with this facility involves dynamic allocation and > linked-list traversal. Why do you need dynamic allocation. The pointer can be in the iterator and put at the start of the list. As most lists have few iterators and when they have more than one, a majority of the uses are nested the list traversal will be done only on list modifications. > That violates our general principle of avoiding > runtime vs. setup overhead, but that could probably(?) be fixed or at least > avoided by the user if noted. Another issue is that it puts a controlled > type in the generic package, which I was trying to avoid so that it was > instantiateable at lower levels. However, it turned out that List has to > be controlled anyway, so perahps this isn't so bad. > > I'm interested in what the general consensus is here. Should we do the > extra work to make iterators safe, given that this will have at least the > following effects: I'm for. > o Add extra dynamic memory operations to any list modification (there were > some there already). I don't think so. > o Add a (usually small) internal list traversal to any element > deletion. Agree. > o Add a small validity check (or possibly two) to every iterator > operation. Agree. > o Possibly make iterator creation non-determistic (time-wise). I don't think so. (Iterator deletion would be made non deterministic if they are assigned in a non nested way and the iterator list is a singly linked one). > o Possibly make iterator assignment non-deterministic. Not if the iterator list is doubly linked. -- Jean-Marc ^ permalink raw reply [flat|nested] 116+ messages in thread
* Re: List container strawman 2001-11-09 18:13 ` Jean-Marc Bourguet @ 2001-11-09 18:55 ` Ted Dennison 2001-11-10 1:48 ` Nick Roberts 0 siblings, 1 reply; 116+ messages in thread From: Ted Dennison @ 2001-11-09 18:55 UTC (permalink / raw) In article <3bec1cbe$0$15824$626a54ce@news.free.fr>, Jean-Marc Bourguet says... > >Ted Dennison<dennison@telepath.com> writes: > >Why do you need dynamic allocation. The pointer can be in the The implementation he presented (a working one, I believe) had it. Since I've only thought about it before, and he's actually implemented it, I'm assuming there's some implementation reason he needed to do it that way that isn't apparent just looking at a spec. Perhaps there isn't. That's what I'd like to hear. >> o Add extra dynamic memory operations to any list modification (there were >> some there already). > >I don't think so. Hmmm. Yeah, your'e right. Its actually another one of those "ususally small" internal list traversals. What will happen is that you have to check all other iterators. But that's probably only nessecary when an item is deleted, which I covered below. >> o Add a (usually small) internal list traversal to any element >> deletion. > >Agree. > >> o Add a small validity check (or possibly two) to every iterator >> operation. > >Agree. > >> o Possibly make iterator creation non-determistic (time-wise). > >I don't think so. (Iterator deletion would be made non deterministic >if they are assigned in a non nested way and the iterator list is a >singly linked one). I said "probably" this for both the last bulletts because he implemented iterators using accesses to controlled types. If it can be done on the stack, then both these "possibly"s go away (and I would thus vote for it). Perhaps it would be best if I could play with an implementation and see if its doable. That would mean I'd have to tear myself away from Civ3 for a few hours though... --- T.E.D. homepage - http://www.telepath.com/dennison/Ted/TED.html No trees were killed in the sending of this message. However a large number of electrons were terribly inconvenienced. ^ permalink raw reply [flat|nested] 116+ messages in thread
* Re: List container strawman 2001-11-09 18:55 ` Ted Dennison @ 2001-11-10 1:48 ` Nick Roberts 2001-11-10 17:04 ` Ted Dennison 2001-11-10 19:36 ` Ehud Lamm 0 siblings, 2 replies; 116+ messages in thread From: Nick Roberts @ 2001-11-10 1:48 UTC (permalink / raw) I'm sorry, I'm throw one of classic spanners in the works here, but I'm afraid I think you've got your approach horribly horribly wrong! For a start, all this mularchy about insertion and deletion is just plain silly! It really is. You don't need them, and shouldn't implement them. Yes, really. Let me show you why. Suppose you want to have a list of names (strings), and you want to normalise them as follows: (a) convert them all to uppercase; (b) all beginning with "MACxy", where x is a letter, to have "MCxy" inserted afterwards; (c) all beginning with "?" to be deleted. I'm going to frame the answer in terms of my own proposal, please forgive me for that. The essential answer is that you don't keep a list of the strings, but you keep a list of access values to them. You then simply build a new list (of access values), and then delete the old one: with Ada.Characters.Handling; use Ada.Characters.Handling; ... type Name_Ref is access [all] String; package Name_Ref_Iteration is new Iteration(Name_Ref); procedure Normalize_Names ( From: in out Name_Ref_Iteration.Sequence_Recorder'Class; Into: Name_Ref_Iteration.Sequence_Recorder'Class) is Ref: Name_Ref; N: Natural; begin Rewrite(Into); -- possibly redundant (possibly poor design, actually) Restart(From); -- ditto while not End_of_Data(From) loop Read(From,Ref); if Ref /= null and then Ref.all'Length > 0 and then Ref(Ref.all'First) /= '?' then To_Upper(Ref.all); Write(Into,Ref); N := Ref.all.First-1; -- in case string doesn't start at 1 if Ref.all'Length >= 5 and then Ref(N+1..N+3) = "MAC" and then Is_Letter(Ref(N+4)) then Write(Into, new String'("MC"&Ref(N+4..Ref.all'Last))); end if; else Ref := null; -- or maybe use Unchecked_Deallocation end if; end loop; Rewrite(From); -- erases it (again, possibly wrong here) Restart(Into); -- again possibly redundant end Normalize_Names; Note how this procedure can be passed parameters of ANY 'sequence recorder' container type (instantiated on Name_Ref), not just lists. Supposing we wanted to use a list container type: package Name_Ref_Lists is new xyz.Lists(Name_Ref_Iteration); subtype Name_List is Name_Ref_Lists.List_Type; L1, L2: Name_List; ... set up L1 with names Normalize_Names(L1,L2); A note about the Restarts and Rewrites: they are probably better left outside procedures such as this, in fact. I have quietly deleted oddities like null pointers: a real program should probably raise exceptions. Trust me, guys, this approach is majorly better in every way (easier to use, easier to read & understand, easier to implement, more memory efficient, more speed efficient) than messing around with inserts and deletes, for the vast majority of situations. I know I can seem pompous, overbearing, etc., etc., especially about this subject, but it pains me to see you going so far astray, and spending so much time arguing about features that you don't need anyway! It also gives me another opportunity to demonstrate the idea of having a set of abstract container types, upon which operations (such as Normalize_Names) can be hung, thus freeing you of: (1) having to worry about which container type to use when writing the procedure; (2) the procedure shackling you to one particular container type. Do you turn away from this Utopia? ;-) -- Best wishes, Nick Roberts ^ permalink raw reply [flat|nested] 116+ messages in thread
* Re: List container strawman 2001-11-10 1:48 ` Nick Roberts @ 2001-11-10 17:04 ` Ted Dennison 2001-11-10 20:59 ` Nick Roberts 2001-11-10 19:36 ` Ehud Lamm 1 sibling, 1 reply; 116+ messages in thread From: Ted Dennison @ 2001-11-10 17:04 UTC (permalink / raw) In article <9sib27$13aeg3$5@ID-25716.news.dfncis.de>, Nick Roberts says... >For a start, all this mularchy about insertion and deletion is just plain >silly! It really is. You don't need them, and shouldn't implement them. Yes, >really. Let me show you why. I'm not sure I understand this. It looks like you are talking about having the users manage the internal details of all their own data structures, to which my first reaction would be "ewwwww.". I'll admit there may be some interesting possiblities I don't see in this though. >It also gives me another opportunity to demonstrate the idea of having a set >of abstract container types, upon which operations (such as Normalize_Names) >can be hung, thus freeing you of: (1) having to worry about which container >type to use when writing the procedure; (2) the procedure shackling you to >one particular container type. Do you turn away from this Utopia? ;-) But remember that one of our stipulations is essentially "no multilevel generic instantiations required". Does this work that way? Without that restriction you could do all sorts of cool things, as has been done in Booch and others. In that enviroment I'd say that we already have plenty of players, and one of them is liable to be perfectly suitable (although I suppose more are always welcome). I don't want to discourage you from making the ultimate container library. But for the purposes of what we are doing here it has to be very easy to use, and frankly I couldn't figure out quite what was going on in the code you presented. --- T.E.D. homepage - http://www.telepath.com/dennison/Ted/TED.html No trees were killed in the sending of this message. However a large number of electrons were terribly inconvenienced. ^ permalink raw reply [flat|nested] 116+ messages in thread
* Re: List container strawman 2001-11-10 17:04 ` Ted Dennison @ 2001-11-10 20:59 ` Nick Roberts 2001-11-10 23:17 ` Larry Hazel 0 siblings, 1 reply; 116+ messages in thread From: Nick Roberts @ 2001-11-10 20:59 UTC (permalink / raw) "Ted Dennison" <dennison@telepath.com> wrote in message news:L6dH7.20105$xS6.32596@www.newsranger.com... > In article <9sib27$13aeg3$5@ID-25716.news.dfncis.de>, Nick Roberts says... > >For a start, all this mularchy about insertion and deletion is just plain > >silly! It really is. You don't need them, and shouldn't implement them. Yes, > >really. Let me show you why. > > I'm not sure I understand this. It looks like you are talking about having the > users manage the internal details of all their own data structures, to which my > first reaction would be "ewwwww.". I'll admit there may be some interesting > possiblities I don't see in this though. In general, of course, you want to hide details such as pointers. But don't get carried away! Sometimes the application programmer has got to deal with things like pointers. In the example I gave, the fact that the list container was used to (explicitly) contain pointers is likely to actually have many advantages for the application programmer: other manipulations of the data - not involving containers - can also be carried out more efficiently (and sometimes more conveniently) using those same pointers. > >It also gives me another opportunity to demonstrate the idea of having a set > >of abstract container types, upon which operations (such as Normalize_Names) > >can be hung, thus freeing you of: (1) having to worry about which container > >type to use when writing the procedure; (2) the procedure shackling you to > >one particular container type. Do you turn away from this Utopia? ;-) > > But remember that one of our stipulations is essentially "no multilevel generic > instantiations required". Does this work that way? Without that restriction you > could do all sorts of cool things, as has been done in Booch and others. In that > enviroment I'd say that we already have plenty of players, and one of them is > liable to be perfectly suitable (although I suppose more are always welcome). I > don't want to discourage you from making the ultimate container library. But for > the purposes of what we are doing here it has to be very easy to use, and > frankly I couldn't figure out quite what was going on in the code you presented. I'm not quite trying to make 'the ultimate library' ;-) but I suppose I am aiming at something that would be useful for 'real' programming, rather than just for students and demos. Ada is not a toy language, it's not a Pascal or BASIC, it's an industrial language intended for building real, big software. Honestly, I think it's a mistake to try to defend students (or anyone else) from this fact. When we make a wooden box for the first time in kindergarten we use one nail per joint. As grown ups, when we make a box for some real purpose, we use two nails per joint. When making toy programs at university we may have used one instantiation per data type; but when as professionals we start writing real software, we use two instantiations per data type! (It's all a part of the maturing process ;-) At the end of the day, a box that falls to pieces (because you only used one nail) doesn't make life easier for anyone. As I say in my reply to Ehud, I really believe this is a situation where trying to make things easier for the user will end up making things much harder for them. To me, you really seem to be saying something like "Oh, there shouldn't be any safety catches on guns: it makes them too complicated for the user! Our guns have just the trigger and nothing else." It may sound nice, but you are inevitably going to cause of lot of users to end up shooting themselves (in the foot, or worse :-) I hope you'll forgive me if I re-post the code I gave, corrected and cleaned up a little, and with a blow-by-blow commentary on what's going on. with Ada.Characters.Handling; use Ada.Characters.Handling; This is to conveniently obtain some character-handling functions provided by Ada. type Name_Ref is access [all] String; Here we declare the access type that is going to be the 'data type' stored by containers. package Name_Ref_Iteration is new Iteration(Name_Ref); This instantiates the package of abstract container types (including Sequence_Recorder), so that they are specialised for Name_Refs (but they are still abstract). procedure Normalize_Names ( Source: in out Name_Ref_Iteration.Sequence_Recorder'Class; Target: in out Name_Ref_Iteration.Sequence_Recorder'Class) is Source and Target are both in the class of the abstract container type Sequence_Recorder. This means that the corresponding actuals, when the procedure is called, must be (concrete types) derived from Sequence_Recorder, and therefore that they must, at the very least, implement the procedures Read, Restart, Rewrite, and Write, and the function End_of_Data. Ref: Name_Ref; N: Natural; Just a couple of temporary variables. begin while not End_of_Data(Source) loop We will iterate over the elements (name pointers, of type Name_Ref) in the Source container. Read(Source,Ref); We read one reference in from the Source container. This is a dispatching call: the correct Read for the actual container will be called. if Ref /= null and then Ref.all'Length > 0 and then Ref(Ref.all'First) /= '?' then This just checks various conditions to ensure the name pointer (in Ref) is usable, and not to be deleted (indicated by the leading '?'). To_Upper(Ref.all); Convert the string (pointed to by the pointer in Ref) to uppercase. Write(Target,Ref); Write the pointer into the Target container. Again, this is a dispatching call. N := Ref.all.First-1; -- in case string doesn't start at 1 if Ref.all'Length >= 5 and then Ref(N+1..N+3) = "MAC" and then Is_Letter(Ref(N+4)) then Write(Target, new String'("MC"&Ref(N+4..Ref.all'Last))); end if; This is just a bit of messing about with the Macs. The important thing to note is that another Write may be performed, thus achieving the effect of insertion. else Ref := null; -- or maybe use Unchecked_Deallocation The effect of deletion is achieved by simply not writing the pointer into Target. end if; end loop; end Normalize_Names; The usage of this procedure, in conjunction with a (concrete) list container type (which we assume is derived from Sequence_Recorder), might be: package Name_Ref_Lists is new SCL.Lists.Unbounded(Name_Ref_Iteration); Now we instantiate the package that will export a list type for use (List_Type) wich is specialised for name pointers (type Name_Ref). subtype Name_List is Name_Ref_Lists.List_Type; This just conveniently renames the exported list type. L1, L2: Name_List; Here we declare two list variables. ... set up L1 with names We will do something (not shown, but e.g. read a file) to read the names, and put the pointers to them into L1. Rewrite(L2); This prepares (and erases, if necessary) L2 for being written into. Restart(L1); This prepares (and rewinds to the start, if necessary) L1 for being read from. Normalize_Names(L1,L2); We call the procedure. The actuals, L1 and L2, could have been of any container type (provided they were both derived from Sequence_Recorder). In this case, they happen to both be lists. Rewrite(L1); This is just a simple way to erase L1. Restart(L2); Get L2 ready to be read, for the next step in the overall processing (whatever that might be). I really hope this helps clarify things. The vital point is that the procedure Normalize_Names can be used with any container type (derived from Sequence_Recorder), rather than being permanently tied down to one container type. -- Best wishes, Nick Roberts ^ permalink raw reply [flat|nested] 116+ messages in thread
* Re: List container strawman 2001-11-10 20:59 ` Nick Roberts @ 2001-11-10 23:17 ` Larry Hazel 2001-11-11 3:27 ` Nick Roberts 0 siblings, 1 reply; 116+ messages in thread From: Larry Hazel @ 2001-11-10 23:17 UTC (permalink / raw) Nick Roberts wrote: > > I hope you'll forgive me if I re-post the code I gave, corrected and cleaned > up a little, and with a blow-by-blow commentary on what's going on. > This mostly looks very good to me except it seems terribly inefficient to have to copy the whole list into a new list then delete the old list if all I need to do is modify a few entries, delete a few others and insert a few. Seems as if we still need methods to delete, update, and insert elements. Larry ^ permalink raw reply [flat|nested] 116+ messages in thread
* Re: List container strawman 2001-11-10 23:17 ` Larry Hazel @ 2001-11-11 3:27 ` Nick Roberts 2001-11-12 18:39 ` Darren New 0 siblings, 1 reply; 116+ messages in thread From: Nick Roberts @ 2001-11-11 3:27 UTC (permalink / raw) "Larry Hazel" <lhhazel@otelco.net> wrote in message news:3BEDB57E.1203D638@otelco.net... > Nick Roberts wrote: > > > > I hope you'll forgive me if I re-post the code I gave, corrected and cleaned > > up a little, and with a blow-by-blow commentary on what's going on. > > > This mostly looks very good to me except it seems terribly inefficient to have > to copy the whole list into a new list then delete the old list if all I need to > do is modify a few entries, delete a few others and insert a few. Seems as if > we still need methods to delete, update, and insert elements. In fact, I completely agree with you. It was extremely clumsy of me to simply say "you don't need inserts or delete". You do. What you don't need is insert or delete in association with an iterator (or a separate iterator type at all). All you need are straightforward insert and delete functions and procedures that identify the position of insertion or deletion with a number (type Positive), starting at 1 for the first item in the list. Detail: A container object would have three modes: seq read; seq write; normal. Calling Read or End_of_Data other than in seq read mode, or calling Write or Terminate_Data other than in seq write mode, would raise an exception (SCL.Exceptions.Mode_Error). Restart causes a switch to seq read mode. Rewrite causes a switch to seq write mode. Any other operation when not in normal mode causes a switch to normal mode. This way, non-sequential modification cannot interfere with iteration. Simple. Doing the equivalent of what my example procedure Normalize_Names did using inserts and deletes with an iterator would have ended up with code that was more difficult to program, more difficult to read, slower in execution, and (I think) more wasteful of memory. Showing this was the true purpose of my example. Admittedly, I really need to add more detail, but it's finding the time :-( -- Best wishes, Nick Roberts ^ permalink raw reply [flat|nested] 116+ messages in thread
* Re: List container strawman 2001-11-11 3:27 ` Nick Roberts @ 2001-11-12 18:39 ` Darren New 2001-11-13 0:35 ` Nick Roberts 0 siblings, 1 reply; 116+ messages in thread From: Darren New @ 2001-11-12 18:39 UTC (permalink / raw) Nick Roberts wrote: > Doing the equivalent of what my example procedure Normalize_Names did using > inserts and deletes with an iterator would have ended up with code that was > more difficult to program, more difficult to read, slower in execution, and > (I think) more wasteful of memory. Showing this was the true purpose of my > example. Admittedly, I really need to add more detail, but it's finding the > time :-( Using sequences like this when the problem is expressed in terms of a loop over all elements makes sense. Using sequences when the problem is expressed in other forms may not. If your list is a list of characters that you're trying to parse, for example, matching up parens or doing reg-exp sorts of stuff (yes, I know you'd use strings) then only doing reads *or* writes, only going in one direction doesn't make good sense. If you have an ordered list and you want to insert an element in the right place, copying the entire list to do so isn't very efficient. -- Darren New San Diego, CA, USA (PST). Cryptokeys on demand. You will soon read a generic fortune cookie. ^ permalink raw reply [flat|nested] 116+ messages in thread
* Re: List container strawman 2001-11-12 18:39 ` Darren New @ 2001-11-13 0:35 ` Nick Roberts 0 siblings, 0 replies; 116+ messages in thread From: Nick Roberts @ 2001-11-13 0:35 UTC (permalink / raw) "Darren New" <dnew@san.rr.com> wrote in message news:3BF01760.A21F56B3@san.rr.com... > Nick Roberts wrote: > > Doing the equivalent of what my example procedure Normalize_Names did using > > inserts and deletes with an iterator would have ended up with code that was > > more difficult to program, more difficult to read, slower in execution, and > > (I think) more wasteful of memory. Showing this was the true purpose of my > > example. Admittedly, I really need to add more detail, but it's finding the > > time :-( > > Using sequences like this when the problem is expressed in terms of a > loop over all elements makes sense. Using sequences when the problem is > expressed in other forms may not. If your list is a list of characters > that you're trying to parse, for example, matching up parens or doing > reg-exp sorts of stuff (yes, I know you'd use strings) then only doing > reads *or* writes, only going in one direction doesn't make good sense. > If you have an ordered list and you want to insert an element in the > right place, copying the entire list to do so isn't very efficient. In essence, I agree, and I've devised a new proposal with bi-directional cursor operations. Hopefully I'll have this ready to send to Ted Dennison in a couple of days time, for him to kindly put on his web site. -- Best wishes, Nick Roberts ^ permalink raw reply [flat|nested] 116+ messages in thread
* Re: List container strawman 2001-11-10 1:48 ` Nick Roberts 2001-11-10 17:04 ` Ted Dennison @ 2001-11-10 19:36 ` Ehud Lamm 2001-11-10 20:15 ` Nick Roberts 1 sibling, 1 reply; 116+ messages in thread From: Ehud Lamm @ 2001-11-10 19:36 UTC (permalink / raw) Nick Roberts <nickroberts@adaos.worldonline.co.uk> wrote in message news:9sib27$13aeg3$5@ID-25716.news.dfncis.de... > > It also gives me another opportunity to demonstrate the idea of having a set > of abstract container types, upon which operations (such as Normalize_Names) > can be hung, thus freeing you of: (1) having to worry about which container > type to use when writing the procedure; (2) the procedure shackling you to > one particular container type. Do you turn away from this Utopia? ;-) These goal are vrey worthy. In fact they are one of the reasons people want inheritance. Problem is that we are looking for a way of achieving these goal, without making newcomers struggle with nested instatiations, and complexities of the Ada tagged type approach (freezing, scope of access types etc. etc.) Perhaps I missed the point - but does your approach solve the dillema? Ehud ^ permalink raw reply [flat|nested] 116+ messages in thread
* Re: List container strawman 2001-11-10 19:36 ` Ehud Lamm @ 2001-11-10 20:15 ` Nick Roberts 0 siblings, 0 replies; 116+ messages in thread From: Nick Roberts @ 2001-11-10 20:15 UTC (permalink / raw) "Ehud Lamm" <mslamm@mscc.huji.ac.il> wrote in message news:9sjvrl$2pd$1@news.huji.ac.il... > ... > These goal are vrey worthy. In fact they are one of the reasons people want > inheritance. > Problem is that we are looking for a way of achieving these goal, without > making newcomers struggle with nested instatiations, and complexities of the > Ada tagged type approach (freezing, scope of access types etc. etc.) > Perhaps I missed the point - but does your approach solve the dillema? I thought we were agreed that there was no way to achieve the goals (of decoupling) without the multiple instantiations. In any case, I believe that is so, and I suppose I am trying to convince people that it's (very much!) the lesser of two evils to have the multiple instantiations and the decoupling. I really think this is a case where the apparently easier way is in fact the harder one. -- Best wishes, Nick Roberts ^ permalink raw reply [flat|nested] 116+ messages in thread
* Re: List container strawman 2001-11-09 18:00 ` Ted Dennison 2001-11-09 18:13 ` Jean-Marc Bourguet @ 2001-11-09 19:27 ` Larry Kilgallen 2001-11-09 20:03 ` Stephen Leake 2001-11-10 20:24 ` ramatthews 3 siblings, 0 replies; 116+ messages in thread From: Larry Kilgallen @ 2001-11-09 19:27 UTC (permalink / raw) In article <DQUG7.19137$xS6.31310@www.newsranger.com>, Ted Dennison<dennison@telepath.com> writes: > I'm interested in what the general consensus is here. Should we do the extra > work to make iterators safe, given that this will have at least the following > effects: For my world, I favor safety over efficiency. I have already decided not to use assembly language, and despite a lack of demand from me, "they" keep making the computers faster. I understand that some might have use for a more efficient package, but I believe the one promulgated to the masses should be the one with maximum error detection. ^ permalink raw reply [flat|nested] 116+ messages in thread
* Re: List container strawman 2001-11-09 18:00 ` Ted Dennison 2001-11-09 18:13 ` Jean-Marc Bourguet 2001-11-09 19:27 ` Larry Kilgallen @ 2001-11-09 20:03 ` Stephen Leake 2001-11-09 21:05 ` Ted Dennison 2001-11-09 22:42 ` Larry Kilgallen 2001-11-10 20:24 ` ramatthews 3 siblings, 2 replies; 116+ messages in thread From: Stephen Leake @ 2001-11-09 20:03 UTC (permalink / raw) Ted Dennison<dennison@telepath.com> writes: I vote for having a truly safe list implementation, like this one, if only for reference. I vote for also having an Unchecked_List package, so we can use it in higher-level abstractions that add safety in different ways. That way, when someone says "why isn't this list package _safe_? I thought Ada was a _safe_ language!", we can say "look at the safe list package; it has too much overhead for _this_ use, but it's available if you want it". It might also inspire some grad student to make a version with less overhead, or a compiler optimization that removes the overhead, or something. -- -- Stephe ^ permalink raw reply [flat|nested] 116+ messages in thread
* Re: List container strawman 2001-11-09 20:03 ` Stephen Leake @ 2001-11-09 21:05 ` Ted Dennison 2001-11-09 22:42 ` Larry Kilgallen 1 sibling, 0 replies; 116+ messages in thread From: Ted Dennison @ 2001-11-09 21:05 UTC (permalink / raw) In article <u7kszpv8k.fsf@gsfc.nasa.gov>, Stephen Leake says... > >Ted Dennison<dennison@telepath.com> writes: > >I vote for having a truly safe list implementation, like this one, if .. Just to make things perfectly clear, these are Stephen's words, not mine. I'm sure he wasn't confused about this, but someone else might be. :-) --- T.E.D. homepage - http://www.telepath.com/dennison/Ted/TED.html No trees were killed in the sending of this message. However a large number of electrons were terribly inconvenienced. ^ permalink raw reply [flat|nested] 116+ messages in thread
* Re: List container strawman 2001-11-09 20:03 ` Stephen Leake 2001-11-09 21:05 ` Ted Dennison @ 2001-11-09 22:42 ` Larry Kilgallen 2001-11-10 4:52 ` Nick Roberts 1 sibling, 1 reply; 116+ messages in thread From: Larry Kilgallen @ 2001-11-09 22:42 UTC (permalink / raw) In article <u7kszpv8k.fsf@gsfc.nasa.gov>, Stephen Leake <stephen.a.leake.1@gsfc.nasa.gov> writes: > Ted Dennison<dennison@telepath.com> writes: > > I vote for having a truly safe list implementation, like this one, if > only for reference. I vote for also having an Unchecked_List package, > so we can use it in higher-level abstractions that add safety in > different ways. > > That way, when someone says "why isn't this list package _safe_? I > thought Ada was a _safe_ language!", we can say "look at the safe list > package; it has too much overhead for _this_ use, but it's available > if you want it". Then how about naming the packages Safe_List and Unchecked_List ? Is it possible for them to have the same profile, allowing people to switch easily if they change their mind or need to debug ? ^ permalink raw reply [flat|nested] 116+ messages in thread
* Re: List container strawman 2001-11-09 22:42 ` Larry Kilgallen @ 2001-11-10 4:52 ` Nick Roberts 0 siblings, 0 replies; 116+ messages in thread From: Nick Roberts @ 2001-11-10 4:52 UTC (permalink / raw) "Larry Kilgallen" <Kilgallen@SpamCop.net> wrote in message news:RyJAqQJQiv6e@eisner.encompasserve.org... > ... > Is it possible for them to have the same profile, allowing people > to switch easily if they change their mind or need to debug ? The answer to this is yes: by basing them both on an abstract type. (On the other hand, I've demonstrated in another post in this thread that you don't need insert or delete anyway.) -- Nick Roberts ^ permalink raw reply [flat|nested] 116+ messages in thread
* Re: List container strawman 2001-11-09 18:00 ` Ted Dennison ` (2 preceding siblings ...) 2001-11-09 20:03 ` Stephen Leake @ 2001-11-10 20:24 ` ramatthews 3 siblings, 0 replies; 116+ messages in thread From: ramatthews @ 2001-11-10 20:24 UTC (permalink / raw) In article <DQUG7.19137$xS6.31310@www.newsranger.com>, Ted Dennison<dennison@telepath.com> wrote: > > I'm interested in what the general consensus is here. Should we do the extra > work to make iterators safe, given that this will have at least the following > effects: > > o Add extra dynamic memory operations to any list modification (there were some > there already). > o Add a (usually small) internal list traversal to any element deletion. > o Add a small validity check (or possibly two) to every iterator operation. > o Possibly make iterator creation non-determistic (time-wise). > o Possibly make iterator assignment non-deterministic. Note that functions are > currently used for iterating, so that would make just about any use of iterators > non-determinstic, unless procedure variants are introduced. > You express some implementation concerns that, for the implementation I have to hand, I hope I can clarify. The list contains two doubly-linked lists: one for the data, the other for the enumerators (also called Iterators and Positions in this discussion on cla). The enumerators list is traversed when the following subprograms are called: Prepend, Append, Delete_All, Insert, Delete and Finalize (for a list). In addition Update will cause a traversal of the enumerators list when the new value cannot be assigned to the existing data element (eg when the new value has a different tag); in this case the new value is assigned to a new data element and the old data element deleted - hence the need to update the enumerators. (Note that the package specification gives an incorrect comment on this). When a list is declared in client code, two data items are created: (1) the list that the client code directly sees (List_Type), and (2) the list header (List_Header_Type) that is created on the heap. A similar situation exists for an enumerator (Enumerator_Type and the heap held Enumerator_Envelope_Type). This split was made, on stylistic grounds, to avoid use of the attribute Unchecked_Access in the body. Having 'safe' enumerators does introduce some extra checking. For example when retrieving the data denoted by an enumerator the subprogram 'Current' checks: (1) that the enumerator's list exists: "Enumerator.Header.List_Header /= null", (2) that the data exists: "Enumerator.Header.Current /= null". Enumerator creation, assignment and finalization involves manipulation of the affected enumerator lists - but does not require list traversal. Robert Matthews. ^ permalink raw reply [flat|nested] 116+ messages in thread
* Re: List container strawman 2001-11-04 18:58 ` Darren New 2001-11-04 19:40 ` Larry Kilgallen @ 2001-11-05 19:28 ` Ted Dennison 2001-11-05 19:42 ` Jean-Marc Bourguet 2001-11-05 20:24 ` Darren New 1 sibling, 2 replies; 116+ messages in thread From: Ted Dennison @ 2001-11-05 19:28 UTC (permalink / raw) In article <3BE58FDD.E1FB1815@san.rr.com>, Darren New says... > >If you really want it to be foolproof, then for each "Location" pointer, >you keep a pointer to the list, a pointer to the element being indexed, >and a list number counter. In each list head, you keep a list number >counter, a counter of the number of Location pointers outstanding, and >the head and tail of the list. That's not good enough either, since the List could change to make the location itself invalid. The List itself could even go out of scope while the location doesn't. I've implemented a lot of these types of iterators in my time, so I have thought through the issue quite a bit already. The best I could come up with for a Right Thing would be to keep a list of extant Location pointers in each List object. That way the list itself can go and invalidate the Location whenever it needs to (probably by flipping some "valid" boolean in the Location type). Locations would have to be limited for this to work, so the functions that return locations would have to be changed to procedures. To my mind, that's a rediculous amount of work and overhead to support a mild "safeing up" of one small facility (iterators). I'm of the inlincation that if you aren't going to do the Right Thing here, then bag it. Half-measures are liable to cause as much harm as good by giving folks a false sense of security. You might as well just aviod the whole issue, save all the work and overhead, and just put it on the user to use this one feature correctly. As long as the issues are well documented (eg: Its a "Bounded Error" to use an iterator after any modification of its list not involving that iterator), then I don't see a big problem. --- T.E.D. homepage - http://www.telepath.com/dennison/Ted/TED.html No trees were killed in the sending of this message. However a large number of electrons were terribly inconvenienced. ^ permalink raw reply [flat|nested] 116+ messages in thread
* Re: List container strawman 2001-11-05 19:28 ` Ted Dennison @ 2001-11-05 19:42 ` Jean-Marc Bourguet 2001-11-05 20:40 ` Ted Dennison 2001-11-05 20:24 ` Darren New 1 sibling, 1 reply; 116+ messages in thread From: Jean-Marc Bourguet @ 2001-11-05 19:42 UTC (permalink / raw) Ted Dennison wrote: [...] > The best I could come up with for a Right Thing would be to keep a list of > extant Location pointers in each List object. That way the list itself can go > and invalidate the Location whenever it needs to (probably by flipping some > "valid" boolean in the Location type). Locations would have to be limited for > this to work, so the functions that return locations would have to be changed to > procedures. Why should they be limited? If they are controlled, that should be enough or do I miss something? [...] -- Jean-Marc ^ permalink raw reply [flat|nested] 116+ messages in thread
* Re: List container strawman 2001-11-05 19:42 ` Jean-Marc Bourguet @ 2001-11-05 20:40 ` Ted Dennison 0 siblings, 0 replies; 116+ messages in thread From: Ted Dennison @ 2001-11-05 20:40 UTC (permalink / raw) In article <3BE6EBB1.EF463656@free.fr>, Jean-Marc Bourguet says... > >Ted Dennison wrote: >[...] >> The best I could come up with for a Right Thing would be to keep a list of >> extant Location pointers in each List object. That way the list itself can go >> and invalidate the Location whenever it needs to (probably by flipping some >> "valid" boolean in the Location type). Locations would have to be limited for >> this to work, so the functions that return locations would have to be changed to >> procedures. > >Why should they be limited? If they are controlled, that should be enough or >do I miss something? That would be a lot tougher, as they'd have to somehow go add themselves and remove themselves from the List's list dynamcily. I guess its doable, its just even more work. :-) --- T.E.D. homepage - http://www.telepath.com/dennison/Ted/TED.html No trees were killed in the sending of this message. However a large number of electrons were terribly inconvenienced. ^ permalink raw reply [flat|nested] 116+ messages in thread
* Re: List container strawman 2001-11-05 19:28 ` Ted Dennison 2001-11-05 19:42 ` Jean-Marc Bourguet @ 2001-11-05 20:24 ` Darren New 2001-11-05 20:45 ` Ted Dennison 1 sibling, 1 reply; 116+ messages in thread From: Darren New @ 2001-11-05 20:24 UTC (permalink / raw) Ted Dennison wrote: > > In article <3BE58FDD.E1FB1815@san.rr.com>, Darren New says... > > > >If you really want it to be foolproof, then for each "Location" pointer, > >you keep a pointer to the list, a pointer to the element being indexed, > >and a list number counter. In each list head, you keep a list number > >counter, a counter of the number of Location pointers outstanding, and > >the head and tail of the list. > > That's not good enough either, since the List could change to make the location > itself invalid. I'm not sure how that could happen. The "location" record itself would be separate from the list. > The List itself could even go out of scope while the location > doesn't. Yes. That's why I suggested that it have a reference count, and finalization would need to either be defered until all the locations are also finalized or all locations would have to be invalidated when the list goes out of scope. Of course, in Ada this is probably a little more complex, and you'd wind up with the public "List" type probably just being a pointer to a controlled record. > I've implemented a lot of these types of iterators in my time, so I > have thought through the issue quite a bit already. Yep. > The best I could come up with for a Right Thing would be to keep a list of > extant Location pointers in each List object. That way the list itself can go > and invalidate the Location whenever it needs to (probably by flipping some > "valid" boolean in the Location type). Locations would have to be limited for > this to work, so the functions that return locations would have to be changed to > procedures. That could work too. You could have a linked list of Locations pointed to by the List object. > To my mind, that's a rediculous amount of work and overhead to support a mild > "safeing up" of one small facility (iterators). Agreed. On the other hand, you could include different bodies depending on whether you were having trouble or not. :-) I.e., the interface shouldn't *preclude* adding all kinds of safety checks, I think. > I'm of the inlincation that if > you aren't going to do the Right Thing here, then bag it. Half-measures are > liable to cause as much harm as good by giving folks a false sense of security. > You might as well just aviod the whole issue, save all the work and overhead, > and just put it on the user to use this one feature correctly. As long as the > issues are well documented (eg: Its a "Bounded Error" to use an iterator after > any modification of its list not involving that iterator), then I don't see a > big problem. Agreed. But it *is* doable. Probably not worth doing, tho. My expectation is that it would be a debugging aid you turned on if you need it, kind of like "Purify" for your C code. -- Darren New San Diego, CA, USA (PST). Cryptokeys on demand. Sore feet from standing in line at airport security checkpoints: Jet Leg. ^ permalink raw reply [flat|nested] 116+ messages in thread
* Re: List container strawman 2001-11-05 20:24 ` Darren New @ 2001-11-05 20:45 ` Ted Dennison 0 siblings, 0 replies; 116+ messages in thread From: Ted Dennison @ 2001-11-05 20:45 UTC (permalink / raw) In article <3BE6F58C.7C88F6CD@san.rr.com>, Darren New says... > >Ted Dennison wrote: >> That's not good enough either, since the List could change to make the >> location itself invalid. > >I'm not sure how that could happen. The "location" record itself would >be separate from the list. Lots of ways. For instance, the element pointed to could be deleted using another iterator. It could get removed with a Pop. It could get removed with that global list empty that someone suggested I add. >> I'm of the inlincation that if >> you aren't going to do the Right Thing here, then bag it. Half-measures are > >Agreed. But it *is* doable. Probably not worth doing, tho. My Exactly. --- T.E.D. homepage - http://www.telepath.com/dennison/Ted/TED.html No trees were killed in the sending of this message. However a large number of electrons were terribly inconvenienced. ^ permalink raw reply [flat|nested] 116+ messages in thread
* Re: List container strawman 2001-11-02 17:44 ` Jeffrey Carter 2001-11-02 20:07 ` Ted Dennison @ 2001-11-03 7:42 ` Simon Wright 1 sibling, 0 replies; 116+ messages in thread From: Simon Wright @ 2001-11-03 7:42 UTC (permalink / raw) Jeffrey Carter <jeffrey.carter@boeing.com> writes: > This is an iterator and should be so named ("Iterate"). I recommend > adding a Quit or Continue out Boolean parameter to Operation to > allow the client to terminate the iteration early. One of my users suggests making this an in out parameter, initialized to "carry on", so that he doesn't have to (remember to) assign it before exit. ^ permalink raw reply [flat|nested] 116+ messages in thread
* Re: List container strawman [not found] ` <3BE29AF4.80804@telepath.com> 2001-11-02 13:14 ` Ted Dennison @ 2001-11-05 14:00 ` Stephen Leake 2001-11-08 11:17 ` Simon Wright 1 sibling, 1 reply; 116+ messages in thread From: Stephen Leake @ 2001-11-05 14:00 UTC (permalink / raw) Do you have an example implimentation? I don't see how you can implement "Sort" without a "Compare" operation on Element. Typically, a user will want more than one "Compare" operation (ie Sort on first name, sort on date). Moving Sort into a child package, that takes a generic parameter of "Compare", would provide this. Also, the semantics of the operations need to be clearly defined. Does calling "Remove" invalidate other Iterators? What, exactly, does "Closure_Operation" do? There should be a "Insert (Iterator)" to add an element at the current iterator position. "List" should be limited, to prevent non-deep copies when Element is an access type. Or it should be derived from Controlled, to allow the user to override Adjust to provide a deep copy. Or a "Copy_Element" generic procedure should be provided. -- -- Stephe ^ permalink raw reply [flat|nested] 116+ messages in thread
* Re: List container strawman 2001-11-05 14:00 ` Stephen Leake @ 2001-11-08 11:17 ` Simon Wright 2001-11-13 16:29 ` Stephen Leake 0 siblings, 1 reply; 116+ messages in thread From: Simon Wright @ 2001-11-08 11:17 UTC (permalink / raw) Stephen Leake <stephen.a.leake.1@gsfc.nasa.gov> writes: > "List" should be limited, to prevent non-deep copies when Element is > an access type. I don't see why you would want to do this specifically? (perhaps I've misunderstood). If I make a List of Bank_Account_Access whose 5th element is a pointer to my bank account, and then make a copy of it, what would you expect the 5th element of the new List to point to? Better not be a *copy* of my bank account! ^ permalink raw reply [flat|nested] 116+ messages in thread
* Re: List container strawman 2001-11-08 11:17 ` Simon Wright @ 2001-11-13 16:29 ` Stephen Leake 2001-11-13 22:43 ` Jeffrey Carter 2001-11-13 22:48 ` Jeffrey Carter 0 siblings, 2 replies; 116+ messages in thread From: Stephen Leake @ 2001-11-13 16:29 UTC (permalink / raw) Simon Wright <simon@pushface.org> writes: > Stephen Leake <stephen.a.leake.1@gsfc.nasa.gov> writes: > > > "List" should be limited, to prevent non-deep copies when Element is > > an access type. > > I don't see why you would want to do this specifically? (perhaps I've > misunderstood). > > If I make a List of Bank_Account_Access whose 5th element is a pointer > to my bank account, and then make a copy of it, what would you expect > the 5th element of the new List to point to? Better not be a *copy* of > my bank account! Good example. But there are many other examples where copying a list does _not_ make sense. For example, if I have a list of controls in a GUI dialog box, and I pop up another dialog box, I want a list of _new_ controls, not the same ones. So the base list container must allow the user to control the copying process. That means either making it Limited and providing a Copy operation, or making it Controlled and providing Adjust. In either case, the user of the package must provide a Copy_Element operation that does the Right Thing. -- -- Stephe ^ permalink raw reply [flat|nested] 116+ messages in thread
* Re: List container strawman 2001-11-13 16:29 ` Stephen Leake @ 2001-11-13 22:43 ` Jeffrey Carter 2001-11-13 22:48 ` Jeffrey Carter 1 sibling, 0 replies; 116+ messages in thread From: Jeffrey Carter @ 2001-11-13 22:43 UTC (permalink / raw) Stephen Leake wrote: > > Good example. But there are many other examples where copying a list > does _not_ make sense. For example, if I have a list of controls in a > GUI dialog box, and I pop up another dialog box, I want a list of > _new_ controls, not the same ones. Since an unbounded list creates values of the Element type, assigns to them, and deallocates them, we must rely on the client to provide an actual type that handles this properly. If an Element contains a pointer and the client wants a deep copy, assignment must perform a deep copy. If the client wants multiple pointers to the same object, assignment need only copy the pointer. This is not a concern of the list. -- Jeffrey Carter ^ permalink raw reply [flat|nested] 116+ messages in thread
* Re: List container strawman 2001-11-13 16:29 ` Stephen Leake 2001-11-13 22:43 ` Jeffrey Carter @ 2001-11-13 22:48 ` Jeffrey Carter 2001-11-14 3:46 ` Nick Roberts 2001-11-14 14:50 ` Marin David Condic 1 sibling, 2 replies; 116+ messages in thread From: Jeffrey Carter @ 2001-11-13 22:48 UTC (permalink / raw) Stephen Leake wrote: > > So the base list container must allow the user to control the copying > process. That means either making it Limited and providing a Copy > operation, or making it Controlled and providing Adjust. In either > case, the user of the package must provide a Copy_Element operation > that does the Right Thing. If the client has to provide an Assign procedure for the Element type, then the Element type should be limited private. While I have no problem with this, I think most of the participants in this discussion have already decided that's too complicated for them. -- Jeffrey Carter ^ permalink raw reply [flat|nested] 116+ messages in thread
* Re: List container strawman 2001-11-13 22:48 ` Jeffrey Carter @ 2001-11-14 3:46 ` Nick Roberts 2001-11-15 10:23 ` Ehud Lamm 2001-11-14 14:50 ` Marin David Condic 1 sibling, 1 reply; 116+ messages in thread From: Nick Roberts @ 2001-11-14 3:46 UTC (permalink / raw) To my mind (and you need to understand that I live in my own little closeted world :-) there might be some mileage in providing some generic functions that provide a deep copy operation: generic type Element_Type(<>) is private; type Access_Type is access Element_Type; function SCL.Deep_Copy_by_Access (Ref: in Access_Type) return Access_Type; function SCL.Deep_Copy_by_Access (Ref: in Access_Type) return Access_Type is begin return new Element_Type'(Ref.all); end; This just provides a convenient way to get a Deep_Copy function for a (pool-specific) access type of a (non-access) data type. Then we could provide a deep copy for unbounded lists: generic with function Deep_Copy (Item: in Element_Type) return Element_Type is <>; function SCL.Lists.Unbounded.List_Deep_Copy (Source: in Unbounded_List) return Unbounded_List; There would be the same for unbounded lists and other container types. -- Best wishes, Nick Roberts ^ permalink raw reply [flat|nested] 116+ messages in thread
* Re: List container strawman 2001-11-14 3:46 ` Nick Roberts @ 2001-11-15 10:23 ` Ehud Lamm 0 siblings, 0 replies; 116+ messages in thread From: Ehud Lamm @ 2001-11-15 10:23 UTC (permalink / raw) Indeed one advantage of having a standard design for the different packages in the library is to encourage this sort of general utilities. Ehud ^ permalink raw reply [flat|nested] 116+ messages in thread
* Re: List container strawman 2001-11-13 22:48 ` Jeffrey Carter 2001-11-14 3:46 ` Nick Roberts @ 2001-11-14 14:50 ` Marin David Condic 2001-11-14 16:53 ` Jeffrey Carter 1 sibling, 1 reply; 116+ messages in thread From: Marin David Condic @ 2001-11-14 14:50 UTC (permalink / raw) I don't think I'd characterize it as "complicated" - more like "awkward". In the past, I've built data structures that would have a "private" flavor and a "limited private" flavor so that when I had the simple case (assignment and equality inherently available) I didn't have to go to the effort of inventing small subprograms or otherwise jockying around the fact that the limited case was going to insist I provide something that was already there. I think the reason for "private" being preferable over "limited private" is that now we can build things that inherit from Controlled, so if you need to do something to control behavior on assignment, you can, but you don't have to for the simple case. Hence, you can save yourself some generic parameters and make instantiation a simpler matter. (Do you really want to have to define an "Assign" procedure every time you want to stack up some integers? Its not complicated - just a pain in the posterior.) MDC -- Marin David Condic Senior Software Engineer Pace Micro Technology Americas www.pacemicro.com Enabling the digital revolution e-Mail: marin.condic@pacemicro.com Web: http://www.mcondic.com/ "Jeffrey Carter" <jeffrey.carter@boeing.com> wrote in message news:3BF1A33D.73DE084F@boeing.com... > > If the client has to provide an Assign procedure for the Element type, > then the Element type should be limited private. While I have no problem > with this, I think most of the participants in this discussion have > already decided that's too complicated for them. > ^ permalink raw reply [flat|nested] 116+ messages in thread
* Re: List container strawman 2001-11-14 14:50 ` Marin David Condic @ 2001-11-14 16:53 ` Jeffrey Carter 2001-11-14 17:59 ` Marin David Condic 0 siblings, 1 reply; 116+ messages in thread From: Jeffrey Carter @ 2001-11-14 16:53 UTC (permalink / raw) Marin David Condic wrote: > > I don't think I'd characterize it as "complicated" - more like "awkward". In > the past, I've built data structures that would have a "private" flavor and > a "limited private" flavor so that when I had the simple case (assignment > and equality inherently available) I didn't have to go to the effort of > inventing small subprograms or otherwise jockying around the fact that the > limited case was going to insist I provide something that was already there. > > I think the reason for "private" being preferable over "limited private" is > that now we can build things that inherit from Controlled, so if you need to > do something to control behavior on assignment, you can, but you don't have > to for the simple case. Hence, you can save yourself some generic parameters > and make instantiation a simpler matter. (Do you really want to have to > define an "Assign" procedure every time you want to stack up some integers? > Its not complicated - just a pain in the posterior.) > > "Jeffrey Carter" <jeffrey.carter@boeing.com> wrote in message > news:3BF1A33D.73DE084F@boeing.com... > > > > If the client has to provide an Assign procedure for the Element type, > > then the Element type should be limited private. While I have no problem > > with this, I think most of the participants in this discussion have > > already decided that's too complicated for them. > > Yes, but I was referring to a comment that suggested an Assign procedure needs to be provided even though Element is private. In that case you might as well make Element limited private since it buys you additional applicability without changing how the component is instantiated. Of course, the real reason not to import Element as private is that it is an incorrect specification, and precise specification is essential to design by contract. A generic package has 2 specifications: the generic formal part, which should specify precisely what the client must provide to use the package, and the package specification, which should specify precisely what services the package provides to its clients. A formal private type specifies that the package requires "=" for type, when in fact a list does not use "=" for its Element type. -- Jeffrey Carter ^ permalink raw reply [flat|nested] 116+ messages in thread
* Re: List container strawman 2001-11-14 16:53 ` Jeffrey Carter @ 2001-11-14 17:59 ` Marin David Condic 2001-11-15 3:33 ` Nick Roberts 0 siblings, 1 reply; 116+ messages in thread From: Marin David Condic @ 2001-11-14 17:59 UTC (permalink / raw) "Jeffrey Carter" <jeffrey.carter@boeing.com> wrote in message news:3BF2A186.F1911068@boeing.com... > > Yes, but I was referring to a comment that suggested an Assign procedure > needs to be provided even though Element is private. In that case you > might as well make Element limited private since it buys you additional > applicability without changing how the component is instantiated. > I would agree that once you've gone to the effort of insisting there be an Assign and an "=" in the generic formal part, then you might just as well have made it limited private and enabled the creation of lists of just about anything. But I don't want to have to specify an Assign and an "=" every time I want to stack up some integers or something similarly simple. I just want to get the job done with as little effort or excess baggage as is possible. > Of course, the real reason not to import Element as private is that it > is an incorrect specification, and precise specification is essential to > design by contract. A generic package has 2 specifications: the generic > formal part, which should specify precisely what the client must provide > to use the package, and the package specification, which should specify > precisely what services the package provides to its clients. > Interesting, but IMHO, not compelling. Some folks may want a list package to satisfy all sorts of requirements that are of some kind of academic interest. They may even want a formal mathematical proof of correctness. I don't think any of this Moves The Mission Forward. My big questions are "Does it work reliably?" and "Is it easy to use?". Design by contract, Ravenscar profiles, Mathematical proofs, etc. may all contribute something to question #1, but if they start getting in the way of question #2, I'd find that a hindrance to producing something large numbers of people will want to use. If we insist on Design By Contract or some other approaches as requirements, I'd ask "Do all the other packages provided by the Ada standard meet these requirements?" I'd suggest that they probably don't - in which case, why should a data-structures-add-on to the language need to do so? > A formal private type specifies that the package requires "=" for type, > when in fact a list does not use "=" for its Element type. > I'd suggest that no matter how hard you try, you aren't going to get me to shed a single tear over the fact that an "=" operation came along for the ride even though a List package (according to what definition? mine is pretty loose!) doesn't need it. Every time I write a math function for a type Float, I bring in a whole slew of operations I may not need. Every time I "with" a package, the same thing happens. Every time you have a generic formal of "digits <>" or similar, you bring in operations that may not be needed. I respectfully submit the question: "So What?" :-) No matter what we do, we will *never* arrive at a "Perfect" List package. The best we can hope for is a "Good Enough" List package that covers some sufficient bulk of the possible uses and does so as easily and with as much functionality as can reasonably be had. MDC -- Marin David Condic Senior Software Engineer Pace Micro Technology Americas www.pacemicro.com Enabling the digital revolution e-Mail: marin.condic@pacemicro.com Web: http://www.mcondic.com/ ^ permalink raw reply [flat|nested] 116+ messages in thread
* Re: List container strawman 2001-11-14 17:59 ` Marin David Condic @ 2001-11-15 3:33 ` Nick Roberts 2001-11-15 15:10 ` Marin David Condic 2001-11-15 18:08 ` Matthew Heaney 0 siblings, 2 replies; 116+ messages in thread From: Nick Roberts @ 2001-11-15 3:33 UTC (permalink / raw) Have I missed something in this discussion? If it is, as I get the impression, over whether the data type (the type of each element of a list) generic parameter should be private or limited private, I think I can give you the definitive answer. Unless I'm really missing something, it's got to be private (non-limited), because otherwise how do you copy values of that type into or out of the list? End of argument (isn't it?). -- Best wishes, Nick Roberts ^ permalink raw reply [flat|nested] 116+ messages in thread
* Re: List container strawman 2001-11-15 3:33 ` Nick Roberts @ 2001-11-15 15:10 ` Marin David Condic 2001-11-16 1:29 ` Nick Roberts 2001-11-15 18:08 ` Matthew Heaney 1 sibling, 1 reply; 116+ messages in thread From: Marin David Condic @ 2001-11-15 15:10 UTC (permalink / raw) Nope. Sorry. You can (and I have) make a list package using limited private that insists on having a procedure called "Assign" and a function called "=" as generic formals. The advantage of that is that now you could do something like make a List of Lists (assuming your list type is limited). The disadvantage is that when you just need a list of integers, you've still got to go define the "Assign" at least - assuming the "=" has the "is <>", so it gloms onto the existing "=" function. O.K. It's not the end of civilization as we know it, but its a pain in the backside - especially where you might have library level instantiations, etc. Who wants to keep writing trivial "Assign" subprograms (and maintaining them in separate files, etc., if you have to do library level instantiations.) for every usage of a list - which most of the time won't need anything tricky in the "Assign" procedure anyway. MDC -- Marin David Condic Senior Software Engineer Pace Micro Technology Americas www.pacemicro.com Enabling the digital revolution e-Mail: marin.condic@pacemicro.com Web: http://www.mcondic.com/ "Nick Roberts" <nickroberts@adaos.worldonline.co.uk> wrote in message news:9svf7q$161cka$1@ID-25716.news.dfncis.de... > > Unless I'm really missing something, it's got to be private (non-limited), > because otherwise how do you copy values of that type into or out of the > list? End of argument (isn't it?). > ^ permalink raw reply [flat|nested] 116+ messages in thread
* Re: List container strawman 2001-11-15 15:10 ` Marin David Condic @ 2001-11-16 1:29 ` Nick Roberts 2001-11-16 16:03 ` Marin David Condic 0 siblings, 1 reply; 116+ messages in thread From: Nick Roberts @ 2001-11-16 1:29 UTC (permalink / raw) Hah, it's pretty funny, Marin. You've made me spot an error in my just released proposal for the list package! I've declared the Abstract_List type limited, and it shouldn't be. Sorry, but my point (now ;-) would be that, whilst you can indeed do what you say, you wouldn't want to. Because lists are non-limited (hah :-) you can have a list of lists (etc.) without any problem. If you have a limited type, you don't want a list of objects of that type, you want a list of access values referencing them (e.g. consider a list of tasks). So, to sum up, I'm certain the data type (generic parameter) should be non-limited, so it can be copied without any sillyness. -- Best wishes, Nick Roberts ^ permalink raw reply [flat|nested] 116+ messages in thread
* Re: List container strawman 2001-11-16 1:29 ` Nick Roberts @ 2001-11-16 16:03 ` Marin David Condic 2001-11-16 20:19 ` Nick Roberts 0 siblings, 1 reply; 116+ messages in thread From: Marin David Condic @ 2001-11-16 16:03 UTC (permalink / raw) Back in the days of Ada83, this was more of a problem. Now that you have Finalization, making a List type non-limited is less of a problem. MDC -- Marin David Condic Senior Software Engineer Pace Micro Technology Americas www.pacemicro.com Enabling the digital revolution e-Mail: marin.condic@pacemicro.com Web: http://www.mcondic.com/ "Nick Roberts" <nickroberts@adaos.worldonline.co.uk> wrote in message news:9t1q26$16frj1$1@ID-25716.news.dfncis.de... > > Sorry, but my point (now ;-) would be that, whilst you can indeed do what > you say, you wouldn't want to. Because lists are non-limited (hah :-) you > can have a list of lists (etc.) without any problem. If you have a limited > type, you don't want a list of objects of that type, you want a list of > access values referencing them (e.g. consider a list of tasks). > ^ permalink raw reply [flat|nested] 116+ messages in thread
* Re: List container strawman 2001-11-16 16:03 ` Marin David Condic @ 2001-11-16 20:19 ` Nick Roberts 0 siblings, 0 replies; 116+ messages in thread From: Nick Roberts @ 2001-11-16 20:19 UTC (permalink / raw) "Marin David Condic" <dont.bother.mcondic.auntie.spam@[acm.org> wrote in message news:9t3ddg$c9c$1@nh.pace.co.uk... > Back in the days of Ada83, this was more of a problem. Now that you have > Finalization, making a List type non-limited is less of a problem. Acknowledged. -- Best wishes, Nick Roberts ^ permalink raw reply [flat|nested] 116+ messages in thread
* Re: List container strawman 2001-11-15 3:33 ` Nick Roberts 2001-11-15 15:10 ` Marin David Condic @ 2001-11-15 18:08 ` Matthew Heaney 1 sibling, 0 replies; 116+ messages in thread From: Matthew Heaney @ 2001-11-15 18:08 UTC (permalink / raw) "Nick Roberts" <nickroberts@adaos.worldonline.co.uk> wrote in message news:9svf7q$161cka$1@ID-25716.news.dfncis.de... > Have I missed something in this discussion? If it is, as I get the > impression, over whether the data type (the type of each element of a list) > generic parameter should be private or limited private, I think I can give > you the definitive answer. The problem is worse, because most of the participants in this discussion have assumed that "list" means a polylithic structure (elements are shared), a la LISP. This is an incorrect model. The container abstraction is monolithlic, and refering to it as a "list" only means that it has constant time insertion and removal. So you don't need "construct" or "cons" or "singleton" or "head" or "tail" or whatever. Furthermore, you can add an item to the list at the front, back, or somewhere in the middle. You can remove any iteim of the list. with Ada.Finalization; generic type Item_Type is private; with function "=" (L, R : Item_Type) return Boolean is <>; package Lists is type List_Type is private; --implies Controlled procedure Push_Front (List : in out List_Type; Item : in Item_Type); procedure Push_Back (List : in out List_Type; Item : in Item_Type); procedure Pop_Front (List : in out List_Type); procedure Pop_Back (List : in out List_Type); function Front (List : List_Type) return Item_Type; function Back (List : List_Type) return Item_Type; function Length (List : List_Type) return Natural; type Iterator_Type (List : access List_Type) is limited private; procedure Insert (Iterator : in Iterator_Type; Item : in Item_Type); procedure Remove (Iterator : in out Iterator_Type); procedure Advance (Iterator : in out Iterator_Type); procedure Backup (Iterator : in out Iterator_Type); function Item (Iterator : in Iterator_Type) return Item_Type; --or maybe --type Iterator_Type is private; --function Front (List : List_Type) return Iterator_Type; --function Back (List : List_Type) return Iterator_Type; --bounded form would probably require: --function Front (List : access List_Type) return Iterator_Type; --procedure Insert (List : in out List_Type; Iterator : Iterator_Type; Item : Item_Type); --procedure Remove (List : in out List_Type; Iterator : in out Iterator_Type); --etc ... end; That's the general idea. I'm undecided about how to declare the iterator type, because the limited form may have a false sense of security, e.g. declare List : aliased Integer_Lists.List_Type; begin Push_Front (List, 42); declare Iter : Iterator_Type (List'Access); begin Pop_Front (List); X := Item (Iter); --uh oh end; end; it may be simpler to just declare List : List_Type; Iter : Iterator_Type; begin Push_Front (List, 42); Iter := Front (List); ... end; It may also be necessary to use "First" and "Last" to refer to the first and last elements in the sequence, and "Front" and "Back" to refer to the nonce values that immediately preceed First and immediately follow Last, eg declare List : List_Type; Iter : Iterator_Type := First (List); begin while Iter /= List.Back loop ... Remove (List, Iter); end loop; end; You could then use First and Back to specify a half-open range, a la the STL in C++. Some food for thought... ^ permalink raw reply [flat|nested] 116+ messages in thread
* Re: List container strawman 2001-11-02 3:56 Ted Dennison ` (6 preceding siblings ...) [not found] ` <3BE29AF4.80804@telepath.com> @ 2001-11-08 14:57 ` M. A. Alves 2001-11-09 2:00 ` Jeffrey Carter 2001-11-09 18:31 ` Ted Dennison 7 siblings, 2 replies; 116+ messages in thread From: M. A. Alves @ 2001-11-08 14:57 UTC (permalink / raw) To: comp.lang.ada On Fri, 2 Nov 2001, Ted Dennison wrote: > Since we do seem to be reaching a small amount of agreement on > details, . . . I went ahead a put together a strawman package spec > (sans private part) for the unbounded list container . . . > http://www.telepath.com/dennison/Ted/Containers-Lists-Unbounded.ads.html > . . . For some time ago now package Unbounded_Array has been serving me well. A public version is at http://lexis.di.fct.unl.pt/ADaLIB/misc.htm and may be worth perusing. A more recent version exists, if someone is interest (the indicated version has a little bug, that site is no longer under my control, I am also looking for web hosting for Adlib, Adlib itself is changing status). I would expect PragmArc, a very nice effort for an Ada standard components library, to have a list containers package also--and very OO as you like it. Just my 2 cents for the List Container thread. Cheers, -- , M A R I O data miner, LIACC, room 221 tel 351+226078830, ext 121 A M A D O Rua Campo Alegre, 823 fax 351+226003654 A L V E S P-4150 PORTO, Portugal mob 351+939354002 ^ permalink raw reply [flat|nested] 116+ messages in thread
* Re: List container strawman 2001-11-08 14:57 ` M. A. Alves @ 2001-11-09 2:00 ` Jeffrey Carter 2001-11-09 18:31 ` Ted Dennison 1 sibling, 0 replies; 116+ messages in thread From: Jeffrey Carter @ 2001-11-09 2:00 UTC (permalink / raw) "M. A. Alves" wrote: > > I would expect PragmArc, a very nice effort for an Ada standard components > library, to have a list containers package also--and very OO as you like > it. Yes, I have already mentioned PragmARC.List_Unbounded_Unprotected in this discussion, and there is also PragmARC.List_Unbounded which is task safe. There are also unbounded stack and queue components built on the list component, and bounded queue components. -- Jeffrey R. Carter PragmAda Software Engineering ^ permalink raw reply [flat|nested] 116+ messages in thread
* Re: List container strawman 2001-11-08 14:57 ` M. A. Alves 2001-11-09 2:00 ` Jeffrey Carter @ 2001-11-09 18:31 ` Ted Dennison 2001-11-10 19:56 ` Ehud Lamm 1 sibling, 1 reply; 116+ messages in thread From: Ted Dennison @ 2001-11-09 18:31 UTC (permalink / raw) In article <mailman.1005231504.1899.comp.lang.ada@ada.eu.org>, M. A. Alves says... >For some time ago now package Unbounded_Array has been serving me well. A >public version is at > > http://lexis.di.fct.unl.pt/ADaLIB/misc.htm I wouldn't be adverse to us doing something like that in a separate package (eg: Containers.Vector if I use STL lingo). The implementation for using direct indexing in Lists would probably be too inneficient to bother with though. But I could see another package implementing a big chunk of contiguous storage, where things like extending the size can be arbitrarily expensive but direct indexing is O(1). --- T.E.D. homepage - http://www.telepath.com/dennison/Ted/TED.html No trees were killed in the sending of this message. However a large number of electrons were terribly inconvenienced. ^ permalink raw reply [flat|nested] 116+ messages in thread
* Re: List container strawman 2001-11-09 18:31 ` Ted Dennison @ 2001-11-10 19:56 ` Ehud Lamm 0 siblings, 0 replies; 116+ messages in thread From: Ehud Lamm @ 2001-11-10 19:56 UTC (permalink / raw) This is indeed a useful abstraction. Ehud ^ permalink raw reply [flat|nested] 116+ messages in thread
end of thread, other threads:[~2001-11-16 20:19 UTC | newest] Thread overview: 116+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2001-11-02 19:54 List container strawman Mike Brenner 2001-11-02 21:04 ` Ted Dennison 2001-11-03 8:09 ` Simon Wright 2001-11-03 12:46 ` Simon Wright -- strict thread matches above, loose matches on Subject: below -- 2001-11-02 3:56 Ted Dennison 2001-11-02 4:20 ` James Rogers 2001-11-02 14:23 ` Ted Dennison 2001-11-02 14:38 ` Preben Randhol 2001-11-02 15:15 ` Larry Kilgallen 2001-11-02 4:35 ` Eric Merritt 2001-11-02 15:46 ` Ted Dennison 2001-11-02 7:28 ` Ehud Lamm 2001-11-02 14:57 ` Marin David Condic 2001-11-02 15:57 ` Francisco Javier Loma Daza 2001-11-02 16:28 ` Marin David Condic 2001-11-02 17:08 ` Ted Dennison 2001-11-02 15:06 ` Ted Dennison 2001-11-02 15:32 ` Marin David Condic 2001-11-02 16:33 ` Ted Dennison 2001-11-02 16:43 ` Marin David Condic 2001-11-02 22:51 ` Jeffrey Carter 2001-11-03 0:24 ` Matthew Heaney 2001-11-03 2:21 ` Jeffrey Carter 2001-11-16 0:31 ` Vincent Marciante 2001-11-05 15:10 ` Marin David Condic 2001-11-05 18:31 ` Ted Dennison 2001-11-05 19:09 ` Marin David Condic 2001-11-05 21:23 ` Ted Dennison 2001-11-07 19:27 ` Stephen Leake 2001-11-02 18:11 ` Mark Johnson 2001-11-02 18:46 ` Marin David Condic 2001-11-02 19:21 ` Larry Kilgallen 2001-11-03 22:30 ` Nick Roberts 2001-11-02 16:26 ` Ted Dennison 2001-11-02 16:36 ` Marin David Condic 2001-11-02 19:31 ` Ted Dennison 2001-11-02 17:49 ` Jeffrey Carter 2001-11-08 10:34 ` Ehud Lamm 2001-11-09 14:49 ` Ted Dennison 2001-11-09 16:12 ` Ehud Lamm 2001-11-09 17:12 ` Marin David Condic 2001-11-09 18:11 ` Ted Dennison 2001-11-09 18:42 ` Matthew Heaney 2001-11-10 17:54 ` Simon Wright 2001-11-02 14:49 ` Marin David Condic 2001-11-02 15:15 ` Ted Dennison 2001-11-02 15:37 ` Marin David Condic 2001-11-02 16:49 ` Ted Dennison 2001-11-02 17:09 ` Marin David Condic 2001-11-04 0:10 ` Nick Roberts 2001-11-03 23:41 ` Nick Roberts 2001-11-02 17:02 ` David Botton 2001-11-02 17:55 ` David Botton 2001-11-03 19:22 ` Nick Roberts [not found] ` <3BE29AF4.80804@telepath.com> 2001-11-02 13:14 ` Ted Dennison 2001-11-02 13:31 ` Larry Kilgallen 2001-11-02 15:09 ` Ted Dennison 2001-11-02 15:13 ` Preben Randhol 2001-11-02 20:48 ` David Starner 2001-11-02 22:49 ` Larry Kilgallen 2001-11-02 17:44 ` Jeffrey Carter 2001-11-02 20:07 ` Ted Dennison 2001-11-02 23:19 ` Jeffrey Carter 2001-11-03 6:56 ` Ted Dennison 2001-11-03 19:22 ` Jeffrey Carter 2001-11-04 18:58 ` Darren New 2001-11-04 19:40 ` Larry Kilgallen 2001-11-04 20:49 ` Darren New 2001-11-07 19:07 ` ramatthews 2001-11-08 0:04 ` Darren New 2001-11-08 4:50 ` Jeffrey Carter 2001-11-08 23:26 ` ramatthews 2001-11-09 18:00 ` Ted Dennison 2001-11-09 18:13 ` Jean-Marc Bourguet 2001-11-09 18:55 ` Ted Dennison 2001-11-10 1:48 ` Nick Roberts 2001-11-10 17:04 ` Ted Dennison 2001-11-10 20:59 ` Nick Roberts 2001-11-10 23:17 ` Larry Hazel 2001-11-11 3:27 ` Nick Roberts 2001-11-12 18:39 ` Darren New 2001-11-13 0:35 ` Nick Roberts 2001-11-10 19:36 ` Ehud Lamm 2001-11-10 20:15 ` Nick Roberts 2001-11-09 19:27 ` Larry Kilgallen 2001-11-09 20:03 ` Stephen Leake 2001-11-09 21:05 ` Ted Dennison 2001-11-09 22:42 ` Larry Kilgallen 2001-11-10 4:52 ` Nick Roberts 2001-11-10 20:24 ` ramatthews 2001-11-05 19:28 ` Ted Dennison 2001-11-05 19:42 ` Jean-Marc Bourguet 2001-11-05 20:40 ` Ted Dennison 2001-11-05 20:24 ` Darren New 2001-11-05 20:45 ` Ted Dennison 2001-11-03 7:42 ` Simon Wright 2001-11-05 14:00 ` Stephen Leake 2001-11-08 11:17 ` Simon Wright 2001-11-13 16:29 ` Stephen Leake 2001-11-13 22:43 ` Jeffrey Carter 2001-11-13 22:48 ` Jeffrey Carter 2001-11-14 3:46 ` Nick Roberts 2001-11-15 10:23 ` Ehud Lamm 2001-11-14 14:50 ` Marin David Condic 2001-11-14 16:53 ` Jeffrey Carter 2001-11-14 17:59 ` Marin David Condic 2001-11-15 3:33 ` Nick Roberts 2001-11-15 15:10 ` Marin David Condic 2001-11-16 1:29 ` Nick Roberts 2001-11-16 16:03 ` Marin David Condic 2001-11-16 20:19 ` Nick Roberts 2001-11-15 18:08 ` Matthew Heaney 2001-11-08 14:57 ` M. A. Alves 2001-11-09 2:00 ` Jeffrey Carter 2001-11-09 18:31 ` Ted Dennison 2001-11-10 19:56 ` Ehud Lamm
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox