Die Methodenauflösungsreihenfolge von Python 2.3
************************************************

Bemerkung:

  Dies ist ein historisches Dokument, das als Anhang zur offiziellen
  Dokumentation bereitgestellt wird. Die hier behandelte
  Methodenauflösungsreihenfolge wurde in Python 2.3 *eingeführt*, wird
  aber auch in späteren Versionen noch verwendet – einschließlich
  Python 3.

Von Michele Simionato.

Zusammenfassung:
   *Dieses Dokument richtet sich an Python-Programmierer, die die in
   Python 2.3 verwendete C3-Methodenauflösungsreihenfolge verstehen
   wollen. Es ist nicht für Anfänger gedacht, aber durchaus lehrreich
   und enthält viele durchgerechnete Beispiele. Mir sind keine anderen
   öffentlich verfügbaren Dokumente mit demselben Umfang bekannt, es
   sollte daher nützlich sein.*

Haftungsausschluss:

   *Ich schenke dieses Dokument der Python Software Foundation, unter
   der Python-2.3-Lizenz. Wie in diesen Fällen üblich, weise ich den
   Leser darauf hin, dass das Folgende korrekt sein* sollte *– ich
   übernehme aber keinerlei Gewähr. Verwendung auf eigene Gefahr!*

Dank:

   *An all die Leute auf der Python-Mailingliste, die mir ihre
   Unterstützung geschickt haben. An Paul Foley, der auf verschiedene
   Unschärfen hingewiesen und mich dazu gebracht hat, den Teil über
   die lokale Vorrangordnung zu ergänzen. An David Goodger für die
   Hilfe bei der Formatierung in reStructuredText. An David Mertz für
   die Hilfe beim Redigieren. Und schließlich an Guido van Rossum, der
   dieses Dokument begeistert auf die offizielle Python-2.3-Homepage
   gestellt hat.*


Der Anfang
==========

   *Felix qui potuit rerum cognoscere causas* – Vergil

Alles begann mit einem Beitrag von Samuele Pedroni auf der
Mailingliste für die Python-Entwicklung [1]. In seinem Beitrag zeigte
Samuele, dass die Methodenauflösungsreihenfolge von Python 2.2 nicht
monoton ist, und schlug vor, sie durch die
C3-Methodenauflösungsreihenfolge zu ersetzen. Guido stimmte seinen
Argumenten zu, und daher verwendet Python 2.3 nun C3. Die C3-Methode
selbst hat nichts mit Python zu tun, denn sie wurde von Leuten
erfunden, die an Dylan arbeiteten, und ist in einem Aufsatz für Lisp-
Programmierer beschrieben [2]. Der vorliegende Aufsatz bietet eine
(hoffentlich) lesbare Erörterung des C3-Algorithmus für Pythonistas,
die die Gründe für die Änderung verstehen wollen.

Zunächst möchte ich darauf hinweisen, dass alles, was ich sagen werde,
nur für die *new style classes* gilt, die in Python 2.2 eingeführt
wurden: *klassische Klassen* behalten ihre alte
Methodenauflösungsreihenfolge – zuerst in die Tiefe, dann von links
nach rechts. Für klassische Klassen bricht also kein alter Code, und
selbst wenn im Grundsatz Code für Python-2.2-new-style-Klassen brechen
könnte, sind die Fälle, in denen sich die C3-Auflösungsreihenfolge von
der Methodenauflösungsreihenfolge von Python 2.2 unterscheidet, in der
Praxis so selten, dass kein wirkliches Brechen von Code zu erwarten
ist. Daher:

   *Keine Angst!*

Außerdem brauchst du den C3-Algorithmus nicht zu verstehen und kannst
diesen Aufsatz ohne Weiteres überspringen, sofern du nicht stark von
Mehrfachvererbung Gebrauch machst und keine nichttrivialen Hierarchien
hast. Wenn du andererseits wirklich wissen willst, wie
Mehrfachvererbung funktioniert, dann ist dieser Aufsatz für dich. Die
gute Nachricht ist, dass die Dinge nicht so kompliziert sind, wie du
vielleicht erwartest.

Ich beginne mit einigen grundlegenden Definitionen.

1. Ist eine Klasse C in einer komplizierten
   Mehrfachvererbungshierarchie gegeben, ist es eine nichttriviale
   Aufgabe, die Reihenfolge anzugeben, in der Methoden überschrieben
   werden, also die Reihenfolge der Vorfahren von C anzugeben.

2. Die Liste der Vorfahren einer Klasse C, einschließlich der Klasse
   selbst, geordnet vom nächsten bis zum entferntesten Vorfahren,
   heißt Klassenvorrangliste oder *Linearisierung* von C.

3. Die *Methodenauflösungsreihenfolge* (MRO) ist der Satz von Regeln,
   der die Linearisierung aufbaut. In der Python-Literatur wird die
   Wendung „die MRO von C“ auch als Synonym für die Linearisierung der
   Klasse C verwendet.

4. Bei einer Hierarchie mit Einfachvererbung ist zum Beispiel die
   Linearisierung von C einfach die Liste [C, C1 , C2], wenn C eine
   Unterklasse von C1 und C1 eine Unterklasse von C2 ist. Bei
   Hierarchien mit Mehrfachvererbung ist der Aufbau der Linearisierung
   dagegen umständlicher, weil es schwieriger ist, eine Linearisierung
   zu bauen, die die *lokale Vorrangordnung* und die *Monotonie*
   beachtet.

5. Die lokale Vorrangordnung erörtere ich später, die Definition der
   Monotonie kann ich hier aber geben. Eine MRO ist monoton, wenn
   Folgendes gilt: *Wenn C1 in der Linearisierung von C vor C2 steht,
   dann steht C1 in der Linearisierung jeder Unterklasse von C vor
   C2*. Andernfalls könnte der harmlose Vorgang, eine neue Klasse
   abzuleiten, die Auflösungsreihenfolge von Methoden ändern und damit
   möglicherweise sehr feine Fehler einschleppen. Beispiele, in denen
   das passiert, werden später gezeigt.

6. Nicht alle Klassen lassen eine Linearisierung zu. Es gibt in
   komplizierten Hierarchien Fälle, in denen es nicht möglich ist,
   eine Klasse so abzuleiten, dass ihre Linearisierung alle
   gewünschten Eigenschaften beachtet.

Hier ein Beispiel für diese Lage. Betrachte die Hierarchie

>>> O = object
>>> class X(O): pass
>>> class Y(O): pass
>>> class A(X,Y): pass
>>> class B(Y,X): pass

die sich mit dem folgenden Vererbungsgraphen darstellen lässt, wobei
ich die Klasse "object" mit O bezeichnet habe, die bei new-style-
Klassen der Anfang jeder Hierarchie ist:

       -----------
      |           |
      |    O      |
      |  /   \    |
       - X    Y  /
         |  / | /
         | /  |/
         A    B
         \   /
           ?

In diesem Fall ist es nicht möglich, eine neue Klasse C von A und B
abzuleiten, weil X in A vor Y steht, in B aber Y vor X. Die
Methodenauflösungsreihenfolge wäre in C daher nicht eindeutig.

Python 2.3 löst in dieser Lage eine Ausnahme aus (TypeError:  MRO
conflict among bases Y, X) und verbietet dem unbedarften Programmierer
damit, nicht eindeutige Hierarchien zu erzeugen. Python 2.2 löst
stattdessen keine Ausnahme aus, sondern wählt eine *ad hoc*
festgelegte Reihenfolge (in diesem Fall CABXYO).


Die C3-Methodenauflösungsreihenfolge
====================================

Ich führe ein paar einfache Schreibweisen ein, die für die folgende
Erörterung nützlich sind. Ich verwende die Kurzschreibweise:

   C1 C2 ... CN

um die Liste der Klassen [C1, C2, ... , CN] zu bezeichnen.

Der *Kopf* der Liste ist ihr erstes Element:

   head = C1

während der *Rumpf* der restliche Teil der Liste ist:

   tail = C2 ... CN.

Ich verwende außerdem die Schreibweise:

   C + (C1 C2 ... CN) = C C1 C2 ... CN

um die Summe der Listen [C] + [C1, C2, ... ,CN] zu bezeichnen.

Nun kann ich erklären, wie die MRO in Python 2.3 arbeitet.

Betrachte eine Klasse C in einer Mehrfachvererbungshierarchie, wobei C
von den Basisklassen B1, B2, ... , BN erbt. Wir wollen die
Linearisierung L[C] der Klasse C berechnen. Die Regel lautet:

   *Die Linearisierung von C ist die Summe aus C und der
   Zusammenführung der Linearisierungen der Eltern und der Liste der
   Eltern.*

In symbolischer Schreibweise:

   L[C(B1 ... BN)] = C + merge(L[B1] ... L[BN], B1 ... BN)

Ist C insbesondere die Klasse "object", die keine Eltern hat, ist die
Linearisierung trivial:

   L[object] = object.

Im Allgemeinen muss man die Zusammenführung aber nach der folgenden
Vorschrift berechnen:

   *Nimm den Kopf der ersten Liste, also L[B1][0]. Steht dieser Kopf
   nicht im Rumpf einer der anderen Listen, dann füge ihn der
   Linearisierung von C hinzu und entferne ihn aus den Listen der
   Zusammenführung. Andernfalls sieh dir den Kopf der nächsten Liste
   an und nimm ihn, wenn er ein guter Kopf ist. Wiederhole den Vorgang
   dann, bis alle Klassen entfernt sind oder es unmöglich ist, gute
   Köpfe zu finden. In diesem Fall ist es unmöglich, die
   Zusammenführung zu bauen; Python 2.3 wird sich weigern, die Klasse
   C zu erzeugen, und eine Ausnahme auslösen.*

Diese Vorschrift stellt sicher, dass die Zusammenführung die
Reihenfolge *erhält*, sofern die Reihenfolge erhalten werden kann.
Lässt sich die Reihenfolge andererseits nicht erhalten (wie im oben
erörterten Beispiel mit schwerwiegender Uneinigkeit über die
Reihenfolge), dann lässt sich die Zusammenführung nicht berechnen.

Die Berechnung der Zusammenführung ist trivial, wenn C nur einen
Elternteil hat (Einfachvererbung). In diesem Fall:

   L[C(B)] = C + merge(L[B],B) = C + L[B]

Bei Mehrfachvererbung sind die Dinge aber umständlicher, und ich
erwarte nicht, dass du die Regel ohne ein paar Beispiele verstehen
kannst ;-)


Beispiele
=========

Erstes Beispiel. Betrachte die folgende Hierarchie:

>>> O = object
>>> class F(O): pass
>>> class E(O): pass
>>> class D(O): pass
>>> class C(D,F): pass
>>> class B(D,E): pass
>>> class A(B,C): pass

In diesem Fall lässt sich der Vererbungsgraph so zeichnen:

                                6
                               ---
      Level 3                 | O |                  (more general)
                            /  ---  \
                           /    |    \                      |
                          /     |     \                     |
                         /      |      \                    |
                        ---    ---    ---                   |
      Level 2        3 | D | 4| E |  | F | 5                |
                        ---    ---    ---                   |
                         \  \ _ /       |                   |
                          \    / \ _    |                   |
                           \  /      \  |                   |
                            ---      ---                    |
      Level 1            1 | B |    | C | 2                 |
                            ---      ---                    |
                              \      /                      |
                               \    /                      \ /
                                 ---
      Level 0                 0 | A |                (more specialized)
                                 ---

Die Linearisierungen von O, D, E und F sind trivial:

   L[O] = O
   L[D] = D O
   L[E] = E O
   L[F] = F O

Die Linearisierung von B lässt sich so berechnen:

   L[B] = B + merge(DO, EO, DE)

Wir sehen, dass D ein guter Kopf ist. Wir nehmen ihn also und müssen
nur noch "merge(O,EO,E)" berechnen. Nun ist O kein guter Kopf, weil es
im Rumpf der Folge EO steht. In diesem Fall sagt die Regel, dass wir
zur nächsten Folge springen müssen. Dann sehen wir, dass E ein guter
Kopf ist. Wir nehmen ihn und müssen nur noch "merge(O,O)" berechnen,
was O ergibt. Daher:

   L[B] =  B D E O

Mit demselben Verfahren findet man:

   L[C] = C + merge(DO,FO,DF)
        = C + D + merge(O,FO,F)
        = C + D + F + merge(O,O)
        = C D F O

Jetzt können wir berechnen:

   L[A] = A + merge(BDEO,CDFO,BC)
        = A + B + merge(DEO,CDFO,C)
        = A + B + C + merge(DEO,DFO)
        = A + B + C + D + merge(EO,FO)
        = A + B + C + D + E + merge(O,FO)
        = A + B + C + D + E + F + merge(O,O)
        = A B C D E F O

In diesem Beispiel ist die Linearisierung recht schön nach der
Vererbungsebene geordnet, in dem Sinne, dass niedrigere Ebenen (also
spezialisiertere Klassen) höheren Vorrang haben (siehe den
Vererbungsgraphen). Das ist jedoch nicht der allgemeine Fall.

Die Linearisierung für mein zweites Beispiel zu berechnen, überlasse
ich dem Leser als Übung:

>>> O = object
>>> class F(O): pass
>>> class E(O): pass
>>> class D(O): pass
>>> class C(D,F): pass
>>> class B(E,D): pass
>>> class A(B,C): pass

Der einzige Unterschied zum vorigen Beispiel ist die Änderung von
B(D,E) nach B(E,D). Doch selbst eine so kleine Änderung verändert die
Reihenfolge der Hierarchie vollständig:

                                 6
                                ---
      Level 3                  | O |
                             /  ---  \
                            /    |    \
                           /     |     \
                          /      |      \
                        ---     ---    ---
      Level 2        2 | E | 4 | D |  | F | 5
                        ---     ---    ---
                         \      / \     /
                          \    /   \   /
                           \  /     \ /
                            ---     ---
      Level 1            1 | B |   | C | 3
                            ---     ---
                             \       /
                              \     /
                                ---
      Level 0                0 | A |
                                ---

Beachte, dass die Klasse E, die in der zweiten Ebene der Hierarchie
liegt, vor der Klasse C steht, die in der ersten Ebene liegt; E ist
also spezialisierter als C, obwohl es in einer höheren Ebene liegt.

Ein fauler Programmierer kann die MRO direkt von Python 2.2 bekommen,
weil sie in diesem Fall mit der Linearisierung von Python 2.3
übereinstimmt. Es genügt, die Methode "mro()" der Klasse A aufzurufen:

>>> A.mro()
[<class 'A'>, <class 'B'>, <class 'E'>,
<class 'C'>, <class 'D'>, <class 'F'>,
<class 'object'>]

Schließlich möchte ich das im ersten Abschnitt erörterte Beispiel mit
der schwerwiegenden Uneinigkeit über die Reihenfolge betrachten. In
diesem Fall sind die Linearisierungen von O, X, Y, A und B unmittelbar
zu berechnen:

      L[O] = 0
      L[X] = X O
      L[Y] = Y O
      L[A] = A X Y O
      L[B] = B Y X O

Es ist jedoch unmöglich, die Linearisierung für eine Klasse C zu
berechnen, die von A und B erbt:

   L[C] = C + merge(AXYO, BYXO, AB)
        = C + A + merge(XYO, BYXO, B)
        = C + A + B + merge(XYO, YXO)

An diesem Punkt können wir die Listen XYO und YXO nicht
zusammenführen, weil X im Rumpf von YXO und Y im Rumpf von XYO steht:
Es gibt also keine guten Köpfe, und der C3-Algorithmus hält an. Python
2.3 löst einen Fehler aus und weigert sich, die Klasse C zu erzeugen.


Schlechte Methodenauflösungsreihenfolgen
========================================

Eine MRO ist *schlecht*, wenn sie so grundlegende Eigenschaften wie
die lokale Vorrangordnung und die Monotonie bricht. In diesem
Abschnitt zeige ich, dass sowohl die MRO für klassische Klassen als
auch die MRO für new-style-Klassen in Python 2.2 schlecht ist.

Es ist einfacher, mit der lokalen Vorrangordnung zu beginnen.
Betrachte das folgende Beispiel:

>>> F=type('Food',(),{'remember2buy':'spam'})
>>> E=type('Eggs',(F,),{'remember2buy':'eggs'})
>>> G=type('GoodFood',(F,E),{}) # under Python 2.3 this is an error!

mit dem Vererbungsdiagramm

                   O
                   |
      (buy spam)   F
                   | \
                   | E   (buy eggs)
                   | /
                   G

            (buy eggs or spam ?)

Wir sehen, dass die Klasse G von F und E erbt, mit F *vor* E: Wir
würden daher erwarten, dass das Attribut *G.remember2buy* von
*F.remember2buy* geerbt wird und nicht von *E.remember2buy*. Python
2.2 liefert dennoch

>>> G.remember2buy
'eggs'

Das ist ein Brechen der lokalen Vorrangordnung, weil die Reihenfolge
in der lokalen Vorrangliste, also der Liste der Eltern von G, in der
Python-2.2-Linearisierung von G nicht erhalten bleibt:

   L[G,P22]= G E F object   # F *follows* E

Man könnte einwenden, F stehe in der Python-2.2-Linearisierung deshalb
hinter E, weil F weniger spezialisiert ist als E, denn F ist die
Oberklasse von E. Dennoch ist das Brechen der lokalen Vorrangordnung
recht wenig naheliegend und fehleranfällig. Das gilt besonders
deshalb, weil es sich von old-style-Klassen unterscheidet:

>>> class F: remember2buy='spam'
>>> class E(F): remember2buy='eggs'
>>> class G(F,E): pass
>>> G.remember2buy
'spam'

In diesem Fall ist die MRO GFEF, und die lokale Vorrangordnung bleibt
erhalten.

Als allgemeine Regel sollten Hierarchien wie die vorige vermieden
werden, weil unklar ist, ob F E überschreiben soll oder umgekehrt.
Python 2.3 löst die Uneindeutigkeit, indem es bei der Erzeugung der
Klasse G eine Ausnahme auslöst und den Programmierer so wirksam davon
abhält, uneindeutige Hierarchien zu erzeugen. Der Grund dafür ist,
dass der C3-Algorithmus scheitert, wenn die Zusammenführung:

   merge(FO,EFO,FE)

nicht berechnet werden kann, weil F im Rumpf von EFO und E im Rumpf
von FE steht.

Die wirkliche Lösung besteht darin, eine eindeutige Hierarchie zu
entwerfen, also G von E und F abzuleiten (das Spezifischere zuerst)
und nicht von F und E. In diesem Fall ist die MRO ohne jeden Zweifel
GEF.

                 O
                 |
                 F (spam)
               / |
      (eggs)   E |
               \ |
                 G
                   (eggs, no doubt)

Python 2.3 zwingt den Programmierer, gute Hierarchien zu schreiben
(oder zumindest weniger fehleranfällige).

In diesem Zusammenhang möchte ich darauf hinweisen, dass der
Algorithmus von Python 2.3 klug genug ist, offensichtliche Fehler zu
erkennen, etwa die Doppelung von Klassen in der Liste der Eltern:

>>> class A(object): pass
>>> class C(A,A): pass # error
Traceback (most recent call last):
  File "<stdin>", line 1, in ?
TypeError: duplicate base class A

Python 2.2 würde in dieser Lage (sowohl bei klassischen als auch bei
new-style-Klassen) keine Ausnahme auslösen.

Schließlich möchte ich auf zwei Lehren hinweisen, die wir aus diesem
Beispiel gezogen haben:

1. Dem Namen zum Trotz bestimmt die MRO die Auflösungsreihenfolge von
   Attributen, nicht nur von Methoden;

2. Die Standardnahrung für Pythonistas ist Spam! (aber das wusstest du
   schon ;-)

Nachdem ich die Frage der lokalen Vorrangordnung erörtert habe, möchte
ich nun die Frage der Monotonie betrachten. Mein Ziel ist, zu zeigen,
dass weder die MRO für klassische Klassen noch die für new-style-
Klassen in Python 2.2 monoton ist.

Zu beweisen, dass die MRO für klassische Klassen nicht monoton ist,
ist recht trivial. Es genügt, sich das Rautendiagramm anzusehen:

         C
        / \
       /   \
      A     B
       \   /
        \ /
         D

Die Widersprüchlichkeit erkennt man leicht:

   L[B,P21] = B C        # B precedes C : B's methods win
   L[D,P21] = D A C B C  # B follows C  : C's methods win!

Mit den MROs von Python 2.2 und 2.3 gibt es dagegen keine Probleme,
beide ergeben:

   L[D] = D A B C

Guido weist in seinem Aufsatz [3] darauf hin, dass die klassische MRO
in der Praxis nicht so schlecht ist, weil man Rauten bei klassischen
Klassen üblicherweise vermeiden kann. Alle new-style-Klassen erben
jedoch von "object", Rauten sind daher unvermeidlich und
Widersprüchlichkeiten treten in jedem Mehrfachvererbungsgraphen auf.

Die MRO von Python 2.2 macht es schwierig, die Monotonie zu brechen,
aber nicht unmöglich. Das folgende Beispiel, ursprünglich von Samuele
Pedroni beigesteuert, zeigt, dass die MRO von Python 2.2 nicht monoton
ist:

>>> class A(object): pass
>>> class B(object): pass
>>> class C(object): pass
>>> class D(object): pass
>>> class E(object): pass
>>> class K1(A,B,C): pass
>>> class K2(D,B,E): pass
>>> class K3(D,A):   pass
>>> class Z(K1,K2,K3): pass

Hier die Linearisierungen gemäß der C3-MRO (der Leser sollte diese
Linearisierungen als Übung nachprüfen und das Vererbungsdiagramm
zeichnen ;-)

   L[A] = A O
   L[B] = B O
   L[C] = C O
   L[D] = D O
   L[E] = E O
   L[K1]= K1 A B C O
   L[K2]= K2 D B E O
   L[K3]= K3 D A O
   L[Z] = Z K1 K2 K3 D A B C E O

Python 2.2 liefert für A, B, C, D, E, K1, K2 und K3 genau dieselben
Linearisierungen, aber eine andere Linearisierung für Z:

   L[Z,P22] = Z K1 K3 A K2 D B C E O

Es ist klar, dass diese Linearisierung *falsch* ist, weil A vor D
kommt, während A in der Linearisierung von K3 *hinter* D kommt. Anders
gesagt: In K3 überschreiben von D geerbte Methoden die von A geerbten,
in Z aber, das immer noch eine Unterklasse von K3 ist, überschreiben
die von A geerbten Methoden die von D geerbten! Das ist ein Verstoß
gegen die Monotonie. Außerdem ist die Python-2.2-Linearisierung von Z
auch mit der lokalen Vorrangordnung unvereinbar, weil die lokale
Vorrangliste der Klasse Z [K1, K2, K3] lautet (K2 steht vor K3),
während in der Linearisierung von Z K2 hinter K3 *folgt*. Diese
Probleme erklären, warum die 2.2-Regel zugunsten der C3-Regel
verworfen wurde.


Das Ende
========

Dieser Abschnitt ist für den ungeduldigen Leser, der alle vorherigen
Abschnitte übersprungen und gleich zum Ende gesprungen ist. Dieser
Abschnitt ist auch für den faulen Programmierer, der sein Gehirn nicht
anstrengen wollte. Und schließlich ist er für den Programmierer mit
etwas Überheblichkeit, denn sonst würde er keinen Aufsatz über die
C3-Methodenauflösungsreihenfolge in Mehrfachvererbungshierarchien
lesen ;-) Diese drei Tugenden zusammengenommen (und *nicht* einzeln)
verdienen einen Preis: Der Preis ist ein kurzes Python-2.2-Skript, mit
dem du die 2.3-MRO berechnen kannst, ohne dein Gehirn zu gefährden.
Ändere einfach die letzte Zeile, um mit den verschiedenen Beispielen
zu spielen, die ich in diesem Aufsatz erörtert habe.:

   #<mro.py>

   """C3 algorithm by Samuele Pedroni (with readability enhanced by me)."""

   class __metaclass__(type):
       "All classes are metamagically modified to be nicely printed"
       __repr__ = lambda cls: cls.__name__

   class ex_2:
       "Serious order disagreement" #From Guido
       class O: pass
       class X(O): pass
       class Y(O): pass
       class A(X,Y): pass
       class B(Y,X): pass
       try:
           class Z(A,B): pass #creates Z(A,B) in Python 2.2
       except TypeError:
           pass # Z(A,B) cannot be created in Python 2.3

   class ex_5:
       "My first example"
       class O: pass
       class F(O): pass
       class E(O): pass
       class D(O): pass
       class C(D,F): pass
       class B(D,E): pass
       class A(B,C): pass

   class ex_6:
       "My second example"
       class O: pass
       class F(O): pass
       class E(O): pass
       class D(O): pass
       class C(D,F): pass
       class B(E,D): pass
       class A(B,C): pass

   class ex_9:
       "Difference between Python 2.2 MRO and C3" #From Samuele
       class O: pass
       class A(O): pass
       class B(O): pass
       class C(O): pass
       class D(O): pass
       class E(O): pass
       class K1(A,B,C): pass
       class K2(D,B,E): pass
       class K3(D,A): pass
       class Z(K1,K2,K3): pass

   def merge(seqs):
       print '\n\nCPL[%s]=%s' % (seqs[0][0],seqs),
       res = []; i=0
       while 1:
         nonemptyseqs=[seq for seq in seqs if seq]
         if not nonemptyseqs: return res
         i+=1; print '\n',i,'round: candidates...',
         for seq in nonemptyseqs: # find merge candidates among seq heads
             cand = seq[0]; print ' ',cand,
             nothead=[s for s in nonemptyseqs if cand in s[1:]]
             if nothead: cand=None #reject candidate
             else: break
         if not cand: raise "Inconsistent hierarchy"
         res.append(cand)
         for seq in nonemptyseqs: # remove cand
             if seq[0] == cand: del seq[0]

   def mro(C):
       "Compute the class precedence list (mro) according to C3"
       return merge([[C]]+map(mro,C.__bases__)+[list(C.__bases__)])

   def print_mro(C):
       print '\nMRO[%s]=%s' % (C,mro(C))
       print '\nP22 MRO[%s]=%s' % (C,C.mro())

   print_mro(ex_9.Z)

   #</mro.py>

Das war's, Leute,

   viel Spaß!


Quellen
=======

[1] Der von Samuele Pedroni auf python-dev begonnene
    Diskussionsstrang: https://mail.python.org/pipermail/python-
    dev/2002-October/029035.html

[2] Der Aufsatz *A Monotonic Superclass Linearization for Dylan*:
    https://doi.org/10.1145/236337.236343

[3] Guido van Rossums Aufsatz *Unifying types and classes in Python
    2.2*: https://web.archive.org/web/20140210194412/http://www.pytho
    n.org/download/releases/2.2.2/descrintro
