Multiple Inheritance in Ada 95 [was Re: Self-referential types]

[Tucker Taft <stt@averstar.com>]

Ted Dennison wrote:
> 
> In article <s06ji18vh1s47@corp.supernews.com>,
>   "news.oxy.com" <Vladimir_Olensky@oxy.com> wrote:
> >
> > Matthew Heaney wrote in message <3802f2db_2@news1.prserv.net>...
> > >This is the basis for programming with access discriminants, which is
> > >how you do MI in Ada95.
> > You might  put a short article regarding this issue to Adapower.
> > I am sure it will be very useful.
> 
> I'd like to heartily second that one. I tried every resource I could
> find to figure this out before I resorted to c.l.a. The example in
> Cohen's book is wrong, and he doesn't address its use in MI at all. The
> rationale just talks about it but doesn't put up any examples. I
> couldn't even find anything in the LRM that said this was legal after
> over an hour of searching. It'd be a shame if the only real
> documentation of this technique was word of mouth.

I have included a copy of a Language Study Note I wrote during the
Ada 9X design process.  It explains the was to support multiple-inheritance
hierarchies using various Ada 95 features.  Feel free to post this
to AdaPower, etc.

> 
> --
> T.E.D.
> 
> Sent via Deja.com http://www.deja.com/
> Before you buy.

-- 
-Tucker Taft   stt@averstar.com   http://www.averstar.com/~stt/
Technical Director, Distributed IT Solutions  (www.averstar.com/tools)
AverStar (formerly Intermetrics, Inc.)   Burlington, MA  USA
--------------------------------------------------------------------
!topic LSN on Multiple Inheritance in Ada 9X
!key LSN-1033 on Multiple Inheritance in Ada 9X
!reference MS-3.4.1;4.6
!reference MS-3.6.1;4.6
!reference MS-12.3.6;4.6
!from Tucker Taft $Date: 92/09/02 17:44:17 $ $Revision: 1.1 $
!discussion

This Language Study Note discusses the creation of
multiple inheritance type (semi-)lattices using the proposed
Ada 9X object-oriented programming features.  
It is in part directed at programmers familiar with
other object-oriented programming languages that 
build in syntax for a particular multiple-inheritance mechanism,
rather than simply providing features needed to support it.

In this discussion, we will in general use Ada 9X terminology, where
every object has a single "type," and multiple similar types
(typically in some kind of hierarchy or oligarchy)
form a "class" of types.  If we want to use the term "class" as
it is used in C++ or Eiffel, we will always say "C++ class" or
"Eiffel class."

In some languages, such as Eiffel, multiple inheritance
serves many purposes.  For example, there is no equivalent in Eiffel
to the "include" statement of C/C++ or the "with/use" clauses
of Ada.  Therefore, to gain direct visibility to the
declarations of some other module, one must inherit from
that module (Eiffel class).

In C/C++, one can simply "include" file containing
a set of type and object definitions.

In Ada, one first identifies the external modules of interest
via "with" clauses, and then chooses selectively whether
to make only the name of the module (package) visible, or
its contents (via a "use" clause).

In both Eiffel and C++, one can choose to inherit from
some other type, without making that visible to clients
of the new type.  Effectively, the linguistic multiple 
inheritance mechanism is being used to express not
an "is a refinement of" relationship, but rather 
an "is implemented using" relationship.

Finally, there are the situations where
a single type visibly inherits from two or
more other types.  In these cases, this is rarely
a symmetric situation.  Rather, one of the ancestor
types is the "primary" ancestor, while the others
are typically "mix-ins" designed to augment behavior
of the primary ancestor.

Ada 9X supports multiple-inheritance module inclusion
(via multiple "with"/"use" clauses), multiple-inheritance
"is-implemented-using" via private extensions and record composition,
and multiple-inheritance mix-ins via the use of
generics, formal packages, and access discriminants.

The Ada 9X mechanisms are designed to eliminate "distributed" overhead,
so that there is no added expense for the general user
of the language because of the presence of the mechanisms supporting
multiple inheritance.

There are basically three distinct situations associated
with multi-inheritance mixins:

  1) The case where the mix-in provides components
     and operations, and any overriding of these operations
     needs only to look at the components of the mix-in itself.

  2) The case where the mix-in provides components and operations,
     and some of the overriding of these operations needs access
     to the whole object, rather than just the components of the mix-in.

  3) Like (2), and in addition, any object with the mix-in must
     be able to be linked onto a list (or into some similar 
     heterogeneous data structure) of other objects with the same mix-in.

Case (1) is handled completely in Ada 9X by a record or private extension,
with the type being mixed in (in a possibly extended form) as a 
component of the record extension.

Case (2) is handled with a generic, that takes any type in
a given class (formal derived type), adds components (via extension) 
and operations, and then reexports the extended type.  The new operations
have access to the whole object, not just to the components
being added.

Case (3) is handled with an access discriminant, that provides
access to the enclosing object for the operations of the mix-in,
while still allowing links through the mix-in.  Generics can
also be used to simplify the definition.

Here are a few examples:

Case (1) --
   One has an abstract type "Set_of_Strings" and one wants to implement
   it by reusing an existing (concrete) type "Hash_Table":

   Here is the abstract type:

      type Set_Of_Strings is tagged limited private;
      type Element_Index is new Natural;  -- Index within set.

      No_Element : constant Element_Index := 0;

      Invalid_Index : exception;

      procedure Enter(
        -- Enter an element into the set, return the index
         Set : in out Set_Of_Strings; 
         S : String; 
         Index : out Element_Index) is <>;

      procedure Remove(
        -- Remove an element from the set; ignore if not there
         Set : in out Set_Of_Strings; 
         S : String) is <>; 

      procedure Combine(
        -- Combine Additional_Set into Union_Set
         Union_Set : in out Set_Of_Strings;
         Additional_Set : Set_Of_Strings) is <>;

      procedure Intersect(
        -- Remove all elements of Removal_Set from Intersection_Set
         Intersection_Set : in out Set_Of_Strings;
         Removal_Set : Set_Of_Strings) is <>;

      function Size(Set : Set_Of_Strings) return Element_Index is <>;
        -- Return a count of the number of elements in the set

      function Index(
        -- Return the index of a given element; return No_Element if not there.
         Set : Set_Of_Strings; 
         S : String) return Element_Index is <>;

      function Element(Index : Element_Index) return String is <>;
        -- Return element at given index position
        -- raise Invalid_Index if no element there.
    private
      type Set_Of_Strings is tagged limited ...

   Here is an implementation of this abstract type that
   inherits its interface from Set_Of_Strings, and its implementation
   from Hash_Table:

      type Hashed_Set(Table_Size : Positive) is 
        new Set_Of_Strings with private;

      -- Now we give the specs of the operations being implemented
      procedure Enter(
        -- Enter an element into the set, return the index
         Set : in out Hashed_Set;
         S : String; 
         Index : out Element_Index);

      procedure Remove(
        -- Remove an element from the set; ignore if not there
         Set : in out Hashed_Set;
         S : String);
      . . . etc.

    private
      type Hashed_Set(Table_Size : Positive) is 
        new Set_Of_Strings with record
          Table : Hash_Table(1..Table_Size);
        end record;

   In the body of this package, we would provide the bodies
   for each of the operations, in terms of the operations
   available from Hash_Table.  Chances are they don't match exactly,
   so a little bit of "glue" code will be necessary in any case.
      
  
Case (2) --
   One has a type Basic_Window that responds to various
   events and calls.  One wants to embellish the Basic_Window
   in various ways with various mix-ins.

     type Basic_Window is tagged limited private;
     procedure Display(W : Basic_Window);
     procedure Mouse_Click(W : in out Basic_Window; Where : Mouse_Coords);
     . . . 

   Now one can define any number of mix-in generics, like the following:
  
     generic
       type Some_Window is new Window with private;
         -- take in any descendant of Window
     package Label_Mixin is
       type Window_With_Label is new Some_Window with private;
         -- Jazz it up somehow.

       -- Overridden operations:
       procedure Display(W : Window_With_Label);

       -- New operations:
       procedure Set_Label(W : in out Window_With_Label; S : String);
         -- Set the label
       function Label(W : Window_With_Label) return String;
         -- Fetch the label
     private
       type Window_With_Label is 
         new Some_Window with record
           Label : String_Quark := Null_Quark;  
             -- An XWindows-Like unique ID for a string
         end record;

   In the generic body, we implement the Overridden and New operations
   as appropriate, using any inherited operations, if necessary.  For
   example, this might be an implementation of the overridden Display:

       procedure Display(W : Window_With_Label) is
       begin
           Display(Some_Window(W));
             -- First display the window normally,
             -- by passing the buck to the parent type.

           if W.Label /= Null_Quark then
             -- Now display the label if it is not null
               Display_On_Screen(XCoord(W), YCoord(W)-5, Value(W.Label));
                 -- Use two inherited functions on Basic_Window
                 -- to get the coordinates where to display the label.
           end if;
       end Display;

   Presuming we have several such generic packages defined,
   We can now create the desired window by mixing in repeatedly.
   First we declare the tailored window as a private extension
   of Basic_Window, and then we define it via a sequence of
   instantiations:

       type My_Window is Basic_Window with private;
       . . .
     private
       package Add_Label is new Label_Mixin(Basic_Window);
       package Add_Border is 
         new Border_Mixin(Add_Label.Window_With_Label);
       package Add_Menu_Bar is 
         new Menu_Bar_Mixin(Add_Border.Window_With_Border);

       type My_Window is 
         new Add_Menu_Bar.Window_With_Menu_Bar with null;
           -- Final window is a null extension of Window_With_Menu_Bar.
           -- We could instead make a record extension and
           -- add components for My_Window over and above those
           -- needed by the mix-ins.

Case(3) --
   In this case, let us presume we have two independent
   hierarchies, one for Windows, which represent areas on the
   screen, and one for Monitors, which wait for an object to change,
   and then do something in reaction to it.
   An object that supports Monitors keeps a linked list of
   Monitors, and calls their Update operation whenever the object
   is changed.  For example:

     type Monitor;
     type Monitor_Ptr is access Monitor'CLASS;

     type Monitored_Object is tagged limited 
       -- Monitored objects are derived from this root type
       record
         First : Monitor_Ptr;  - List of monitors
         -- More components to be added by extension
       end record;

     type Monitored_Object_Ptr is access Monitored_Object'CLASS;
  
     type Monitor is tagged limited 
       record
         Next : Monitor_Ptr;
         Obj : Monitored_Object_Ptr;
         -- More components to be added by extension
       end record;
     procedure Update(M : in out Monitor) is <>;
       -- Dispatching operation, called when monitored object
       -- is changed.

   Now suppose we want to create a Window that can
   act as a Monitor as well as a Window:

   First we define a mix-in that is a monitor, and override its Update op:

     type Monitor_Mixin(Win : access Basic_Window'CLASS) is 
       new Monitor with null;
     procedure Update(M : in out Monitor_Mixin);

   The body for this Update could be:

     procedure Update(M : in out Monitor_Mixin) is
       -- On an Update, simply re-Display the window
     begin
         Display(M.Win);  -- This is a dispatching call
     end Update;

   Now we can "mix" this Monitor_Mixin into any window type, as follows:

     type Window_That_Monitors is 
       new My_Window with record
         Mon : Monitor_Mixin(Window_That_Monitors'ACCESS);
       end record;

   We could define a tailored Monitor mix-in that did something 
   besides just call the Display operation of the associated
   Window.  But in many cases, this simple one will do the job.

-----------------------------
As these examples illustrate, Ada 9X provides support
for the construction of essentially arbitrary multiple
inheritance type lattices, without having to commit itself
to a single linguistic mechanism for multiple inheritance, and
without burdening simple single-inheritance problems with the complexity
and implementation burden of linguistic multiple inheritance.