A superclass linearization (also known as a class precedence list or CPL) is used for resolving conflicts among multiply-inherited superclasses which provide differing definitions of the same method. As part of the design of Dylan, several of us studied the properties of linearizations and algorithms for constructing them. The results are discussed in:
Kim Barrett, Bob Cassels, Paul Haahr, David A. Moon, Keith Playford, and P. Tucker Withington, A Monotonic Superclass Linearization for Dylan.
The paper was presented on 12 October 1996 at the 1996 Object-Oriented Programming Systems, Languages and Applications (OOPSLA '96) conference in San Jose, California. The abstract for the paper is:
Object-oriented languages with multiple inheritance and automatic conflict resolution typically use a linearization of superclasses to determine which version of a property to inherit when several superclasses provide definitions. Recent work has defined several desirable characteristics for linearizations, the most important being monotonicity, which prohibits inherited properties from skipping over direct superclasses. Combined with Dylan's sealing mechanism, a monotonic linearization enables some compile-time method selection that would otherwise be impossible in the absence of a closed-world assumption.
The Dylan linearization is monotonic, easily described, strictly observes local precedence order, and produces the same ordering as CLOS when that is monotonic. We present an implementation based on merging and a survey of class heterarchies from several large programs, analyzing where commonly used linearizations differ.
The paper is available in HTML and PostScript.
Our paper compared several linearizations. Untested source code for all of them (in Dylan) is available below. See the paper for details about the linearizations and their implementations.
(Coming some day: slides from the talk I gave at OOPSLA.)