グラフのはなし・その9 - cocoatomo衝動日記〈移行後版〉

今日は Perl や Python のクラスの多重継承で使われているアルゴリズム C3 を紹介します.

多重継承でメソッドを呼び出した場合, 複数の親クラスを持つので今呼び出しているメソッドがどの親に属しているのかを調べなければなりません.
そしてその順序も決めておき, 必ず決まったメソッドが呼ばれるようにしなくてはなりません.

それを実現する C3 アルゴリズムとはどんなものなのでしょうか?

C3 アルゴリズム概要

このページを参考にして解説を行います.
http://www.python.org/download/releases/2.3/mro/

数式で書いてしまえば,

$\mathrm{mro}(C) = [C] + \mathrm{merge}(\mathrm{mro}(P_1),\quad \mathrm{mro}(P_2),\quad \dots,\quad \mathrm{mro}(P_n),\quad [P_1,\quad P_2,\dots,\quad P_n])$

([P1, P2,..., Pn] は C の親クラス)

となります.
[C] は C 1 つからなるリストで, その後ろの "+" はリストの結合です.

右辺で再度 mro 関数が呼び出されていますが, 親クラスを持たないクラス C に対して $\mathrm{mro}(C) = C$ と定義されるので, この計算はどこかで止まります.

merge 関数では引数に入ってきたリストの順序を崩さずに, 新たなリストを作っているので, まさにトポロジカルソートが行われています.

C3 アルゴリズムの動き

具体的な merge 関数の動きを見ていきましょう.

まず, 先頭の引数 $\mathrm{mro}(P_1)$ (実体はリスト) から先頭の元 $P$ を取ってきます.
$P$ が他の引数 $\mathrm{mro}(P_2),\quad\mathrm{mro}(P_3),\dots,\quad\mathrm{mro}(P_n),\quad[P_1,\quad P_2,\dots,\quad P_n]$ のそれぞれの先頭にあるか, それとも含まれないか, をチェックします.
そのチェックが通った場合は $P$ を括り出します. (例はまた後で)
もしそのチェックに通らなければ, $\mathrm{mro}(P_2)$ に対して同じチェックを行います.
全ての引数でチェックが通らなければ $\mathrm{mro}$ 失敗です.

例

言葉だけの説明では分かりづらいので, 具体例を扱っていきましょう. (何度も言ってますが, 具体例を考えるのはすごく重要です.)

クラス: 親クラス
C: B

単純な継承です. すごく簡単だし, わざわざ計算しなくてもすぐに分かりますが, 練習として解いてみましょう.

$\begin{align*}\mathrm{mro}(C) &= [C] + \mathrm{merge}(\mathrm{mro}(B),\quad [B]) \\ &= [C] + \mathrm{merge}([B],\quad [B]) \\ &= [C] + [B] \\ &= [C,\quad B]\end{align*}$

確かに望んだ結果が出てきましたね.

では次はもう少し出てくるクラスを増やしましょう.

クラス: 親クラス
C: B1, B2

単純な多重継承です.

$\begin{align*}\mathrm{mro}(C) &= [C] + \mathrm{merge}(\mathrm{mro}(B_1),\quad \mathrm{mro}(B_2) [B_1,\quad B_2]) \\ &= [C] + \mathrm{merge}([B_1],\quad [B_2],\quad [B_1,\quad B_2]) \\ &= [C] + [B_1] + \mathrm{merge}([],\quad [B_2],\quad [B_2]) \\ &= [C] + [B_1] + [B_2] \\ &= [C] + [B_1,\quad B_2] \\ &= [C,\quad B_1,\quad B_2]\end{align*}$

こんな継承関係を考えてみましょう. これは有名なダイヤモンド継承ですね.

クラス: 親クラス
C: B1, B2
B1: A
B2: A

$\begin{align*}\mathrm{mro}(C) &= [C] + \mathrm{merge}(\mathrm{mro}(B_1),\quad\mathrm{mro}(B_2),\quad[B_1,\quad B_2]) \\ &= [C] + \mathrm{merge}([B_1,\quad A],\quad [B_2,\quad A] ,\quad[B_1,\quad B_2])\\ &= [C] + [B_1] + \mathrm{merge}([A],\quad [B_2,\quad A],\quad [B_2] ) \\ &= [C] + [B_1] + [B_2] + \mathrm{merge}([A],\quad [A],\quad []) \\ &= [C] + [B_1] + [B_2] + [A] \\ &= [C,\quad B_1,\quad B_2,\quad A] \end{align}$

今度はこんな計算になり, 上手く多重継承の先祖クラスの順序を扱えていますね.

4 段目で $A$ ではなく $B_2$ が括り出されているのは, $\mathrm{merge}$ 関数の第 2 引数に $[B_2,\quad A]$ というリストがあり, この順序を守るためです.

では最後に mro に失敗する例を考えてみましょう.

クラス: 親クラス
B1: A
B2: A
C1: B1, B2
C2: B2, B1
D: C1, C2

この継承関係では $C_1$ の親クラスの順序と $C_2$ の親クラスの順序が食い違っているので, きちんと先祖クラスの順序が付けられません.

実際に Python でクラス D を作ろうとすると, 以下のようにエラーが出て作ることができません.

>>> A = object
>>> class B1(A): pass
... 
>>> class B2(A): pass
... 
>>> class C1(B1, B2): pass
... 
>>> class C2(B2, B1): pass
... 
>>> class D(C1, C2): pass
... 
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: Error when calling the metaclass bases
    Cannot create a consistent method resolution
order (MRO) for bases B2, B1

さて $\mathrm{mro}$ で計算してみましょう.

$\begin{align*}\mathrm{mro}(D) &= [D] + \mathrm{merge}(\mathrm{mro}(C_1),\quad \mathrm{mro}(C_2),\quad [C_1,\quad C_2]) \\ &= [D] + \mathrm{merge}([C_1,\quad B_1,\quad B_2,\quad A],\quad [C_2,\quad B_2,\quad B_1,\quad A],\quad [C_1,\quad C_2]) \\ &= [D] + [C_1,\quad C_2] + \mathrm{merge}([B_1,\quad B_2,\quad A],\quad [B_2,\quad B_1,\quad A],\quad [])\end{align*}$

とここまできて困ってしまいました. B1 と B2 の順序をどちらを先としてもうまく $\mathrm{merge}$ できません.
なので $\mathrm{mro}$ の計算は失敗し, ここで終了です.

あとがき

今日はトポロジカルソートが使われている一例として, Python の mro を扱いました.
昨日のトポロジカルソートとのつながりが話せていないので, 次回は Python の mro を実装し, 今までのトポロジカルソートと比べてみます.