🦔

論文から学ぶ C3 Linearization

2021/05/10に公開

C3 Linearization とは

オブジェクト指向言語では、クラスメンバ (フィールドやメソッド) のアクセスのために、クラスを特定の順序でたどる必要があります。C++, Python など、多重継承を持つような言語においては、その順序には複数の選び方があり、えてして複雑になります。この順序 (または順序決定アルゴリズム) を一般的には method resoluton order (メソッド解決順序; MRO) と呼びます。

C3 Linearization (以下、C3) はこのような MRO の一つで、元 Apple の Barrett らにより国際会議 OOPSLA '96 で発表されました。C3 は今でも Python などいくつかの言語で使用されています。

C3 のアルゴリズム自体はシンプルで、Wikipedia や Python のドキュメントにわかりやすく書かれています。しかし、何故そのようなアルゴリズムが導かれたのかについては、あまり記述がありません。この記事では、原論文を参考にその理由を概説します。

参考文献

原論文: K. Barrett et al. A Monotonic Superclass Linearization for Dylan. OOPSLA '96.
Python ドキュメント 3.9.4 - Python チュートリアル - 9. クラス - 9.5.1. 多重継承: https://docs.python.org/ja/3/tutorial/classes.html#multiple-inheritance
Michele Simionato. The Python 2.3 Method Resolution Order: https://www.python.org/download/releases/2.3/mro/
Wikipedia: C3 Linearization: https://en.wikipedia.org/wiki/C3_linearization (日本語記事なし)

本記事で示す例のほとんどは、上記参考文献を参考にしたものです。

記法

ソースコードは Python を使用します。

クラスの継承関係を継承グラフで表現します。子クラスから親クラスへと矢印を引き、継承関係を表現します。また、特筆しない限り、多重継承において、コード上の指定順序と、グラフ上のクラスの左右順が一致しているものとします。

つまり、次のソースコード

sample.py

class D:
    pass

class B(D):
    pass

class C(D):
    pass

class A(B, C):
    pass

に対する継承グラフは次のようになります。A は B を先に継承しているので、グラフにおいて B は C より左にあります。

C3 が満たす条件

C3 は以下の3つの条件 (Condition) を満たすように線形化を行うアルゴリズムであることからそう呼ばれます。以下、precedence を 優先度 と呼びます。

[C-1] Local precedence order (ローカル優先度) を保存する。
[C-2] Monotonicity、つまり線形化に関する 単調性 を満たす。
[C-3] 継承グラフから導かれる extended precedence graph (拡張優先度グラフ; EPG) が引き起こす制約に対して consistent である。

あるクラスが定義されようとするときに、上記の条件を満たす C3 線形化が存在すればクラスは定義できます。存在しない場合はクラス定義は失敗します。
以下、クラス $C$ の C3 による線形化の結果をリスト $L(C)$ で表します。リストの先頭に近いほど、クラスメンバの探索における優先度が高いことを意味します。

では、上の3つの条件のそれぞれが、線形化にあたってどのような制約を引き起こすかを見ていきます。

[C-0] 継承関係による制約

当たり前過ぎて、上の3条件には含まれていませんが、子クラスは親クラスより先に探索されるという制約があります。例えば:

class A:
    pass

class B:
    pass

class C(A, B):
    pass

という (多重) 継承がある場合は、 $C$ は $A$ および $B$ より先に検索されます。この制約は継承グラフにおいてすでに黒の矢印で表現されています。

なお、この制約は $A$ と $B$ の探索順序については何も言っておらず、それについては [C-1] で制約されます。

[C-1] ローカル優先度による制約

これは、あるクラスが多重継承している場合、その多重継承の順番と矛盾しないように線形化されるべき、という制約です。例えば:

class A:
    pass

class B:
    pass

class C:
    pass

class D(B, C):
    pass

class E(A, D):
    pass

という例では、クラス $E$ は $A,D$ の順で多重継承しているので、 $L(E)$ において、 $A$ は $D$ より先に探索される必要があります。 $A$ と $D$ の間に他のクラスが入っても構いませんが、逆順になるのは許されません。継承グラフに入っているすべての多重継承についてこれが要求されます。

[C-1] による制約を青い破線で追加した継承グラフは次のようになります:

上記制約を満たす線形化は一意に決まります: $L(E) = [E, A, D, B, C]$ .

[C-2] 単調性

クラス $A$ が $B$ および $C$ の子クラスである (class A(B, C)) とします。単調性とは $L(A)$ が $L(B)$ および $L(C)$ の拡張 (＝それらと矛盾しない順序) になっているべき、という制約です。

これは、例えば $L(B) = [B, D], L(C) = [C, D]$ であるときに、 $L(A) = [A, B, C, D]$ または $L(A) = [A, C, B, D]$ となっているのは OK という意味です。 $B\cdot D$ 間および $C\cdot D$ 間の順序は保存されています。一方で、 $L(A) = [A, B, D, C]$ は NG となります。

これにより、継承を利用するプログラマにとっては、クラスを継承するときの挙動が予測しやすくなります。また、線形化の実装者にとっては、 $L(A)$ を計算する際には $L(B)$ および $L(C)$ から再帰的に作ればいいので容易に実装できます。

なお、これを満たさない線形化の例 (つまり、 $L(B),L(C)$ と矛盾する形で $L(A)$ が構成できる例) について論文に載っていますが、複雑なので説明は省略します。

ここまでで、線形化に重要な制約は概ね記述できていますが、これだけでは線形化が一意に決まらないケースがあります。それを解決するために次の制約を設けます。

[C-3] 拡張優先度グラフとの整合性

クラスの継承グラフにここまで説明した制約を追加した、探索優先度に関するグラフを、原論文では優先度グラフ (precedence graph) と呼んでいます。ここではさらに制約を追加して拡張優先度グラフというものを考え、それに矛盾しないような線形化を生成する方法を考えます。

ここで導入する制約は、[C-1] のローカル優先度制約を先祖クラス側に伝播させていったようなものです。この制約は互いに先祖-子孫関係にないクラスたちに導入されます。

次の優先度グラフを考えます:

なお、class B(F, D) および class C(F, E) の順で継承しているとします。

この段階では、クラス $D$ と $E$ には明示的な制約はありませんが、[C-3] により $D\to E$ という制約が追加されます。まず、 $D,E$ が合流するもっとも上にあるクラスを考えることができます。この場合 $A$ になります。 $A$ のローカル優先度による制約は $B\to C$ です。ここで $D$ の子孫が $B$ 、 $E$ の子孫が $C$ になるので、この優先度を伝播させて $D\to E$ なる制約を導入します。

他にも該当するクラスの組があれば制約を追加していきます。上のグラフに追加制約を赤の点線で追加したのが次の図です (注: $C$ の継承順序が逆になってしまっています):

なお、この制約は線形化アルゴリズムにおいて条件を満たすクラスが2つ以上あるときに、より左のリストにあるクラスを優先することよって実現されます。

アルゴリズム

Wikipedia の記事がわかりやすいので見てもらうといいです。簡単に説明すると、[C-0], [C-1], [C-2] をもとに制約を作って、複数の制約を マージ して求める線形化を作ります。マージ手続きにおいて、ある条件を満たすノードが複数選択できる場面では、[C-3] にしたがって最左のクラスを選択します。

クラス $C$ がクラス $C_1,\dots,C_n$ をこの順で継承しているとき、求める線形化 $L(C)$ は以下のように計算できます:

L(C) = [C] + \text{merge}(L(C_1), \dots, L(C_n), [C_1, \dots, C_n])

ここで、 $\text{merge}(L_1,\dots, L_m)$ は優先度リストたち $L_1,\dots, L_m$ のすべてに矛盾しないような順序をリストとして返す手続きです。そのようなものがない場合は途中で失敗します。

[C-0] により $C$ は先頭に来ます。
[C-1] により $[C_1, \dots, C_n]$ に矛盾しないような線形化が求められます。
[C-2] により $L(C_1), \dots, L(C_n)$ に矛盾しないような線形化が求められます。

[C-3] の適用場面

[C-3] の説明画面に出てきた継承グラフについて $L(A)$ を求めると:

\begin{aligned} L(A) &= [A] + \text{merge}(L(B), L(C), [B, C]) \\ &= [A] + \text{merge}([B, F, D], [C, F, E], [B, C]) \end{aligned}

$\text{merge}$ の部分を計算します。見やすさのため、その途中経過を蓄積する変数を加えた $\text{merge}'$ を使って計算します。 $\text{merge}'(\text{出力結果の蓄積} \mid \text{入力リストたち})$ みたいなイメージです:

\begin{aligned} \text{merge}([B, F, D], [C, F, E], [B, C]) &= \text{merge}'([] \mid [B, F, D], [C, F, E], [B, C]) \\ &= \text{merge}'([B] \mid [F, D], [C, F, E], [C]) \\ &= \text{merge}'([B, C] \mid [F, D], [F, E], []) \\ &= \text{merge}'([B, C, F] \mid [D], [E], []) \\ \end{aligned}

ナイーブなマージ手続きとしては $D, E$ のどちらも選択条件を満たします。しかし、[C-3] を満たすために、もっとも左にある候補、この場合 $D$ 、を選びます。よって:

\begin{aligned} \text{merge}'([B, C, F] \mid [D], [E], []) &= \text{merge}'([B, C, F, D] \mid [], [E], []) \\ &= \text{merge}'([B, C, F, D, E] \mid [], [], []) \\ \end{aligned}

これでマージが完了したので、求める $L(A) = [A, B, C, F, D, E]$ となります。[C-3] の制約を導入したことにより、このアルゴリズムは決定的 (deterministic) になります。

以上です。誤りのご指摘およびコメントを歓迎します。