×

A semantics of multiple inheritance. (English) Zbl 0543.68011

Semantics of data types, Proc. int. Symp., Sophia-Antipolis/France 1984, Lect. Notes Comput. Sci. 173, 51-67 (1984).
[For the entire collection see Zbl 0534.00019.]
There are two major ways of structuring data in programming languages. The first (and common) one, used for example in Pascal, can be said to derive from standard branches of mathematics. Data is organized in Cartesian products (i.e. record types), disjoint sums (i.e. unions or variant types) and function spaces (i.e. functions and procedures). The second method can be said to derive from biology and taxonomy. Data is organized in a hierarchy of classes and subclasses, and data at any level of the hierarchy inherits all the attributes of data higher up in the hierarchy. The top level of this hierarchy is usually called the class of all ”objects”; every datum is an object and every datum inherits the basic properties of objects, like the ability to tell whether two objects are the same or not. Functions and procedures are also considered as local actions of objects, as opposed to global operations. These different ways of structuring data have generated distinct classes of programming languages, and induced different programming styles. Programming with taxonomically organized data is often called object- oriented programming, and has been advocated as an effective way of structuring programming environments, data bases, and large systems in general. Inheritance can be single or multiple. In the case of single inheritance the subclass hierarchy has the form of a tree, i.e. every class has a unique superclass. Exmples can be shown where a class can be indifferently considered a subclass of two incompatible superclasses; then an arbitrary decision has to be made to determine which superclass to use. This problem leads naturally to the idea of multiple inheritance. The scope of this paper is to present a clean semantics of multiple inheritance and to show that in the context of strongly-typed statically- scoped languages, a sound typechecking algorithm exists. Multiple inheritance is also interpreted in a broad sense: instead of being limited to objects, it is extended in a natural way to union types and to higher functional types. The first part of this paper is informal, and presents the basic notations and intuitions by means of examples. The second part is formal: it introduces a language, a semantics, a type inference system and a typechecking algorithm. The algorithm is proved sound with respect to the inference system, and the inference system is proved sound with respect to the semantics.

MSC:

68P05 Data structures
68Q60 Specification and verification (program logics, model checking, etc.)
68N01 General topics in the theory of software

Citations:

Zbl 0534.00019