* Ada Generic Library (very) preliminary release @ 1997-07-08 0:00 Brian Rogoff 1997-07-09 0:00 ` Richard Kenner 1997-07-09 0:00 ` Mats Weber 0 siblings, 2 replies; 13+ messages in thread From: Brian Rogoff @ 1997-07-08 0:00 UTC (permalink / raw) Hi, I've been hacking away at a clone of the STL in Ada 95 (who says you can't hack in Ada ;-) and I have enough that I'd like to get some feedback from the Ada cognoscenti as to just how awful some of these hacks are. Comments from programmers familiar with the C++ STL would also be appreciated. I started with the design of the RPI Ada STL, and I've added quite a few more containers (singly linked lists, deques, ordered sets, and ordered multisets) and cleaned it up a bit. Since the RPI Ada STL will probably clone the ISO C++ STL, I'll be a bit more experimental and add things like three way compare. I'm releasing the library under LGPL with the GNAT exception (sorry Dave :-). It is a very preliminary release mainly for getting feedback, so don't expect to get useful work done with it! Now that you've been warned, http://www.best.com/~bpr/AGL.html -- Brian ^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: Ada Generic Library (very) preliminary release 1997-07-08 0:00 Ada Generic Library (very) preliminary release Brian Rogoff @ 1997-07-09 0:00 ` Richard Kenner 1997-07-09 0:00 ` Brian Rogoff 1997-07-09 0:00 ` Robert Dewar 1997-07-09 0:00 ` Mats Weber 1 sibling, 2 replies; 13+ messages in thread From: Richard Kenner @ 1997-07-09 0:00 UTC (permalink / raw) In article <Pine.SGI.3.95.970708195446.25610A-100000@shellx.best.com> Brian Rogoff <bpr@shellx.best.com> writes: >I'm releasing the library under LGPL with the GNAT exception >(sorry Dave :-). Did you mean precisely what you wrote? It would make sense to release it under the LGPL (since it's a library) or the GPL with the "special exception", but the LGPL plus special exception seems strange. ^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: Ada Generic Library (very) preliminary release 1997-07-09 0:00 ` Richard Kenner @ 1997-07-09 0:00 ` Brian Rogoff 1997-07-09 0:00 ` Robert Dewar 1 sibling, 0 replies; 13+ messages in thread From: Brian Rogoff @ 1997-07-09 0:00 UTC (permalink / raw) To: Richard Kenner Yes you're right of course, that special exception is overkill with the LGPL, and I'll remove it asap. I was trying to be clear that instantiating generics from the library doesn't make your work a "derivative work" but rather a "work that uses the library", but I believe that is covered in the LGPL, no? If not, then I think I have to change the release to "GPL with GNAT exception". -- Brian On 9 Jul 1997, Richard Kenner wrote: > In article <Pine.SGI.3.95.970708195446.25610A-100000@shellx.best.com> Brian Rogoff <bpr@shellx.best.com> writes: > >I'm releasing the library under LGPL with the GNAT exception > >(sorry Dave :-). > > Did you mean precisely what you wrote? It would make sense to release it > under the LGPL (since it's a library) or the GPL with the "special > exception", but the LGPL plus special exception seems strange. > > ^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: Ada Generic Library (very) preliminary release 1997-07-09 0:00 ` Richard Kenner 1997-07-09 0:00 ` Brian Rogoff @ 1997-07-09 0:00 ` Robert Dewar 1 sibling, 0 replies; 13+ messages in thread From: Robert Dewar @ 1997-07-09 0:00 UTC (permalink / raw) iRichard said <<Did you mean precisely what you wrote? It would make sense to release it under the LGPL (since it's a library) or the GPL with the "special exception", but the LGPL plus special exception seems strange.>> The LGPL notion is an obsolete notion that does not apply at all to generic packages in e4ither C++ or in Ada 95. The idea of relinking with new versions makes no sense at all for generic isntantiations (use of templates). That is why we uwse the modified GPL for GNAYT, and that is the right choice (given the author';s aims) for the Ada STL. And please note, despite confusing posts from RObert Leif and others, use of the modified GPL means that the package is equally usable with all Ada compilers that support it. ^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: Ada Generic Library (very) preliminary release 1997-07-08 0:00 Ada Generic Library (very) preliminary release Brian Rogoff 1997-07-09 0:00 ` Richard Kenner @ 1997-07-09 0:00 ` Mats Weber 1997-07-09 0:00 ` Brian Rogoff 1 sibling, 1 reply; 13+ messages in thread From: Mats Weber @ 1997-07-09 0:00 UTC (permalink / raw) Just had a fast look at it, here are a few comments: - A minor glitch: all files have cr lf as line separators, but most unices prefer just a single line feed. I had to pass them through for f in * do cat $f | tr -d \\015 >/tmp/xuixuixui mv /tmp/xuixuixui $f done before I could watch them comfortably. - Many components are just plain record types, where I think good Ada 95 style would make them tagged types for several reasons: automatic finalization and possibility of inheritance among others. - I don't know STL so my commments are from a "neutral" point of view. - Some components need a Nil constant of the Element_Type, some not. I think this should be more uniform (I don't like that Nil convention BTW). - The components taking type Element_Type is private as a generic parameter should also have with funciton "=" (l, r : element_Type) return Boolean; to avoid the reemergence of predefined "=". - Red_Black_Trees should raise an exception when trying to insert a duplicate element and Insert_Always is False. - Many things are done in the visible part of packages, but could very well be hidden, e.g. Ordered_Maps exports its implementation (instance of Red_Black_Trees), Read_Black_Trees exports the type Value_Ref_Type, which is not used in the specification. - Maybe I'll make more comments if I get to look at it a bit closer. Mats ^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: Ada Generic Library (very) preliminary release 1997-07-09 0:00 ` Mats Weber @ 1997-07-09 0:00 ` Brian Rogoff 1997-07-13 0:00 ` Matthew Heaney 0 siblings, 1 reply; 13+ messages in thread From: Brian Rogoff @ 1997-07-09 0:00 UTC (permalink / raw) On Wed, 9 Jul 1997, Mats Weber wrote: > Just had a fast look at it, here are a few comments: > > - A minor glitch: all files have cr lf as line separators, but most unices > prefer just a single line feed. I had to pass them through > > for f in * > do > cat $f | tr -d \\015 >/tmp/xuixuixui > mv /tmp/xuixuixui $f > done > > before I could watch them comfortably. Noted. I'll fix that. > - Many components are just plain record types, where I think good Ada 95 style > would make them tagged types for several reasons: automatic finalization and > possibility of inheritance among others. Deliberate choice. STL uses no dynamic dispatch, and strives for the efficiency of "hand coded C". While it may not be there, automatic finalization of components won't help the Ada version. Besides, you can make your own "safe" AGL from primitive components, the other way is an abstraction inversion. > - I don't know STL so my commments are from a "neutral" point of view. > > - Some components need a Nil constant of the Element_Type, some not. I think > this should be more uniform (I don't like that Nil convention BTW). Yes, the component interfaces are not as uniform as I'd like them. I agree, that Nil element type is wrong. However, the Nil node in Red_Black_Trees will probably stay. > - The components taking type Element_Type is private as a generic parameter > should also have > with funciton "=" (l, r : element_Type) return Boolean; > to avoid the reemergence of predefined "=". Good point. In the ordered containers, I'll ultimately provide a three way compare for element types, so this won't be a problem there. > - Red_Black_Trees should raise an exception when trying to insert a duplicate > element and Insert_Always is False. Agreed. > - Many things are done in the visible part of packages, but could very well be > hidden, e.g. Ordered_Maps exports its implementation (instance of > Red_Black_Trees), Read_Black_Trees exports the type Value_Ref_Type, which is > not used in the specification. > > - Maybe I'll make more comments if I get to look at it a bit closer. Thanks. Some of the things you mentioned will be fixed. -- Brian ^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: Ada Generic Library (very) preliminary release 1997-07-09 0:00 ` Brian Rogoff @ 1997-07-13 0:00 ` Matthew Heaney 1997-07-13 0:00 ` Brian Rogoff 0 siblings, 1 reply; 13+ messages in thread From: Matthew Heaney @ 1997-07-13 0:00 UTC (permalink / raw) In article <Pine.SGI.3.95.970709082112.10832B-100000@shellx.best.com>, Brian Rogoff <bpr@shellx.best.com> wrote: >> - Many components are just plain record types, where I think good Ada 95 style >> would make them tagged types for several reasons: automatic finalization and >> possibility of inheritance among others. > >Deliberate choice. STL uses no dynamic dispatch, and strives for the >efficiency of "hand coded C". While it may not be there, automatic >finalization of components won't help the Ada version. There may be confusion here: in Ada 95, there is no dynamic dispatch unless it's on a class-wide object. There is only a small space-penalty, to store the tag. Be very careful about using the STL - written in C++, using all the idioms of that language - as a model for an Ada 95 component library. Given this: type Root_Stack is abstract tagged private; type Bounded_Stack is new Root_Stack with private; ... The_Stack : Bounded_Stack; begin Push (5, On => The_Stack); This is as time-efficient as "hand coded Ada 83." (Or C, for that matter.) The operation Push is statically bound, even though the type itself is tagged. It would be true, however, that if Root_Stack derived (either publicly or privately) from Finalization.Controlled, then there would be a small penalty to call Initialize, Finalize, and Adjust, a penalty that need not be incured by bounded forms (ie, implemented as an array). To get maximum efficiency (and to not give those programmers with "optimitis" the excuse not to use the library), the library designer might very well decide to not inherit from controlled at the root, and to implement an unbounded form (say) by extending the uncontrolled parent with a component that is controlled. This localizes the "inefficiency" of controlled type usage to only those branches where it is strictly required. -------------------------------------------------------------------- Matthew Heaney Software Development Consultant <mailto:matthew_heaney@acm.org> (818) 985-1271 ^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: Ada Generic Library (very) preliminary release 1997-07-13 0:00 ` Matthew Heaney @ 1997-07-13 0:00 ` Brian Rogoff 1997-07-13 0:00 ` Matthew Heaney 1997-07-14 0:00 ` Jon S Anthony 0 siblings, 2 replies; 13+ messages in thread From: Brian Rogoff @ 1997-07-13 0:00 UTC (permalink / raw) On Sun, 13 Jul 1997, Matthew Heaney wrote: > In article <Pine.SGI.3.95.970709082112.10832B-100000@shellx.best.com>, > Brian Rogoff <bpr@shellx.best.com> wrote: > >Deliberate choice. STL uses no dynamic dispatch, and strives for the > >efficiency of "hand coded C". While it may not be there, automatic > >finalization of components won't help the Ada version. > > There may be confusion here: in Ada 95, there is no dynamic dispatch unless > it's on a class-wide object. There is only a small space-penalty, to store > the tag. I am aware of the "dispatch at call site" nature of Ada 95 OO. But the STL is an emphatically non-OO library, and I have decided to explore that design space, rather than using an OO approach. > Be very careful about using the STL - written in C++, using all the idioms > of that language - as a model for an Ada 95 component library. Based on a library developed in Ada 83, based on one in Scheme, ... No, that argument doesn't work. What I like about STL is not C++ specific, and though there are some things about C++ that make the expression of this library cleaner (gasp!), for example the ability to interleave public and private parts of a class, there are lots of things that allow the Ada version to be cleaner. STL is based on an analysis of the underlying structure of many algorithms, and is more rooted in algebraic specification than in BS-oriented, er, object-oriented programming. :-) It pretty much pushes the "cursor" type iterator design as far as possible. Yes, there are higher level ways to do iteration (Sather style iters, Icon style goal directed evaluation, ...) but the STL approach makes sense for an Ada 95 collection component library. STL is not just a collection of language dependent idioms. If you want to argue against it, you should at least have an understanding of it! > It would be true, however, that if Root_Stack derived (either publicly or > privately) from Finalization.Controlled, then there would be a small > penalty to call Initialize, Finalize, and Adjust, a penalty that need not > be incured by bounded forms (ie, implemented as an array). How small is this "small penalty"? I guess what you and I should do is measure the overhead of the suggested approaches, if efficiency were the overriding concern (it isn't, but I'm still intrereseted). > To get maximum efficiency (and to not give those programmers with > "optimitis" the excuse not to use the library), the library designer might > very well decide to not inherit from controlled at the root, and to > implement an unbounded form (say) by extending the uncontrolled parent with > a component that is controlled. This localizes the "inefficiency" of > controlled type usage to only those branches where it is strictly required. This is what I am suggesting for all of the AGL components. If you want safe versions "roll your own" from AGL. I'll probably provide safe versions "pre-wrapped", but it isn't a high priority with me now. (The high priority is finding a better way around the interleaving omission I mention above, since it forces too much to be public, as Mats Weber pointed out. I know this, but I am uncertain as to what to do. One solution might be to just break up the iterator child package into two or more, and use with clauses to "order" the elaboration of the children). -- Brian ^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: Ada Generic Library (very) preliminary release 1997-07-13 0:00 ` Brian Rogoff @ 1997-07-13 0:00 ` Matthew Heaney 1997-07-13 0:00 ` Brian Rogoff 1997-07-14 0:00 ` Jon S Anthony 1 sibling, 1 reply; 13+ messages in thread From: Matthew Heaney @ 1997-07-13 0:00 UTC (permalink / raw) In article <Pine.SGI.3.95.970713094409.22907C-100000@shellx.best.com>, Brian Rogoff <bpr@shellx.best.com> wrote: >(The high priority >is finding a better way around the interleaving omission I mention above, >since it forces too much to be public, as Mats Weber pointed out. I know >this, but I am uncertain as to what to do. One solution might be to just >break up the iterator child package into two or more, and use with clauses >to "order" the elaboration of the children). I haven't seen the library, but if you want some parts public and some private, you have to do it this way in Ada 95: type Root_Stack_Public is tagged record <public components here> end record; type Root_Stack is new Root_Stack_Public with private; procedure Push (Item : in Stack_Item; On : in out Root_Stack); private procedure <private op> (Stack : in out Root_Stack); ... end Stacks_G; What are you trying to do, exactly, that can't be done as is shown above? Matt P.S. Actually, I was in Troy last weekend. Didn't get a chance to visit the VCC, though. (I graduated from RPI back in '85.) -------------------------------------------------------------------- Matthew Heaney Software Development Consultant <mailto:matthew_heaney@acm.org> (818) 985-1271 ^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: Ada Generic Library (very) preliminary release 1997-07-13 0:00 ` Matthew Heaney @ 1997-07-13 0:00 ` Brian Rogoff 1997-07-14 0:00 ` Jon S Anthony 0 siblings, 1 reply; 13+ messages in thread From: Brian Rogoff @ 1997-07-13 0:00 UTC (permalink / raw) On Sun, 13 Jul 1997, Matthew Heaney wrote: > In article <Pine.SGI.3.95.970713094409.22907C-100000@shellx.best.com>, > Brian Rogoff <bpr@shellx.best.com> wrote: > >(The high priority > >is finding a better way around the interleaving omission I mention above, > >since it forces too much to be public, as Mats Weber pointed out. I know > >this, but I am uncertain as to what to do. One solution might be to just > >break up the iterator child package into two or more, and use with clauses > >to "order" the elaboration of the children). Which does not work for generic children. > I haven't seen the library, but if you want some parts public and some > private, you have to do it this way in Ada 95: > > ... stuff deleted ... No, what I want is something different, the problem is related to freezing and when I can instantiate generics. In the AGL, I use generic formal package parameters to plug algorithms to iterators (cursors) and in order to make the library comfortable I instantiate all of the "signatures" (null bodied generic packages which act like interfaces) that an Iterator_Type supports in the Iterators package (which is a child package of the generic container). The problem is that I can't instantiate those signature packages in the spec unless everything it needs is public, which is rather blecherous (for Ada). So a typical Iterators child package looks like this: generic package AGL.Some_Container.Iterators is type Iterator_Type is ... public type declaration, ugly ... ... Start(), Finish(), Increment(), etc ... ... other package decls ... package Bidirectional_Iterators is new AGL.Bidirectional_Iterators(Value_Type, Value_Ref_Type, Iterator_Type, Increment, Decrement, Get_Value, Set_Value, Get_Pointer, "=" ); ... etc ... and that Iterator_Type declaration has to be public for me to have that Bidirectional_Iterators instantiation. What I'd like is something like (pseudo Ada ahead) generic package AGL.Deques.Iterators is type Iterator_Type is private; private type Iterator_Type is ... full declaration here ... end private -- Illegal Ada ... stuff ... package Input_Iterators is new AGL.Input_Iterators( Value_Type, Iterator_Type, Increment, Get_Value ); ... more stuff ... private ... another private section ... end private ... more stuff ... end AGL.Deques.Iterators; Of course, that would fix my problem, but I believe that some other issues in Ada (the withing problem) require other fixes, so it is probably best to get many examples of things that are hard to do now, get workarounds, and see how heinous the results are before proposing a sweeping language change. Maybe a radical new view of packages is needed for the next Ada? For now, I'd settle for a tolerable workaround. Separating the child package into two parts doesn't help, because there seems to be no way for a child of a generic parent to use types from a sibling. It is clear that the STL, or a "generic library" like it can be implemented in Ada 95 (the RPI paper shows that nicely, and I highly recommend it) but I'd like to get the most elegant implementation I can, with visibility suitably restricted. > What are you trying to do, exactly, that can't be done as is shown above? I hope I've been clearer. -- Brian ^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: Ada Generic Library (very) preliminary release 1997-07-13 0:00 ` Brian Rogoff @ 1997-07-14 0:00 ` Jon S Anthony 1997-07-14 0:00 ` Brian Rogoff 0 siblings, 1 reply; 13+ messages in thread From: Jon S Anthony @ 1997-07-14 0:00 UTC (permalink / raw) In article <Pine.SGI.3.95.970713193310.25027A-100000@shellx.best.com> Brian Rogoff <bpr@shellx.best.com> writes: > child package of the generic container). The problem is that I can't > instantiate those signature packages in the spec unless everything it needs > is public, which is rather blecherous (for Ada). So a typical Iterators > child package looks like this: > > generic > package AGL.Some_Container.Iterators is > type Iterator_Type is > ... public type declaration, ugly ... > > ... Start(), Finish(), Increment(), etc ... > > ... other package decls ... > > package Bidirectional_Iterators is > new AGL.Bidirectional_Iterators(Value_Type, > Value_Ref_Type, > Iterator_Type, What was the design rationale for not allowing/wanting Iterator_Type to be a reference type (to a private Iterator_Struct_Type)? /Jon -- Jon Anthony OMI, Belmont, MA 02178 617.484.3383 "Nightmares - Ha! The way my life's been going lately, Who'd notice?" -- Londo Mollari ^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: Ada Generic Library (very) preliminary release 1997-07-14 0:00 ` Jon S Anthony @ 1997-07-14 0:00 ` Brian Rogoff 0 siblings, 0 replies; 13+ messages in thread From: Brian Rogoff @ 1997-07-14 0:00 UTC (permalink / raw) On 14 Jul 1997, Jon S Anthony wrote: > In article <Pine.SGI.3.95.970713193310.25027A-100000@shellx.best.com> Brian Rogoff <bpr@shellx.best.com> writes: > > > child package of the generic container). The problem is that I can't > > instantiate those signature packages in the spec unless everything it needs > > is public, which is rather blecherous (for Ada). So a typical Iterators > > child package looks like this: > > > > generic > > package AGL.Some_Container.Iterators is > > type Iterator_Type is > > ... public type declaration, ugly ... > > > > ... Start(), Finish(), Increment(), etc ... > > > > ... other package decls ... > > > > package Bidirectional_Iterators is > > new AGL.Bidirectional_Iterators(Value_Type, > > Value_Ref_Type, > > Iterator_Type, > > What was the design rationale for not allowing/wanting Iterator_Type > to be a reference type (to a private Iterator_Struct_Type)? I wanted my Iterator_Type to be stack-allocatable, and have value semantics. If I make an Iterator_Record_Type, and have Iterator_Type be a reference to it, I lose all that. Since the containers themselves are usually access types, my largest Iterator_Type is just a record with an access type and an integer offset. As an aside, the "Allocators" of the STL are the part I am least comfortable with. What you have in mind would obviously allow the iterator record declaration to be hidden. I think it is rather unfortunate that Ada doesn't allow interleaved public and private parts of the package spec. Was anything like that considered during the 9X revision process? It seems to fit OK with the "essence of Ada" as I see it, and would certainly make what I'm trying to do now a lot prettier. Most of the workarounds I have considered seem awfully ugly. -- Brian ^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: Ada Generic Library (very) preliminary release 1997-07-13 0:00 ` Brian Rogoff 1997-07-13 0:00 ` Matthew Heaney @ 1997-07-14 0:00 ` Jon S Anthony 1 sibling, 0 replies; 13+ messages in thread From: Jon S Anthony @ 1997-07-14 0:00 UTC (permalink / raw) In article <Pine.SGI.3.95.970713094409.22907C-100000@shellx.best.com> Brian Rogoff <bpr@shellx.best.com> writes: > STL is based on an analysis of the underlying structure of many algorithms, > and is more rooted in algebraic specification than in BS-oriented, er, > object-oriented programming. :-) ;^) I hear ya! > > It would be true, however, that if Root_Stack derived (either publicly or > > privately) from Finalization.Controlled, then there would be a small > > penalty to call Initialize, Finalize, and Adjust, a penalty that need not > > be incured by bounded forms (ie, implemented as an array). > > How small is this "small penalty"? I guess what you and I should do is > measure the overhead of the suggested approaches, if efficiency were the > overriding concern (it isn't, but I'm still intrereseted). IME, your instincts here Brian are quite right. For something like the STL level of "componentry", this is _not_ a "small overhead", given any half reasonable definition of "small". /Jon -- Jon Anthony OMI, Belmont, MA 02178 617.484.3383 "Nightmares - Ha! The way my life's been going lately, Who'd notice?" -- Londo Mollari ^ permalink raw reply [flat|nested] 13+ messages in thread
end of thread, other threads:[~1997-07-14 0:00 UTC | newest] Thread overview: 13+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 1997-07-08 0:00 Ada Generic Library (very) preliminary release Brian Rogoff 1997-07-09 0:00 ` Richard Kenner 1997-07-09 0:00 ` Brian Rogoff 1997-07-09 0:00 ` Robert Dewar 1997-07-09 0:00 ` Mats Weber 1997-07-09 0:00 ` Brian Rogoff 1997-07-13 0:00 ` Matthew Heaney 1997-07-13 0:00 ` Brian Rogoff 1997-07-13 0:00 ` Matthew Heaney 1997-07-13 0:00 ` Brian Rogoff 1997-07-14 0:00 ` Jon S Anthony 1997-07-14 0:00 ` Brian Rogoff 1997-07-14 0:00 ` Jon S Anthony
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox