C3線形化

コンピューティングでは、 C3スーパークラスの線形化は、主に、多重継承が存在する場合にメソッドを継承する順序を取得するために使用されるアルゴリズムです。つまり、C3スーパークラス線形化の出力は、決定論的なメソッド解決順序 （ MRO ）です。

C3スーパークラス線形化は、3つの重要なプロパティをもたらします。

一貫した拡張優先順位グラフ、
ローカル優先順位の保存、および
単調性基準に適合します。

1996年のOOPSLA会議で、「ディランのための単調なスーパークラス線形化」という題名の論文で最初に発表されました。 2012年1月に、拡張提案に従ってOpen Dylanの実装に適合しました。 Python 2.3（およびそれ以降）、Perl 6、Parrot、Solidity、およびPGF / TikZのオブジェクト指向プログラミングモジュールのメソッド解決のデフォルトアルゴリズムとして選択されています。また、バージョン5.10.0以降のPerl 5のコアで、デフォルトではないMROの代替として使用できます。 Class :: C3という名前の以前のバージョンのPerl 5の拡張機能の実装がCPANに存在します。

PythonのGuido Van Rossumは、C3スーパークラスの線形化を次のように要約しています。

基本的に、C3の背後にある考え方は、複雑なクラス階層の継承関係によって課せられたすべての順序付け規則を書き留めた場合、アルゴリズムはそれらすべてを満たすクラスの単調な順序付けを決定するということです。そのような順序を決定できない場合、アルゴリズムは失敗します。

説明

この記事は読者を混乱させたりあいまいにしたりします 。記事の明確化にご協力ください。トークページでこれについての議論があるかもしれません。 （2018年4月） （このテンプレートメッセージを削除する方法とタイミングを学ぶ）

クラスのC3スーパークラス線形化は、クラスの合計に、その親の線形化と親自体のリストの一意のマージを加えたものです。マージプロセスの最後の引数としての親のリストは、直接の親クラスのローカルな優先順位を保持します。

親の線形化と親リストのマージは、リストの末尾（最初を除くリストのすべての要素）に表示されないリストの最初のヘッドを選択することによって行われます。良いヘッドは、同時に複数のリストの最初の要素として表示される場合がありますが、他の場所に表示することは禁止されています。選択した要素は、ヘッドとして表示されるすべてのリストから削除され、出力リストに追加されます。適切なヘッドを選択して削除して出力リストを拡張するプロセスは、残りのリストがすべてなくなるまで繰り返されます。残りのすべてのリストのヘッドがリストのいずれかのテールに表示されるため、ある時点で適切なヘッドを選択できない場合、継承階層の依存関係の一貫性のない順序と元の線形化がないため、マージを計算することは不可能ですクラスが存在します。

クラスの線形化を計算する単純な分割統治アプローチでは、アルゴリズムを再帰的に呼び出して、マージサブルーチンの親クラスの線形化を見つけることができます。ただし、これにより、循環クラス階層が存在する場合、無限ループの再帰が発生します。このようなサイクルを検出し、無限再帰を解除する（および以前の計算の結果を最適化として再利用する）ために、再帰呼び出しはキャッシュまたはメモ化によって以前の引数の再入から保護される必要があります。

例

与えられた

クラスOクラスA拡張OクラスB拡張OクラスC拡張OクラスD拡張OクラスE拡張OクラスK1拡張A、B、CクラスK2拡張D、B、EクラスK3拡張D、AクラスZ拡張K1、K3 、K2

Zの線形化は次のように計算されます

L（O）：= // Oには親が存在しないため、Oの線形化は単純なシングルトンリストですL（A）：= + merge（L（O）、）// Aの線形化はAとAのマージです親のリストを使用した親の線形化... = + merge（、）= // ...単純にAを単一の親の線形化L（B）の先頭に追加します：= // B、C、D、Eの線形化AL（C）と同じように計算されます：= L（D）：= L（E）：= L（K1）：= + merge（L（A）、L（B）、L（C）、）/ /まず、K1の親であるL（A）、L（B）、およびL（C）の線形化を見つけ、それらを親リストとマージします= + merge（、、、）//クラスAは、最初と最後のリストの先頭としてのみ表示されるため、最初のマージステップ= + merge（、、、）//クラスOは、リストの末尾にも表示されるため、次のマージステップには適していません2および3;ただし、クラスBは適切な候補です= + merge（、、、）//クラスCは適切な候補です。クラス3はまだリスト3の末尾に表示されます= = merge（、、）//最後に、クラスOは有効な候補であり、残りのリストもすべて使い果たします= L（K2）：= + merge（L（D）、L （B）、L（E）、）= + merge（、、、）// D = + merge（、、、）を選択// Oに失敗、B = + merge（、、、）を選択// Oに失敗select E = + merge（、、）// O = L（K3）を選択：= + merge（L（D）、L（A）、）= + merge（、、）// D = + merge（、を選択、）// Oに失敗、A = + merge（、）を選択// O = L（Z）：= + merge（L（K1）、L（K2）、L（K3）、）= + merge（、、、）// K1 = + merge（、、、）を選択// Aに失敗、K2 = + merge（、、、）を選択// Aに失敗、Dに失敗、K3 = + merge（、、）に選択//失敗A、select D = + merge（、、）// A = + merge（、、）を選択// B = + merge（、、）を選択// C = + merge（、、）を選択// Oに失敗、選択E = + merge（、、）//選択O = //完了

Python 3で実証された例

最初に、たとえばclass '__main __。A'>の代わりに名前によるオブジェクトの短い表現を可能にするメタクラス：

クラスType（type）：def __repr __（cls）：return cls .__ name__ class O（object、metaclass = Type）：pass

次に、継承ツリーを構築します。

クラスA（O）：クラスB（O）を渡す：クラスC（O）を渡す：クラスD（O）を渡す：クラスE（O）を渡す：クラスK1（A、B、C）を渡す：クラスK2（Dを渡す、B、E）：クラスK3（D、A）を渡す：クラスZ（K1、K2、K3）を渡す：パス

そしていま：

>>> Z.mro（）

Perl 6での例

Perl 6は、デフォルトでクラスにC3線形化を使用します。

クラスA {}クラスB {}クラスC {}クラスD {}クラスE {}クラスK1はA is B is C {}クラスK2はD is B is E {}クラスK3はD is A {}クラスZ is K1 is K2 is K3 {} say Z. ^ mro; ＃出力：（（Z）（K1）（K2）（K3）（D）（A）（B）（C）（E）（任意）（Mu））

（AnyおよびMuは、すべてのPerl 6オブジェクトが継承するタイプです）