25.8 IMPLEMENTATION INHERITANCE

A form of inheritance that has often been criticized but is in fact both convenient and conceptually valid is the use of an inheritance link between a class describing a certain implementation of an abstract data structure and the class providing the implementation.

Arrayed stacks

We can use multiple inheritance is to provide an implementation of an abstraction defined by a deferred class, using facilities provided by an effective class.

Consider the implementation of stacks by arrays. Since both stacks and arrays are described by classes (deferred for STACK, effective for ARRAY), the best way to implement class ARRAYED_STACK, describing stacks implemented as arrays, is to define it as an heir to both STACK and ARRAY. The general form is:

      -- Stacks implemented by arrays indexing   description: "Stacks
implemented as arrays" class ARRAYED_STACK [G] inherit 
STACK [G];
  ARRAY [G]
    rename       count as capacity, put as
array_put     export       {NONE} all
    end feature   ... Implementation of the
deferred featuresof STACK       in terms of ARRAY operations (see
examples below) ...  end 

ARRAYED_STACK offers the same functionality as STACK. It gives effective versions of the routines deferred in STACK, implemented here in terms of array operations. Here are three example --- full, count and put.

The condition under which a stack is full is given by

full: BOOLEAN is     -- Is stack
representation full?    do     Result = (count = capacity)
  end 

where capacity, inherited from class ARRAY, gives is an attribute inherited from arrays. Feature capacity was called count in ARRAY; this causes a name clash with count from STACK, resolved through renaming. It is appropriate to keep the name count for the feature that has the same semantics in ARRAYED_STACK as it has in STACK.

The procedure that pushes an element onto a stack is effected as

 put
(x: G) is     -- Push x onto top of stack.  
do     count := count +1;
    array_put (x, count)   end 

Note the renaming of ARRAY's feature put --- the procedure for replacing the value of array items, where array_put (v, i) assigns value v to the i-th item --- into array_put. The name put remains reserved for the stack-pushing procedure, coming deferred from STACK.

Besides providing effective implementations of routines deferred in STACK, class ARRAYED_STACK may also redefine some which were not deferred. In particular, with an array representation, change_top (x: G), implemented in STACK as removefollowed by put (x), may be implemented more efficiently as

 put (x, count) 

To make this redefinition valid, do not forget to announce it in the inheritance clause:

 class ARRAYED_STACK [G] inherit 
STACK [G]
    redefine change_top end;   ARRAY [G] 
... The rest as before (page 778)
...  

The marriage of convenience

The ARRAYED_STACK example is representative of a common kind of multiple inheritance which may be called the marriage of convenience. It is like a marriage uniting a noble family and a rich one. The bride, a deferred class, belongs to the aristocratic family of stacks: it brings prestigious functionality but no practical wealth --- no implementation. The groom comes from a well-to-do bourgeois family, arrays, but needs some luster to match the efficiency of its implementation. The two make a perfect match.

It is interesting to compare ARRAYED_STACK, as sketched here, with the class STACK2 of an earlier discussion --- an array implementation of stacks defined without any use of inheritance. Note in particular how avoiding the need for the class to be a client of ARRAY simplifies the notation (the previous version had to use implementationlput where we can now just write put).

You will have noted that in the inheritance part for ARRAY all features have been made secret:

class ARRAYED_STACK [G] inherit   STACK [G];
  ARRAY [G]
    rename ... export       {NONE} all
    end   ...  

This is typical of marriage-of-convenience inheritance: all the features from the specification-providing parent, here STACK, are exported; all the features from the implementation-providing parent, here ARRAY, are hidden. This makes sure that clients of class ARRAY_STACK use the corresponding instances through stack operations only; we do not want to let them perform arbitrary array operations on the representation, such as changing the value of an element other than the top one.

It feels so good, but is it wrong?

Implementation inheritance is not without its critics. That we hide many inherited features seems to some people a violation of the "is-a" principle of inheritance.

It is not. There are different forms of "is-a". By its behavior, an arrayed stack is a stack; but internally it is an array. In fact the representation of an instance of ARRAYED_STACK is exactly the same as that of an instance of ARRAY, enriched with one attribute (count). Being made in the same way is a rather strong form of "is-a". And it is not just the representation: all the features of ARRAY, such as put (renamed array_put), infix "@" and count (renamed capacity) are available to ARRAYED_STACK, although not exported to its clients; the class needs them to implement the STACK features.

So there is nothing conceptually wrong with such implementation-only inheritance. The comparison with the counter-example studied at the beginning of this chapter is striking: for CAR_OWNER we had a gross misunderstanding of the concept; with ARRAYED_STACK we have a well-identified form of "is-a" relationship.

There is one drawback: permitting the inheritance mechanism to restrict the export availability of an inherited feature --- that is to say, permitting the export clause --- makes static type checking more difficult, as we have studied in detail. But this difficulty is largely for the compiler writer, not for the software developer.

Doing without inheritance

Let us probe further and see what it would take to work without implementation inheritance in our example case. This has been seen already: class STACK2 of an earlier chapter. It has an attribute representation of type ARRAY [G] and stack procedures implemented like this (assertions omitted):

 put (x: G) is
    -- Add x on top   require     ...
  do     count := count + 1;
    representationlput (count, x)   ensure     ...  
end 

Every manipulation of the representation requires a call to a feature of ARRAY with representation as the target. There is a performance penalty: minor for space (the representation attribute), more serious for time (going through representation, that is to say adding an indirection, for each operation).

But the efficiency issue may not be crucial. Tediousness is another problem, with all the "representationl" prefixes that must be added before every array operations. This will be true in all the classes that implement various data structures --- stacks, but also lists, queues and others --- through arrays.

The object-oriented designer hates tedious, repetitive task. "Encapsulate repetition" could be his motto. If we see such a pattern occurring repeatedly throughout a set of classes, the natural and healthy reaction is to try to understand the common abstraction, and encapsulate it in a class. The abstraction here is something like "data structure that has access to an array and its operations". The class could be:

indexing   description: "Objects that have access to an array and its
operations" class   ARRAYED [G] feature --
Access   item (i: INTEGER): G is     -- The representation's
element at index i
    require       ...
    do       Result := representationlitem (i) 
ensure       ...
    end; feature -- Element change   put (x:
G; i: INTEGER) is     -- Replace by x the representation's
element at index i
    require       ...
    do       representationlitem (x, i)     ensure
      ...
    end; feature {NONE} -- Implementation 
representation: ARRAY [G]; end -- class ARRAYED 

The features item and put have been exported. Since ARRAYED only describes internal properties of a data structure, it does not really need exported features. So someone who disagrees with the very idea of a descendant hiding some of the features that it inherits from its parents may prefer to make all the features of ARRAYED secret. They will by default remain secret in descendants.

With this class definition it is perfectly legitimate to make classes such as ARRAYED_STACK or ARRAYED_LIST inherit from ARRAYED: they indeed describe "arrayed" structures. These classes can now use item instead of representationlitem and so on; we have rid ourselves of the tediousness.

But wait a minute! If it is right to inherit from ARRAYED, why can we not inherit directly from ARRAY? We gain nothing from the further layer or encapsulation that we have thrown over ARRAY --- a form of encapsulation that starts looking more like obfuscation. By going through ARRAYED we are just pretending to ourselves that we are not using implementation inheritance, but for all practical purposes we are. We have just made the software more complex and less efficient.

There is indeed no reason in this example for class ARRAYED. Direct implementation inheritance from classes such as ARRAY is simpler and legitimate.

PREVIOUS SECTION ---- NEXT SECTION