Loading article…
「多重継承を持つオブジェクト指向システムでは、複数のスーパークラスから同じプロパティの異なる定義を継承する場合、競合を解決するための何らかのメカニズムを使用する必要があります。」[1] C3スーパークラスの線形化は、多重継承がある場合にメソッドを継承する順序を取得するために主に使用されるアルゴリズムです。言い換えると、 C3スーパークラスの線形化の出力は、決定論的なメソッド解決順序（MRO ）です。
C3スーパークラスの線形化は、「3つの特性と一致する」ためC3と呼ばれます。[1]
- 一貫した拡張優先順位グラフ、
- ローカル優先順位の維持、および
- 単調性基準に適合する。
これは、1996年のOOPSLAカンファレンスで「A Monotonic Superclass Linearization for Dylan」と題された論文で初めて発表されました。 [1]これは、機能強化提案を受けて、 2012年1月にOpen Dylan実装に採用されました。 [ 2]これは、Python 2.3（およびそれ以降）、[4] [5] Raku、[6] Parrot、[7] Solidity、およびPGF/TikZのオブジェクト指向プログラミングモジュールでメソッド解決のデフォルトアルゴリズムとして選択されています。[8]また、バージョン5.10.0以降のPerl 5コアでは、代替の非デフォルトMROとしても利用できます。[9] Perl 5の以前のバージョン用の拡張実装は、CPANClass::C3に存在します。[10]
PythonのGuido van RossumはC3スーパークラスの線形化を次のように要約している: [11]
基本的に、C3 の背後にある考え方は、複雑なクラス階層内の継承関係によって課される順序付けルールをすべて書き出すと、アルゴリズムはそれらすべてを満たすクラスの単調な順序付けを決定するというものです。そのような順序付けを決定できない場合、アルゴリズムは失敗します。
説明
クラスの C3 スーパークラスの線形化は、クラスとその親の線形化の一意のマージと親のリスト自体の合計です。マージ プロセスの最後の引数としての親のリストは、直接の親クラスのローカルの優先順位を保持します。
親の線形化と親リストのマージは、リストの末尾 (リストの最初の要素を除くすべての要素) に表示されないリストの最初のヘッドを選択することによって行われます。適切なヘッドは、複数のリストで同時に最初の要素として表示されることがありますが、他の場所に表示することは禁止されていることに注意してください。選択された要素は、ヘッドとして表示されるすべてのリストから削除され、出力リストに追加されます。出力リストを拡張するために適切なヘッドを選択して削除するプロセスは、残りのリストがすべてなくなるまで繰り返されます。ある時点で、残りのすべてのリストのヘッドがリストのいずれかの末尾に表示されるため、適切なヘッドを選択できない場合は、継承階層内の依存関係の順序が一貫していないため、マージを計算できず、元のクラスの線形化は存在しません。
クラスの線形化を計算する単純な分割統治法では、マージ サブルーチンの親クラスの線形化を見つけるためにアルゴリズムを再帰的に呼び出す場合があります。ただし、循環的なクラス階層が存在する場合、この方法では無限ループの再帰が発生します。このようなサイクルを検出し、無限再帰を中断するには (また、最適化として以前の計算結果を再利用するには)、キャッシュまたはメモ化によって、再帰呼び出しが以前の引数の再入から保護される必要があります。
このアルゴリズムは、位相的な順序付けを見つけることに似ています。
例
与えられた
クラス O
クラスAはOを拡張しますクラスBはO を拡張しますクラスCはOを拡張しますクラスD はO を拡張しますクラスEはOを拡張しますクラスK1はC 、A 、Bを拡張しますクラスK3はA 、D を拡張しますクラスK2はB 、D 、Eを拡張しますクラスZ はK1 、K3 、K2を拡張します
Zの線形化は次のように計算される。
L ( O ) := [ O ] // O の線形化は、O には親がないので、当然のことながらシングルトン リスト [O] です。L ( A ) := [ A ] + merge ( L ( O ) , [ O ]) // A の線形化は、A にその親の線形化と親のリストとのマージを加えたものです... = [ A ] + merge ([ O ] , [ O ]) = [ A , O ] // ...これは、A をその単一の親の線形化の先頭に追加するだけです。L ( B ) := [ B , O ] // B、C、D、および E の線形化は、A の場合と同様に計算されます。L ( C ) := [ C , O ] L ( D ) := [ D , O ] L ( E ) := [ E , O ] L ( K1 ) := [ K1 ] + merge ( L ( C ) , L ( B ) , L ( A ) , [ C , A , B ]) // まず、K1 の親である L(C)、L(B)、L(A) の線形化を見つけて、親リスト [C, A, B] とマージします= [ K1 ] + merge ([ C , O ] , [ B , O ] , [ A , O ] , [ C , A , B ]) // クラス C は、最初と最後のリストの先頭としてのみ表示されるため、最初のマージ ステップに適した候補です= [ K1 , C ] + merge ([ O ] , [ B ,
O ] , [ A , O ] , [ A , B ]) // クラス O はリスト 2 と 3 の末尾にも出現するため、次のマージ ステップの適切な候補ではありません。クラス B も適切ではありません。ただし、クラス A は適切な候補です= [ K1 , C , A ] + merge ([ O ] , [ B , O ] , [ O ] , [ B ]) // クラス B は適切な候補です。クラス O はまだリスト 2 の末尾に現れます= [ K1 , C , A , B ] + merge ([ O ] , [ O ] , [ O ]) // 最終的に、クラス O は有効な候補となり、残りのリストもすべて尽きます= [ K1 , C , A , B , O ] L ( K3 ) := [ K3 ] + merge ( L ( A ) , L ( D ) , [ A , D ]) = [ K3 ] + merge ([ A , O ] , [ D , O ] , [ A , D ]) // A を選択= [ K3 , A ] + merge ([ O ] , [ D , O ] , [ D ]) // O は失敗、D を選択= [ K3 , A , D ] + merge ([ O ] , [ O ]) // O を選択= [ K3 , A , D , O ] L ( K2 ) := [
K2 ] + merge ( L ( B ) , L ( D ) , L ( E ) , [ B , D , E ]) = [ K2 ] + merge ([ B , O ] , [ D , O ] , [ E , O ] , [ B , D , E ]) // 選択 B = [ K2 , B ] + merge ([ O ] , [ D , O ] , [ E , O ] , [ D , E ]) // O が失敗、選択 D = [ K2 , B , D ] + merge ([ O ] , [ O ] , [ E , O ] , [ E ]) // O が失敗、選択 E = [ K2 , B , D , E ] + merge ([ O ] , [ O ] , [ O ]) // O = [ K2 , B , D , E , O ] L を選択( Z ) := [ Z ] +マージ( L ( K1 ) , L ( K3 ) , L ( K2 ) , [ K1 , K3 , K2 ]) = [ Z ] +マージ([ K1 , C , A , B , O ] , [ K3 ]
, A , D , O ] , [ K2 , B , D , E , O ] , [ K1 , K3 , K2 ]) // select K1 = [ Z , K1 ] + merge ([ C , A , B , O ] 、[ K3 、A 、D 、O ] 、[ K2 、B 、D 、E 、O ] 、[ K3 ] , K2 ]) // select C = [ Z , K1 , C ] + merge ([ A , B , O ] , [ K3 , A , D , O ] , [ K2 , B , D , E , O ] , [ K3 , K2 ]) // A が失敗、K3 を選択= [ Z , K1 , C , K3 ] + merge ([ A , B 、O ] 、[ A 、D 、O ] , [ K2 , B , D , E , O ] , [ K2 ]) // select A = [ Z , K1 , C , K3 , A ] + merge ([ B , O ] , [ D , O ] , [ K2 、B 、D 、E 、O ] 、[ K2 ])
// B は失敗、D は失敗、K2
= [ Z 、K1 、C 、K3 、A 、K2 ] + merge ([ B 、O ] 、[ D 、O ] 、[ B 、D 、E 、O ])を選択 // B = [ Z 、K1 、C 、K3 、A 、K2 、B ] + merge ([ O ] 、[ D 、O ] 、[ D 、E 、O ])を選択 // O は失敗、D = [ Z 、K1 、C 、K3 、A 、K2 、B 、D ] + merge ([ O ] 、[ O ] 、[ E 、O ])を選択// O は失敗、E = [ Z 、K1 、C 、K3 、A 、K2 、B 、D 、E ] + merge ([ O ] 、[ O ] 、[ O ]) を選択// select O = [ Z 、K1 、C 、K3 、A 、K2 、B 、D 、E 、O ] // 完了。
Python 3での例
まず、デフォルトのクラス REPR 値の代わりに名前によるオブジェクトの短い表現を有効にするメタクラス:
class Type ( type ):
def __repr__ ( cls ):
# repr(O) が "<__main__.O>" ではなく "O" になるようにします。
# O のサブクラスでも同様です。
return cls . __name__
クラス O (オブジェクト、 メタクラス= Type ): 渡す
次に、基本クラスを定義します。
クラス A （O ）： 合格
クラス B （O ）： 合格
クラス C （O ）： 合格
クラス D （O ）： 合格
クラス E （O ）： 合格
次に継承ツリーを構築します。
クラス K1 ( C , A , B ): 合格
クラス K3 （A 、 D ）： 合格
クラス K2 ( B 、 D 、 E ): 合格
クラス Z （K1 、 K3 、 K2 ）： 合格
そして今:
>>> Z . mro ()
[Z、K1、C、K3、A、K2、B、D、E、O、<クラス 'オブジェクト'>]
Rakuで示した例
Raku はデフォルトでクラスに C3 線形化を使用します。
クラス A {}
クラス B {}
クラス C {}
クラス D {}
クラス E {}
クラス K1 は C は A は B {}
クラス K3 は A は D {}
クラス K2 は B は D は E {}
クラス Z は K1 は K3 は K2 {}
Zと言います 。^ mro ; # 出力: ((Z) (K1) (C) (K3) (A) (K2) (B) (D) (E) (Any) (Mu))
(Anyと はMuすべての Raku オブジェクトが継承する型なので、AnyO の代わりになります)
参考文献
- ^ abc Kim Barrett、Bob Cassels、Paul Haahr、David A. Moon、Keith Playford、P. Tucker Withington (1996-06-28)。「Dylan の単調なスーパークラス線形化」。OOPSLA '96カンファレンスプロシーディング。ACMプレス。pp . 69–82。CiteSeerX 10.1.1.19.3910。doi : 10.1145 /236337.236343。ISBN 0-89791-788-X。
{{cite conference}}: CS1 maint: multiple names: authors list (link) - ^ opendylan.org のニュース記事
- ^ Dylan 拡張提案 3: C3 スーパークラスの線形化
- ^ Python 2.3 の C3 MRO の使用
- ^ Python を使用した C3 線形化の実践的応用に関するチュートリアル
- ^ Perl 6 の C3 MRO の使用
- ^ 「Parrot が C3 MRO を使用」。2007 年 2 月 8 日時点のオリジナルよりアーカイブ。2006 年 12 月 6 日閲覧。
- ^ タンタウ、ティル (2015年8月29日)。 TikZ & PGF マニュアル(PDF) (3.1.9a 版)。 p. 1062 . 2021年5月15日閲覧。
- ^ C3 MRO は Perl 5.10 以降で利用可能
- ^ CPAN の C3 MRO 用 Perl 5 拡張
- ^ van Rossum, Guido (2010 年 6 月 23 日). 「メソッド解決順序」. Python の歴史. 2018 年1 月 18 日閲覧。