An inheritance hierarchy is a way of classifying data according to subclasses of objects, as determined by their features. This paper studies the properties of feature types, inheritance, and unification through initial algebra semantics. It suggests that feature types are related to constructor types, which provide a fundamental means of defining data types in algebraic specifications. Features can be interpreted as selecting subclasses from a class of objects, and constructors as defining superclasses. In this way, feature types can be expressed as algebraic types if we supply the implicit constructors.
Two feature terms, or subsets of feature types, may or may not have a common intersection. We can determine such an intersection by feature unification. The paper gives a unitary unification algorithm in the form of rewriting rules in initial algebra semantics. The simplification rules are proved to be invariant, terminating, and complete. In essence, an equation system without implicit constructors is unifiable if and only if a solved system can be derived from it through a finite number of simplification steps.
The paper is an excellent attempt to provide an initial algebra semantics for feature inheritance and to apply the framework to feature unification. One slight problem with the authors’ presentation is that even though they provide vivid examples at the beginning of the paper they do not give examples for more complex subjects.