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.
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.
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.
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.
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.
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.
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:
Dem Namen zum Trotz bestimmt die MRO die Auflösungsreihenfolge von Attributen, nicht nur von Methoden;
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ß!