Re: Some questions on a library design

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

On Wed, 18 Jun 1997, Robert A Duff wrote:
> In article <Pine.SGI.3.95.970617154248.6950A-100000@shellx.best.com>,
> Brian Rogoff  <bpr@shellx.best.com> wrote:
> >There is nothing stopping the client from storing tagged types in the 
> >AGL collections, and dispatching on them in the client code. But why 
> >should I have dispatching in the library when all of the container types 
> >are known statically? 
> 
> I wasn't suggesting that you have dispatching in the library.  I was
> suggesting that the client be able to *choose* dispatching, by creating
> (e.g.) a "vector of sequence'Class", where sequence is a superclass of
> vector, list, deque, etc., and then the client could iterate through
> that vector, and dispatch to the appropriate *whatever* for that class.
> 
> But the client that just wants a vector of lists would get *zero*
> dispatching calls.

I'd have to think about that approach some more. Sounds like a reasonable
alternative approach. Of course, you'd still parametrize (with generics)
the element types and comparison operations too.

> I admit, I haven't thought this through.  But it seems like Ada's
> ability to choose dispatching-vs-not-dispatching at the call site should
> allow you to do what STL does in terms of efficiency, while still
> *allowing* polymorphic calls to sequence operations.  In C++, you have
> to choose virtual-or-not at the declaration of the function, which
> constrains you a bit.

Actually, there was a raging multi-NG debate on the efficiency of the STL 
which casts some doubt on the speed claims. The important reasons to 
copy the STL for me are more "social" than "technical"; lots of people 
use C++ (including me), so commonality of libraries saves precious brain
space :-). 

> >In any case, I am deliberately copying the STL, in which dynamic dispatch, 
> >benefits and all, is avoided. You may prefer the Booch components to the 
> >AGL, and there is room for both (and more!).
> 
> Fair enough.  I'm just wondering if one can't get the best of both
> worlds in Ada.

Now I'm wondering the same thing...

> >I'm not sure I understand your suggestion. Do you mean pass in a generic
> >formal package (which would get Red_Black_Trees or Splay_Trees) to the
> >Sets package, ...
> 
> Yeah, something like that.  I guess I don't understand what you're
> trying to do.  Do you want the client to be able to choose which sort of
> set is used?  Or not?

Originally not, although obviously the client with source code should be
able to change the representation, and I'll make my sources available when
they are ready. The C++ STL uses red-black trees to represent sets,
multisets, maps, and multimaps (all of these are *ordered*, the SGI STL
also supports hashed/unordered versions of all of these) so I am following 
its lead for now. I had hoped that I could avoid making the client do lots 
of instantiations by being clever (instantiating each iterator class in 
the child Container.Iterators of Container, see the end of this message)
but I am being thwarted so far.

Since I am having trouble doing what I wanted to do, I may actually just go
ahead and have a representation package parameter. I'm thinking that its
use would be something like this:

package Integer_RBTrees is 
    new Red_Black_Trees(Integer,"<",Insert_Always=>False);

package Integer_Set_Rep is 
    new AGL.Set_Signature( Integer_RBTrees.Tree_Type,
                           Integer_RBTrees.Value_Type,
                           ... etc ... );

package Integer_Set is new AGL.Sets( Integer, "<", Integer_Set_Rep );

which is a bit heavier than what I wanted: 

package Integer_Set is new AGL.Sets( Integer, "<" );

since instantiating the signature package requires that the client provide 
a lot of parameters, but has the advantage that the client can select the 
set representation.

> >A while ago, Norman Cohen suggested "package parts" as a solution to the 
> >infamous "withing problem". There have been quite a few times while I've 
> >been crafting at this library that I also wished for the ability to
> >interleave specs and private parts, so I certainly appreciate that
> >suggestion a lot more now, outside of the context of package spanning
> >mutually recursive specs!
> 
> Maybe just alternating public and private parts of a package would
> suffice here?

Absolutely. Let me provide a real piece of code, so I can illustrate a bit 
better what I am trying to do, and we can really see if there is a problem 
or I am just clueless (or both ;-)

with AGL.Basic_Types;
with AGL.Input_Iterators;
with AGL.Output_Iterators;
with AGL.Forward_Iterators;
with AGL.Bidirectional_Iterators;

generic
package AGL.Lists.Iterators is
    type Iterator_Type is
       record
           Node: Cell_Ptr := null;
       end record;

    function Start( L: List_Type ) return Iterator_Type;
    function Finish( L: List_Type ) return Iterator_Type;
    function "=" ( I: Iterator_Type; J: Iterator_Type ) return Boolean;
    procedure Next( I: in out Iterator_Type );
    procedure Prev( I: in out Iterator_Type );
    function Get_Value( I: in Iterator_Type ) return Value_Type;
    procedure Set_Value( I: in Iterator_Type; V: in Value_Type );
    function Get_Pointer( I: in Iterator_Type ) return Value_Ptr;

    package Input_Iterators is
      new AGL.Input_Iterators(Value_Type,
                          Iterator_Type,
                          Next,
                          Get_Value
                          );
    package Output_Iterators is
      new AGL.Output_Iterators(Value_Type,
                               Iterator_Type,
                               Next,
                               Set_Value
                               );
    package Forward_Iterators is
      new AGL.Forward_Iterators(Value_Type,
                            Iterator_Type,
                            Value_Ptr,
                            Next,
                            Get_Value,
                            Set_Value,
                            Get_Pointer
                            );
    package Bidirectional_Iterators is
      new AGL.Bidirectional_Iterators(Value_Type,
                                  Iterator_Type,
                                  Value_Ptr,
                                  Next,
                                  Prev,
                                  Get_Value,
                                  Set_Value,
                                  Get_Pointer,
                                  "=");
end AGL.Lists.Iterators;

In the Iterators package for the Lists container, I instantiate all of the 
possible Iterator signatures (Input, Output, Forward, Bidirectional) that a 
list supports, so that a client can get at it without doing the
instantiation herself. Now, if we could alternate public and private parts
of a package, I could move my Iterator_Type to the private part of the 
package, and then put those signature instantiations after that. (Ada
newbie quiz: why doesn't it work if we make Iterator_Type private?). And
while that is helpful here, it is *way* more helpful with respect to your
suggestion about formal package parameters, since I could then instantiate
Set_Signature inside Red_Black_Trees (and Splay_Trees, and others...) and
avoid that onerous instantiation by the client. 

-- Brian