Prev Up
Go backward to Using Genericity to Improve OO Designs
Karsten Weihe
Go up to Foundations and Methodology Comparisons

Inheritance, Genericity, and Class Hierarchies
Wolf Zimmermann

The talk reports experiences and conclusions drawn from the development of the class library KARLA (KARlsruhe Library on Algorithms). We observed that combining classes using genericity and inheritance may lead to unexpected errors which might occur deeply in the calling hierarchy of a library. The talk presents results on how to combine classes safely using inheritance and genericity.

We assume that every class C is specified by its invariant InvC, and pre- and postconditions Prem,C and Postm,C, respectively, for all its methods m. Consider now method calls x.m(y1,...,yk) where the declared type A of x is polymorphic (i.e., x can be an object of any subclass of A) or a parameter of a generic class. Two questions arise:

  1. What must be satisfied in order to ensure the precondition of the method call without knowing the concrete class of x?
  2. What is satisfied after the method call; i.e., which invariant and postcondition?
The conformance condition is the key to answer these questions. Informally, a class B conforms to a class A iff A can always be substituted by B. Formally, this condition is defined by implications on invariants, pre- and postconditions. If conformance is required for inheritance, then for the method call x.m(y1,...,yk) it is sufficient to show that Prem,A is satisfied, and after the call InvA  and Postm,A is satisfied. If the declared type of x is a generic parameter T and we bound the genericity by A, i.e., all instances for T must conform to A, we have the same situation.

Inheritance is also used for code reuse. Therefore, there are non-conforming inheritance relations. In particular, the specialization relation turns out to be important in practice. Informally, a class B is more special than a class A, if all objects of class B are the objects of A which satisfy some constraint, e.g. the class of acyclic directed graphs is a specialization of the class of directed graphs. The talk discusses several specialization hierarchies and their systematic construction.

 

Prev Up