Re: Active Iteration (was: How to use abstract data types)

[matthew_heaney@acm.org (Matthew Heaney)]

In article <6jcov8$ske$1@nnrp1.dejanews.com>, adam@irvine.com wrote:

(start of quote)
Regarding the example at LRM 3.9.3(15-16):

    package Sets is
        subtype Element_Type is Natural;
        type Set is abstract tagged null record;
        function Empty return Set is abstract;
        function Union(Left, Right : Set) return Set is abstract;
        function Intersection(Left, Right : Set) return Set is abstract;
        function Unit_Set(Element : Element_Type) return Set is abstract;
        procedure Take(Element : out Element_Type; From : in out Set)
             is abstract;
    end Sets;

    Notes on the example: Given the above abstract type, one could
    then derive various (nonabstract) extensions of the type,
    representing alternative implementations of a set.  One might use
    a bit vector, but impose an upper bound on the largest element
    representable, while another might use a hash table, trading off
    space for flexibility.

It seems to me that, if your two choices are a bit vector and a hash
table, it's likely that other modules in the program that use a Set
would make this choice statically, because they'd already have an idea
of the upper bound on elements in the set.  My question: Would you
therefore choose instead to use a generic to implement a "Set"?  If
not, but if you would choose to use a generic to implement a Library
in my example, what's is the difference between the two examples that
would cause you to use different language constructs to implement
them?
(end of quote)

I probably wouldn't have bothered with the abstract root tagged type.

In fact, this is the very thing I didn't like about David Weller's
implementation of the Ada 95 Booch components.  I feel that Root_Queue and
Root_Stack etc abstract tagged types are unnecessary, and complicate my
life as an instantiator of a component.

Let's fix up the example a bit.  Realistically, you're going to make the
unit generic no matter what, because your set should work for any kind of
type.  Here, though, it looks like they intend for the set to work with
discrete types only, so let's import a generic discrete type:

generic
   type Element_Type is (<>);
package Sets is
        
        type Set is abstract tagged null record;
        function Empty return Set is abstract;
        function Union(Left, Right : Set) return Set is abstract;
        function Intersection(Left, Right : Set) return Set is abstract;
        function Unit_Set(Element : Element_Type) return Set is abstract;
        procedure Take(Element : out Element_Type; From : in out Set)
             is abstract;
end Sets;

Let's create a derived type:

generic
package Sets.Bit_Vector_G is

   type Bit_Vector_Set is new Set with private;
   <primitive ops for Bit_Vector_Set>
...
end Sets.Bit_Vector_G;

My issue is that if I want a bit vector set, I have to do two instantiations:

type Device_Id is range 1 .. 10;

package Device_Id_Sets is 
   new Sets (Device_Id);

package Device_Id_Sets.Bit_Vector is
   new Device_Id_Sets.Bit_Vector_G;

Not that big of a deal, but if I want just a bit vector set, it'd be nice
to only have to create one instantiation.  The benefit of the tagged type
approach is that it allows you to copy between set representations, using
primitive operations of the type.

To the root set package, let's add another class-wide operation:

   procedure Copy 
      (From : in Set'Class;
        To      : in out Set'Class) is

        From_Copy : Set'Class := From;
        Element : Element_Type;
   begin
      To := Empty;

      while not Is_Empty (From_Copy) loop
         Take (Element, From_Copy);
          To := Union (To, Unit_Set (Element));
      end loop;
   end Copy;

You see that this works with any type that derives from type Set.  And
that's what the tagged type approach buys you: the ability to manipulate
objects of different types within the same type class.

But...it's not the only way. You can do a lot of the same things with a
generic using "static polymorphism."  It's just that you have to
instantiate the copy operation (or any class-wide utility operation) with
your type (because it's not in the same class anymore).  Let's write the
set so it's not derived:

package Sets is
   pragma Pure;
end;

generic
   type Element_Type is (<>);
package Sets.Bit_Vector is
   
   type Bit_Vector_Set is private;  -- doesn't really need to be tagged
   <primitive ops>
...
end Sets.Bit_Vector;

Now we can make a "class-wide" operation, implemented as a generic, to do a
copy:

generic
   type Element_Type is (<>);

   type Source_Set (<>) is private;
   procedure Take
      (Element :     out Element_Type; 
       From      : in out Source_Set) is <>;
...
   type Target_Set (<>) is private;
   function Empty return Target_Set is <>;
   function Union (L, R : Target_Set) return Target_Set is <>;
   function Unit_Set (Element : Element_Type) return Target_Set is <>;

procedure Sets.Generic_Copy 
   (From : in Source_Set;
     To     : in out Target_Set);

procedure Sets.Generic_Copy (...) is

   From_Copy : Source_Set := From;
   Element : Element_Type;
begin
   To := Empty;

   while not Is_Empty (From_Copy) loop
      Take (Element, From_Copy);
       To := Union (To, Unit_Set (Element));
   end loop;  
end Sets.Generic_Copy;

Pretty much the same as before.  Note that the instantiation penalty is
small, because all the operations for the type are imported as default ops.

(Another note: the examples above have a relatively inefficient
implementation, because you have to make a copy of the source set.  Why
bother?  If your type exports an active iterator, then no copy is required,
because you can non-destructively visit every item in the source set. 
Write me if you have questions about how to do it.)

So it's a bit of a tradeoff.  If you need just one kind of set most of the
time, then the non-derived technique is easier, because you only require
just the one instantiation.  But if you need a "class-wide" utility
operation that operates on different kinds of sets, then you do have to do
an "extra" instantiation, of the (generic) utility.

If you have different kinds of sets (bit vector vs hash table) in your
application, and you need to operate on different kinds, then maybe the
derived technique is better, because it will simplify the implementation
(and invokation) of class-wide operations.

A approximate analogy is the types in the children of Ada.Strings.  Here,
you have Bounded_String and Unbounded_String as different classes of type. 
The types aren't tagged, nor do they derive from a common root type.  So
there aren't any "class-wide" operations to convert between Bounded_String
and Unbounded_String.

But this "inconvenience" isn't much of an inconvenience, because you just
convert the source type to an intermediate representation, type
Standard.String, and then pass that to the constructor for the target type.

Just imagine that if you wanted an unbounded queue or stack.  This is
pretty common - you don't want to have to worry about how big you have to
declare the bounded version.  To go the derived type technique, you'd have
to create that root queue type every time for every different instantation,
and then create another instantiation (the child) to get the type you
"really" want.  All this because of that 1-in-100th time you need some
variation (say, a bounded queue).

I'm exaggerating a little, but it's to make a point.  You can get a ton of
mileage out of generics, especially nowadays with the ability to import a
package as a generic formal parameter.

I do use tagged types.  In some of the ACL stuff I've done, tagged-ness
shows up as an implementation technique (the memory management stuff comes
to mind).  But different types are usually different classes.  For example,
I wrote

ACL.Trees.B_Trees
ACL.Trees.BStar_Trees
ACL.Trees.BPlus_Trees

All three types are different classes; there is no "Root_B_Tree" type from
which all the others derive.  Although I made the types publically tagged,
it's only because I had to make the types tagged anyway, because it needs
to (privately) inherit from Finalization.Controlled.  So tagged-ness was
basically a freebee for the client (who I would never expect to actually
derive from it, but who knows?).

Hope that sheds some light,
Matt