Class Precedence List

The Class Precedence List (CPL) is a data structure in object-oriented programming which the runtime system uses to select the method. It is often used in programming languages that support multiple inheritance .

The necessity of a CPL arises from the fact that in the case of multiple inheritance more than one path from a certain class to the root of the class tree is possible, or priority is not automatically given between secondary classes.

Mathematically, the CPL of a class is a total order of its superclasses according to priority. As part of the method call, the CPL is used together with the parameters of the method call to generate another structure, the list of sorted applicable methods . The method selection is then carried out via this.

synthesis

Each class is defined with one or more direct superclasses. The order in which the superclasses are named in the class definitions gives a topological order as follows:

Suppose a class is derived from the direct superclasses (in that order). Then creates the two-digit relation ${\ displaystyle C}$ ${\ displaystyle C_ {1}, C_ {2}, .. C_ {n}}$

{\ displaystyle R_ {C} = \ lbrace (C, C_ {1}), (C_ {1}, C_ {2}), .., (C_ {n-1}, C_ {n}) \ rbrace}

a total order on the crowd and their direct superclasses. If one forms the association with ${\ displaystyle C}$ ${\ displaystyle R}$

{\ displaystyle R = \ bigcup _ {C \ in S_ {c}} {R_ {C}}}

of all direct / and / indirect superclasses of , then this relation is a partial order of the superclasses. ${\ displaystyle S_ {c}}$ ${\ displaystyle C}$

There are contradicting cases in which the priority of a superclass over a superclass with regard to the derived class is just as required as vice versa. In this case, the compiler issues an error message. ${\ displaystyle C_ {i}}$ ${\ displaystyle C_ {j}}$ ${\ displaystyle C}$

But if it is consistent, every topological order compatible with it is a class precedence list of for . ${\ displaystyle R}$ ${\ displaystyle C}$

In a programming language without multiple inheritance, such as Java, the determination of the CPL is trivial and it is identical to the direct ascent path from the class to the root of the class tree. ${\ displaystyle C}$

Different programming languages that support multiple inheritance ( Common Lisp , Dylan , Julia etc.) treat individual cases differently within the scope of the above definition. In practice this is almost always irrelevant. Some implementations (Perl) form the CPL implicitly through recursive descent in the class tree. The resulting priority, however, is not always intuitive.

literature

Common Lisp Standard - ANSI INCITS 226-1994 (R2004) ( Memento from January 1, 2014 in the Internet Archive )