Порядок Разрешения Методов Python 2.3

Начало

Felix qui potuit rerum cognoscere causas – Вергилий

Всё началось с поста Самуэле Педрони на список рассылки Python development [1]. В своём посте Самуэле показал, что порядок разрешения методов Python 2.2 не монотонный и предложил заменить его порядком разрешения методов C3. Гвидо согласился с его аргументами, и поэтому сейчас Python 2.3 использует C3. Сам метод C3 не имеет отношения к Python, так как был изобретён людьми, работающими над Dylan, и описан в статье, предназначенной для lispers [2]. Настоящая статья даёт (надеюсь, читабельное) обсуждение алгоритма C3 для Pythonistas, которые хотят понять причины изменения.

Прежде всего, позвольте мне указать, что сказанное мной относится только к классам нового стиля, введённым в Python 2.2: классы классического стиля сохраняют свой старый порядок разрешения методов, сначала в глубину, а затем слева направо. Поэтому не происходит нарушения старого кода для классических классов; и даже если в принципе могло произойти нарушение кода для классов нового стиля Python 2.2, на практике случаи, в которых порядок разрешения C3 отличается от порядка разрешения методов Python 2.2, настолько редки, что реального нарушения кода не ожидается. Следовательно:

Не бойтесь!

Более того, если вы не используете многократное наследование и у вас нет сложных иерархий, вам не нужно понимать алгоритм C3, и вы можете легко пропустить эту статью. С другой стороны, если вы действительно хотите узнать, как работает множественное наследование, то эта статья для вас. Хорошая новость заключается в том, что всё не так сложно, как вы могли бы ожидать.

Давайте начнём с некоторых основных определений.

1. Учитывая класс C в сложной иерархии множественного наследования, указать порядок переопределения методов, т.е. указать порядок предков C, является нетривиальной задачей.
2. Список предков класса C, включая сам класс, упорядоченный от ближайшего предка до самого дальнего, называется списком приоритета классов или линейной последовательностью класса C.
3. Порядок разрешения методов (MRO) — это набор правил, которые строят линейную последовательность. В литературе по Python также используется выражение «MRO класса C» как синоним линейной последовательности класса C.
4. Например, в случае иерархии одиночного наследования, если C является подклассом C1, а C1 является подклассом C2, то линейная последовательность C — это просто список [C, C1, C2]. Однако при иерархиях множественного наследования построение линейной последовательности более сложно, так как труднее построить линейную последовательность, которая соблюдает локальный порядок приоритета и монотонность.
5. Я обсужу локальный порядок приоритета позже, но могу дать здесь определение монотонности. MRO является монотонным, когда выполняется следующее: если C1 предшествует C2 в линейной последовательности C, то C1 предшествует C2 в линейной последовательности любого подкласса C. В противном случае, невинная операция получения нового класса может изменить порядок разрешения методов, потенциально введя очень тонкие ошибки. Примеры, где это происходит, будут показаны позже.
6. Не все классы допускают линейную последовательность. В сложных иерархиях есть случаи, когда невозможно получить класс, линейная последовательность которого соответствует всем желаемым свойствам.

Вот пример такой ситуации. Рассмотрим иерархию

>>> 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 conflict among bases Y, X), запрещая неопытному программисту создавать неоднозначные иерархии. Python 2.2 вместо этого не поднимает исключение, а выбирает ad hoc порядок (CABXYO в этом случае).

Порядок Разрешения Методов C3

Давайте введём несколько простых обозначений, которые будут полезны для дальнейшего обсуждения. Я буду использовать сокращённое обозначение:

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 в иерархии множественного наследования с наследованием от базовых классов 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]

Однако в случае множественного наследования вещи более сложны, и я не ожидаю, что вы сможете понять правило без пары примеров ;-)

Примеры

Первый пример. Рассмотрим следующую иерархию:

>>> 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.

Плохие порядки разрешения методов

Порядок разрешения методов (MRO) является плохим, когда он нарушает такие фундаментальные свойства, как локальный порядок приоритета и монотонность. В этом разделе я покажу, что порядок разрешения методов как для классических классов, так и для новых стилей классов в Python 2.2 является плохим.

Легче начать с локального порядка приоритета. Рассмотрим следующий пример:

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

с диаграммой наследования

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

      (buy eggs or spam ?)

Мы видим, что класс G наследуется от F и E, причём F предыдущий E: поэтому мы ожидали бы, что атрибут G.remember2buy будет унаследован от F.rembermer2buy, а не от E.remember2buy: тем не менее Python 2.2 даёт

>>> G.remember2buy  
'eggs'

Это нарушение локального порядка приоритета, так как порядок в списке локального приоритета, то есть списке родителей G, не сохраняется в линейном представлении G в Python 2.2:

L[G,P22]= G E F object   # F *follows* 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 # error
Traceback (most recent call last):
  File "<stdin>", line 1, in ?
TypeError: duplicate base class A

Python 2.2 (как для классических классов, так и для новых стилей классов) в этой ситуации не вызовет никаких исключений.

Наконец, я хотел бы отметить два урока, которые мы извлекли из этого примера:

1. несмотря на название, порядок разрешения методов (MRO) определяет порядок разрешения атрибутов, а не только методов;
2. стандартный продукт для Python-разработчиков — спам! (но вы уже это знали ;-)

После обсуждения вопроса о локальном порядке приоритета позвольте мне теперь рассмотреть вопрос о монотонности. Моя цель — показать, что ни порядок разрешения методов (MRO) для классических классов, ни порядок разрешения методов (MRO) для новых стилей классов Python 2.2 не является монотонным.

Доказательство того, что порядок разрешения методов (MRO) для классических классов не является монотонным, довольно тривиально, достаточно взглянуть на диаграмму алмаза:

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

Легко заметить несоответствие:

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!

С другой стороны, проблем с порядками разрешения методов (MRO) Python 2.2 и 2.3 нет, они оба дают:

L[D] = D A B C

Гвидо в своей статье [3] отмечает, что классический порядок разрешения методов (MRO) на практике не так плох, так как обычно можно избегать алмазов для классических классов. Но все классы нового стиля наследуются от object, поэтому алмазы неизбежны, и несоответствия проявляются в каждой диаграмме множественного наследования.

Порядок разрешения методов (MRO) Python 2.2 затрудняет, но не делает невозможным нарушение монотонности. Следующий пример, первоначально предоставленный Samuele Pedroni, показывает, что порядок разрешения методов (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

Вот линейные представления в соответствии с порядком разрешения методов (MRO) C3 (читатель должен проверить эти линейные представления как упражнение и нарисовать диаграмму наследования ;-)

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.

Конец

Этот раздел предназначен для нетерпеливого читателя, который пропустил все предыдущие разделы и сразу перешёл к концу. Этот раздел также предназначен для ленивого программиста, который не хотел напрягать свой мозг. Наконец, это для программиста с некоторой самоуверенностью, иначе он не читал бы статью о порядке разрешения методов C3 в иерархиях множественного наследования ;-) Эти три добродетели, взятые вместе (а не по отдельности), заслуживают награды: награда — это короткий скрипт Python 2.2, который позволяет вам вычислить порядок разрешения методов (MRO) 2.3, не рискуя своим мозгом. Просто измените последнюю строку, чтобы поиграть с различными примерами, которые я обсуждал в этой статье.:

#<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>

Вот и всё,

приятного чтения!

Ресурсы