Re: STL in Ada95 [was: Any research putting c above ada?]

[Brian Rogoff <bpr@shellx.best.com>]

John Volan wrote: 
> The C++ STL was forced into some particularly goofy complexities because
> of C++'s lack of anything comparable to Ada95's generic contract model.
> For instance, every container class that allows bidirectional traversal
> has to be accompanied by both a forward iterator class _and_ a reverse
> iterator class.  Why? Because all those reusable algorithm templates are
> written in terms of an iterator having a "++" increment operator.  If
> you have a bidirectional iterator that has both "++" and "--", you can't
> instantiate an algorithm twice using "++" in one case and "--" in the
> other.  Instead, you have to have a reverse iterator class wrapped
> around your forward iterator class, with the "++" for the reverse
> iterator being implemented using the "--" of the forward iterator.
> 
> In Ada95, this is totally unnecessary.  Suppose you have
> Some_Iterator_Type that has both an Advance procedure (++ analog) and a
> Backup procedure (-- analog).  A reusable algorithm template might look
> something like this:
> 
>   generic
>     type Iterator_Type is private;
>     type Item_Type is private;
>     with procedure Advance (Iterator : in out Iterator_Type);                  
>     with function Get_Item (Iterator : in Iterator_Type) return
> Item_Type;
>     ... -- whatever other formals
>   procedure Do_Whatever                     -- whatever the algorithm is
>     (Start, Stop : in Iterator_Type; ... ); -- whatever parameters
> 
> ... followed by instantiation of Do_Whatever with Advance => Retreat 
>     to get Reverse_Iterators
> No need for all those reverse iterator types!

Yes, the RPI version omitted reverse iterators, and the authors wrote that
they planned to use Adaptors to do this. 

> > One thing I wish I could do better is have the structure of Iterator
> > categories reflected in the Ada code.
> >
> > In the STL, Forward_Iterators
> > have properties of both Input_Iterators and Output_Iterators, i.e.
> ...
> > Now, I could just define Forward_Iterators by having two generic
package
> > parameters, but then I'd have to instantiate an Input/Output Iterator
pair
> > every time I wanted a Forward_Iterators package.

> Nah, I wouldn't bother.  Again, that's the contortions C++ forces you
> into because you can't really specify generic contracts.  If an                
> algorithm needs something that supports the interface for an "input
> iterator", the generic clause on that algorithm should just look
> something like what you wrote:

I disagree. I think that if we see the same contract over and over again,
we should be able to capture that contract and replace it with an
abstraction, so I'd write 

> generic
>   type Value_Type is private;
>   type Iterator_Type is private;
>   with procedure Next ( i: in out Iterator_Type ) is <>;
>   with function  Get_Value ( i: in Iterator_Type ) return Value_Type is
<>;
>  procedure ... -- whatever algorithm
>  -- (but don't bother with an Input_Iterator package)

as

generic
    type Value_Type is private;
    type Iterator_Type is private;
    with procedure Next ( i: in out Iterator_Type ) is <>;
    with function  Get_Value ( i: in Iterator_Type ) return Value_Type is
<>;
package AGL.Input_Iterators is
end AGL.Input_Iterators;

generic 
	with package Iterators is new AGL.Input_Iterators(<>);
procedure ... -- whatever algorithm

and so I capture the contract as a "signature". Why do you feel that it is 
better to explicitly write out the parameters during instantiation rather 
than capturing the commonality in a signature package?

In my current implementation, every generic container representation has a
child package Iterators which instantiates nested packages corresponding to
each of the iterator categories (Input, Output, Forward, etc.) that it
supports, so you get packages which can be used as generic parameters to
these algorithms easily. It's pretty much the same as it is in the RPI
implementation, except that they nested the Iterator package, and
instantiated the different categories, inside the top package, i.e., they
had 


Lists.Iterators,             -- Iterators textually nested inside Lists
Lists.Forward_Iterators,     -- Forward_Iterators textually nested inside
Lists
etc., 

and I have 

Lists
Lists.Iterators                     -- Child package
Lists.Iterators.Forward_Iterators   -- Forward_Iterators textually nested 
                                    -- inside Lists.Iterators
etc.

I like this, because it separates the iterators from their containers, so
you can use the containers without dragging the iterators along. 

Where I wish I could do better is in  the factoring of the iterator
categories. The categories form an inheritance hierarchy of sorts. If we
were to write these in pseudo-Java:  

interface InputEnumerator extends TrivialEnumerator {
	void next();
	Element getValue();
	void setValue(Element e);
}

interface OutputEnumerator extends TrivialEnumerator {
	void next();
	void setValue(Element e);
}

interface ForwardEnumerator extends OutputEnumerator, InputEnumerator {
}

interface BidirectionalIterator extends ForwardEnumerator {
	void prev();
	boolean equals( BidirectionalIterator bdi );
}

etc.

I can combine interfaces, and inherit from them. If I try to do something 
similar with the generic signatures, I would then have to instantiate 
every "super-signature" that the signature "inherits" from, where by 
inheritance I mean something like 

generic 
	-- And Forward_Iterators is built from Input and Output
Iterators...
	with package Supersig is new Forward_Iterators(<>);
	with procedure Prev ( Iterator : in out Supersig.Iterator_Type );
	with function "=" ( Left, Right : Supersig.Iterator_Type ) 
               return Boolean;
package Bidirectional_Iterators is
end Bidirectional_Iterators;

So this Ada idiom of using generic signatures doesn't seem to be
"composable", in that if I want to have signatures composed of signatures 
composed..., I'll have to instantiate each one to just get the one I want.
Rather than not use these signature packages at all though, I just have one
for each category, and leave them independent. That's OK for this library,
because it is small, but for a library with many more categories and
relationships, I think there might be a problem. 

-- Brian