(日本語訳)The Python 2.3 Method Resolution Order

クラスシステムを書いているため,継承時のメソッド検索の資料として The Python 2.3 Method Resolution Orderを抜粋して翻訳しました.

The Python 2.3 Method Resolution Order

By Michele Simionato.

Moreover, unless you make strong use of multiple inheritance and you have non-trivial hierarchies, you don't need to understand the C3 algorithm, and you can easily skip this paper. On the other hand, if you really want to know how multiple inheritance works, then this paper is for you. The good news is that things are not as complicated as you might expect.

多重継承をちょっと使うだけだったり継承関係が明確なら, C3アルゴリズムを理解する必要はなく, この論文は簡単に読み飛ばすことができます. 一方,多重継承がどのように機能するのか本当に知りたいのであれば, この論文が役に立ちます.良いことに思ったほど複雑ではありません.

Let me begin with some basic definitions.

まずは基本定義から始めましょう.

  1. Given a class C in a complicated multiple inheritance hierarchy, it is a non-trivial task to specify the order in which methods are overridden, i.e. to specify the order of the ancestors of C.

  2. The list of the ancestors of a class C, including the class itself, ordered from the nearest ancestor to the furthest, is called the class precedence list or the linearization of C.

  3. The Method Resolution Order (MRO) is the set of rules that construct the linearization. In the Python literature, the idiom "the MRO of C" is also used as a synonymous for the linearization of the class C.

  4. For instance, in the case of single inheritance hierarchy, if C is a subclass of C1, and C1 is a subclass of C2, then the linearization of C is simply the list [C, C1 , C2]. However, with multiple inheritance hierarchies, the construction of the linearization is more cumbersome, since it is more difficult to construct a linearization that respects local precedence ordering and monotonicity.

  5. I will discuss the local precedence ordering later, but I can give the definition of monotonicity here. A MRO is monotonic when the following is true: if C1 precedes C2 in the linearization of C, then C1 precedes C2 in the linearization of any subclass of C. Otherwise, the innocuous operation of deriving a new class could change the resolution order of methods, potentially introducing very subtle bugs. Examples where this happens will be shown later.

  6. Not all classes admit a linearization. There are cases, in complicated hierarchies, where it is not possible to derive a class such that its linearization respects all the desired properties.

  1. 複雑な多重継承されたクラスCがあるとき,メソッドがオーバーライドされている順序,つまりCの祖先の順序を整理する方法は自明ではない.

  2. クラスCから見て近い祖先から遠い祖先へと整列されたCの祖先のリスト(クラスC自身を含む)は,クラス優先リストとかCの線形化と呼ばれる.

  3. メソッド解決順序(MRO)とは,線形化するためのいくつかのルールのこと. Pythonの文献では,クラスCの線形化と同じ意味で「CのMRO」という語がつかわれている.

  4. たとえば,単一継承階層の場合として CがC1のサブクラスであり,さらにC1がC2のサブクラスとすると, Cの線形化は単純に[C, C1, C2]というリストになる. とはいえ,多重継承階層の線形化は,局所的な優先順位や単調性のためにもっと扱いにくいものとなる.

  5. 局所的な優先順位については後ほど論じるとして,単調性の定義をここで示す. 次の場合MROは単調である: Cの線形化においてC1がC2に優先するとき, どんなCのサブクラスについてもC1はC2に優先する. さもなければ 新しいクラスを派生させただけでメソッドの解決順序が変化してしまい, 実に名状しがたいバグを引き起こす可能性がある. 後ほどこの実例を示す.

  6. すべてのクラスが線形化できるわけではない. 複雑な階層のクラスでは,これらの特性をみたす線形化ができないことがある.

Here I give an example of this situation. Consider the hierarchy

例として次のような階層を考えてみましょう.

>>> O = object
>>> class X(O): pass
>>> class Y(O): pass
>>> class A(X,Y): pass
>>> class B(Y,X): pass

which can be represented with the following inheritance graph, where I have denoted with O the object class, which is the beginning of any hierarchy for new style classes:

これは以下のようなグラフで表現できます.このグラフでは新スタイル(訳注: Python3スタイル)で継承階層の始めとなるObjectクラスをOと表記しています.

 -----------
|           |
|    O      |
|  /   \    |
 - X    Y  /
   |  / | /
   | /  |/
   A    B
   \   /
     ?

In this case, it is not possible to derive a new class C from A and B, since X precedes Y in A, but Y precedes X in B, therefore the method resolution order would be ambiguous in C.

この場合, クラスAではXがYより優先されますが クラスBではYがXより優先されるため, メソッド解決順序のあいまいさが生じてクラスCをAとBから派生させることができません.

Python 2.3 raises an exception in this situation (TypeError: MRO conflict among bases Y, X) forbidding the naive programmer from creating ambiguous hierarchies. Python 2.2 instead does not raise an exception, but chooses an ad hoc ordering (CABXYO in this case).

Python 2.3ではこの状況で例外(TypeError: MRO conflict among bases Y, X) を発生させて,経験不足なプログラマがつくる曖昧な階層を禁じています. Python 2.2では例外を起こさずに,その場しのぎ的な順序(この場合ではCABXYO)を採用します.

C3メソッド解決順序 (The C3 Method Resolution Order)

Let me introduce a few simple notations which will be useful for the following discussion. I will use the shortcut notation

今後の議論のためにシンプルな記述法をいくつか導入しよう.

クラスのリスト[C1, C2, ... , CN] を

C1 C2 ... CN

と書きます.

リストのヘッドはリストの最初の項目で

head = C1

テールはリストの残りの部分

tail = C2 ... CN

とします. さらに[C] + [C1, C2, ... ,CN]のようにリストを足すことを

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

と表記します.

Now I can explain how the MRO works in Python 2.3.

ではPython 2.3でMROがどのように動くのか示しましょう.

Consider a class C in a multiple inheritance hierarchy, with C inheriting from the base classes B1, B2, ... , BN. We want to compute the linearization L[C] of the class C. The rule is the following:

親クラスB1, B2, ..., BN から派生したクラスCについて考えてみましょう. クラスCの線形化L[C]を求めたい. 線形化のルールは:

the linearization of C is the sum of C plus the merge of the linearizations of the parents and the list of the parents.

Cの線形化は,Cに「親の線形化」と「親のリスト」をマージ(merge)したものを足したものになる.

In symbolic notation:

記号で表現すると:

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

In particular, if C is the object class, which has no parents, the linearization is trivial:

CがObjectクラス(親を持たない)ときの線形化は明らかにこうなる.

L[object] = object

However, in general one has to compute the merge according to the following prescription:

普遍的には以下の方法でマージを行う.

take the head of the first list, i.e L[B1][0]; if this head is not in the tail of any of the other lists, then add it to the linearization of C and remove it from the lists in the merge, otherwise look at the head of the next list and take it, if it is a good head. Then repeat the operation until all the class are removed or it is impossible to find good heads. In this case, it is impossible to construct the merge, Python 2.3 will refuse to create the class C and will raise an exception.

最初のリストのヘッド,すなわちL[B1][0]に注目する. これがほかのリストのテールに現れないなら,Cの線形化に付け加えてマージリストから削除する. そうでない場合は,次のリストに同じことをしていく. この作業を適合するヘッドが無くなるまで続ける. この例ではマージできないので,Python 2.3ではクラスCは生成されず例外が発生する.

This prescription ensures that the merge operation preserves the ordering, if the ordering can be preserved. On the other hand, if the order cannot be preserved (as in the example of serious order disagreement discussed above) then the merge cannot be computed.

順序付けできる場合ならこの方法で適切にマージができる. 一方で順序付けできない(前出の例のような)場合には,マージはできない.

The computation of the merge is trivial if C has only one parent (single inheritance); in this case

Cの親が一つだけ(単一継承)の場合のマージは次のように計算できる.

L[C(B)] = C + merge(L[B],B) = C + L[B]

However, in the case of multiple inheritance things are more cumbersome and I don't expect you can understand the rule without a couple of examples ;-)

多重継承の場合はもっと複雑で,いくつかの例を挙げないとには 線形化のルールを理解してもらえないと思う😉

例

First example. Consider the following hierarchy:

最初の例. このような階層を考える:

>>> 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 this case the inheritance graph can be drawn as

これを継承グラフにするとこうなる.

                          6
                         ---
Level 3                 | O |                  (より一般)
                      /  ---  \
                     /    |    \                      |
                    /     |     \                     |
                   /      |      \                    |
                  ---    ---    ---                   |
Level 2        3 | D | 4| E |  | F | 5                |
                  ---    ---    ---                   |
                   \  \ _ /       |                   |
                    \    / \ _    |                   |
                     \  /      \  |                   |
                      ---      ---                    |
Level 1            1 | B |    | C | 2                 |
                      ---      ---                    |
                        \      /                      |
                         \    /                      \ /
                           ---
Level 0                 0 | A |                (より専門)
                           ---

The linearizations of O,D,E and F are trivial:

O,D,E,Fの線形化は自明で:

L[O] = O
L[D] = D O
L[E] = E O
L[F] = F O

The linearization of B can be computed as

Bの線形化は次のように計算可能

L[B] = B + merge(DO, EO, DE)

We see that D is a good head, therefore we take it and we are reduced to compute merge(O,EO,E). Now O is not a good head, since it is in the tail of the sequence EO. In this case the rule says that we have to skip to the next sequence. Then we see that E is a good head; we take it and we are reduced to compute merge(O,O) which gives O. Therefore

Dは良いヘッドとなるので,Dを取り出してマージを整理すると merge(O, EO, E) となる. OはEOのテールにあるので悪いヘッドである.ルールはこの場合,次のシーケンスに行けと言っている. 次のEは良いヘッドとなるので,Eを取り出してマージを整理すると merge(O, O) になり,これはOとなる.したがって

L[B] =  B D E O

Using the same procedure one finds:

同様に:

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

In this example, the linearization is ordered in a pretty nice way according to the inheritance level, in the sense that lower levels (i.e. more specialized classes) have higher precedence (see the inheritance graph). However, this is not the general case.

この例では, より専門化したクラスの方が継承レベルに応じて優先度が高くなる(継承グラフを参照)ような,いい感じの順序付けになっています.でもこの様なことは一般的ではありません.

I leave as an exercise for the reader to compute the linearization for my second example:

線形化の別の例を,読者の練習問題として挙げておきます.

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

The only difference with the previous example is the change B(D,E) --> B(E,D); however even such a little modification completely changes the ordering of the hierarchy

前の例との違いは 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 |
                          ---

Notice that the class E, which is in the second level of the hierarchy, precedes the class C, which is in the first level of the hierarchy, i.e. E is more specialized than C, even if it is in a higher level.

第二レベルのクラスEは第一レベルのクラスCより優先されています. つまり,上位階層にあるEの方がCより専門化されていることに注意してください.

A lazy programmer can obtain the MRO directly from Python 2.2, since in this case it coincides with the Python 2.3 linearization. It is enough to invoke the .mro() method of class A:

不精なプログラマはバージョン2.2以降のPythonから直接MROを得ることができます. このケースではPython 2.3の線形化と一致します.クラスAのmro()メソッドを呼び出すだけです.

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

Finally, let me consider the example discussed in the first section, involving a serious order disagreement. In this case, it is straightforward to compute the linearizations of O, X, Y, A and B:

最後に,最初のセクションで論じた ゆゆしき順序不適合が含まれた例について考えましょう.

このケースでは 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

However, it is impossible to compute the linearization for a class C that inherits from A and B:

けれども,AとBから継承するCの線形化は導出できません.

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

At this point we cannot merge the lists XYO and YXO, since X is in the tail of YXO whereas Y is in the tail of XYO: therefore there are no good heads and the C3 algorithm stops. Python 2.3 raises an error and refuses to create the class C.

この時点でXがYXOのテールにあり,YもXYOのテールにあるので,XYOとYXOをマージすることができません.良いヘッドがないのでC3アルゴリズムは停止します.Python 2.3はエラーを発生させクラスCの生成を拒否します.