* List container strawman @ 2001-11-02 3:56 Ted Dennison 2001-11-02 4:20 ` James Rogers ` (7 more replies) 0 siblings, 8 replies; 166+ 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] 166+ messages in thread
* Re: List container strawman 2001-11-02 3:56 List container strawman 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; 166+ 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] 166+ 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; 166+ 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] 166+ 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; 166+ 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] 166+ 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; 166+ 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] 166+ messages in thread
* Re: List container strawman 2001-11-02 3:56 List container strawman 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; 166+ 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] 166+ 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; 166+ 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] 166+ messages in thread
* Re: List container strawman 2001-11-02 3:56 List container strawman 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; 166+ 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] 166+ 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; 166+ 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] 166+ 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; 166+ 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] 166+ 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; 166+ 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] 166+ 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; 166+ 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] 166+ 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; 166+ 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] 166+ 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; 166+ 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] 166+ 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; 166+ 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] 166+ 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; 166+ 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] 166+ 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; 166+ 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] 166+ 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; 166+ 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] 166+ messages in thread
* Re: List container strawman 2001-11-03 0:24 ` Matthew Heaney @ 2001-11-03 2:21 ` Jeffrey Carter 2001-11-03 22:51 ` Rosen Trick [List container strawman] Nick Roberts 2001-11-16 0:31 ` List container strawman Vincent Marciante 0 siblings, 2 replies; 166+ 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] 166+ messages in thread
* Rosen Trick [List container strawman] 2001-11-03 2:21 ` Jeffrey Carter @ 2001-11-03 22:51 ` Nick Roberts 2001-11-04 13:07 ` Robert Dewar 2001-11-16 0:31 ` List container strawman Vincent Marciante 1 sibling, 1 reply; 166+ messages in thread From: Nick Roberts @ 2001-11-03 22:51 UTC (permalink / raw) I've always felt that this whole charade is an academic Alice-in-Wonderland adventure. The right solution, of course, is to use a procedure (with an in-out parameter) instead of a function. Grrr. PS: Why? Because functions should not have side-effects (in a language like Ada). I don't care about expediencies that are to do with debugging, profiling, auditing, and that sort of thing (where the effort of not using functions would be silly), but where the main thrust of the logic has a side effect, use a procedure! Good programming (in Ada) is not about what weird and funny things you can do that will catch people by surpise (and so be likely to cause bugs, or angst, or both). PPS: I don't think allocating an RNG state block on the heap, rather than the stack, is likely to have much effect on speed; surely the burden of indirect access would be vastly outweighed by the burden of computation for each number generation cycle? And why would using finalisation be inefficient? -- Nick Roberts ^ permalink raw reply [flat|nested] 166+ messages in thread
* Re: Rosen Trick [List container strawman] 2001-11-03 22:51 ` Rosen Trick [List container strawman] Nick Roberts @ 2001-11-04 13:07 ` Robert Dewar 2001-11-04 17:17 ` Side-Effects in Functions [Rosen Trick] Nick Roberts 0 siblings, 1 reply; 166+ messages in thread From: Robert Dewar @ 2001-11-04 13:07 UTC (permalink / raw) "Nick Roberts" <nickroberts@adaos.worldonline.co.uk> wrote in message news:<9s230d$107b5a$2@ID-25716.news.dfncis.de>... > PS: Why? Because functions should not have side-effects (in a language like > Ada). You present this as a kind of obvious ab initio fact, but it is nothing of the kind. Here are the facts: Ada permits functions to have side effects, and does not attempt to prohibit side effects in functions (an odd and inconsistent exception is functions in protected types, and that was indeed a major discussion point in the design) There was some attept early on to consider trying to stop functions from having side effects, and indeed I think one published early version of Ada distinguished functions and value returning procedures, or at least that was discussed. But such attempts were firmly rejected, and the decision was that there are situations where it makes perfectly good sense for functions to have side effects, and an absolute rule prohibiting them is in the same not-well-thought-out category as absolute rules against use clauses, goto statements, unchecked conversion, and various other very useful features of Ada. Useful does not mean that they should be used all the time, or misused, just that they have some legitimate use. Another important factor is that other languages agree with Ada that functions should be allowed to have side effects. In particular C takes this viewpoint, and side effects in functions are common in C, including side effects in calls to standard functions in the C library. Now in Ada, the rule for functions is a bit odd: Side effects from access to global variables - permitted Side effects from modifying access type args - permitted Side effects from in out parameters - prohibited I have never understood the rationale for this inconsistent design. When I talk to someone like Tuck, who basically supports the prohibition, it seems to come from a general feeling that functions should not have side effects. OK, but that's some other language than Ada, where functions are permitted to have side effects. Most annoyingly, the natural translation of a * arg in a C function, e.g. *int, is to translate it to an IN OUT parameter, but that is arbitrarily not allowed. It is of course allowed to translate it to an access-to-int parameter, since there is no restriction on the use of such parameters for functions, even though they are obviously logically equivalent from an expressive point of view. The trouble is that although in-out parameters and access-type-to-foo parameters are equivalent from a logical point of view, they are very different syntactically, and we are left with the following unpleasant alternatives in interfacing to C functions: 1. Interface as procedures. This either requires a wrapper or something like the Valued_Procedure interface available in GNAT. The trouble with this is that the calls get really ugly. Yes, in the case where the result is just an error code it's acceptable, but that's by no means always the case. 2. Interface using named access types. The calls are somewhat better here, but you get a plague of aliased variables appearing, and the access types need defining which is messy. 3. Use a wrapper with global variables for the missing parameters. But this is nasty anyway, and gets too far from the C form. To me, the arguments for allowing IN OUT parameters, at least for interfaced functions, are very strong, but unfortunately, this is an argument that cannot be won. There seem to be three kinds of people: 1. Those who are adamantly opposed to IN OUT parameters on basically religeous (i.e. belief based) grounds without very strong technical justification in many cases, or with the technical justification being inconsistent with the general permission for functions to have side effects in Ada. This is a surprisingly large group. 2. Those who really don't like functions with side effects much, but would tolerate IN OUT parameters if they had to, but are certainly not going to fight for them, and would vote no or abstain. I think I correctly label Tuck and the design team in this second group, which is also fairly large. 3. Those who really find this restriction annoying, and have fought to get it lifted. They are a large group, but somewhat less than a working majority. I don't see anything that would put group 3 in a position to fix this annoying restriction in the near future, so it to me is just a minor defect in the language that will stay uncorrected, but we can live with it, it's not fatal, just very annoying. ^ permalink raw reply [flat|nested] 166+ messages in thread
* Side-Effects in Functions [Rosen Trick] 2001-11-04 13:07 ` Robert Dewar @ 2001-11-04 17:17 ` Nick Roberts 2001-11-05 2:46 ` Robert Dewar 0 siblings, 1 reply; 166+ messages in thread From: Nick Roberts @ 2001-11-04 17:17 UTC (permalink / raw) "Robert Dewar" <dewar@gnat.com> wrote in message news:5ee5b646.0111040507.5ca7ea23@posting.google.com... > "Nick Roberts" <nickroberts@adaos.worldonline.co.uk> wrote in message news:<9s230d$107b5a$2@ID-25716.news.dfncis.de>... > > > PS: Why? Because functions should not have side-effects (in a language like > > Ada). > > You present this as a kind of obvious ab initio fact, but > it is nothing of the kind. I was hoping that it would be obvious that I was putting this point in a deliberately polemical style. I am merely stating my own strongly held belief on this subject, based on perfectly good reasoning, as well as the consensus of programming wisdom. > Here are the facts: > ... > There was some attept early on to consider trying to stop > functions from having side effects, and indeed I think one > published early version of Ada distinguished functions and > value returning procedures, or at least that was discussed. I'm glad this didn't happen, because, as mentioned in my previous post, there are occasions -- such as debugging, profiling, auditing -- when it is useful for a function to have a side-effect, and forcing the programmer to convert it to a procedure -- and thus all calls on it to procedure calls -- would be wholly unjustified. > But such attempts were firmly rejected, and the decision > was that there are situations where it makes perfectly good > sense for functions to have side effects, and an absolute > rule prohibiting them is in the same not-well-thought-out > category as absolute rules against use clauses, goto statements, > unchecked conversion, and various other very > useful features of Ada. Useful does not mean that they should be used > all the time, or misused, just that they have some legitimate use. I agree there. > Another important factor is that other languages agree with > Ada that functions should be allowed to have side effects. > In particular C takes this viewpoint, and side effects in > functions are common in C, including side effects in calls > to standard functions in the C library. The fact that the C language permits something, or that C programmers do a particular thing, is surely no recommendation that Ada programmers should do the same! > Now in Ada, the rule for functions is a bit odd: > > Side effects from access to global variables - permitted > Side effects from modifying access type args - permitted > Side effects from in out parameters - prohibited These rules may seem a little odd, but they pertain to what Ada allows programmers to do, not what Ada programmers should do. My point was entirely about what Ada programmers should do. > I have never understood the rationale for this inconsistent > design. The rationale is simple and well-known Robert! Good grief, every Ada textbook on the planet has an example of how side-effects in functions can introduce subtle and pernicious bugs (especially on porting). Must I really repeat these? > Most annoyingly, the natural translation of a * arg in a > C function, e.g. *int, is to translate it to an IN OUT > parameter, but that is arbitrarily not allowed. This isn't the most natural translation, and the prevention of the use of in-out parameters in functions is not arbitrary, it was, as you said earlier, carefully debated. > It is of > course allowed to translate it to an access-to-int parameter, since > there is no restriction on the use of > such parameters for functions, even though they are obviously > logically equivalent from an expressive point of view. They are not logically equivalent. The use of the access parameter implies the (actual) object is aliased (kept in memory essentially all the time). This may be something that C assumes for all its variables (clever compiler deductions notwithstanding), but Ada does not, and rightly so. > The trouble is that although in-out parameters and access-type-to-foo > parameters are equivalent from a logical > point of view, they are very different syntactically, and > we are left with the following unpleasant alternatives in > interfacing to C functions: > > 1. Interface as procedures. This either requires a > wrapper or something like the Valued_Procedure > interface available in GNAT. The trouble with > this is that the calls get really ugly. Yes, in > the case where the result is just an error code > it's acceptable, but that's by no means always > the case. > > 2. Interface using named access types. The calls are > somewhat better here, but you get a plague of aliased > variables appearing, and the access types need > defining which is messy. > > 3. Use a wrapper with global variables for the missing > parameters. But this is nasty anyway, and gets too > far from the C form. To me, it is obvious that option 2 should be used. To describe the required aliasing of variables as a 'plague' is rather an overstatement: it simply means adding the word 'aliased' to the appropriate objects; that's not a plague! It is absolutely right, since they must (at least in effect) be aliased for the called C routine(s) to access them via a pointer. > To me, the arguments for allowing IN OUT parameters, at > least for interfaced functions, are very strong, but > unfortunately, this is an argument that cannot be won. > There seem to be three kinds of people: > > 1. Those who are adamantly opposed to IN OUT parameters > on basically religeous (i.e. belief based) grounds without > very strong technical justification in many cases, or with > the technical justification being inconsistent with the > general permission for functions to have side effects in > Ada. This is a surprisingly large group. Well, as I say above, there is indeed a very strong, very well documented, and generally accepted technical justification for avoiding side-effects in functions (which is the point I was originally making), and disallowing in-out parameters in Ada functions seems to be be perfectly in tune with this principle. > ... To sum up, I am amazed at Robert's opposition to what I have always understood to be a very well established programming principle (in procedural languages such as Ada). That principle is taught for very good software engineering reasons. I said "Must I really repeat these?". If the answer is simply "Yes.", then please just answer "Yes" and I will. -- Nick Roberts ^ permalink raw reply [flat|nested] 166+ messages in thread
* Re: Side-Effects in Functions [Rosen Trick] 2001-11-04 17:17 ` Side-Effects in Functions [Rosen Trick] Nick Roberts @ 2001-11-05 2:46 ` Robert Dewar 2001-11-05 7:26 ` pete ` (2 more replies) 0 siblings, 3 replies; 166+ messages in thread From: Robert Dewar @ 2001-11-05 2:46 UTC (permalink / raw) "Nick Roberts" <nickroberts@adaos.worldonline.co.uk> wrote in message news:<9s3tl3$111hco$1@ID-25716.news.dfncis.de>... > I was hoping that it would be obvious that I was putting > this point in a > deliberately polemical style. I am merely stating my own > strongly held > belief on this subject, based on perfectly good > reasoning, as well as the > consensus of programming wisdom. No, this is by no means a consensus. Most procedural languages, including Ada, allow functions to have side effects. And on the narrower issue of allowing IN OUT parameters in functions, there is nothing like a consensus opposing this. Indeed my guess is that during the design phase on Ada 95, if a show down had been insisted on, the side favoring IN OUT parameters would have (narrowly) won, but it seemed inappropriate to force this change in the absence of a consensus on the other side. So your understanding of the consensus here is completely wrong. > > Now in Ada, the rule for functions is a bit odd: > > > > Side effects from access to global variables - permitted > > Side effects from modifying access type args - permitted > > Side effects from in out parameters - prohibited > > These rules may seem a little odd, but they pertain to what Ada allows > programmers to do, not what Ada programmers should do. My point was entirely > about what Ada programmers should do. Features in Ada are there to be used, anyone who announces that some feature should never be used probably just does not understand the issues. Of course they should not be abused. > The rationale is simple and well-known Robert! Good grief, every Ada > textbook on the planet has an example of how side-effects in functions can > introduce subtle and pernicious bugs (especially on porting). Must I really > repeat these? Please don't! Many people would say EXACTLY the same about assignments, or global variables. Of course this feature can be misused, as can many features. Forbidding something because it can be misused is an absurd design approach and one that fortunately Ada seldom indulges in. > > Most annoyingly, the natural translation of a * arg in a > > C function, e.g. *int, is to translate it to an IN OUT > > parameter, but that is arbitrarily not allowed. > > This isn't the most natural translation, and the prevention of the use of > in-out parameters in functions is not arbitrary, it was, as you said > earlier, carefully debated. Actually the issue of IN OUT parameters was never carefully debated. It was clear early on that it was one of these religeous issues (note Nick's odd use of the phrase "strong belief") which was not something that could be calmly debated (your "good grief" shows this nicely -- why people get so excercised over this issue is a puzzle to me). > To me, it is obvious that option 2 should be used. To describe the required > aliasing of variables as a 'plague' is rather an overstatement: it simply > means adding the word 'aliased' to the appropriate objects; that's not a > plague! It is absolutely right, since they must (at least in effect) be > aliased for the called C routine(s) to access them via a pointer. Most people feel that being forced to add aliased keywords all over the place, just because of odd interfacing requirements for C functions, is unfortunate. If you find it perfectly fine to have aliased keywords around, fine, but you obviously don't have the alergy to aliasing that many people have. It is not accidental that aliased is not the default. > To sum up, I am amazed at Robert's opposition to what I > have always understood to be a very well established > programming principle (in procedural languages such as > Ada). No wonder if you are amazed if you think this is a "very well established programming principle". That's just wrong. As I noted earlier, nearly all procedural languages DO allow side effects in functions. And of course Ada does too (allow side effects in functions), but has the odd attitude that side effects are only OK if they are not announced in the spec. Consider the following: function f return integer; -- Increments the global variable Q and returns the -- incremented value. function f (Q : in out integer) return integer; -- Increments its argument and returns the incremented -- value. I find it odd that Ada allows the first and disallows the second, and many others would agree with me. Nick, no one will try to convince you that you are wrong here, because it is a waste of time, but you should learn that you are quite wrong if you think your viewpoint somehow represents a general consensus. I and many other experts in programming languages in general, and Ada in particular, disagree with you. The fact is there is no consensus on either side of this issue. Oddly, the feeling that goto statements should never be used has much *stronger* support than the feeling that IN OUT parameters should not be allowed in functions, yet Ada does permit goto statements. I think the actual situation is that this is one of these cases where the designers get to decide, since there is no consensus. JDI accepted gotos, but felt that functions should have no side effects whatever. That was untenable, and he was argued out of this extreme position, with the result that we ended up with a rather odd compromise. Tuck is also somewhat (though not fanatically like you) opposed to IN OUT parameters for functions, so was not about to decree that they should go in. > That principle is taught for very good > software engineering reasons. I said "Must I really > repeat these?". If you have been taught that functions should never ever have side effects, you have been taught by a fanatic. Such fanaticism is almost never helpful. ^ permalink raw reply [flat|nested] 166+ messages in thread
* Re: Side-Effects in Functions [Rosen Trick] 2001-11-05 2:46 ` Robert Dewar @ 2001-11-05 7:26 ` pete 2001-11-05 10:29 ` Dmitry A. Kazakov 2001-11-05 13:56 ` Robert Dewar 2001-11-05 15:56 ` Ted Dennison 2001-11-05 18:46 ` Nick Roberts 2 siblings, 2 replies; 166+ messages in thread From: pete @ 2001-11-05 7:26 UTC (permalink / raw) functions, in the mathemtical sense, do not accept an IN OUT paramters, and do not have side effects. y=f(x), x here can never be modified by the function f(). so, Ada function is more like a math function. ^ permalink raw reply [flat|nested] 166+ messages in thread
* Re: Side-Effects in Functions [Rosen Trick] 2001-11-05 7:26 ` pete @ 2001-11-05 10:29 ` Dmitry A. Kazakov 2001-11-05 11:19 ` pete 2001-11-06 0:10 ` Nick Roberts 2001-11-05 13:56 ` Robert Dewar 1 sibling, 2 replies; 166+ messages in thread From: Dmitry A. Kazakov @ 2001-11-05 10:29 UTC (permalink / raw) On 4 Nov 2001 23:26:03 -0800, pete@nospam <pete_member@newsguy.com> wrote: >functions, in the mathemtical sense, do not accept an IN OUT paramters, >and do not have side effects. > >y=f(x), x here can never be modified by the function f(). > >so, Ada function is more like a math function. No function in a programming language may have no side effects. One could say that there are side effects which are of no interest, but no more than that. The discussion about in out parameters is proved to be evergreen (:-)). But what I presonally cannot understand is why not to allow PROCEDUREs having a result, i.e. procedure Find (Folder : in out Table) return Table_Token; procedure GetNext (Item_List : in out Iterator) return Element; etc. Regards, Dmitry Kazakov ^ permalink raw reply [flat|nested] 166+ messages in thread
* Re: Side-Effects in Functions [Rosen Trick] 2001-11-05 10:29 ` Dmitry A. Kazakov @ 2001-11-05 11:19 ` pete 2001-11-05 14:59 ` Dmitry A. Kazakov 2001-11-06 0:10 ` Nick Roberts 1 sibling, 1 reply; 166+ messages in thread From: pete @ 2001-11-05 11:19 UTC (permalink / raw) In article <3be666fe.6426140@News.CIS.DFN.DE>, dmitry@elros.cbb-automation.de says... > >But what I presonally cannot understand is why not to allow >PROCEDUREs having a result, i.e. > >procedure Find (Folder : in out Table) return Table_Token; > >procedure GetNext (Item_List : in out Iterator) return Element; > this is a joke, right? ^ permalink raw reply [flat|nested] 166+ messages in thread
* Re: Side-Effects in Functions [Rosen Trick] 2001-11-05 11:19 ` pete @ 2001-11-05 14:59 ` Dmitry A. Kazakov 2001-11-05 15:21 ` Preben Randhol 0 siblings, 1 reply; 166+ messages in thread From: Dmitry A. Kazakov @ 2001-11-05 14:59 UTC (permalink / raw) On 5 Nov 2001 03:19:39 -0800, pete@nospam <pete_member@newsguy.com> wrote: >In article <3be666fe.6426140@News.CIS.DFN.DE>, dmitry@elros.cbb-automation.de >says... >> > >>But what I presonally cannot understand is why not to allow >>PROCEDUREs having a result, i.e. >> >>procedure Find (Folder : in out Table) return Table_Token; >> >>procedure GetNext (Item_List : in out Iterator) return Element; >> > >this is a joke, right? Nope. It is exactly what is required, namely a subroutine having a distinguished parameter called result and allowed to modify its arguments. It is not a function (in Ada sense), thus it is a procedure. Compare: procedure Find (Folder : in out Table) return Table_Token; with procedure Find (Folder : in out Table; Result : out Table_Token); The difference between them is rather syntactical. Semantically they do same: search table, cash internally the result of search (thus in out for the fist argument), return the found element. Regards, Dmitry Kazakov ^ permalink raw reply [flat|nested] 166+ messages in thread
* Re: Side-Effects in Functions [Rosen Trick] 2001-11-05 14:59 ` Dmitry A. Kazakov @ 2001-11-05 15:21 ` Preben Randhol 2001-11-05 16:04 ` Ted Dennison 2001-11-05 16:33 ` Dmitry A. Kazakov 0 siblings, 2 replies; 166+ messages in thread From: Preben Randhol @ 2001-11-05 15:21 UTC (permalink / raw) On Mon, 05 Nov 2001 14:59:15 GMT, Dmitry A. Kazakov wrote: > On 5 Nov 2001 03:19:39 -0800, pete@nospam <pete_member@newsguy.com> > wrote: > > procedure Find (Folder : in out Table) return Table_Token; > > with > > procedure Find (Folder : in out Table; Result : out Table_Token); > > The difference between them is rather syntactical. Semantically they Yes and I don't understand why you want it. What if you expect to change two wariables in the procedure like: procedure Find (Folder : in out Table; Result : out Table_Token; Unique : out Boolean); to do it like: procedure Find (Folder : in out Table; Unique : out Boolean) return Table_Token; looks a bit messy I think. What is the difference between a function with in out and a procedure with a return value? It amounts to the same thing I think. Preben ^ permalink raw reply [flat|nested] 166+ messages in thread
* Re: Side-Effects in Functions [Rosen Trick] 2001-11-05 15:21 ` Preben Randhol @ 2001-11-05 16:04 ` Ted Dennison 2001-11-05 16:33 ` Dmitry A. Kazakov 1 sibling, 0 replies; 166+ messages in thread From: Ted Dennison @ 2001-11-05 16:04 UTC (permalink / raw) In article <slrn9udfg3.4dc.randhol+abuse@kiuk0156.chembio.ntnu.no>, Preben Randhol says... > >What is the difference between a function with in out and a procedure >with a return value? It amounts to the same thing I think. I think it would actually give functions *back* their purity. It would allow functions to continue to be used for non-side-effect functions, but give folks who would otherwise have to resort to pointers, unchecked_access tricks, or the Rosen trick in a function a language-defined way to achieve the result they require. When reading a spec, "function" would be a bit stronger of a statement about what is going on. Plus folks who feel religously about it could just outlaw value-returning procedures like they always have for "goto". However, I think about %90 of this issue would go away if some other method of modifying "bookkeeping" fields in private types was provided. --- 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] 166+ messages in thread
* Re: Side-Effects in Functions [Rosen Trick] 2001-11-05 15:21 ` Preben Randhol 2001-11-05 16:04 ` Ted Dennison @ 2001-11-05 16:33 ` Dmitry A. Kazakov 2001-11-05 17:42 ` Warren W. Gay VE3WWG 1 sibling, 1 reply; 166+ messages in thread From: Dmitry A. Kazakov @ 2001-11-05 16:33 UTC (permalink / raw) On Mon, 5 Nov 2001 15:21:13 +0000 (UTC), Preben Randhol <randhol+abuse@pvv.org> wrote: >On Mon, 05 Nov 2001 14:59:15 GMT, Dmitry A. Kazakov wrote: >> On 5 Nov 2001 03:19:39 -0800, pete@nospam <pete_member@newsguy.com> >> wrote: >> >> procedure Find (Folder : in out Table) return Table_Token; >> >> with >> >> procedure Find (Folder : in out Table; Result : out Table_Token); >> >> The difference between them is rather syntactical. Semantically they > >Yes and I don't understand why you want it. What if you expect to change >two wariables in the procedure like: > >procedure Find (Folder : in out Table; Result : out Table_Token; > Unique : out Boolean); Well, multiple results is another story. Some languages have return tuples, but I am not convinced that Ada really needs it. Then your argument could be well applied to pure functions as well. Why not to replace them by procedures with an extra out parameter? A bit more work with temporal variables, unability to initialize constants, but generally no problem (:-)) >to do it like: > >procedure Find (Folder : in out Table; Unique : out Boolean) return Table_Token; > >looks a bit messy I think. Yes. But I still have a choice to make it: procedure Find (Folder : in out Table; Result : out Table_Token; Unique : out Boolean); It is of course not so that any out parameter has to be declared as the result. All we need is an impure function. As Robert have pointed, it is ridiculous to have an ability to write impure functions and have no right to manifest them as such (openly using in out parameters). If the word "function" makes people so sensitive, let's use "procedure" instead! >What is the difference between a function with in out and a procedure >with a return value? It amounts to the same thing I think. There is no difference other than functions with in out parameters are unacceptable for some part of Ada community, which is enough powerful to ban them forever (:-)). P.S. I do not belong to this part. Regards, Dmitry Kazakov ^ permalink raw reply [flat|nested] 166+ messages in thread
* Re: Side-Effects in Functions [Rosen Trick] 2001-11-05 16:33 ` Dmitry A. Kazakov @ 2001-11-05 17:42 ` Warren W. Gay VE3WWG 2001-11-05 18:11 ` Preben Randhol 2001-11-06 8:38 ` Dmitry A. Kazakov 0 siblings, 2 replies; 166+ messages in thread From: Warren W. Gay VE3WWG @ 2001-11-05 17:42 UTC (permalink / raw) Dmitry A. Kazakov wrote: > On Mon, 5 Nov 2001 15:21:13 +0000 (UTC), Preben Randhol > <randhol+abuse@pvv.org> wrote: >>On Mon, 05 Nov 2001 14:59:15 GMT, Dmitry A. Kazakov wrote: >>>On 5 Nov 2001 03:19:39 -0800, pete@nospam <pete_member@newsguy.com> >>>wrote: ... > Yes. But I still have a choice to make it: > > procedure Find (Folder : in out Table; Result : out Table_Token; > Unique : out Boolean); > > It is of course not so that any out parameter has to be declared as > the result. All we need is an impure function. As Robert have pointed, > it is ridiculous to have an ability to write impure functions and have > no right to manifest them as such (openly using in out parameters). If > the word "function" makes people so sensitive, let's use "procedure" > instead! > >>What is the difference between a function with in out and a procedure >>with a return value? It amounts to the same thing I think. > > There is no difference other than functions with in out parameters are > unacceptable for some part of Ada community, which is enough powerful > to ban them forever (:-)). > > P.S. I do not belong to this part. > > Regards, > Dmitry Kazakov I think one of the issues at stake here is that Ada was meant to be easy to read. If you allow procedures to return values, then it is no longer a valid assumption that what looks like a function call, does not produce side effects (ie. you cannot assume that the arguments are not modified, without looking at the declaration). To pull it off, you'd have to make some sort of syntactical difference in procedure-function calls, to maintain the status quo for functions. In case I am not explaining this clear enough, the following example might help: declare Arg : Boolean; -- Argument R : Boolean; -- Result begin R := My_Function(Arg); -- Assumed that Arg is not modified R := My_Proc_Function[Arg]; -- A procedure returning.. identified by [] I am not suggesting the [] make a good syntax here, but you'd have to do something like this to maintain the distinction that Functions already enjoy within Ada. -- Warren W. Gay VE3WWG http://home.cogeco.ca/~ve3wwg ^ permalink raw reply [flat|nested] 166+ messages in thread
* Re: Side-Effects in Functions [Rosen Trick] 2001-11-05 17:42 ` Warren W. Gay VE3WWG @ 2001-11-05 18:11 ` Preben Randhol 2001-11-06 8:38 ` Dmitry A. Kazakov 1 sibling, 0 replies; 166+ messages in thread From: Preben Randhol @ 2001-11-05 18:11 UTC (permalink / raw) On Mon, 05 Nov 2001 17:42:14 GMT, Warren W. Gay VE3WWG wrote: > > I think one of the issues at stake here is that Ada was meant to be > > easy to read. If you allow procedures to return values, then it is > no longer a valid assumption that what looks like a function call, > does not produce side effects (ie. you cannot assume that the arguments > are not modified, without looking at the declaration). Not only that. If one allow return values in procedures one cannot know that the procedure won't return a value unless one look at the definition. It would make things a mess and I think it clearly would break down readability. > R := My_Function(Arg); -- Assumed that Arg is not modified > R := My_Proc_Function[Arg]; -- A procedure returning.. identified by [] > > > I am not suggesting the [] make a good syntax here, but you'd have > to do something like this to maintain the distinction that Functions > already enjoy within Ada. Ouch! Very bad (I think) as you then will introduce: 1. Very confusing syntax for beginners 2. Harder to "read" the difference => Lower readability 3. More easy to write wrong code. You may type [] and mean (). 4. How should one solve dispatching? I don't understand the need for neither function with in out nor procedure with return values. Preben Randhol -- Please, stop bombing civilians in Afghanistan. One cannot write off killing innocent children and other civilians as "collateral damage". A civilian is a civilian whether he or she is American or from another country in the world. http://web.amnesty.org/11september.htm ^ permalink raw reply [flat|nested] 166+ messages in thread
* Re: Side-Effects in Functions [Rosen Trick] 2001-11-05 17:42 ` Warren W. Gay VE3WWG 2001-11-05 18:11 ` Preben Randhol @ 2001-11-06 8:38 ` Dmitry A. Kazakov 2001-11-06 9:31 ` tgingold 1 sibling, 1 reply; 166+ messages in thread From: Dmitry A. Kazakov @ 2001-11-06 8:38 UTC (permalink / raw) On Mon, 05 Nov 2001 17:42:14 GMT, "Warren W. Gay VE3WWG" <ve3wwg@home.com> wrote: >I think one of the issues at stake here is that Ada was meant to be > >easy to read. If you allow procedures to return values, then it is >no longer a valid assumption that what looks like a function call, >does not produce side effects (ie. you cannot assume that the arguments >are not modified, without looking at the declaration). Why something that looks like a call returning a result should have no side effects? There are two completely different and independent properties of a subroutine: a) It does not modify arguments b) It returns a result What we have in Ada is: subroutine is a function => a & b subroutine is a procedure => not b Now the question, why on Earth b=>a? >To pull it off, you'd have to make some sort of syntactical difference > >in procedure-function calls, to maintain the status quo for functions. >In case I am not explaining this clear enough, the following example >might help: > >declare > Arg : Boolean; -- Argument > R : Boolean; -- Result >begin > > R := My_Function(Arg); -- Assumed that Arg is not modified > R := My_Proc_Function[Arg]; -- A procedure returning.. identified by [] > >I am not suggesting the [] make a good syntax here, but you'd have >to do something like this to maintain the distinction that Functions >already enjoy within Ada. Seems like Hungarian notation reincarnation. It is IMO a wrong idea. All that a user should know about a subroutine is its contract. The parameter mode is a part of the contract. When a user do not want (in your example) Arg to be modified, he/she must simply say it by declaring Arg constant, which would make the second call illegal. Regards, Dmitry Kazakov ^ permalink raw reply [flat|nested] 166+ messages in thread
* Re: Side-Effects in Functions [Rosen Trick] 2001-11-06 8:38 ` Dmitry A. Kazakov @ 2001-11-06 9:31 ` tgingold 0 siblings, 0 replies; 166+ messages in thread From: tgingold @ 2001-11-06 9:31 UTC (permalink / raw) In article <3be79e7c.551796@News.CIS.DFN.DE>, Dmitry A. Kazakov wrote: > On Mon, 05 Nov 2001 17:42:14 GMT, "Warren W. Gay VE3WWG" ><ve3wwg@home.com> wrote: > >>I think one of the issues at stake here is that Ada was meant to be >> >>easy to read. If you allow procedures to return values, then it is >>no longer a valid assumption that what looks like a function call, >>does not produce side effects (ie. you cannot assume that the arguments >>are not modified, without looking at the declaration). Just for your information, VHDL-93 has PURE and IMPURE keyword. Such a declaration: pure function sum (a,b : integer) return integer; means that SUM has no side effects (and therefore is expected to return the same result when the set of argument is the same). However, INOUT and OUT mode are not allowed in IMPURE FUNCTION. Note also that return a value is *VERY* different from an OUT parameter, since the return type can be unconstrained. Tristan. ^ permalink raw reply [flat|nested] 166+ messages in thread
* Re: Side-Effects in Functions [Rosen Trick] 2001-11-05 10:29 ` Dmitry A. Kazakov 2001-11-05 11:19 ` pete @ 2001-11-06 0:10 ` Nick Roberts 2001-11-06 9:30 ` Dmitry A. Kazakov 2001-11-06 20:08 ` Side-Effects in Functions [Rosen Trick] Florian Weimer 1 sibling, 2 replies; 166+ messages in thread From: Nick Roberts @ 2001-11-06 0:10 UTC (permalink / raw) "Dmitry A. Kazakov" <dmitry@elros.cbb-automation.de> wrote in message news:3be666fe.6426140@News.CIS.DFN.DE... > On 4 Nov 2001 23:26:03 -0800, pete@nospam <pete_member@newsguy.com> > wrote: > > >functions, in the mathemtical sense, do not accept an IN OUT paramters, > >and do not have side effects. > > > >y=f(x), x here can never be modified by the function f(). > > > >so, Ada function is more like a math function. From a pedagogical point of view, care needs to be taken not to give the impression that a function in a procedural programming language (most programming languages, really) is the same thing as a mathematical function. Clearly it isn't: a mathematical function is a kind of relation called a 'bijection' (and is nowadays specifically defined as such, I think); a programming function is really just an encapsulated computation. Nevertheless, because a great many (practically useful) computations are, in fact, essentially to work out the mapping represented by a mathematical function from one value to another, it has become idiomatic to call these computations functions. Classic examples include such functions as sin, cos, and tan. Since the computations involve no side-effects, they neatly fit the 'no side-effects' model for programming functions. > No function in a programming language may have no side effects. One > could say that there are side effects which are of no interest, but no > more than that. I think, perhaps, that depends on precisely how you define a side-effect. If you include modification of registers or memory as side-effects, then it's true. However, we are only interested in side-effects in which we are interested! > The discussion about in out parameters is proved to be evergreen > (:-)). But what I presonally cannot understand is why not to allow > PROCEDUREs having a result, i.e. > > procedure Find (Folder : in out Table) return Table_Token; > > procedure GetNext (Item_List : in out Iterator) return Element; It would be pointless to have value-returning procedures in Ada. The reason why is because procedures of this kind would suffer from precisely the same dangers as functions (and would therefore be of no benefit over functions). I'm going to spell out the problems with side-effects in functions, so that (hopefully) everyone will be aware of them. Ada (like many procedural languages) permits compilers to evaluate the arguments of a function call in any order it chooses. (Obviously we are talking about a functions with more than one parameter here.) The arguments to this function call could be other function calls (nested within). For example: A := B(C(E),D(E)); B, C, and D are all functions. First, the compiler will compile code to evaluate E, then it will compile code to evaluate (call) C and D, and then finally code that evaluates (calls) B, passing in the results from C and D. The code calling C may come before or after the code calling D: it is the choice of the compiler. Now, suppose B, C, and D all have a side-effect when called: they print their name onto a log file. The result on the log file of compiling and executing this line of code with one compiler could be "C D B", but with another compiler it could be "D C B". You have the self-same program, compiled on two perfectly correct and compliant compilers, doing two different things. The two different behaviours may seem innocuous in the above example, but consider this example, adapted from a real-life situation: Header := Decode(Data(1..4)) & Decode(Data(5..8)); The Decode function was really a pseudo-random number generator, but it used the values it generated to decode an encrypted message. It used a global variable for its state, which had to be seeded with the correct encryption key; its side-effect was to update this state. Each 'chunk' that it decoded had to be 4 bytes long. The header of a certain message format was 8 bytes long, so we passed it into Decode in two 4-byte chunks, as shown. This code worked fine for us, but half-way through the project we changed compilers, and suddenly it stopped working. Nobody had altered the code. Recriminations flew. Can you see what had happened? Answer: the first compiler evaluated Decode(Data(1..4)) first, and Decode(Data(5..8)) second. So the first decryption value generated (at that point in the program) by Decode was used on Data(1..4) first, and the second on Data(5..8); the second compiler did it the other way around (as it was perfectly entitled to do, since the two calls to Decode are the two arguments of a call to "&"). If we had declared Decode as a procedure instead, and then written: Decode(Data(1..4),Header(1..4)); Decode(Data(5..8),Header(5..8)); this bizarre and mystifying problem would never had occurred (and a certain blameless manager -- not myself, I was a junior at the time -- would probably not had been sacked). Side-effects can be programmed into functions quite safely, if you know what you're doing. As a rule of thumb, either: (a) diligently ensure that the side-effect can't possibly cause a (significant) problem due to an 'order-of-evaluation dependency', or (b) remove the side-effect. Typically, the easiest way to remove a side-effect from a function is to turn the function into a procedure. I hope I've convinced any doubters, at this point. If you're still not sure, just trust your uncle Nicky, eh? -- Nick Roberts ^ permalink raw reply [flat|nested] 166+ messages in thread
* Re: Side-Effects in Functions [Rosen Trick] 2001-11-06 0:10 ` Nick Roberts @ 2001-11-06 9:30 ` Dmitry A. Kazakov 2001-11-06 16:18 ` Lazy Evaluation [Side-Effects in Functions] Nick Roberts 2001-11-06 20:08 ` Side-Effects in Functions [Rosen Trick] Florian Weimer 1 sibling, 1 reply; 166+ messages in thread From: Dmitry A. Kazakov @ 2001-11-06 9:30 UTC (permalink / raw) On Tue, 6 Nov 2001 00:10:31 -0000, "Nick Roberts" <nickroberts@adaos.worldonline.co.uk> wrote: >"Dmitry A. Kazakov" <dmitry@elros.cbb-automation.de> wrote in message >news:3be666fe.6426140@News.CIS.DFN.DE... >> On 4 Nov 2001 23:26:03 -0800, pete@nospam <pete_member@newsguy.com> >> wrote: >> >> >functions, in the mathemtical sense, do not accept an IN OUT paramters, >> >and do not have side effects. >> > >> >y=f(x), x here can never be modified by the function f(). >> > >> >so, Ada function is more like a math function. > >From a pedagogical point of view, care needs to be taken not to give the >impression that a function in a procedural programming language (most >programming languages, really) is the same thing as a mathematical function. >Clearly it isn't: a mathematical function is a kind of relation called a >'bijection' (and is nowadays specifically defined as such, I think); a >programming function is really just an encapsulated computation. > >Nevertheless, because a great many (practically useful) computations are, in >fact, essentially to work out the mapping represented by a mathematical >function from one value to another, it has become idiomatic to call these >computations functions. Classic examples include such functions as sin, cos, >and tan. Since the computations involve no side-effects, they neatly fit the >'no side-effects' model for programming functions. > >> No function in a programming language may have no side effects. One >> could say that there are side effects which are of no interest, but no >> more than that. > >I think, perhaps, that depends on precisely how you define a side-effect. If >you include modification of registers or memory as side-effects, then it's >true. However, we are only interested in side-effects in which we are >interested! It is a great problem to give a careful definition of side-effects. Ada follows rather a pragmatic view, side-effects are ones of arguments. Unfortunately this definition is too weak for correctness checks. Though I doubt that a correct definition exists. Just consider an assertion that includes absolute time! >> The discussion about in out parameters is proved to be evergreen >> (:-)). But what I presonally cannot understand is why not to allow >> PROCEDUREs having a result, i.e. >> >> procedure Find (Folder : in out Table) return Table_Token; >> >> procedure GetNext (Item_List : in out Iterator) return Element; > >It would be pointless to have value-returning procedures in Ada. The reason >why is because procedures of this kind would suffer from precisely the same >dangers as functions (and would therefore be of no benefit over functions). > >I'm going to spell out the problems with side-effects in functions, so that >(hopefully) everyone will be aware of them. > >Ada (like many procedural languages) permits compilers to evaluate the >arguments of a function call in any order it chooses. (Obviously we are >talking about a functions with more than one parameter here.) The arguments >to this function call could be other function calls (nested within). For >example: > > A := B(C(E),D(E)); > >B, C, and D are all functions. First, the compiler will compile code to >evaluate E, then it will compile code to evaluate (call) C and D, and then >finally code that evaluates (calls) B, passing in the results from C and D. >The code calling C may come before or after the code calling D: it is the >choice of the compiler. > >Now, suppose B, C, and D all have a side-effect when called: they print >their name onto a log file. The result on the log file of compiling and >executing this line of code with one compiler could be "C D B", but with >another compiler it could be "D C B". You have the self-same program, >compiled on two perfectly correct and compliant compilers, doing two >different things. > >The two different behaviours may seem innocuous in the above example, but >consider this example, adapted from a real-life situation: > > Header := Decode(Data(1..4)) & Decode(Data(5..8)); > >The Decode function was really a pseudo-random number generator, but it used >the values it generated to decode an encrypted message. It used a global >variable for its state, which had to be seeded with the correct encryption >key; its side-effect was to update this state. Each 'chunk' that it decoded >had to be 4 bytes long. > >The header of a certain message format was 8 bytes long, so we passed it >into Decode in two 4-byte chunks, as shown. This code worked fine for us, >but half-way through the project we changed compilers, and suddenly it >stopped working. Nobody had altered the code. Recriminations flew. Can you >see what had happened? > >Answer: the first compiler evaluated Decode(Data(1..4)) first, and >Decode(Data(5..8)) second. So the first decryption value generated (at that >point in the program) by Decode was used on Data(1..4) first, and the second >on Data(5..8); the second compiler did it the other way around (as it was >perfectly entitled to do, since the two calls to Decode are the two >arguments of a call to "&"). > >If we had declared Decode as a procedure instead, and then written: > > Decode(Data(1..4),Header(1..4)); > Decode(Data(5..8),Header(5..8)); > >this bizarre and mystifying problem would never had occurred (and a certain >blameless manager -- not myself, I was a junior at the time -- would >probably not had been sacked). > >Side-effects can be programmed into functions quite safely, if you know what >you're doing. As a rule of thumb, either: (a) diligently ensure that the >side-effect can't possibly cause a (significant) problem due to an >'order-of-evaluation dependency', or (b) remove the side-effect. > >Typically, the easiest way to remove a side-effect from a function is to >turn the function into a procedure. > >I hope I've convinced any doubters, at this point. If you're still not sure, >just trust your uncle Nicky, eh? The above is of course correct. Perhaps everybody enjoyed things like that at least once [lucky ones did it several times (:-))] Yet it proves nothing more than if you have side-effects then, well, there are side-effects. Side-effects are bad, dangerous, nasty,... but sometimes necessary. Then, can Ada's functions prevent users from writting things like above? The answer is no. P.S. A comment about computation order. I am not sure, but maybe it would be worth to think about introducing lazy parameters (Algol's by name). Ada already has them hard-wired in "and then" and "or else". The order lazy parameters are evaluated is obviously defined by the implementation of the subroutine, thus the above problems will disappear, or better to say, become the responsibility of the implementation. In your example "&" should have the second parameter lazy, so Decode(Data(1..4)) & Decode(Data(5..8)); would mean: evaluate Decode(Data(1..4)); call "&", which internally calls Decode(Data(5..8)). Regards, Dmitry Kazakov ^ permalink raw reply [flat|nested] 166+ messages in thread
* Lazy Evaluation [Side-Effects in Functions] 2001-11-06 9:30 ` Dmitry A. Kazakov @ 2001-11-06 16:18 ` Nick Roberts 2001-11-07 3:42 ` Robert Dewar 2001-11-07 9:28 ` Dmitry A. Kazakov 0 siblings, 2 replies; 166+ messages in thread From: Nick Roberts @ 2001-11-06 16:18 UTC (permalink / raw) "Dmitry A. Kazakov" <dmitry@elros.cbb-automation.de> wrote in message news:3be7a31d.1736453@News.CIS.DFN.DE... above? The answer is no. > ... > P.S. A comment about computation order. I am not sure, but maybe it > would be worth to think about introducing lazy parameters (Algol's by > name). Ada already has them hard-wired in "and then" and "or else". > The order lazy parameters are evaluated is obviously defined by the > implementation of the subroutine, thus the above problems will > disappear, or better to say, become the responsibility of the > implementation. In your example "&" should have the second parameter > lazy, so > > Decode(Data(1..4)) & Decode(Data(5..8)); > > would mean: evaluate Decode(Data(1..4)); call "&", which internally > calls Decode(Data(5..8)). Briefly, the combination of lazy evaluation and side-effects, as such, would be rather like the combination of a keg of TNT and a blowtorch. The problem of side-effects in Ada would be largely solved by fixing the order in which arguments are evaluated (e.g. strictly in the order they are declared) for all functions. But this would be a pity in that it would significantly hamper many compilers' efforts to optimise a lot of ordinary code. Lazy evaluation is an interesting idea. How about: function Sin (X: delay in Float) return Float; where the 'delay' means that what is passed into Sin is an access value to a temporary routine (X'Computation) that computes the required value of X. In the body of Sin, a flag X'Computed is set False, and any reference to X either: if X'Computed is False, causes a call to the temporary routine, places the result into a temporary store for X, and sets X'Computed to True; if X'Computed is True, retrieves the value of X from its temporary store. Hey presto! Lazy evaluation. "and then" and "or else" could become first class citizens. The access value X'Computation would be subject to the same accessibility rules as any other access (-to-subprogram) value. This business is, I guess, closely related to that of lambdas etc. I not actually saying that I like this idea, by the way, just that it's intriguing. -- Nick Roberts ^ permalink raw reply [flat|nested] 166+ messages in thread
* Re: Lazy Evaluation [Side-Effects in Functions] 2001-11-06 16:18 ` Lazy Evaluation [Side-Effects in Functions] Nick Roberts @ 2001-11-07 3:42 ` Robert Dewar 2001-11-07 4:42 ` Darren New 2001-11-07 9:28 ` Dmitry A. Kazakov 1 sibling, 1 reply; 166+ messages in thread From: Robert Dewar @ 2001-11-07 3:42 UTC (permalink / raw) "Nick Roberts" <nickroberts@adaos.worldonline.co.uk> wrote > Briefly, the combination of lazy evaluation > and side-effects, as such, would > be rather like the combination of a keg of TNT and a > blowtorch. Well yes, of course this is a text book answer, but in fact we are not talking about lazy evaluation here, but rather call by name (referring to call by name as lazy evaluation is a recipe for confusion). Of course there is no particular conflict between side effects and call by name, as anyone who has programmed in Algol-60 extensively is perfectly aware. ^ permalink raw reply [flat|nested] 166+ messages in thread
* Re: Lazy Evaluation [Side-Effects in Functions] 2001-11-07 3:42 ` Robert Dewar @ 2001-11-07 4:42 ` Darren New 2001-11-07 11:54 ` Robert Dewar 0 siblings, 1 reply; 166+ messages in thread From: Darren New @ 2001-11-07 4:42 UTC (permalink / raw) Robert Dewar wrote: > Of course there is no particular conflict between side > effects and call by name, as anyone who has programmed > in Algol-60 extensively is perfectly aware. Uh, unless you do something like Swap(A(I), I) (where A is an array, of course) -- 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] 166+ messages in thread
* Re: Lazy Evaluation [Side-Effects in Functions] 2001-11-07 4:42 ` Darren New @ 2001-11-07 11:54 ` Robert Dewar 2001-11-07 13:32 ` Florian Weimer 2001-11-09 18:06 ` Ted Dennison 0 siblings, 2 replies; 166+ messages in thread From: Robert Dewar @ 2001-11-07 11:54 UTC (permalink / raw) Darren New <dnew@san.rr.com> wrote in message news:<3BE8BBC2.A8563DBD@san.rr.com>... > Robert Dewar wrote: > > Of course there is no particular conflict between side > > effects and call by name, as anyone who has programmed > > in Algol-60 extensively is perfectly aware. > > Uh, unless you do something like > Swap(A(I), I) > (where A is an array, of course) Well yes, we all know Algol-60! (or at least I hope any serious student of programming languages does). But there is no special problem here. In Algol-60, the effect will be canonical, depending on the exact order of statements in the body. Sure, it might not do what the programmer expects in this case, but it will do EXACTLY what the programmer programmed. No language can avoid this discrepancy in all cases. Are you arguing that in practice call-by-name is troublesome for this reason? I think that's a bogus argument. I certainly never found it to be the case in my Algol-60 programming days, how about you? Note that in Ada, simple out parameters generate similar concerns, except that the result is *not* canonical, if you do x (m.m) when x has two out parameters, the order in which things get assigned is undefined in Ada. ^ permalink raw reply [flat|nested] 166+ messages in thread
* Re: Lazy Evaluation [Side-Effects in Functions] 2001-11-07 11:54 ` Robert Dewar @ 2001-11-07 13:32 ` Florian Weimer 2001-11-07 13:24 ` Jean-Marc Bourguet 2001-11-09 18:06 ` Ted Dennison 1 sibling, 1 reply; 166+ messages in thread From: Florian Weimer @ 2001-11-07 13:32 UTC (permalink / raw) dewar@gnat.com (Robert Dewar) writes: >> Uh, unless you do something like >> Swap(A(I), I) >> (where A is an array, of course) > > Well yes, we all know Algol-60! (or at least I hope any > serious student of programming languages does). But there > is no special problem here. In Algol-60, the effect will be canonical, > depending on the exact order of statements in the body. Even if you use two temporary variables instead of a single one (which is more usual, but in this case, the implementation hardly reflects the symmetry of the operation)? ^ permalink raw reply [flat|nested] 166+ messages in thread
* Re: Lazy Evaluation [Side-Effects in Functions] 2001-11-07 13:32 ` Florian Weimer @ 2001-11-07 13:24 ` Jean-Marc Bourguet 0 siblings, 0 replies; 166+ messages in thread From: Jean-Marc Bourguet @ 2001-11-07 13:24 UTC (permalink / raw) Florian Weimer <fw@deneb.enyo.de> writes: > dewar@gnat.com (Robert Dewar) writes: > > >> Uh, unless you do something like > >> Swap(A(I), I) > >> (where A is an array, of course) > > > > Well yes, we all know Algol-60! (or at least I hope any > > serious student of programming languages does). But there > > is no special problem here. In Algol-60, the effect will be canonical, > > depending on the exact order of statements in the body. > > Even if you use two temporary variables instead of a single one (which > is more usual, but in this case, the implementation hardly reflects > the symmetry of the operation)? Swap(I, A(I)) -- Jean-Marc ^ permalink raw reply [flat|nested] 166+ messages in thread
* Re: Lazy Evaluation [Side-Effects in Functions] 2001-11-07 11:54 ` Robert Dewar 2001-11-07 13:32 ` Florian Weimer @ 2001-11-09 18:06 ` Ted Dennison 2001-11-09 18:27 ` M. A. Alves 2001-11-11 20:13 ` Georg Bauhaus 1 sibling, 2 replies; 166+ messages in thread From: Ted Dennison @ 2001-11-09 18:06 UTC (permalink / raw) In article <5ee5b646.0111070354.55494ec2@posting.google.com>, Robert Dewar says... >Well yes, we all know Algol-60! (or at least I hope any >serious student of programming languages does). But there I have to say I don't, and unless there's a free PC implmentation floating around somewhere, that's not liable to change. I may have learned some stuff about it indirectly, but I won't say I "know" a language unless I've used it at least a little. So it seems you permanently restricting the set of "serious students of programming languages" to folks who were around when Algol-60 compilers were commonly available. --- 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] 166+ messages in thread
* Re: Lazy Evaluation [Side-Effects in Functions] 2001-11-09 18:06 ` Ted Dennison @ 2001-11-09 18:27 ` M. A. Alves 2001-11-11 20:13 ` Georg Bauhaus 1 sibling, 0 replies; 166+ messages in thread From: M. A. Alves @ 2001-11-09 18:27 UTC (permalink / raw) To: comp.lang.ada On Fri, 9 Nov 2001, Ted Dennison wrote: > In article <5ee5b646.0111070354.55494ec2@posting.google.com>, Robert Dewar > says... > >Well yes, we all know Algol-60! (or at least I hope any > >serious student of programming languages does). But there > > I have to say I don't, and unless there's a free PC implmentation floating > around somewhere, that's not liable to change. I may have learned some stuff > about it indirectly, but I won't say I "know" a language unless I've used it at > least a little. > > So it seems you permanently restricting the set of "serious students of > programming languages" to folks who were around when Algol-60 compilers were > commonly available. Yes. Well, I am sure Dewar was not expecting such _practical_ knowledge of Algol from all such students ;-) -- , 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] 166+ messages in thread
* Re: Lazy Evaluation [Side-Effects in Functions] 2001-11-09 18:06 ` Ted Dennison 2001-11-09 18:27 ` M. A. Alves @ 2001-11-11 20:13 ` Georg Bauhaus 2001-12-06 17:47 ` Harri J Haataja 1 sibling, 1 reply; 166+ messages in thread From: Georg Bauhaus @ 2001-11-11 20:13 UTC (permalink / raw) Ted Dennison <dennison@telepath.com> wrote: : In article <5ee5b646.0111070354.55494ec2@posting.google.com>, Robert Dewar : says... : : there's a free PC implmentation floating : around somewhere, http://packages.debian.org/stable/interpreters/nase-a60.html georg ^ permalink raw reply [flat|nested] 166+ messages in thread
* Re: Lazy Evaluation [Side-Effects in Functions] 2001-11-11 20:13 ` Georg Bauhaus @ 2001-12-06 17:47 ` Harri J Haataja 0 siblings, 0 replies; 166+ messages in thread From: Harri J Haataja @ 2001-12-06 17:47 UTC (permalink / raw) Georg Bauhaus wrote: >Ted Dennison <dennison@telepath.com> wrote: >: In article <5ee5b646.0111070354.55494ec2@posting.google.com>, Robert Dewar >: says... >: >: there's a free PC implmentation floating >: around somewhere, > >http://packages.debian.org/stable/interpreters/nase-a60.html $ grep MAST /export/pkgsrc/lang/a60/Makefile MASTER_SITES= ftp://ftp.ibr.cs.tu-bs.de/pub/local/algol60/ The real address might be that. -- Seagoon: Will my aeroplane need a hangar? Crun: It'd lose its shape hanging on a nail, you know. -- T.A.Milligan & L.Stephens 10 Jan 1957 ^ permalink raw reply [flat|nested] 166+ messages in thread
* Re: Lazy Evaluation [Side-Effects in Functions] 2001-11-06 16:18 ` Lazy Evaluation [Side-Effects in Functions] Nick Roberts 2001-11-07 3:42 ` Robert Dewar @ 2001-11-07 9:28 ` Dmitry A. Kazakov 1 sibling, 0 replies; 166+ messages in thread From: Dmitry A. Kazakov @ 2001-11-07 9:28 UTC (permalink / raw) On Tue, 6 Nov 2001 16:18:12 -0000, "Nick Roberts" <nickroberts@adaos.worldonline.co.uk> wrote: >"Dmitry A. Kazakov" <dmitry@elros.cbb-automation.de> wrote in message >news:3be7a31d.1736453@News.CIS.DFN.DE... >above? The answer is no. >> ... >> P.S. A comment about computation order. I am not sure, but maybe it >> would be worth to think about introducing lazy parameters (Algol's by >> name). Ada already has them hard-wired in "and then" and "or else". >> The order lazy parameters are evaluated is obviously defined by the >> implementation of the subroutine, thus the above problems will >> disappear, or better to say, become the responsibility of the >> implementation. In your example "&" should have the second parameter >> lazy, so >> >> Decode(Data(1..4)) & Decode(Data(5..8)); >> >> would mean: evaluate Decode(Data(1..4)); call "&", which internally >> calls Decode(Data(5..8)). > >Briefly, the combination of lazy evaluation and side-effects, as such, would >be rather like the combination of a keg of TNT and a blowtorch. > >The problem of side-effects in Ada would be largely solved by fixing the >order in which arguments are evaluated (e.g. strictly in the order they are >declared) for all functions. But this would be a pity in that it would >significantly hamper many compilers' efforts to optimise a lot of ordinary >code. Yes. Then fixing the order does not solve another problem of side-effects: when same objects are visible through different arguments. The problem is of course in-out parameters per se. To the list of their "crimes": LSP violation by generalization or specialization; interesting effects in by-value vs. by-reference parameter passing etc. >Lazy evaluation is an interesting idea. How about: > > function Sin (X: delay in Float) return Float; > >where the 'delay' means that what is passed into Sin is an access value to a >temporary routine (X'Computation) that computes the required value of X. In >the body of Sin, a flag X'Computed is set False, and any reference to X >either: if X'Computed is False, causes a call to the temporary routine, >places the result into a temporary store for X, and sets X'Computed to True; >if X'Computed is True, retrieves the value of X from its temporary store. >Hey presto! Lazy evaluation. "and then" and "or else" could become first >class citizens. Something like this. Maybe pragma Volatile (X) should ensure that X is computed each time it is accessed. Otherwise, X is computed only once. Then (a crazy idea), it would be nice to have an ability for a lazy parameter to evaluate discriminants (and type tags) separately from the value. I do not know whether it possible, but it could solve the "problem of measurement units". The type of dimensioned values will have a discriminant specifying the unit of measure. Being static (in most cases) it can be evaluated statically (for inlined subroutines), thus units checks can be efficiently removed by the compiler. >The access value X'Computation would be subject to the same accessibility >rules as any other access (-to-subprogram) value. This business is, I guess, >closely related to that of lambdas etc. > >I not actually saying that I like this idea, by the way, just that it's >intriguing. It would be a dangerous stuff in right hands (:-)). Then I think to get pragma Inlined working efficiently for subroutines with lazy parameters would be not very easy. Regards, Dmitry Kazakov ^ permalink raw reply [flat|nested] 166+ messages in thread
* Re: Side-Effects in Functions [Rosen Trick] 2001-11-06 0:10 ` Nick Roberts 2001-11-06 9:30 ` Dmitry A. Kazakov @ 2001-11-06 20:08 ` Florian Weimer 2001-11-06 22:48 ` Nick Roberts 1 sibling, 1 reply; 166+ messages in thread From: Florian Weimer @ 2001-11-06 20:08 UTC (permalink / raw) "Nick Roberts" <nickroberts@adaos.worldonline.co.uk> writes: > From a pedagogical point of view, care needs to be taken not to give the > impression that a function in a procedural programming language (most > programming languages, really) is the same thing as a mathematical function. > Clearly it isn't: a mathematical function is a kind of relation called a > 'bijection' (and is nowadays specifically defined as such, I think); A function f : M -> N are two sets M, N and a subset G_f of the Cartesian product M x N with the following property: for all m in M, there exists exactly one n in N such that (m, n) in G_f. > a programming function is really just an encapsulated computation. Yes, such functions take an additional implicit argument (the machine state before execution) and have an invisible result (the machine state after execution). However, there are programming languages which use only mathematical functions, and a special construct for I/O, Haskell for example. ^ permalink raw reply [flat|nested] 166+ messages in thread
* Re: Side-Effects in Functions [Rosen Trick] 2001-11-06 20:08 ` Side-Effects in Functions [Rosen Trick] Florian Weimer @ 2001-11-06 22:48 ` Nick Roberts 2001-11-07 10:46 ` Florian Weimer 0 siblings, 1 reply; 166+ messages in thread From: Nick Roberts @ 2001-11-06 22:48 UTC (permalink / raw) "Florian Weimer" <fw@deneb.enyo.de> wrote in message news:87itcn8xxx.fsf@deneb.enyo.de... > "Nick Roberts" <nickroberts@adaos.worldonline.co.uk> writes: > > > From a pedagogical point of view, care needs to be taken not to give the > > impression that a function in a procedural programming language (most > > programming languages, really) is the same thing as a mathematical function. > > Clearly it isn't: a mathematical function is a kind of relation called a > > 'bijection' (and is nowadays specifically defined as such, I think); > > A function f : M -> N are two sets M, N and a subset G_f of the > Cartesian product M x N with the following property: for all m in M, > there exists exactly one n in N such that (m, n) in G_f. That actually sounds like an injection to me (1 to 1), whereas I get the impression mathematicians (discrete ones anyway ;-) tend to insist nowadays on the definition of a function as a bijection (both 1 to 1 and 'onto', i.e. both an injection and a surjection, so that f' is also a bijection). However IANAM. > > a programming function is really just an encapsulated computation. > > Yes, such functions take an additional implicit argument (the machine > state before execution) and have an invisible result (the machine > state after execution). Neatly put. Of course, if the (programming) function might perform I/O, we are potentially talking about 'world state' (or even 'universe state') rather than just machine state! (And then we have the problem with enthalpy, but that, as they say, is a different game of banana and clotted cream.) > However, there are programming languages which use only mathematical > functions, and a special construct for I/O, Haskell for example. I'm not a Haskell expert, but functional languages in general do fix the order of evaluation of their functions (or some of their functions) precisely because of the side-effect problem. I presume lazy evaluation can be a serious hazard, if used without care, nevertheless. -- Nick Roberts ^ permalink raw reply [flat|nested] 166+ messages in thread
* Re: Side-Effects in Functions [Rosen Trick] 2001-11-06 22:48 ` Nick Roberts @ 2001-11-07 10:46 ` Florian Weimer 0 siblings, 0 replies; 166+ messages in thread From: Florian Weimer @ 2001-11-07 10:46 UTC (permalink / raw) "Nick Roberts" <nickroberts@adaos.worldonline.co.uk> writes: > "Florian Weimer" <fw@deneb.enyo.de> wrote in message > news:87itcn8xxx.fsf@deneb.enyo.de... >> "Nick Roberts" <nickroberts@adaos.worldonline.co.uk> writes: >> >> > From a pedagogical point of view, care needs to be taken not to give the >> > impression that a function in a procedural programming language (most >> > programming languages, really) is the same thing as a mathematical > function. >> > Clearly it isn't: a mathematical function is a kind of relation called a >> > 'bijection' (and is nowadays specifically defined as such, I think); >> >> A function f : M -> N are two sets M, N and a subset G_f of the >> Cartesian product M x N with the following property: for all m in M, >> there exists exactly one n in N such that (m, n) in G_f. > > That actually sounds like an injection to me (1 to 1), Actually, it's many to one. The uniqueness constraint is only there to ensure that for each value m in M, there is only one value of the function at m (usually denoted by "f(m)" or "m f", if you write functions from the right). > whereas I get the impression mathematicians (discrete ones anyway > ;-) tend to insist nowadays on the definition of a function as a > bijection (both 1 to 1 and 'onto', i.e. both an injection and a > surjection, so that f' is also a bijection). I've yet to meet a mathematician who claims that functions are always bijective. Quite the contrary, in almost all the set-based categories I've seen so far, morphisms weren't generally bijective. >> However, there are programming languages which use only mathematical >> functions, and a special construct for I/O, Haskell for example. > > I'm not a Haskell expert, but functional languages in general do fix the > order of evaluation of their functions (or some of their functions) > precisely because of the side-effect problem. Haskell functions do not have side effects. Side effects are introduced by a special construct call a "monad", which essentially introduces explicit machine state parameters. There's a construct ("do") which makes them implicit again, too. > I presume lazy evaluation can be a serious hazard, if used without > care, nevertheless. Lazy evaluation is a nice thing, as long as functions have no side effects. ^ permalink raw reply [flat|nested] 166+ messages in thread
* Re: Side-Effects in Functions [Rosen Trick] 2001-11-05 7:26 ` pete 2001-11-05 10:29 ` Dmitry A. Kazakov @ 2001-11-05 13:56 ` Robert Dewar 2001-11-05 16:08 ` Ted Dennison 1 sibling, 1 reply; 166+ messages in thread From: Robert Dewar @ 2001-11-05 13:56 UTC (permalink / raw) pete@nospam <pete_member@newsguy.com> wrote in message news:<9s5eub02j61@drn.newsguy.com>... > functions, in the mathemtical sense, do not accept an IN OUT paramters, > and do not have side effects. > > y=f(x), x here can never be modified by the function f(). > > so, Ada function is more like a math function. Yes of course, that is the naive view that might be taught in a beginning course, but it is bogus. Sure, Ada functions can be used to model mathematical functions, that's true in any case, but Ada functions are not a bit like math functions. Mathematical functions cannot take pointer arguments allowing modification of the calling variable, mathematical functions cannot generate output on files, mathematical functions cannot modify global variables. Mathematical functions are very restrictive, and the language makes no attempt to limit the semantics to functions that have some sensible meaning as mathematical functions. That's the whole point here. Functions in Ada DO allow side effects quite freely, and what seems odd is the Ada rule in this case: Functions are allowed to have side effects, providing that there is no trace of this in the function specification :-) The real issue here, and the point at which this becomes significant, is that we use functions in Ada for interfacing to foreign languages and there the restriction is quite onerous, as anyone who has designed bindings to C knows. Yes, access parameters help, but the requirement that access parameters be non-null means that this usage often is inapplicable. For an example of functions that modify their parameters, which is in fact possible in GNAT in some cases, using implementation dependent features, see gnat.spitbol.patterns (g-spipat.ads). Here the goal was to model SNOBOL-4 style as closely as possible, and in some cases, functions modifying their parameters lead to the most natural usage from a SNOBOL-4 point of view. Since the point of this package is to assist in translation of existing SNOBOL-4 programs, stylistic considerations are significant. If (important criterion) you are familiar with SNOBOL4, feel free to suggest other approaches that would avoid this usage, I didn't find anything as convenient, and would have preferred being able to program this in a more direct manner. ^ permalink raw reply [flat|nested] 166+ messages in thread
* Re: Side-Effects in Functions [Rosen Trick] 2001-11-05 13:56 ` Robert Dewar @ 2001-11-05 16:08 ` Ted Dennison 2001-11-05 17:44 ` Warren W. Gay VE3WWG 0 siblings, 1 reply; 166+ messages in thread From: Ted Dennison @ 2001-11-05 16:08 UTC (permalink / raw) In article <5ee5b646.0111050556.1f9137ff@posting.google.com>, Robert Dewar says... > >The real issue here, and the point at which this becomes >significant, is that we use functions in Ada for interfacing to >foreign languages and there the restriction >is quite onerous, as anyone who has designed bindings to >C knows. Yes, access parameters help, but the requirement >that access parameters be non-null means that this usage >often is inapplicable. Actually access parameters are next to useless in C bindings for that very reason. However this isn't a huge issue with C bindings, as C has no "out" parameters in functions either. At *worst*, you have to do what C coders have to do: use pointers. If you lie down with dogs, you are going to get up with fleas. :-) --- 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] 166+ messages in thread
* Re: Side-Effects in Functions [Rosen Trick] 2001-11-05 16:08 ` Ted Dennison @ 2001-11-05 17:44 ` Warren W. Gay VE3WWG 0 siblings, 0 replies; 166+ messages in thread From: Warren W. Gay VE3WWG @ 2001-11-05 17:44 UTC (permalink / raw) Ted Dennison wrote: > In article <5ee5b646.0111050556.1f9137ff@posting.google.com>, Robert Dewar > says... ... > However this isn't a huge issue with C bindings, as C has no "out" parameters in > functions either. At *worst*, you have to do what C coders have to do: use > pointers. If you lie down with dogs, you are going to get up with fleas. :-) You may also "smell like dogs" ;-) -- Warren W. Gay VE3WWG http://home.cogeco.ca/~ve3wwg ^ permalink raw reply [flat|nested] 166+ messages in thread
* Re: Side-Effects in Functions [Rosen Trick] 2001-11-05 2:46 ` Robert Dewar 2001-11-05 7:26 ` pete @ 2001-11-05 15:56 ` Ted Dennison 2001-11-05 18:46 ` Nick Roberts 2 siblings, 0 replies; 166+ messages in thread From: Ted Dennison @ 2001-11-05 15:56 UTC (permalink / raw) In article <5ee5b646.0111041846.93f3e07@posting.google.com>, Robert Dewar says... >No, this is by no means a consensus. Most procedural >languages, including Ada, allow functions to have side >effects. And on the narrower issue of allowing IN OUT C actually does not allow "OUT" parameters in functions either. In fact its even worse than Ada here, in that it doesn't have procedures either, so there is *no* language-defined way to pass values out through a paramter. I does allow one to get around this restriction using pointers, but then so does Ada. >Most people feel that being forced to add aliased keywords >all over the place, just because of odd interfacing requirements for C >functions, is unfortunate. If you find Any C interfacing code is going to be somewhat ugly, not due to any failing in Ada, just because C *is* ugly. That's why "most people" I talk to prefer thick C bindings, to localize the uglyness. Now all this being said, I am beginning to come around to your point of view. Perhaps value-returning procedures should be reconsidered for the next Ada rev? That would let folks keep their no (visible) side-effect functions. I'm also beginning to think that some rethinking needs to be done about Ada's whole parameter-passing scheme. It works well for public types, but blows for private types. For a private type, its quite possible for me to not want to change the users' view of a parameter, but to want to change some internal data in it (eg: cache a location in a structure to speed up the next access if it is liable to be nearby). Labelling such parameters as "in out" misleads the clients (and not so incidentally, prevents use of functions). I'm getting really tired of the gymnastics the language makes me go through to do this. Rosen trick aside, there ought to be a way to specify certian portions of a private record and tagged types as "internal", and thus always updatatable. --- 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] 166+ messages in thread
* Re: Side-Effects in Functions [Rosen Trick] 2001-11-05 2:46 ` Robert Dewar 2001-11-05 7:26 ` pete 2001-11-05 15:56 ` Ted Dennison @ 2001-11-05 18:46 ` Nick Roberts 2001-11-08 11:51 ` Georg Bauhaus 2 siblings, 1 reply; 166+ messages in thread From: Nick Roberts @ 2001-11-05 18:46 UTC (permalink / raw) Just briefly, because I don't want to waste any more of my time on this, I'm not entirely sure whether Robert is being serious, or is just arguing for the fun of it (or something). As to the issue of whether Ada should permit in-out parameters in functions, I hold no strong opinion, and my original point had nothing to do with this. Maybe it would be a nice idea, but you can always use a procedure instead; no big deal. The 'problems' cited by various people about using access parameters for interfacing with C functions are silly: if you need to be able to pass a null value, you use an access type (and pass it in as an 'in' parameter); again, no big deal. On whether it is good practice to program functions with side-effects, in a procedural language which doesn't specify the order in which the arguments of functions are evaluated (such as Ada), I hold the very strong opinion that it is generally not, for the perfectly rational, and well-established, reason that it can introduce subtle and pernicious bugs. Robert has said absolutely nothing to refute this. Twisting the argument between what can and should be done may be a clever rhetorical technique, but it isn't good science. -- Nick Roberts ^ permalink raw reply [flat|nested] 166+ messages in thread
* Re: Side-Effects in Functions [Rosen Trick] 2001-11-05 18:46 ` Nick Roberts @ 2001-11-08 11:51 ` Georg Bauhaus 0 siblings, 0 replies; 166+ messages in thread From: Georg Bauhaus @ 2001-11-08 11:51 UTC (permalink / raw) Nick Roberts <nickroberts@adaos.worldonline.co.uk> wrote: : On whether it is good practice to program functions with side-effects, Well, that's it, then? If your opinion is that strong, maybe you should really give Haskell a chance. Also, I've found Paulson's remarks on the issue (in an early chapter of his ML book) instructive. (But then I am not someone with an abundance of languages and their compilation techniques in his head, like others here, but I seem to recall that this subject has been debated for decades?) Georg ^ permalink raw reply [flat|nested] 166+ messages in thread
* Re: List container strawman 2001-11-03 2:21 ` Jeffrey Carter 2001-11-03 22:51 ` Rosen Trick [List container strawman] Nick Roberts @ 2001-11-16 0:31 ` Vincent Marciante 1 sibling, 0 replies; 166+ 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] 166+ 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; 166+ 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] 166+ 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; 166+ 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] 166+ 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; 166+ 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] 166+ 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; 166+ 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] 166+ 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; 166+ 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] 166+ 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; 166+ 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] 166+ 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; 166+ 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] 166+ 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; 166+ 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] 166+ 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; 166+ 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] 166+ 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; 166+ 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] 166+ 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; 166+ 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] 166+ 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; 166+ 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] 166+ 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; 166+ 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] 166+ 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-08 18:53 ` Better Finalisation [List container strawman] Nick Roberts 2001-11-09 14:49 ` List container strawman Ted Dennison 2 siblings, 2 replies; 166+ 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] 166+ messages in thread
* Better Finalisation [List container strawman] 2001-11-08 10:34 ` Ehud Lamm @ 2001-11-08 18:53 ` Nick Roberts 2001-11-09 13:36 ` Robert Dewar ` (2 more replies) 2001-11-09 14:49 ` List container strawman Ted Dennison 1 sibling, 3 replies; 166+ messages in thread From: Nick Roberts @ 2001-11-08 18:53 UTC (permalink / raw) "Ehud Lamm" <mslamm@mscc.huji.ac.il> wrote in message news:9sdnb2$dd4$1@news.huji.ac.il... > ... > 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. I am of this conclusion, as regards finalisation. It's not a criticism of the designers of Ada 95: it's so very easy to be wise when you have the benefit of hindsight, and I think we'd all agree that overall those designers did a superb job. However, it seems feasible to me to introduce a new finalisation mechanism in the next revision. All we really need (am I wrong?) is three attributes, applying to any type T, which are the procedures carried out whenever an object of the type is created, copied, and destroyed: procedure T'Construct (Object: in out T); procedure T'Destroy (Object: in out T); procedure T'Assign (Source, Target: in out T); These attributes would, naturally, have implementation-supplied defaults, but could be overidden by attribute definition clauses, as normal. Obviously Assign would not apply to a limited type. It would probably be best if none applied to a task or protected type. The exact details of when these procedures were called, etc., would be quite complex, but I think this is essentially all we need. As for storage pools, I think the existing design is fine. I would like to see the addition (in the next language revision) of a package declaring a type, derived from Root_Storage_Pool, which had extra operations better supporting full garbage collection. I posted something (maybe a little premature) about this a while back; perhaps I'll write a paper on the subject, or something. -- Nick Roberts ^ permalink raw reply [flat|nested] 166+ messages in thread
* Re: Better Finalisation [List container strawman] 2001-11-08 18:53 ` Better Finalisation [List container strawman] Nick Roberts @ 2001-11-09 13:36 ` Robert Dewar 2001-11-09 15:04 ` Florian Weimer 2001-11-10 0:36 ` Nick Roberts 2001-11-09 15:16 ` Ted Dennison 2001-11-09 17:30 ` Better control of assignment Jeffrey Carter 2 siblings, 2 replies; 166+ messages in thread From: Robert Dewar @ 2001-11-09 13:36 UTC (permalink / raw) "Nick Roberts" <nickroberts@adaos.worldonline.co.uk> wrote in message news:<9seup3$12h0ar$2@ID-25716.news.dfncis.de>... > procedure T'Construct (Object: in out T); > procedure T'Destroy (Object: in out T); > procedure T'Assign (Source, Target: in out T); It's easy to suggest something at this level, but much much harder to work out the full implications. A starting point would be to work up a full complete coherent description based on the above thought. You will find it much harder than you think. You should also thoroughly review the discussion of this issue during the design phase. In fact finalization (note by the way that we spell it with a z in the Ada world, and indeed that's the preferred spelling anyway) was extensively discussed during the design phase, and of course the above general idea was explored (this is hardly a non-obvious idea). The conclusion at that time (I don't see anything that would change it) is that this was too complex to work out, and the feature was dropped. Finalization was reintroduced when a suggestion based on the current semantics was made. This seemed much simpler, and was put in relatively late. However, it has turned out from an implementation point of view that even this proposal was far harder to implement that expected. But anyway, read the old stuff, no point in reinventing the wheel. As so often happens in language design, ideas that seem simple at the naive user level turn out to be a den of vipers at the detailed semantic specification level. Nick, you should certainly have all the old mapping documents on your shelf. You will find these a fertile source of interesting ideas. The old mapping documents are full of coherent well worked out useful ideas that did not make it into the final language not because they were wrong (*) but simply because there was a requirement to keep the entire language at an acceptable level of complexity (**). Can we do more for the next version? Perhaps in some critical areas, but not much. If the next version of Ada is too big a delta, it will simply be ignored by vendors at this stage. Even now, we have lots of customers running Ada 83 rather than Ada 95 -- transition takes a long long time. Robert Dewar (*) Tuck always used to demand that we show why a feature was wrong before he would agree to remove it, but most often there was nothing wrong. The straw was all high quality, but the camel's back was still in danger :-) (**) I think we probably hit about the right level in retrospect. We lost one major vendor (DEC, who decided that the effort in moving to Ada 95 would be too great, and so abandoned their successful and profitable Ada product), and we lost a couple of other front ends (Alsys and Telesoft), but we gained a couple of front ends (GNAT and Intermetrics), and it proved possible to move an Ada 83 compiler to Ada 95 (Rational and others). ^ permalink raw reply [flat|nested] 166+ messages in thread
* Re: Better Finalisation [List container strawman] 2001-11-09 13:36 ` Robert Dewar @ 2001-11-09 15:04 ` Florian Weimer 2001-11-10 0:36 ` Nick Roberts 1 sibling, 0 replies; 166+ messages in thread From: Florian Weimer @ 2001-11-09 15:04 UTC (permalink / raw) dewar@gnat.com (Robert Dewar) writes: > Can we do more for the next version? I would like to see a generic version of Ada.Finalization, to work around the problem that all objects with finalizers have to be declared at the library level. ^ permalink raw reply [flat|nested] 166+ messages in thread
* Re: Better Finalisation [List container strawman] 2001-11-09 13:36 ` Robert Dewar 2001-11-09 15:04 ` Florian Weimer @ 2001-11-10 0:36 ` Nick Roberts 1 sibling, 0 replies; 166+ messages in thread From: Nick Roberts @ 2001-11-10 0:36 UTC (permalink / raw) "Robert Dewar" <dewar@gnat.com> wrote in message news:5ee5b646.0111090536.5fe5852e@posting.google.com... > ... > You should also thoroughly review the discussion of this > issue during the design phase. > ... > But anyway, read the old stuff, no point in reinventing > the wheel. > ... > Nick, you should certainly have all the old mapping documents on your > shelf. Okay, I'll look over them (on the ARA web site). Are they available in print? -- Nick Roberts ^ permalink raw reply [flat|nested] 166+ messages in thread
* Re: Better Finalisation [List container strawman] 2001-11-08 18:53 ` Better Finalisation [List container strawman] Nick Roberts 2001-11-09 13:36 ` Robert Dewar @ 2001-11-09 15:16 ` Ted Dennison 2001-11-09 17:30 ` Better control of assignment Jeffrey Carter 2 siblings, 0 replies; 166+ messages in thread From: Ted Dennison @ 2001-11-09 15:16 UTC (permalink / raw) In article <9seup3$12h0ar$2@ID-25716.news.dfncis.de>, Nick Roberts says... > >"Ehud Lamm" <mslamm@mscc.huji.ac.il> wrote in message >news:9sdnb2$dd4$1@news.huji.ac.il... >However, it seems feasible to me to introduce a new finalisation mechanism >in the next revision. All we really need (am I wrong?) is three attributes, The suggestion I heard that I think is most doable was to simply make a generic version of Ada.Finalization. The current package could then be a library-level instantiation of the new generic one. That would fix the library-level problem, and still be backwards-compatable with old code. The only old code I could think of that could get hosed would be something that checks types against Ada.Finialzation.Controlled'Class, and assumes that failure means it isn't controlled. As Robert pointed out, I haven't looked deeply enough into this to know that it isn't unfeasable somehow. --- 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] 166+ messages in thread
* Re: Better control of assignment 2001-11-08 18:53 ` Better Finalisation [List container strawman] Nick Roberts 2001-11-09 13:36 ` Robert Dewar 2001-11-09 15:16 ` Ted Dennison @ 2001-11-09 17:30 ` Jeffrey Carter 2001-11-10 0:32 ` Nick Roberts 2 siblings, 1 reply; 166+ messages in thread From: Jeffrey Carter @ 2001-11-09 17:30 UTC (permalink / raw) Nick Roberts wrote: > > However, it seems feasible to me to introduce a new finalisation mechanism > in the next revision. All we really need (am I wrong?) is three attributes, > applying to any type T, which are the procedures carried out whenever an > object of the type is created, copied, and destroyed: > > procedure T'Construct (Object: in out T); > procedure T'Destroy (Object: in out T); > procedure T'Assign (Source, Target: in out T); Assignment should not be able to modify the RHS, especially as it may be an expression, not a variable. > > These attributes would, naturally, have implementation-supplied defaults, > but could be overidden by attribute definition clauses, as normal. I was thinking recently of how to provide a different implementation of Ada.Strings.Unbounded, and came to the conclusion that the current controlled-type handling of user-defined assignment is not able to handle the concept I had in mind. Of course, I might be wrong about this, and would be happy if I am. The basic idea is to define an Unbounded_String as Initial_Max_Length : constant := ...; type Unbounded_String is [new Ada.Finalization.Controlled with] record Length : Natural := 0; Value : String_Access := new String (1 .. Initial_Max_Length); end record; Finalization would free Value. Then, given LHS : Unbounded_String; ... LHS := RHS; where RHS is an expression of type Unbounded_String, would operate along the lines of LHS.Length := RHS.Length; if LHS.Value'Length < RHS.Length then Free (LHS.Value); LHS.Value := new String (1 .. RHS.Value'Length); end if; LHS.Value (1 .. RHS.Length) := RHS.Value (1 .. RHS.Length); The general idea is to exchange some space for the ability to avoid deallocation and reallocation with every assignment, doing so only when it is necessary. Although I have used Unbounded_String as an example, this basic idea would be useful for many user-defined types. It appears that controlled types are unable to implement this, while the proposal above could. Of course, such things are easy to propose but difficult to specify completely, and the implementation burden may be unacceptable. The implications of redefining assignment in C++ are extremely complex, and we should avoid such complexity in Ada. On the other hand, this is a very useful capability that we should consider including in Ada 0X. One can implement this capability with a limited type and an Assign procedure, but Unbounded_String may not be implemented that way. -- Jeffrey Carter ^ permalink raw reply [flat|nested] 166+ messages in thread
* Re: Better control of assignment 2001-11-09 17:30 ` Better control of assignment Jeffrey Carter @ 2001-11-10 0:32 ` Nick Roberts 2001-11-10 22:27 ` Jeffrey Carter 0 siblings, 1 reply; 166+ messages in thread From: Nick Roberts @ 2001-11-10 0:32 UTC (permalink / raw) "Jeffrey Carter" <jeffrey.carter@boeing.com> wrote in message news:3BEC12BA.E72A81EC@boeing.com... > Nick Roberts wrote: > > procedure T'Construct (Object: in out T); > > procedure T'Destroy (Object: in out T); > > procedure T'Assign (Source, Target: in out T); > > Assignment should not be able to modify the RHS, especially as it may be > an expression, not a variable. Perhaps the name Assign is wrong. Maybe Copy would be better. To my mind, it seems obvious (of course ;-) that if the RHS is a constant, this procedure is not invoked; it is only invoked for a copy (including parameter passing by copy (if selected)) from one variable object of type T to another. If this does not deliver enough control, you must make the type private. For example: type Odd_Counter is new Integer; procedure Assign_Odd (Src, Tgt: in out Odd_Counter); for Odd_Counter'Copy use Assign_Odd; ... procedure Assign_Odd (Src, Tgt: in out Odd_Counter) is begin if not Is_Odd(Src) then raise Oddness_Error; else Tgt := Src; -- inherited assignment used here by a language rule end if; end; The idea is that an object of type Odd_Counter can only ever hold an odd number. But nothing prevents: C: Odd_Counter := 2; -- oddness violation, but it will not be caught So we must instead declare (in a package specification): type Odd_Counter is private; ... procedure Init (Ctr: in out Odd_Counter; Int: in Integer); ... private type Odd_Counter is new Integer; ... And then (in the package body) we can check for oddness: procedure Init (Ctr: in out Odd_Counter; Int: in Integer) is begin if not Is_Odd(Int) then raise Oddness_Error; else Ctr := Odd_Counter(Int); end if; end; Of course, in this case, if we want the bastion of operations pre-defined for Integer, we must explicitly declare functions for "+", "-", "*", "/" and so on. Too bad. > I was thinking recently of how to provide a different implementation of > Ada.Strings.Unbounded, and came to the conclusion that the current > controlled-type handling of user-defined assignment is not able to > handle the concept I had in mind. Of course, I might be wrong about > this, and would be happy if I am. I believe my proposal would solve the problem of the kind of implementation of Ada unbounded strings that Jeff suggests. -- Nick Roberts ^ permalink raw reply [flat|nested] 166+ messages in thread
* Re: Better control of assignment 2001-11-10 0:32 ` Nick Roberts @ 2001-11-10 22:27 ` Jeffrey Carter 2001-11-13 6:36 ` Craig Carey ` (2 more replies) 0 siblings, 3 replies; 166+ messages in thread From: Jeffrey Carter @ 2001-11-10 22:27 UTC (permalink / raw) Nick Roberts wrote: > > "Jeffrey Carter" <jeffrey.carter@boeing.com> wrote in message > > Assignment should not be able to modify the RHS, especially as it may be > > an expression, not a variable. > > Perhaps the name Assign is wrong. Maybe Copy would be better. To my mind, it > seems obvious (of course ;-) that if the RHS is a constant, this procedure > is not invoked; it is only invoked for a copy (including parameter passing > by copy (if selected)) from one variable object of type T to another. If > this does not deliver enough control, you must make the type private. For > example: > > type Odd_Counter is new Integer; > procedure Assign_Odd (Src, Tgt: in out Odd_Counter); > for Odd_Counter'Copy use Assign_Odd; > ... > procedure Assign_Odd (Src, Tgt: in out Odd_Counter) is > begin > if not Is_Odd(Src) then > raise Oddness_Error; > else > Tgt := Src; -- inherited assignment used here by a language rule > end if; > end; There is still no need for Src to be mode in out. -- Jeff Carter "Son of a window-dresser." Monty Python & the Holy Grail ^ permalink raw reply [flat|nested] 166+ messages in thread
* Re: Better control of assignment 2001-11-10 22:27 ` Jeffrey Carter @ 2001-11-13 6:36 ` Craig Carey 2001-11-13 6:39 ` Craig Carey 2001-11-13 8:53 ` Craig Carey 2 siblings, 0 replies; 166+ messages in thread From: Craig Carey @ 2001-11-13 6:36 UTC (permalink / raw) On Sat, 10 Nov 2001 22:27:25 GMT, Jeffrey Carter <jrcarter@acm.org> wrote: >Nick Roberts wrote: >> >> "Jeffrey Carter" <jeffrey.carter@boeing.com> wrote in message >> > Assignment should not be able to modify the RHS, especially as it may be >> > an expression, not a variable. >> >> Perhaps the name Assign is wrong. Maybe Copy would be better. To my mind, it >> seems obvious (of course ;-) that if the RHS is a constant, this procedure >> is not invoked; it is only invoked for a copy (including parameter passing >> by copy (if selected)) from one variable object of type T to another. If >> this does not deliver enough control, you must make the type private. For >> example: >> >> type Odd_Counter is new Integer; >> procedure Assign_Odd (Src, Tgt: in out Odd_Counter); >> for Odd_Counter'Copy use Assign_Odd; >> ... >> procedure Assign_Odd (Src, Tgt: in out Odd_Counter) is >> begin >> if not Is_Odd(Src) then >> raise Oddness_Error; >> else >> Tgt := Src; -- inherited assignment used here by a language rule >> end if; >> end; > >There is still no need for Src to be mode in out. --- >Nick Roberts wrote: >> >> However, it seems feasible to me to introduce a new finalisation >> in the next revision. All we really need (am I wrong?) is three >> attributes, ... >> procedure T'Construct (Object: in out T); >> procedure T'Destroy (Object: in out T); >> procedure T'Assign (Source, Target: in out T); > >Assignment should not be able to modify the RHS, especially as it may > be an expression, not a variable. > Are you sure you want to allow Strings to be destroyed?. Suppose the pointers got copied, as in this example: procedure Crash_Ada is A, B, C : Unlimited_String; begin Make_New (A); B.Ref := A.Ref; B.Length := ... C.Ref := A.Ref; -- At scope exit, the Destructor presumably is called onto all -- 3 variables. end Crash_Ada; A fix is to stop the assignments to the ".Ref" fields. There could be an agreement that we want to allow assigning to the Length and Ref.all fields to quite available to packages with-ing the package. The whole program could crash when the Destructor frees the same memory twice. --- One problem is that letting the programmer do a swapping assign instead of a copying assign, e.g. A :=. B is that the routine holding B might have to be recoded like this: From: procedure T (B : in Unlimited_String) into: procedure T (B : in out Unlimited_String). That is undesirable and it may be possible to allow records to have read-only fields that can be altered (by routines declared in the same package that declares the type), even though they are supposed to be constant because they are an "in" mode parameter. An aim here is to not force people to have pointers to pointers just to avoid rewritng procedure F (B : in Unlimited_String.Vstr) is begin A :=. B; -- Fast Assign with pointer swapping and loss of RHS end F; as procedure F (B : in Unlimited_String.Vstr) is begin A :=. B; end F; It can be just a matter of adding the "out" mode to a record field which makes the type have a read-only field. An example of a new proposed feature for Ada: package Q is type Vstr is record -- Ref is exported read only Ref : out String_Access := Null_String_Access; Length : Natural := 0; end record; procedure ":=." (L : out Vstr; R : in Vstr); -- Swaps pointers and changes the pointer value, R.Ref. It is -- read-only, not constant. end Q; package body Q is procedure ":=." (L : out Vstr; R : in Vstr) is Tmp : Access_String; -- Fast assign with ptr swapping begin LHS.Length := RHS.Length; Tmp := LHS.Ref; LHS.Ref := RHS.Ref; RHS.Ref := Tmp; RHS.Length := 0; -- Invalidate the RHS pointer end ":=."; end Y; procedure R (B : in Q.Vstr) is A : Q.Vstr; begin Unknown1 (Alter_It => B); -- This proc is not able to alter B.Ref -- but it can change B.Ref.all. ... -- Final access of the data from B destroys it. -- It is either that for inefficiency or lazy ":="-ing A :=. B; -- B.Ref can be changed by the Fast Assignment operator -- since it is in the package defining (or extending) -- the type. That B (and B.Ref) is of the "in" mode -- would not stop any routine in Q from altering B.Ref. ... end R; A big advantage of that is that there are no pointers to pointers to mislead the language into believing a value changed is not. Maybe lazy assignments could be slower and it is not clear why such a complex scheme ought be implented, with its destructors, when this far simpler can't properly get destructors. http://groups.google.com/groups?hl=en&rnum=11&selm=dewar.848839209%40merv > From: Robert Dewar > Subject: Re: Unbounded strings (Was: Java vs Ada 95 (Was Re: Once > again, Ada absent from DoD SBIR solicitation)) > Newsgroups: comp.lang.ada > Date: 1996/11/24 Mr Dewar's lazy assignment idea might not be a remedy for the problem of slow String handling code. To put a pointer inside of a record and make it private or limited, won't stop writing to the pointer while allowing writing to the ".all" value. It is a bug in the language. No is "access constant [subtype]" helpful. Maybe M Carter can come up with an example arguing for user defining of assignment that keeps away from Strings where what seem to be language design defects become explicit. When there are two pointers, then the first pointer can be made a pointer to a 2nd pointer that is defined to be of this type: type [name] is access constant [second_pointer_subtype]; That stops all alteration of the B.Ref1.Ref2 while fully allowing alterating of B.Ref1.Ref12.all (1 .. Sockets_Buffer_Maxlength). ^ permalink raw reply [flat|nested] 166+ messages in thread
* Re: Better control of assignment 2001-11-10 22:27 ` Jeffrey Carter 2001-11-13 6:36 ` Craig Carey @ 2001-11-13 6:39 ` Craig Carey 2001-11-13 8:53 ` Craig Carey 2 siblings, 0 replies; 166+ messages in thread From: Craig Carey @ 2001-11-13 6:39 UTC (permalink / raw) On Sat, 10 Nov 2001 22:27:25 GMT, Jeffrey Carter <jrcarter@acm.org> wrote: >Nick Roberts wrote: >> >> "Jeffrey Carter" <jeffrey.carter@boeing.com> wrote in message >> > Assignment should not be able to modify the RHS, especially as it may be >> > an expression, not a variable. >> >> Perhaps the name Assign is wrong. Maybe Copy would be better. To my mind, it >> seems obvious (of course ;-) that if the RHS is a constant, this procedure >> is not invoked; it is only invoked for a copy (including parameter passing >> by copy (if selected)) from one variable object of type T to another. If >> this does not deliver enough control, you must make the type private. For >> example: >> >> type Odd_Counter is new Integer; >> procedure Assign_Odd (Src, Tgt: in out Odd_Counter); >> for Odd_Counter'Copy use Assign_Odd; >> ... >> procedure Assign_Odd (Src, Tgt: in out Odd_Counter) is >> begin >> if not Is_Odd(Src) then >> raise Oddness_Error; >> else >> Tgt := Src; -- inherited assignment used here by a language rule >> end if; >> end; > >There is still no need for Src to be mode in out. --- >Nick Roberts wrote: >> >> However, it seems feasible to me to introduce a new finalisation >> in the next revision. All we really need (am I wrong?) is three >> attributes, ... >> procedure T'Construct (Object: in out T); >> procedure T'Destroy (Object: in out T); >> procedure T'Assign (Source, Target: in out T); > >Assignment should not be able to modify the RHS, especially as it may > be an expression, not a variable. > Are you sure you want to allow Strings to be destroyed?. Suppose the pointers got copied, as in this example: procedure Crash_Ada is A, B, C : Unlimited_String; begin Make_New (A); B.Ref := A.Ref; B.Length := ... C.Ref := A.Ref; -- At scope exit, the Destructor presumably is called onto all -- 3 variables. end Crash_Ada; A fix is to stop the assignments to the ".Ref" fields. There could be an agreement that we want to allow assigning to the Length and Ref.all fields to quite available to packages with-ing the package. The whole program could crash when the Destructor frees the same memory twice. --- One problem is that letting the programmer do a swapping assign instead of a copying assign, e.g. A :=. B is that the routine holding B might have to be recoded like this: From: procedure T (B : in Unlimited_String) into: procedure T (B : in out Unlimited_String). That is undesirable and it may be possible to allow records to have read-only fields that can be altered (by routines declared in the same package that declares the type), even though they are supposed to be constant because they are an "in" mode parameter. An aim here is to not force people to have pointers to pointers just to avoid rewritng procedure F (B : in Unlimited_String.Vstr) is begin A :=. B; -- Fast Assign with pointer swapping and loss of RHS end F; as procedure F (B : in Unlimited_String.Vstr) is begin A :=. B; end F; It can be just a matter of adding the "out" mode to a record field which makes the type have a read-only field. An example of a new proposed feature for Ada: package Q is type Vstr is record -- Ref is exported read only Ref : out String_Access := Null_String_Access; Length : Natural := 0; end record; procedure ":=." (L : out Vstr; R : in Vstr); -- Swaps pointers and changes the pointer value, R.Ref. It is -- read-only, not constant. end Q; package body Q is procedure ":=." (L : out Vstr; R : in Vstr) is Tmp : Access_String; -- Fast assign with ptr swapping begin LHS.Length := RHS.Length; Tmp := LHS.Ref; LHS.Ref := RHS.Ref; RHS.Ref := Tmp; RHS.Length := 0; -- Invalidate the RHS pointer end ":=."; end Y; procedure R (B : in Q.Vstr) is A : Q.Vstr; begin Unknown1 (Alter_It => B); -- This proc is not able to alter B.Ref -- but it can change B.Ref.all. ... -- Final access of the data from B destroys it. -- It is either that for inefficiency or lazy ":="-ing A :=. B; -- B.Ref can be changed by the Fast Assignment operator -- since it is in the package defining (or extending) -- the type. That B (and B.Ref) is of the "in" mode -- would not stop any routine in Q from altering B.Ref. ... end R; A big advantage of that is that there are no pointers to pointers to mislead the language into believing a value changed is not. Maybe lazy assignments could be slower and it is not clear why such a complex scheme ought be implented, with its destructors, when this far simpler can't properly get destructors. http://groups.google.com/groups?hl=en&rnum=11&selm=dewar.848839209%40merv > From: Robert Dewar > Subject: Re: Unbounded strings (Was: Java vs Ada 95 (Was Re: Once > again, Ada absent from DoD SBIR solicitation)) > Newsgroups: comp.lang.ada > Date: 1996/11/24 Mr Dewar's lazy assignment idea might not be a remedy for the problem of slow String handling code. To put a pointer inside of a record and make it private or limited, won't stop writing to the pointer while allowing writing to the ".all" value. It is a bug in the language. No is "access constant [subtype]" helpful. Maybe M Carter can come up with an example arguing for user defining of assignment that keeps away from Strings where what seem to be language design defects become explicit. When there are two pointers, then the first pointer can be made a pointer to a 2nd pointer that is defined to be of this type: type [name] is access constant [second_pointer_subtype]; That stops all alteration of the B.Ref1.Ref2 while fully allowing alterating of B.Ref1.Ref12.all (1 .. Sockets_Buffer_Maxlength). ^ permalink raw reply [flat|nested] 166+ messages in thread
* Re: Better control of assignment 2001-11-10 22:27 ` Jeffrey Carter 2001-11-13 6:36 ` Craig Carey 2001-11-13 6:39 ` Craig Carey @ 2001-11-13 8:53 ` Craig Carey 2001-11-14 9:42 ` Craig Carey 2 siblings, 1 reply; 166+ messages in thread From: Craig Carey @ 2001-11-13 8:53 UTC (permalink / raw) On Sat, 10 Nov 2001 22:27:25 GMT, Jeffrey Carter <jrcarter@acm.org> wrote: >s only invoked for a copy (including parameter passing >> by copy (if selected)) from one variable object of type T to another. If >> this does not deliver enough control, you must make the type private. For >> example: >> >> type Odd_Counter is new Integer; >> procedure Assign_O The Oberon-2 language implements a feature of read-only record field components. Also it allows package spec variables (Module identifiers) to be exported read-only. A page on Oberon-2, that mentions the "read-only" "export mark" feature of Oberon-2, is here: http://www-cse.ucsd.edu/classes/sp01/cse131B_A/oberon2.htm | |[Module] Identifiers [variables] marked with " - " in their declaration | are read-only in importing modules. | Qualident = [ident "."]ident. | IdentDef = ident [" * " | " - "]. ... |If a [an array] or r [a record or a component record in a record] are | read-only, then also a[e] and r.f are read-only. ... |MODULE Trees; (* exports: Tree, Node, Insert, Search, Write, Init *) | IMPORT Texts, Oberon; (* exports read-only: Node.name *) | | TYPE | Tree* = POINTER TO Node; | Node* = RECORD | name-: POINTER TO ARRAY OF CHAR; | left, right: Tree | END; ... I never saw a comment saying that a using module can't assign chars to x.name^ [X.name.all]. If Ada were following closely an Oberon-2 style, then this could a the way to make Ref be read-only: type Unbounded_String is [? new Ada.Finalization.Controlled with] record Length : Natural := 0; Ref- : String_Access := ...; end record; That is sure to be rejected: the modifier ought be on the right of the ":" since it affects the type and not the name. More on Modula-2: http://www.cetus-links.org/oo_oberon.html Some selected Error messages of the "Optimizing Oberon-2 Compiler", follow. Error messages 244 & 245 imply that in Oberon, making X.Ref be exported as read-only [either the type of a module variable], where X is a record type and Ref is a pointer, does not cause X.Ref.all (i.e. X.Ref^) to be read-only. Just as is hoped for. http://ooc.sourceforge.net/OOCref/OOCref_19.html | |*201: Can only be exported with **'' | |Constants, types, and procedures cannot be exported with *-' |because the notion of a restricted, read-only access doesn't make |sense for these objects. | | |*244: This isn't a variable designator' | |This applies to the following cases: | Only a modifiable variable designator may appear on the left | side of an assignment statement. The variable designator may | not refer to a variable or record field that has been | exported as read-only. | The control variable of a FOR statement has to be an | unqualified (i.e., local) variable identifier. |Note that dereferencing a read-only pointer variable will grant |unrestricted access to the pointer's contents. | | |*245: This is imported read-only' | |This applies to the left side of an assignment statement and to |variables passed to a VAR parameter as part of a procedure call. |This means that the destination variable (or designator) has to be |either | 1. imported as read-write (and no following selector accesses | a read-only record field), or | 2. the value of a dereferenced pointer variable. |Contrary to a pointer dereference, an element of a read-only array |is read-only, just like a field of a read-only record variable. | I have doubts about Mr Carter's assignment, with its familiar right hand side is read only and left hand side is written too nature. I my proposal, the left side is read-only [i.e. writable to only by subprocedures in its package], and the right hand side can be written to (pointers swapped) even though an "in" mode parameter [this last may need to be checked]. Either that or C-isms of pointers to pointers may appear. --------- PS. I accidentally 'double posted' the same message. In some cases the duplicate could be deleted. PS. By sending data through a debugging TCP proxy, such accidents ought be harder to do. Here is Win32 GUI debugging proxy that shows bytes passing through it: TCP Viewer: http://www.westbrooksoftware.com/ ^ permalink raw reply [flat|nested] 166+ messages in thread
* Re: Better control of assignment 2001-11-13 8:53 ` Craig Carey @ 2001-11-14 9:42 ` Craig Carey 0 siblings, 0 replies; 166+ messages in thread From: Craig Carey @ 2001-11-14 9:42 UTC (permalink / raw) In this message I propose a way if importing package spec variables as being read-only even though they were not exported as being read-only. Faster strings too. On Tue, 13 Nov 2001 21:53:21 +1300, Craig Carey <research@ijs.co.nz> wrote: >On Sat, 10 Nov 2001 22:27:25 GMT, Jeffrey Carter <jrcarter@acm.org> >wrote: >>Nick Roberts wrote: >>s only invoked for a copy (including parameter passing >>> by copy (if selected)) from one variable object of type T to another. If >>> this does not deliver enough control, you must make the type private. For >>> example: ... No need to make the type 'private' if there is a read-only feature like what Oberon has. > >http://www-cse.ucsd.edu/classes/sp01/cse131B_A/oberon2.htm ... >More on Modula-2: http://www.cetus-links.org/oo_oberon.html ... >http://ooc.sourceforge.net/OOCref/OOCref_19.html ... >|'245: This is imported read-only' >| >|This applies to the left side of an assignment statement and to >|variables passed to a VAR parameter as part of a procedure call. >|This means that the destination variable (or designator) has to be >|either >| 1. imported as read-write (and no following selector accesses >| a read-only record field), or >| 2. the value of a dereferenced pointer variable. >|Contrary to a pointer dereference, an element of a read-only array >|is read-only, just like a field of a read-only record variable. >| ... It seems that a record with both read-only and read-write fields, and that is exported as being read-write, can be imported as being read-only. That read-only importing overrides the read-write exporting. That seems to Oberon feature that can be copied and implemented with pragmas. It is Here is a quick proposed way of making imported package variables be read only: package RW is X : in out Integer; end RW; --- with RW; package P is package RO renames out RW; -- Rename, make T2.* be read-only RO.X := 5; -- illegal!, can use RW.X to get write access end P; --- >subprocedures in its package], and the right hand side can be written >to (pointers swapped) even though an "in" mode parameter [this last >may need to be checked]. That is wrong (the fields of an "in" mode record parameter do not get copied back to the caller, and presumably that is not going to be altered). Hence the improved fast Strings package with no use of private may need to have pointers to pointers even in the distant future. Here is fragment of a new spec file. This thread has been useful since it got to conclude the pointers to pointers seem to be needed. package Strings_Unlimited is -- Note: duplicating pointers may lead to faulty behaviour -- The arrival of read-only or limited pointers can lead to -- a fix. type String_Access is access all String; type String_Access_Ptr is access constant String_Access; Null_String_Access : aliased constant String_Access := new String (1 .. 0); Null_String_Access_Ptr : aliased constant String_Access_Ptr := Null_String_Access'Access; type Unlimited_String is limited record Ref : String_Access_Ptr := Null_String_Access_Ptr; Len : Natural := 0; end record; ... end Strings_Unlimited; I would have some code implementing this package once it is checked and/or debugged. I wonder how the US military gets on with those slow Strings. Pointer copying could also be stopped by allowing pointer types to be "limited". What a interesting finding: Oberon-2 is a better than Ada 95 in sime areas. ^ permalink raw reply [flat|nested] 166+ messages in thread
* Re: List container strawman 2001-11-08 10:34 ` Ehud Lamm 2001-11-08 18:53 ` Better Finalisation [List container strawman] Nick Roberts @ 2001-11-09 14:49 ` Ted Dennison 2001-11-09 16:12 ` Ehud Lamm 2001-11-09 17:12 ` Marin David Condic 1 sibling, 2 replies; 166+ 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] 166+ messages in thread
* Re: List container strawman 2001-11-09 14:49 ` List container strawman Ted Dennison @ 2001-11-09 16:12 ` Ehud Lamm 2001-11-09 17:12 ` Marin David Condic 1 sibling, 0 replies; 166+ 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] 166+ messages in thread
* Re: List container strawman 2001-11-09 14:49 ` List container strawman 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; 166+ 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] 166+ 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; 166+ 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] 166+ 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; 166+ 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] 166+ 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; 166+ 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] 166+ messages in thread
* Re: List container strawman 2001-11-02 3:56 List container strawman 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; 166+ 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] 166+ 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; 166+ 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] 166+ 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; 166+ 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] 166+ 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; 166+ 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] 166+ 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; 166+ 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] 166+ 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; 166+ 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] 166+ 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; 166+ 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] 166+ messages in thread
* Re: List container strawman 2001-11-02 3:56 List container strawman 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; 166+ 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] 166+ 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; 166+ 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] 166+ messages in thread
* Re: List container strawman 2001-11-02 3:56 List container strawman 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; 166+ 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] 166+ 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; 166+ 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] 166+ 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; 166+ 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] 166+ 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; 166+ 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] 166+ 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; 166+ 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] 166+ 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; 166+ 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] 166+ 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; 166+ 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] 166+ 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 ` List container strawman Simon Wright 1 sibling, 2 replies; 166+ 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] 166+ 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-05 17:21 ` List container strawman; Construct alternatives Stephen Leake 2001-11-03 7:42 ` List container strawman Simon Wright 1 sibling, 2 replies; 166+ 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] 166+ 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 2001-11-05 17:21 ` List container strawman; Construct alternatives Stephen Leake 1 sibling, 1 reply; 166+ 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] 166+ 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; 166+ 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] 166+ 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; 166+ 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] 166+ 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; 166+ 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] 166+ 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; 166+ 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] 166+ 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; 166+ 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] 166+ 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; 166+ 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] 166+ 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; 166+ 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] 166+ 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; 166+ 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] 166+ messages in thread
* Re: List container strawman 2001-11-08 4:50 ` Jeffrey Carter @ 2001-11-08 23:26 ` ramatthews 0 siblings, 0 replies; 166+ 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] 166+ 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; 166+ 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] 166+ 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; 166+ 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] 166+ 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; 166+ 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] 166+ 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; 166+ 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] 166+ 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; 166+ 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] 166+ 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; 166+ 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] 166+ 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; 166+ 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] 166+ 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; 166+ 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] 166+ 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; 166+ 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] 166+ 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; 166+ 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] 166+ 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; 166+ 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] 166+ 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; 166+ 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] 166+ 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; 166+ 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] 166+ 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; 166+ 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] 166+ 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; 166+ 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] 166+ 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; 166+ 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] 166+ 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; 166+ 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] 166+ 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; 166+ 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] 166+ 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; 166+ 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] 166+ 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; 166+ 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] 166+ 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; 166+ 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] 166+ 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; 166+ 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] 166+ 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; 166+ 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] 166+ messages in thread
* Re: List container strawman; Construct alternatives 2001-11-02 20:07 ` Ted Dennison 2001-11-02 23:19 ` Jeffrey Carter @ 2001-11-05 17:21 ` Stephen Leake 1 sibling, 0 replies; 166+ messages in thread From: Stephen Leake @ 2001-11-05 17:21 UTC (permalink / raw) Ted Dennison<dennison@telepath.com> writes: > In article <3BE2DB99.B707D409@boeing.com>, Jeffrey Carter says... > <snip> > >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? I like "Create". However, if you do end up with "type List" being derived from Controlled, then you do _not_ want "Create" to be a primitive operation; derived types must have their own "Create". One good solution is to put the "Create" routines (there are usually more than one) in a local nested package: package Containers.Lists is type List_Type is ... package Creators is procedure Create (List : in out List_Type); -- Create an empty list procedure Create (List : in out List_Type; Initial : in Element); end Creators; end Containers.Lists; Also, I prefer "List_Type" and "Element_Type", for all the reasons in the recent thread on that topic! -- -- Stephe ^ permalink raw reply [flat|nested] 166+ 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; 166+ 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] 166+ 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; 166+ 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] 166+ 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; 166+ 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] 166+ 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; 166+ 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] 166+ 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; 166+ 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] 166+ 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; 166+ 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] 166+ 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; 166+ 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] 166+ 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; 166+ 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] 166+ 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; 166+ 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] 166+ 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; 166+ 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] 166+ 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; 166+ 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] 166+ 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; 166+ 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] 166+ 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; 166+ 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] 166+ 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; 166+ 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] 166+ 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; 166+ 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] 166+ 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; 166+ 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] 166+ 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; 166+ 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] 166+ messages in thread
* Re: List container strawman 2001-11-02 3:56 List container strawman 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; 166+ 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] 166+ 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; 166+ 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] 166+ 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; 166+ 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] 166+ 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; 166+ 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] 166+ messages in thread
* Re: List container strawman @ 2001-11-02 19:54 Mike Brenner 2001-11-02 21:04 ` Ted Dennison 0 siblings, 1 reply; 166+ 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] 166+ messages in thread
* Re: List container strawman 2001-11-02 19:54 Mike Brenner @ 2001-11-02 21:04 ` Ted Dennison 2001-11-03 8:09 ` Simon Wright 0 siblings, 1 reply; 166+ 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] 166+ 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; 166+ 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] 166+ 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; 166+ 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] 166+ messages in thread
end of thread, other threads:[~2001-12-06 17:47 UTC | newest] Thread overview: 166+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2001-11-02 3:56 List container strawman 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-03 22:51 ` Rosen Trick [List container strawman] Nick Roberts 2001-11-04 13:07 ` Robert Dewar 2001-11-04 17:17 ` Side-Effects in Functions [Rosen Trick] Nick Roberts 2001-11-05 2:46 ` Robert Dewar 2001-11-05 7:26 ` pete 2001-11-05 10:29 ` Dmitry A. Kazakov 2001-11-05 11:19 ` pete 2001-11-05 14:59 ` Dmitry A. Kazakov 2001-11-05 15:21 ` Preben Randhol 2001-11-05 16:04 ` Ted Dennison 2001-11-05 16:33 ` Dmitry A. Kazakov 2001-11-05 17:42 ` Warren W. Gay VE3WWG 2001-11-05 18:11 ` Preben Randhol 2001-11-06 8:38 ` Dmitry A. Kazakov 2001-11-06 9:31 ` tgingold 2001-11-06 0:10 ` Nick Roberts 2001-11-06 9:30 ` Dmitry A. Kazakov 2001-11-06 16:18 ` Lazy Evaluation [Side-Effects in Functions] Nick Roberts 2001-11-07 3:42 ` Robert Dewar 2001-11-07 4:42 ` Darren New 2001-11-07 11:54 ` Robert Dewar 2001-11-07 13:32 ` Florian Weimer 2001-11-07 13:24 ` Jean-Marc Bourguet 2001-11-09 18:06 ` Ted Dennison 2001-11-09 18:27 ` M. A. Alves 2001-11-11 20:13 ` Georg Bauhaus 2001-12-06 17:47 ` Harri J Haataja 2001-11-07 9:28 ` Dmitry A. Kazakov 2001-11-06 20:08 ` Side-Effects in Functions [Rosen Trick] Florian Weimer 2001-11-06 22:48 ` Nick Roberts 2001-11-07 10:46 ` Florian Weimer 2001-11-05 13:56 ` Robert Dewar 2001-11-05 16:08 ` Ted Dennison 2001-11-05 17:44 ` Warren W. Gay VE3WWG 2001-11-05 15:56 ` Ted Dennison 2001-11-05 18:46 ` Nick Roberts 2001-11-08 11:51 ` Georg Bauhaus 2001-11-16 0:31 ` List container strawman 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-08 18:53 ` Better Finalisation [List container strawman] Nick Roberts 2001-11-09 13:36 ` Robert Dewar 2001-11-09 15:04 ` Florian Weimer 2001-11-10 0:36 ` Nick Roberts 2001-11-09 15:16 ` Ted Dennison 2001-11-09 17:30 ` Better control of assignment Jeffrey Carter 2001-11-10 0:32 ` Nick Roberts 2001-11-10 22:27 ` Jeffrey Carter 2001-11-13 6:36 ` Craig Carey 2001-11-13 6:39 ` Craig Carey 2001-11-13 8:53 ` Craig Carey 2001-11-14 9:42 ` Craig Carey 2001-11-09 14:49 ` List container strawman 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-05 17:21 ` List container strawman; Construct alternatives Stephen Leake 2001-11-03 7:42 ` List container strawman 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 -- strict thread matches above, loose matches on Subject: below -- 2001-11-02 19:54 Mike Brenner 2001-11-02 21:04 ` Ted Dennison 2001-11-03 8:09 ` Simon Wright 2001-11-03 12:46 ` Simon Wright
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox