In section 
I introduced the precedence list representation
of objects in the single-inheritance case. In this section I will
discuss a similar representation when using multiple inheritance
in the class hierarchy. The precedence list representation
is inspired by the class precedence lists from
the Common Lisp Object System (CLOS) [3].
A class precedence list of a class C is a total ordering of
C and all its (direct and indirect) superclasses.
In this ordering of classes, each of the classes occurs exactly once.
If C is a class with the direct super classes 
, 
, ... 
(in this order),
the following rules define a class precedence list:
, 
, ... and 
in the ordering, and
precedes 
, for i from 1 to n-1.
An object precedence list is similar to a class precedence list. I.e., an object precedence list of an instance of a class C is the similar total ordering of the object parts of the instance, where each part occurs only once. The same constraints as described in the two points above should also hold for the object parts.
Let me illustrate class precedence lists and object
precedence lists with the example in figure .
Figure: A sample class hierarchy with multiple inheritance.
For each class in the figure, precedence lists of the components (classes or instances) are shown in boxes. Considering for example the class F, an instance of F consists of the following ordered collection of parts:
A is the last one, because it must be preceded by both B and C according to (two applications of) rule number one from above; B precedes C because of rule number two; F is the first one, again because of rule number one. Using a precedence list representation of objects, an instance of the class F is represented as the list
where each part is a reference to the dispatch procedure of the part.
It is worth noticing, that using this representation
of objects, the method lookup procedure in the multiple-super-class
case is the same as in the single-super-class case.
The method lookup procedure which applies
has already been shown in section .
Compared with the version of method-lookup
from section
(the so-called simple approach), in which the search strategy
is encoded into the lookup procedure,
the procedure shown in section is clearly a
simplification. However, there is of course a price for this
simplicity. The price is so to speak paid in class-handle
,
which is described next.
The procedure class-handle makes and returns a precedence list representation of an object. Recall that class-handle is used directly in the class definition template, and it is used in the procedure instantiate-super-class to fake the instantiation of an object part from already existing parts.
(define (class-handle self super-list) (cons self (merge-parts super-list)))
This procedure reflects rule number one in the definition of the class precedence list. Self is supposed to be a dispatch procedure, and super-list is a list of object precedence lists of the super parts of the object. The procedure must return an object precedence list of the object, to which self belongs.
The procedure merge-parts reflects rule number two in the definition of the class precedence list. Merge-parts is defined through an iterative (tail-recursive) helping procedure called merge-parts-1 .
(define (merge-parts lists)
(reverse (merge-parts-1 () lists)))
(define (merge-parts-1 result input)
(if (null? input)
result
(let* ((first-list (car input))
(first-el (car first-list))
(rest-lists (cdr input)))
(merge-parts-1
(if (multi-member object-eq? first-el rest-lists)
result
(cons first-el result))
(if (cdr first-list)
(cons (cdr first-list) rest-lists)
rest-lists)))))
(define (object-eq? x y)
(eq? (class-of-object x) (class-of-object y)))
It is probably easiest to understand these merge procedures through
an example of the merge process. Let us assume that we are about
to instantiate an H object, relative to figure .
In order to do that the three precedence lists of the super parts
of H have to be merged. I.e., input
to the procedure
merge-parts-1
becomes:
) (
) (
)
Merge-parts-1
first checks if 
is a member of either of the
lists
(
) or (
).
It is not, and therefore 
is
included into result
.
Next, it is checked if 
is part of the two lists
(
) or (
).
That is the case, and therefore
this instance of 
is ``postponed'' until it is met later during the
merge process.
Continuing this way,
the result of merging the three lists becomes
(
).
The remaining procedures are multi-member and, in turn, its helping procedures. Multi-member tests whether an element is a member of a list, in a list of lists. The following implementation of multi-member just maps the member -like procedure, called memb , over the list of lists, and or -reduces the result to an boolean value:
(define (multi-member comparison el list-of-lists)
(reduce or-proc
(map (lambda (l)
(memb comparison el l))
list-of-lists)
#f))
Reduce is well-known, and or-proc is or , just in procedure form (in Scheme it is not possible to use a special form as a parameter to a higher order procedure). For the sake of completeness, these procedures are shown next:
(define (reduce combiner list initial-value)
(if (null? list)
initial-value
(combiner (car list)
(reduce combiner
(cdr list)
initial-value))))
(define (or-proc x y)
(or x y))
This concludes the description of how to construct the precedence list representation of objects in the case of multiple super classes.