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.python.org/download/releases/2.2.2/descrintro