Die Methodeauflösungsreihenfolge (MRO) in Python 2.3¶
Hinweis
Dies ist ein historisches Dokument, das als Anhang zur offiziellen Dokumentation dient. Die hier diskutierte Methodeauflösungsreihenfolge wurde in Python 2.3 *eingeführt*, wird aber auch in späteren Versionen – einschließlich Python 3 – verwendet.
Von Michele Simionato.
- Zusammenfassung:
Dieses Dokument richtet sich an Python-Programmierer, die die in Python 2.3 verwendete C3-Methodeauflösungsreihenfolge verstehen möchten. Obwohl es nicht für Anfänger gedacht ist, ist es mit vielen ausgearbeiteten Beispielen recht pädagogisch. Mir sind keine anderen öffentlich zugänglichen Dokumente mit demselben Umfang bekannt, daher sollte es nützlich sein.
Haftungsausschluss
Ich spende dieses Dokument der Python Software Foundation unter der Python 2.3-Lizenz. Wie üblich unter diesen Umständen warne ich den Leser, dass das Folgende korrekt sein *sollte*, aber ich gebe keine Garantie. Verwenden Sie es auf eigene Gefahr!
Danksagung
Alle Leute aus der Python-Mailingliste, die mir ihre Unterstützung geschickt haben. Paul Foley, der auf verschiedene Ungenauigkeiten hinwies und mich dazu brachte, den Teil über lokale Vorrangordnungen hinzuzufügen. David Goodger für Hilfe bei der Formatierung in reStructuredText. David Mertz für Hilfe bei der Bearbeitung. Schließlich Guido van Rossum, der dieses Dokument begeistert zur offiziellen Python 2.3-Homepage hinzugefügt hat.
Der Anfang¶
Felix qui potuit rerum cognoscere causas – Virgilius
Alles begann mit einem Beitrag von Samuele Pedroni an die Python-Entwicklungs-Mailingliste [1]. In seinem Beitrag zeigte Samuele, dass die Methodeauflösungsreihenfolge von Python 2.2 nicht monoton ist, und schlug vor, sie durch die C3-Methodeauflösungsreihenfolge zu ersetzen. Guido stimmte seinen Argumenten zu, und daher verwendet Python 2.3 jetzt C3. Die C3-Methode selbst hat nichts mit Python zu tun, da sie von Leuten entwickelt wurde, die an Dylan gearbeitet haben, und in einem Papier für Lisper beschrieben wird [2]. Das vorliegende Papier gibt eine (hoffentlich) lesbare Diskussion des C3-Algorithmus für Pythonistas, die die Gründe für die Änderung verstehen wollen.
Zunächst möchte ich darauf hinweisen, dass das, was ich sagen werde, nur für die in Python 2.2 eingeführten neuen Klassen gilt: klassische Klassen behalten ihre alte Methodeauflösungsreihenfolge, Tiefe zuerst und dann von links nach rechts. Daher gibt es keine Unterbrechung von altem Code für klassische Klassen; und auch wenn es im Prinzip zu einer Unterbrechung von Code für neue Klassen von Python 2.2 kommen könnte, sind die Fälle, in denen die C3-Auflösungsreihenfolge von der Python 2.2-Methodeauflösungsreihenfolge abweicht, so selten, dass keine tatsächliche Unterbrechung von Code erwartet wird. Daher
Hab keine Angst!
Darüber hinaus, es sei denn, Sie nutzen intensiv Mehrfachvererbung und haben nicht-triviale Hierarchien, müssen Sie den C3-Algorithmus nicht verstehen und können dieses Papier problemlos überspringen. Wenn Sie jedoch wirklich wissen wollen, wie Mehrfachvererbung funktioniert, dann ist dieses Papier für Sie. Die gute Nachricht ist, dass die Dinge nicht so kompliziert sind, wie Sie vielleicht erwarten.
Lassen Sie mich mit einigen grundlegenden Definitionen beginnen.
Gegeben sei eine Klasse C in einer komplizierten Mehrfachvererbungshierarchie. Es ist keine triviale Aufgabe, die Reihenfolge zu spezifizieren, in der Methoden überschrieben werden, d.h. die Reihenfolge der Vorfahren von C zu spezifizieren.
Die Liste der Vorfahren einer Klasse C, einschließlich der Klasse selbst, geordnet vom nächstgelegenen Vorfahren zum weiter entfernten, wird als Klassen-Vorrangliste oder Linearisierung von C bezeichnet.
Die Methodeauflösungsreihenfolge (MRO) ist die Menge von Regeln, die die Lineariserung konstruieren. In der Python-Literatur wird die Formulierung „die MRO von C“ auch als Synonym für die Lineariserung der Klasse C verwendet.
Beispielsweise ist im Falle einer einfachen Vererbungshierarchie, wenn C eine Unterklasse von C1 ist und C1 eine Unterklasse von C2 ist, die Lineariserung von C einfach die Liste [C, C1, C2]. Bei Mehrfachvererbungshierarchien ist die Konstruktion der Lineariserung jedoch umständlicher, da es schwieriger ist, eine Lineariserung zu konstruieren, die die lokale Vorrangordnung und die Monotonie respektiert.
Ich werde die lokale Vorrangordnung später diskutieren, kann aber hier die Definition der Monotonie geben. Eine MRO ist monoton, wenn Folgendes gilt: Wenn C1 in der Lineariserung von C vor C2 kommt, dann kommt C1 in der Lineariserung jeder Unterklasse von C vor C2. Andernfalls könnte der harmlose Vorgang der Ableitung einer neuen Klasse die Auflösungsreihenfolge von Methoden ändern und potenziell sehr subtile Fehler einführen. Beispiele, wo dies geschieht, werden später gezeigt.
Nicht alle Klassen erlauben eine Lineariserung. Es gibt Fälle in komplizierten Hierarchien, in denen es nicht möglich ist, eine Klasse abzuleiten, deren Lineariserung alle gewünschten Eigenschaften respektiert.
Hier gebe ich ein Beispiel für diese Situation. Betrachten Sie die Hierarchie
>>> O = object
>>> class X(O): pass
>>> class Y(O): pass
>>> class A(X,Y): pass
>>> class B(Y,X): pass
die mit dem folgenden Vererbungsgraphen dargestellt werden kann, wobei ich mit O die object-Klasse bezeichnet habe, die der Anfang jeder Hierarchie für neue Klassen ist
----------- | | | O | | / \ | - X Y / | / | / | / |/ A B \ / ?
In diesem Fall ist es nicht möglich, eine neue Klasse C von A und B abzuleiten, da X in A vor Y kommt, aber Y in B vor X kommt, daher wäre die Methodeauflösungsreihenfolge in C mehrdeutig.
Python 2.3 löst in dieser Situation eine Ausnahme aus (TypeError: MRO-Konflikt unter Basisklassen Y, X) und verbietet dem naiven Programmierer die Erstellung mehrdeutiger Hierarchien. Python 2.2 löst stattdessen keine Ausnahme aus, wählt aber eine *Ad-hoc*-Ordnung (in diesem Fall CABXYO).
Die C3-Methodeauflösungsreihenfolge¶
Lassen Sie mich einige einfache Notationen einführen, die für die folgende Diskussion nützlich sein werden. Ich werde die Kurzschreibweise verwenden
C1 C2 ... CN
um die Liste der Klassen [C1, C2, … , CN] anzuzeigen.
Der Kopf der Liste ist ihr erstes Element
head = C1
während der Schwanz der Rest der Liste ist
tail = C2 ... CN.
Ich werde auch die Notation verwenden
C + (C1 C2 ... CN) = C C1 C2 ... CN
um die Summe der Listen [C] + [C1, C2, … ,CN] darzustellen.
Nun kann ich erklären, wie die MRO in Python 2.3 funktioniert.
Betrachten Sie eine Klasse C in einer Mehrfachvererbungshierarchie, wobei C von den Basisklassen B1, B2, … , BN erbt. Wir möchten die Lineariserung L[C] der Klasse C berechnen. Die Regel lautet:
die Lineariserung von C ist die Summe von C plus das Zusammenführen der Lineariserungen der Eltern und der Liste der Eltern.
In symbolischer Notation
L[C(B1 ... BN)] = C + merge(L[B1] ... L[BN], B1 ... BN)
Insbesondere, wenn C die object-Klasse ist, die keine Eltern hat, ist die Lineariserung trivial
L[object] = object.
Im Allgemeinen muss jedoch das Zusammenführen gemäß der folgenden Vorschrift berechnet werden
nimm den Kopf der ersten Liste, d.h. L[B1][0]; wenn dieser Kopf nicht im Schwanz einer der anderen Listen ist, füge ihn zur Lineariserung von C hinzu und entferne ihn aus den Listen beim Zusammenführen, schaue dann auf den Kopf der nächsten Liste und nimm ihn, wenn er ein guter Kopf ist. Wiederhole dann den Vorgang, bis alle Klassen entfernt sind oder es unmöglich ist, gute Köpfe zu finden. In diesem Fall ist es unmöglich, das Zusammenführen zu konstruieren, Python 2.3 verweigert die Erstellung der Klasse C und löst eine Ausnahme aus.
Diese Vorschrift stellt sicher, dass der Zusammenführungsvorgang die Reihenfolge *beibehält*, wenn die Reihenfolge beibehalten werden kann. Wenn die Reihenfolge hingegen nicht beibehalten werden kann (wie im Beispiel einer ernsten Meinungsverschiedenheit bezüglich der Reihenfolge, die oben besprochen wurde), dann kann die Zusammenführung nicht berechnet werden.
Die Berechnung des Zusammenführens ist trivial, wenn C nur einen Elternteil hat (einfache Vererbung); in diesem Fall
L[C(B)] = C + merge(L[B],B) = C + L[B]
Im Falle von Mehrfachvererbung sind die Dinge jedoch umständlicher und ich erwarte nicht, dass Sie die Regel ohne ein paar Beispiele verstehen ;-)
Beispiele¶
Erstes Beispiel. Betrachten Sie 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 kann der Vererbungsgraph gezeichnet werden als
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 Lineariserungen von O, D, E und F sind trivial
L[O] = O
L[D] = D O
L[E] = E O
L[F] = F O
Die Lineariserung von B kann berechnet werden als
L[B] = B + merge(DO, EO, DE)
Wir sehen, dass D ein guter Kopf ist, also nehmen wir ihn und sind darauf reduziert, merge(O,EO,E) zu berechnen. Nun ist O kein guter Kopf mehr, da es im Schwanz der Sequenz EO vorkommt. In diesem Fall besagt die Regel, dass wir zur nächsten Sequenz springen müssen. Dann sehen wir, dass E ein guter Kopf ist; wir nehmen ihn und sind darauf reduziert, merge(O,O) zu 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
Nun 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 Lineariserung in einer ziemlich schönen Weise entsprechend dem Vererbungsebene geordnet, in dem Sinne, dass niedrigere Ebenen (d.h. spezialisiertere Klassen) eine höhere Priorität haben (siehe Vererbungsgraph). Dies ist jedoch nicht der allgemeine Fall.
Ich überlasse es dem Leser als Übung, die Lineariserung für mein zweites Beispiel zu berechnen
>>> 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 vorherigen Beispiel ist die Änderung B(D,E) -> B(E,D); jedoch verändert selbst eine so kleine Modifikation 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 | ---
Beachten Sie, dass die Klasse E, die sich auf der zweiten Ebene der Hierarchie befindet, vor der Klasse C liegt, die sich auf der ersten Ebene der Hierarchie befindet, d.h. E ist spezialisierter als C, obwohl sie sich auf einer höheren Ebene befindet.
Ein fauler Programmierer kann die MRO direkt aus Python 2.2 erhalten, da sie in diesem Fall mit der Python 2.3-Lineariserung übereinstimmt. Es reicht aus, die Methode mro() der Klasse A aufzurufen
>>> A.mro()
[<class 'A'>, <class 'B'>, <class 'E'>,
<class 'C'>, <class 'D'>, <class 'F'>,
<class 'object'>]
Abschließend betrachten wir das im ersten Abschnitt besprochene Beispiel, das eine ernste Meinungsverschiedenheit bezüglich der Reihenfolge betrifft. In diesem Fall ist es unkompliziert, die Lineariserungen von O, X, Y, A und B 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 Lineariserung 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, da X im Schwanz von YXO und Y im Schwanz von XYO vorkommt: Daher gibt es keine guten Köpfe und der C3-Algorithmus stoppt. Python 2.3 löst einen Fehler aus und weigert sich, die Klasse C zu erstellen.
Schlechte Methodeauflösungsreihenfolgen¶
Eine MRO ist *schlecht*, wenn sie grundlegende Eigenschaften wie lokale Vorrangordnung und Monotonie bricht. In diesem Abschnitt werde ich zeigen, dass sowohl die MRO für klassische Klassen als auch die MRO für neue Klassen in Python 2.2 schlecht sind.
Es ist einfacher, mit der lokalen Vorrangordnung zu beginnen. Betrachten Sie 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 Vererbungsgrafik
O | (buy spam) F | \ | E (buy eggs) | / G (buy eggs or spam ?)
Wir sehen, dass die Klasse G von F und E erbt, wobei F *vor* E steht: Daher würden wir erwarten, dass das Attribut G.remember2buy von F.remember2buy und nicht von E.remember2buy geerbt wird: Dennoch liefert Python 2.2
>>> G.remember2buy
'eggs'
Dies ist ein Bruch der lokalen Vorrangordnung, da die Reihenfolge in der lokalen Vorrangliste, d.h. die Liste der Eltern von G, in der Python 2.2-Lineariserung von G nicht beibehalten wird
L[G,P22]= G E F object # F *follows* E
Man könnte argumentieren, dass der Grund dafür, dass F in der Python 2.2-Lineariserung nach E steht, darin liegt, dass F weniger spezialisiert ist als E, da F die Oberklasse von E ist; dennoch ist der Bruch der lokalen Vorrangordnung ziemlich unintuitiv und fehleranfällig. Dies gilt insbesondere, da sie sich von alten 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 wird beibehalten.
Als allgemeine Regel sollten Hierarchien wie die vorherige vermieden werden, da unklar ist, ob F E überschreiben sollte oder umgekehrt. Python 2.3 löst die Mehrdeutigkeit, indem es beim Erstellen der Klasse G eine Ausnahme auslöst und damit den Programmierer effektiv daran hindert, mehrdeutige Hierarchien zu generieren. Der Grund dafür ist, dass der C3-Algorithmus fehlschlägt, wenn das Zusammenführen
merge(FO,EFO,FE)
nicht berechnet werden kann, da F im Schwanz von EFO und E im Schwanz von FE vorkommt.
Die wirkliche Lösung ist es, eine nicht-mehrdeutige Hierarchie zu entwerfen, d.h. G von E und F (die spezifischere zuerst) abzuleiten und nicht von F und E; in diesem Fall ist die MRO zweifelsfrei GEF.
O | F (spam) / | (eggs) E | \ | G (eggs, no doubt)
Python 2.3 zwingt den Programmierer, gute Hierarchien (oder zumindest weniger fehleranfällige) zu schreiben.
In einem verwandten Zusammenhang möchte ich darauf hinweisen, dass der Algorithmus von Python 2.3 schlau genug ist, offensichtliche Fehler zu erkennen, wie die Duplizierung von Klassen in der Elternliste
>>> 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 (sowohl für klassische Klassen als auch für neue Klassen) würde in dieser Situation keine Ausnahme auslösen.
Schließlich möchte ich zwei Lehren hervorheben, die wir aus diesem Beispiel gezogen haben
trotz des Namens bestimmt die MRO die Auflösungsreihenfolge von Attributen, nicht nur von Methoden;
das Standardfutter für Pythonistas ist Spam! (aber das wusstest du schon ;-)
Nachdem das Problem der lokalen Vorrangordnung erörtert wurde, möchte ich nun auf das Problem der Monotonie eingehen. Mein Ziel ist es zu zeigen, dass weder die MRO für klassische Klassen noch die für neue Klassen von Python 2.2 monoton ist.
Um zu beweisen, dass die MRO für klassische Klassen nicht-monoton ist, ist es recht trivial, man muss sich nur das Rauten-Diagramm ansehen
C / \ / \ A B \ / \ / D
Man erkennt leicht die Inkonsistenz
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!
Andererseits gibt es keine Probleme mit den MROs von Python 2.2 und 2.3, beide ergeben
L[D] = D A B C
Guido weist in seinem Essay [3] darauf hin, dass die klassische MRO in der Praxis nicht so schlecht ist, da man typischerweise Rauten für klassische Klassen vermeiden kann. Aber alle neuen Klassen erben von object, daher sind Rauten unvermeidlich und Inkonsistenzen zeigen sich in jeder Mehrfachvererbungsgrafik.
Die MRO von Python 2.2 macht das Brechen der Monotonie schwierig, aber nicht unmöglich. Das folgende Beispiel, ursprünglich von Samuele Pedroni bereitgestellt, 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 sind die Lineariserungen gemäß der C3 MRO (der Leser sollte diese Lineariserungen als Übung überprüfen und das Vererbungsgrafik 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 Lineariserungen, aber eine andere Lineariserung für Z
L[Z,P22] = Z K1 K3 A K2 D B C E O
Es ist klar, dass diese Lineariserung *falsch* ist, da A vor D kommt, während in der Lineariserung von K3 A *nach* D kommt. Mit anderen Worten, in K3 überschreiben Methoden, die von D abgeleitet sind, Methoden, die von A abgeleitet sind, aber in Z, das immer noch eine Unterklasse von K3 ist, überschreiben Methoden, die von A abgeleitet sind, Methoden, die von D abgeleitet sind! Dies ist eine Verletzung der Monotonie. Darüber hinaus ist die Python 2.2-Lineariserung von Z auch inkonsistent mit der lokalen Vorrangordnung, da die lokale Vorrangliste der Klasse Z [K1, K2, K3] lautet (K2 vor K3), während in der Lineariserung von Z K2 nach K3 kommt. 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 sofort zum Ende gesprungen ist. Dieser Abschnitt ist auch für den faulen Programmierer, der sein Gehirn nicht trainieren wollte. Schließlich ist er für den Programmierer mit etwas Überheblichkeit, sonst würde er kein Papier über die C3-Methodeauflösungsreihenfolge in Mehrfachvererbungshierarchien lesen ;-) Diese drei Tugenden, zusammen genommen (und *nicht* separat), verdienen einen Preis: Der Preis ist ein kurzes Python 2.2-Skript, das es Ihnen ermöglicht, die 2.3 MRO ohne Risiko für Ihr Gehirn zu berechnen. Ändern Sie einfach die letzte Zeile, um mit den verschiedenen Beispielen zu spielen, die ich in diesem Papier besprochen 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 ist alles, Leute,
Viel Spaß!