Ada Generic Library (very) preliminary release

Ada Generic Library (very) preliminary release

[Brian Rogoff]

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

Re: Ada Generic Library (very) preliminary release

[Richard Kenner]

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.

Re: Ada Generic Library (very) preliminary release

[Robert Dewar]

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.

Re: Ada Generic Library (very) preliminary release

[Brian Rogoff]

	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.
> 
> 

Re: Ada Generic Library (very) preliminary release

[Mats Weber]

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

Re: Ada Generic Library (very) preliminary release

[Brian Rogoff]

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

Re: Ada Generic Library (very) preliminary release

[Matthew Heaney]

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

Re: Ada Generic Library (very) preliminary release

[Brian Rogoff]

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

Re: Ada Generic Library (very) preliminary release

[Matthew Heaney]

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

Re: Ada Generic Library (very) preliminary release

[Brian Rogoff]

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

Re: Ada Generic Library (very) preliminary release

[Jon S Anthony]

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

Re: Ada Generic Library (very) preliminary release

[Brian Rogoff]

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

Re: Ada Generic Library (very) preliminary release

[Jon S Anthony]

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