Содержание страницы
Порядок разрешения методов Python 2.3¶The Python 2.3 Method Resolution Order
Примечание
Это исторический документ, предоставленный в качестве приложения к официальной документации. Порядок разрешения методов, описанный здесь, был введён в Python 2.3, но всё ещё используется в более поздних версиях, включая Python 3.
Автор: Микеле Симонато.
- Аннотация:
Этот документ предназначен для программистов Python, которые хотят понять порядок разрешения методов C3, используемый в Python 2.3. Хотя он не рассчитан на новичков, он достаточно педагогичен и содержит много проработанных примеров. Мне не известно о других общедоступных документах такого же охвата, поэтому он должен быть полезен.
Отказ от ответственности:
Я передаю этот документ Python Software Foundation по лицензии Python 2.3. Как обычно в таких случаях, я предупреждаю читателя, что последующее должно быть корректным, но я не даю никаких гарантий. Используйте на свой страх и риск!
Благодарности:
Всем участникам списка рассылки Python, которые меня поддерживали. Полу Фоли, указавшему на различные неточности и побудившему меня добавить раздел о локальном порядке предшествования. Дэвиду Гуджеру за помощь с форматированием в reStructuredText. Дэвиду Мерцу за помощь с редактированием. И, наконец, Гвидо ван Россуму, который с энтузиазмом добавил этот документ на официальную страницу Python 2.3.
Начало¶The beginning
Felix qui potuit rerum cognoscere causas – Вергилий
Всё началось с сообщения Самуэле Педрони в список рассылки разработчиков Python [1]. В своём сообщении Самуэле показал, что порядок разрешения методов Python 2.2 не является монотонным, и предложил заменить его на порядок разрешения методов C3. Гвидо согласился с его аргументами, и теперь Python 2.3 использует C3. Сам метод C3 не имеет никакого отношения к Python, поскольку он был изобретён людьми, работавшими над Dylan, и описан в статье, предназначенной для лисперов [2]. Настоящая статья даёт (надеюсь) читаемое обсуждение алгоритма C3 для питонистов, желающих понять причины изменений.
Прежде всего, позвольте отметить, что сказанное относится только к классам нового стиля, введённым в Python 2.2: классические классы сохраняют свой старый порядок разрешения методов – в глубину, затем слева направо. Поэтому для классических классов не происходит нарушения работы старого кода; и даже если в принципе могло бы быть нарушение для классов нового стиля Python 2.2, на практике случаи, в которых порядок разрешения C3 отличается от порядка разрешения методов Python 2.2, настолько редки, что не ожидается никакого реального нарушения. Поэтому:
Не бойтесь!
Более того, если вы не используете активно множественное наследование и у вас нет нетривиальных иерархий, вам не нужно понимать алгоритм C3, и вы можете смело пропустить эту статью. С другой стороны, если вы действительно хотите узнать, как работает множественное наследование, эта статья для вас. Хорошая новость в том, что всё не так сложно, как может показаться.
Начнём с некоторых базовых определений.
Для класса C в сложной иерархии множественного наследования указать порядок, в котором методы переопределяются, т.е. указать порядок предков C, является нетривиальной задачей.
Список предков класса C, включая сам класс, упорядоченный от ближайшего предка к самому дальнему, называется списком предшествования класса или линеаризацией C.
Порядок разрешения методов (MRO) – это набор правил, которые строят линеаризацию. В литературе по Python выражение «MRO C» также используется как синоним линеаризации класса C.
Например, в случае иерархии одиночного наследования, если C является подклассом C1, а C1 – подклассом C2, то линеаризация C – это просто список [C, C1, C2]. Однако в иерархиях множественного наследования построение линеаризации более громоздко, поскольку сложнее построить линеаризацию, которая соблюдает локальный порядок предшествования и монотонность.
Локальный порядок предшествования я обсужу позже, но здесь я могу дать определение монотонности. MRO является монотонным, когда выполняется следующее: если C1 предшествует C2 в линеаризации C, то C1 предшествует C2 в линеаризации любого подкласса C. В противном случае безобидная операция создания нового класса может изменить порядок разрешения методов, потенциально внося очень тонкие ошибки. Примеры, когда это происходит, будут показаны позже.
Не все классы допускают линеаризацию. В сложных иерархиях встречаются случаи, когда невозможно создать класс, линеаризация которого удовлетворяет всем желаемым свойствам.
Вот пример такой ситуации. Рассмотрим иерархию
>>> O = object
>>> class X(O): pass
>>> class Y(O): pass
>>> class A(X,Y): pass
>>> class B(Y,X): pass
что можно представить следующим графом наследования, где я
обозначил через O класс object, который является началом любой
иерархии для классов нового стиля:
----------- | | | O | | / \ | - X Y / | / | / | / |/ A B \ / ?
В этом случае невозможно вывести новый класс C из A и B, поскольку X предшествует Y в A, но Y предшествует X в B, поэтому порядок разрешения методов был бы неоднозначным в C.
Python 2.3 в такой ситуации вызывает исключение (TypeError: конфликт MRO среди базовых классов Y, X), запрещая неопытному программисту создавать неоднозначные иерархии. Python 2.2 вместо этого не вызывает исключение, а выбирает специфический порядок (в данном случае CABXYO).
Порядок разрешения методов C3¶The C3 Method Resolution Order
Введём несколько простых обозначений, которые будут полезны для дальнейшего обсуждения. Я буду использовать сокращённую запись:
C1 C2 ... CN
для обозначения списка классов [C1, C2, … , CN].
Голова списка – это первый элемент:
head = C1
а хвост – это остаток списка:
tail = C2 ... CN.
Также я буду использовать обозначение:
C + (C1 C2 ... CN) = C C1 C2 ... CN
для обозначения суммы списков [C] + [C1, C2, … ,CN].
Теперь я могу объяснить, как работает MRO в Python 2.3.
Рассмотрим класс C в иерархии множественного наследования, где C наследует от базовых классов B1, B2, … , BN. Нам нужно вычислить линеаризацию L[C] класса C. Правило таково:
линеаризация C – это сумма C и слияния линеаризаций родителей и списка родителей.
В символьной записи:
L[C(B1 ... BN)] = C + merge(L[B1] ... L[BN], B1 ... BN)
В частности, если C является классом object, не имеющим родителей,
линеаризация тривиальна:
L[object] = object.
Однако в общем случае необходимо вычислить слияние в соответствии со следующим предписанием:
взять голову первого списка, то есть L[B1][0]; если эта голова не находится в хвосте ни одного из других списков, то добавить её к линеаризации C и удалить её из списков в слиянии, в противном случае посмотреть на голову следующего списка и взять её, если она является подходящей головой. Затем повторять операцию, пока все классы не будут удалены или не станет невозможно найти подходящие головы. В этом случае невозможно построить слияние, Python 2.3 откажется создавать класс C и вызовет исключение.
Это предписание гарантирует, что операция слияния сохраняет порядок, если порядок может быть сохранён. С другой стороны, если порядок не может быть сохранён (как в примере серьёзного рассогласования порядка, рассмотренного выше), то слияние не может быть вычислено.
Вычисление слияния тривиально, если у C только один родитель (одиночное наследование); в этом случае:
L[C(B)] = C + merge(L[B],B) = C + L[B]
Однако в случае множественного наследования всё сложнее, и я не ожидаю, что правило можно понять без пары примеров ;-)
Примеры¶Examples
Первый пример. Рассмотрим следующую иерархию:
>>> 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
В этом случае граф наследования можно изобразить так:
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) ---
Линеаризации O, D, E и F тривиальны:
L[O] = O
L[D] = D O
L[E] = E O
L[F] = F O
Линеаризация B может быть вычислена так:
L[B] = B + merge(DO, EO, DE)
Мы видим, что D – подходящая голова, поэтому мы берём её и сводим задачу к
вычислению merge(O,EO,E). Теперь O не является подходящей головой, так как он находится в
хвосте последовательности EO. В этом случае правило говорит, что нужно
перейти к следующей последовательности. Затем мы видим, что E – подходящая голова; мы берём
её и сводим задачу к вычислению merge(O,O), что даёт O. Следовательно:
L[B] = B D E O
Используя ту же процедуру, находим:
L[C] = C + merge(DO,FO,DF)
= C + D + merge(O,FO,F)
= C + D + F + merge(O,O)
= C D F O
Теперь мы можем вычислить:
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
В этом примере линеаризация упорядочена довольно хорошо в соответствии с уровнем наследования, в том смысле, что более низкие уровни (т.е. более специализированные классы) имеют более высокий приоритет (см. граф наследования). Однако это не общий случай.
Я оставляю читателю в качестве упражнения вычислить линеаризацию для моего второго примера:
>>> 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
Единственное отличие от предыдущего примера – изменение B(D,E) на B(E,D); однако даже такая небольшая модификация полностью меняет порядок иерархии:
6 --- Level 3 | O | / --- \ / | \ / | \ / | \ --- --- --- Level 2 2 | E | 4 | D | | F | 5 --- --- --- \ / \ / \ / \ / \ / \ / --- --- Level 1 1 | B | | C | 3 --- --- \ / \ / --- Level 0 0 | A | ---
Обратите внимание, что класс E, находящийся на втором уровне иерархии, предшествует классу C, находящемуся на первом уровне, то есть E более специализирован, чем C, даже несмотря на то, что он находится на более высоком уровне.
Ленивый программист может получить MRO непосредственно из Python 2.2, так как в
этом случае он совпадает с линеаризацией Python 2.3. Достаточно
вызвать метод mro() класса A:
>>> A.mro()
[<class 'A'>, <class 'B'>, <class 'E'>,
<class 'C'>, <class 'D'>, <class 'F'>,
<class 'object'>]
Наконец, рассмотрим пример из первого раздела, где был серьёзный конфликт порядка. В этом случае линеаризации O, X, Y, A и B вычисляются без труда:
L[O] = 0 L[X] = X O L[Y] = Y O L[A] = A X Y O L[B] = B Y X O
Однако вычислить линеаризацию для класса C, наследующего от A и B, невозможно:
L[C] = C + merge(AXYO, BYXO, AB)
= C + A + merge(XYO, BYXO, B)
= C + A + B + merge(XYO, YXO)
На этом этапе слить списки XYO и YXO нельзя: X находится в хвосте YXO, а Y – в хвосте XYO. Подходящих голов не остаётся, и алгоритм C3 останавливается. Python 2.3 выдаёт ошибку и отказывается создавать класс C.
Плохие порядки разрешения методов¶Bad Method Resolution Orders
MRO считается плохим, если нарушает такие фундаментальные свойства, как порядок локального старшинства и монотонность. В этом разделе я покажу, что и MRO для классических классов, и MRO для классов нового стиля в Python 2.2 являются плохими.
Начнём с порядка локального старшинства – это проще. Рассмотрим следующий пример:
>>> F=type('Food',(),{'remember2buy':'spam'})
>>> E=type('Eggs',(F,),{'remember2buy':'eggs'})
>>> G=type('GoodFood',(F,E),{}) # В Python 2.3 это ошибка!
с диаграммой наследования
O | (buy spam) F | \ | E (buy eggs) | / G (buy eggs or spam ?)
Мы видим, что класс G наследует от F и E, причём F перед E. Поэтому можно ожидать, что атрибут G.remember2buy унаследуется от F.remember2buy, а не от E.remember2buy. Однако Python 2.2 выдаёт
>>> G.remember2buy
'eggs'
Это нарушение порядка локального старшинства, поскольку порядок в списке локальных предшественников (то есть список родителей G) не сохраняется в линеаризации Python 2.2 для G:
L[G,P22]= G E F object # F *следует за* E
Можно возразить, что F идёт после E в линеаризации Python 2.2, потому что F менее специализирован, чем E (F – суперкласс E). Тем не менее нарушение порядка локального старшинства совершенно неинтуитивно и чревато ошибками. Особенно это заметно в сравнении с классическими классами:
>>> class F: remember2buy='spam'
>>> class E(F): remember2buy='eggs'
>>> class G(F,E): pass
>>> G.remember2buy
'spam'
В этом случае MRO – GFEF, и порядок локального старшинства сохраняется.
Как общее правило, иерархий, подобных предыдущей, следует избегать, поскольку непонятно, должен ли F переопределять E или наоборот. Python 2.3 решает эту неоднозначность – при создании класса G возникает исключение, что фактически не позволяет программисту создавать двусмысленные иерархии. Причина в том, что алгоритм C3 не может выполнить слияние:
merge(FO,EFO,FE)
не может быть выполнено, так как F находится в хвосте EFO, а E – в хвосте FE.
Настоящее решение – спроектировать недвусмысленную иерархию, то есть наследовать G от E и F (сначала более конкретный), а не от F и E. В этом случае MRO будет GEF – без всяких сомнений.
O | F (spam) / | (eggs) E | \ | G (eggs, no doubt)
Python 2.3 вынуждает программиста писать хорошие иерархии (или, по крайней мере, менее подверженные ошибкам).
Кстати, стоит отметить, что алгоритм Python 2.3 достаточно умён, чтобы распознавать очевидные ошибки, например дублирование классов в списке родителей:
>>> class A(object): pass
>>> class C(A,A): pass # ошибка
Traceback (most recent call last):
File "<stdin>", line 1, in ?
TypeError: duplicate base class A
Python 2.2 (как для классических классов, так и для классов нового стиля) в такой ситуации не выдавал бы никакого исключения.
Наконец, хотелось бы выделить два урока, которые можно извлечь из этого примера:
несмотря на название, MRO определяет порядок разрешения атрибутов, а не только методов;
обычная еда для питонистов – spam! (но вы и так это знали ;-)
Обсудив проблему порядка локального старшинства, перейдём теперь к монотонности. Моя цель – показать, что ни MRO для классических классов, ни MRO для классов нового стиля в Python 2.2 не являются монотонными.
Доказать немонотонность MRO для классических классов довольно тривиально – достаточно взглянуть на ромбовидную диаграмму:
C / \ / \ A B \ / \ / D
Несоответствие легко заметить:
L[B,P21] = B C # B предшествует C : методы B побеждают
L[D,P21] = D A C B C # B следует за C : методы C побеждают!
С другой стороны, с MRO Python 2.2 и 2.3 проблем нет – оба дают:
L[D] = D A B C
Гвидо отмечает в своей статье [3], что классический MRO на практике не так уж плох, поскольку для классических классов ромбов обычно удаётся избегать. Но все классы нового стиля наследуют от object, поэтому ромбы неизбежны, и несоответствия проявляются в любом графе множественного наследования.
MRO Python 2.2 делает нарушение монотонности маловероятным, но возможным. Следующий пример, изначально предложенный Самуэле Педрони, показывает, что MRO Python 2.2 немонотонен:
>>> 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
Вот линеаризации по C3 MRO (читателю предлагается проверить их самостоятельно и начертить диаграмму наследования ;-)
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 даёт те же линеаризации для A, B, C, D, E, K1, K2 и K3, но другую линеаризацию для Z:
L[Z,P22] = Z K1 K3 A K2 D B C E O
Понятно, что эта линеаризация неверна, поскольку A идёт перед D, тогда как в линеаризации K3 A идёт после D. Иными словами, в K3 методы, унаследованные от D, переопределяют методы от A, а в Z, который всё ещё является подклассом K3, методы от A переопределяют методы от D! Это нарушение монотонности. Более того, линеаризация Z в Python 2.2 также противоречит порядку локального старшинства: список локальных предшественников класса Z – [K1, K2, K3] (K2 предшествует K3), а в линеаризации Z K2 следует за K3. Эти проблемы объясняют, почему правило 2.2 было отброшено в пользу правила C3.
Конец¶The end
Этот раздел – для нетерпеливого читателя, который пропустил все предыдущие разделы и прыгнул сразу в конец. Он также для ленивого программиста, который не хотел напрягать мозги. Наконец, он для программиста с некоторым самомнением – иначе бы он не читал статью о порядке разрешения методов C3 при множественном наследовании ;-) Все три добродетели вместе (и не по отдельности) заслуживают награды: награда – короткий скрипт на Python 2.2, который позволяет вычислить MRO 2.3 без риска для мозга. Просто измените последнюю строку, чтобы поиграть с различными примерами, которые я обсуждал в этой статье.:
#<mro.py>
"""Алгоритм C3 от Самуэле Педрони (с улучшенной мной читаемостью)."""
class __metaclass__(type):
"All classes are metamagically modified to be nicely printed"
__repr__ = lambda cls: cls.__name__
class ex_2:
"Serious order disagreement" #От Гвидо
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 #создаёт Z(A,B) в Python 2.2
except TypeError:
pass # Z(A,B) невозможно создать в 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" #От Самуэле
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: # поиск кандидатов на слияние среди голов последовательностей
cand = seq[0]; print ' ',cand,
nothead=[s for s in nonemptyseqs if cand in s[1:]]
if nothead: cand=None #отклонить кандидата
else: break
if not cand: raise "Inconsistent hierarchy"
res.append(cand)
for seq in nonemptyseqs: # удалить кандидата
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>
Ну вот и всё, народ,
Наслаждайтесь!