Python 2.3 のメソッド解決順序
*****************************

注釈:

  これは公式ドキュメントの付録として提供する歴史的な文書です。 ここで
  説明するメソッド解決順序は Python 2.3 で *導入* されましたが、Python
  3 を含む後のバージョンでも使われています。

著者: Michele Simionato。

概要:
   *この文書は、Python 2.3 で使われる C3 メソッド解決順序を理解したい
   Python プログラマ向けです。 初心者向けではありませんが、詳しく解説
   した例を多数交えて学べるようにしています。 同じ範囲を扱う公開文書を
   他に知らないので、役に立つはずです。*

免責事項:

   *この文書を Python 2.3 ライセンスの下で Python Software Foundation
   に寄贈します。 このような場合の通例どおり、以下の内容は正しい* はず
   *ですが、保証はしないことをお断りします。 ご自身の責任でご利用くだ
   さい。*

謝辞:

   *Python メーリングリストで応援してくださった皆さんに感謝します。
   Paul Foley は不正確な点を指摘し、局所優先順位についての説明を追加す
   るきっかけをくれました。 David Goodger は reStructuredText での整形
   を、David Mertz は編集を手伝ってくれました。 最後に、Guido van
   Rossum はこの文書を熱心に公式の Python 2.3 ホームページに加えてくれ
   ました。*


はじめに
========

   *物事の原因を知ることができた者は幸いである* ― ウェルギリウス

すべては Samuele Pedroni による Python 開発メーリングリストへの投稿
[1] から始まりました。 Samuele は Python 2.2 のメソッド解決順序が単調
でないことを示し、C3 メソッド解決順序への置き換えを提案しました。
Guido が賛成したため、Python 2.3 は C3 を使っています。 C3 自体は
Python とは無関係で、Dylan の開発者によって考案され、Lisp 利用者向けの
論文 [2] に記述されています。 この文書では、変更の理由を知りたい
Python 利用者に向けて、C3 アルゴリズムをできるだけ読みやすく説明します
。

まず、これからの説明は Python 2.2 で導入された *新スタイルクラス* だけ
に当てはまります。 *旧スタイルクラス* は、深さ優先で左から右に調べる従
来のメソッド解決順序を維持します。 したがって、旧スタイルクラスを使う
既存のコードは壊れません。 Python 2.2 の新スタイルクラスを使うコードは
、理屈の上では壊れる可能性があります。 しかし、C3 と Python 2.2 のメソ
ッド解決順序が異なる場合は極めてまれなので、実際にコードが壊れることは
ないと考えられます。 つまり:

   *怖がらなくて大丈夫です！*

また、多重継承を多用して複雑な階層を作っているのでなければ、C3 アルゴ
リズムを理解する必要はなく、この文書は読み飛ばして構いません。 一方、
多重継承の仕組みを本当に知りたいなら、この文書はあなたのためのものです
。 うれしいことに、予想するほど複雑ではありません。

まず、基本的な定義から始めます。

1. 複雑な多重継承の階層にあるクラス C について、メソッドのオーバーライ
   ドの順序、つまり C の祖先の順序を定めるのは簡単ではありません。

2. クラス C 自身を含む祖先を、近いものから遠いものへ並べたリストを、ク
   ラス優先順位リスト、または C の *線形化* と呼びます。

3. *メソッド解決順序* (MRO) は、線形化を構築する規則の集まりです。
   Python の文献では「C の MRO」という表現を、クラス C の線形化と同じ
   意味でも使います。

4. 例えば単一継承で、C が C1 のサブクラス、C1 が C2 のサブクラスであれ
   ば、C の線形化は単に [C, C1, C2] です。 しかし多重継承では、*局所優
   先順位* と *単調性* を満たす線形化の構築が難しくなります。

5. 局所優先順位は後で説明しますが、単調性はここで定義できます。 次が成
   り立つ MRO は単調です。 *C の線形化で C1 が C2 より前にあれば、C の
   どのサブクラスの線形化でも C1 が C2 より前にある。* そうでなければ
   、新しいクラスを派生させるだけでメソッドの解決順序が変わり、非常に
   分かりにくいバグを持ち込む可能性があります。 後でその例を示します。

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
         \   /
           ?

この場合、A と B から新しいクラス C を派生させることはできません。 A
では X が Y に先行するのに、B では Y が X に先行するため、C のメソッド
解決順序が曖昧になるからです。

Python 2.3 はこの場合に例外 (TypeError: MRO conflict among bases Y, X)
を送出し、プログラマがうっかり曖昧な階層を作るのを防ぎます。 対して
Python 2.2 は例外を送出せず、その場限りの順序 (この場合は CABXYO) を選
びます。


C3 メソッド解決順序
===================

以降の説明に使う簡単な記法を導入します。 次の省略記法で、

   C1 C2 ... CN

クラスのリスト [C1, C2, ... , CN] を表します。

リストの *head* は最初の要素です。

   head = C1

一方、*tail* はリストの残りの部分です。

   tail = C2 ... CN.

また、次の記法で、

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

リストの連結 [C] + [C1, C2, ... , CN] を表します。

これで Python 2.3 の MRO の仕組みを説明する準備ができました。

多重継承の階層で、基底クラス B1、B2、...、BN を継承するクラス C を考え
ます。 クラス C の線形化 L[C] を求める規則は次のとおりです:

   *C の線形化は、C に、各親クラスの線形化と親クラスのリストをマージし
   たものを連結して求めます。*

記号で表すと次のとおりです。

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

特に C が親を持たない "object" クラスなら、線形化は単純です。

   L[object] = object.

ただし、一般の場合は次の手順でマージを計算する必要があります:

   *最初のリストの先頭、つまり L[B1][0] を取り出します。 この要素が他
   のどのリストの tail にも含まれていなければ、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 の tail に含まれるため、条件を満たしません。 この場
合は次の列を調べます。 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 |
                                ---

階層のレベル 2 にある E が、レベル 1 にある C より先行することに注目し
てください。 つまり、E は高い階層にあるのに、C より特化したものとして
扱われます。

計算を省きたいプログラマは、Python 2.2 で MRO を直接取得できます。 こ
の場合は Python 2.3 の線形化と一致するためです。 クラス A の "mro()"
メソッドを呼び出すだけです:

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

最後に、最初の節で扱った、順序に重大な矛盾がある例を考えます。 O、X、Y
、A、B の線形化は簡単に計算できます:

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

しかし A と B を継承するクラス C の線形化は計算できません。

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

この段階で XYO と YXO をマージすることはできません。 X は YXO の tail
にあり、Y は XYO の tail にあるため、条件を満たす先頭要素がないからで
す。 C3 アルゴリズムはここで停止し、Python 2.3 はエラーを送出してクラ
ス C の作成を拒否します。


問題のあるメソッド解決順序
==========================

局所優先順位や単調性といった基本的な性質を満たさない MRO は、*問題があ
る* といえます。 この節では、旧スタイルクラスの MRO と Python 2.2 の新
スタイルクラスの MRO が、どちらも問題を持つことを示します。

まずは簡単な局所優先順位から始めます。 次の例を考えてください:

>>> 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* は *E.remember2buy* ではなく *F.remember2buy* を継承
すると期待するでしょう。 しかし Python 2.2 の結果は次のとおりです:

>>> G.remember2buy
'eggs'

これは局所優先順位に反しています。 局所優先順位リスト、つまり G の親の
リストの順序が、Python 2.2 による G の線形化では維持されていません。

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

Python 2.2 の線形化で F が E の後になるのは、F が E のスーパークラスで
、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 の tail にあり、E は FE の tail にあるので、計算できません。

The real solution is to design a non-ambiguous hierarchy, i.e. to
derive G from E and F (the more specific first) and not from F and E;
in this case the MRO is GEF without any doubt.

                 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 も
Python 2.2 の新スタイルクラスの MRO も単調でないことを示します。

旧スタイルクラスの 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!

一方、Python 2.2 と 2.3 の MRO にはこの問題はなく、どちらも次の結果に
なります。

   L[D] = D A B C

Guido は論考 [3] で、旧スタイルクラスでは通常ダイヤモンド型の継承を避
けられるため、その MRO は実際にはそれほど悪くないと指摘しています。 し
かし、新スタイルクラスはすべて "object" を継承するため、ダイヤモンドを
避けられず、どの多重継承の図にも不整合が現れます。

Python 2.2 の MRO は単調性を破りにくくしていますが、不可能にしたわけで
はありません。 Samuele Pedroni が最初に示した次の例は、Python 2.2 の
MRO が単調でないことを示します:

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

この線形化は明らかに *間違っています*。 K3 の線形化では A が D の *後*
にあるのに、ここでは A が D より前だからです。 つまり K3 では D から継
承したメソッドが A のものをオーバーライドするのに、K3 のサブクラスであ
る Z では A のメソッドが D のものをオーバーライドします。 これは単調性
への違反です。 さらに Python 2.2 による Z の線形化は、局所優先順位にも
反します。 Z の局所優先順位リストは [K1, K2, K3] で K2 が K3 より前な
のに、線形化では K2 が K3 の *後* にあるからです。 こうした問題のため
、2.2 の規則は C3 に置き換えられました。


おわりに
========

この節は、前の節をすべて飛ばしてすぐ最後に来た、せっかちな読者のための
ものです。 また、頭を働かせたくなかった怠け者のプログラマのためでもあ
ります。 そして多少の傲慢さを持つプログラマのためでもあります。 そうで
なければ、多重継承の階層における C3 メソッド解決順序の文書など読まない
でしょう ;-) この三つの美徳をすべて兼ね備えていれば (別々では *だめで
す*)、ご褒美に値します。 ご褒美は、頭を悩ませずに 2.3 の MRO を計算で
きる、短い Python 2.2 スクリプトです。 最後の行を変えるだけで、この文
書のさまざまな例を試せます。

   #<mro.py>

   """Samuele Pedroni による C3 アルゴリズム (筆者が読みやすく変更)。"""

   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>

これでおしまいです。

   楽しんでください！


参考資料
========

[1] Samuele Pedroni が始めた python-dev のスレッド:
    https://mail.python.org/pipermail/python-
    dev/2002-October/029035.html

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

[3] Guido van Rossum の論考 *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
