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

["John G. Volan" <johnvolan@sprintmail.com>]

Brian Rogoff wrote:
> 
> Same here. It is even possible to program at the same "low-level" as the
> C++ STL by using Interfaces.C. 

Nah...why bother?  I'd rather provide a Size_Type and whatnot as generic
formal parameters, rather than kludge in a lot of
implementation-dependent details.

> OTOH, I agree with Kevin Cline that the
> type inferencing done in C++ is convenient, and that a C++ programmer might
> find the long declarations troubling, especially for textbook examples
> where the length of the working code is close to the length of the
> declaration section. I suspect that this will be less of a problem in
> most real code.

I suppose you're talking about all those generic algorithms (template
functions) in the STL.  Shrug.  Personally, I'd rather _know_ what
instantiations are being linked into my program, than have them all be
implicit.  Goes back to the easy-to-write vs.
easy-to-read/understand/debug issue between C++ and Ada95.

> I'm "evolving" a version for my own use. I am trying to stay as close to
> the C++ STL as possible, but I've left out custom allocators (still
> experimenting) 

I assume you mean passing a Storage_Pool as a generic formal parameter
into a container generic package.  Might be nice to have, but I wouldn't
bother for a first cut.  Personally, I'm a little mystified about all
those contortions the STL had to go into about allocators. All that
stuff about distinguishing pointers as NEAR vs. FAR vs. HUGE -- is that
just a peculiarity of doing C on the Wintel platform, or is that a
platform-independent peculiarity of C programming? :-) 

> and I'm starting to diverge in that I'd prefer a more
> integrated approach to exceptions in the library, more like Cay Horstmann's
> Safe STL. 

Hmm, sounds interesting... is there a URL for that?

> The two languages and their respective programming cultures are
> different enough that the the design priorities in the source library (C++
> STL) will differ a bit.

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

  procedure Do_Whatever   
    (Start, Stop : in Iterator_Type; ...)
  is
    Iterator : Iterator_Type := Start;
    Item : Item_Type;
  begin
    while Iterator /= Stop loop
      Item := Get_Item(Iterator);
      ... -- whatever
      Advance (Iterator);
    end loop;
  end Do_Whatever;

This could be instantiated on the one hand:

  procedure Do_Whatever_Forward is new Do_Whatever
    (Iterator_Type => Some_Iterator_Type,
     Item_Type     => Some_Item_Type,
     Advance       => Advance,
     Get_Item      => Get_Item,
     ... whatever else... );

and on the other hand:

  procedure Do_Whatever_Backward is new Do_Whatever
    (Iterator_Type => Some_Iterator_Type,
     Item_Type     => Some_Item_Type,
     Advance       => Backup,          -- !!
     Get_Item      => Get_Item,
     ... whatever else... );

No need for all those reverse iterator types!

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

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

Or if the algorithm needs an "output iterator" contract:

> generic
>   type Value_Type is private;
>   type Iterator_Type is private;
>   with procedure Next ( i: in out Iterator_Type ) is <>;
>   with procedure Set_Value ( I: in Iterator_Type; V: Value_Type) is <>;
  procedure ... -- whatever algorithm
  -- (but don't bother with an Output_Iterator package)

Or if the algorithm needs the full "forward iterator" contract:

> generic
>   type Value_Type is private;
>   type Iterator_Type is private;
>   type Value_Ptr is access all Value_Type;
>   with procedure Next ( I: in out Iterator_Type ) is <>;
>   with function Get_Value ( I: in Iterator_Type ) return Value_Type is <>;
>   with procedure Set_Value ( I: in Iterator_Type; V: Value_Type) is <>;
>   with function Get_Pointer ( I: in Iterator_Type ) return Value_Ptr is <>;
>   with function "="(I: Iterator_Type; J: Iterator_Type) return Boolean is <>;
  procedure ... -- whatever algorithm
  -- (but don't bother with a Forward_Iterator package)

> Right now I just leave
> this commonality in the documents, and express each Iterator independently.

Exactly the right thing, IMHO.

------------------------------------------------------------------------
Internet.Usenet.Put_Signature 
  (Name => "John G. Volan",  Home_Email => "johnvolan@sprintmail.com",
   Slogan => "Ada95: The World's *FIRST* International-Standard OOPL",
   Disclaimer => "These opinions were never defined, so using them " & 
     "would be erroneous...or is that just nondeterministic now? :-) ");
------------------------------------------------------------------------