跳至內容

C3線性化

本頁使用了標題或全文手工轉換
維基百科，自由的百科全書

在計算機科學中，C3算法主要用在多重繼承中，確定子類應該繼承哪一個父類的方法。換句話說，C3超類線性化的輸出是確定性的方法決定次序（MRO：Method Resolution Order）。

描述

[編輯]

C3算法得名於它的實現符合三種重要性質：一致性擴展優先圖（英語：precedence graph）（EPG）、保留局部優先次序和適合單調性準則[1]。

在1996年的OOPSLA會議上，發表的論文《Dylan的單調超類線性化》[1]，首次提出了C3超類線性化。它在2012年1月被適配到了Open Dylan實現[2]，跟從了一個增進的提議[3]。Python 2.3[4][5]、Raku[6]、Parrot[7]、Solidity和PGF/TikZ（英語：PGF/TikZ）的面向對象語言模塊[8]等，將它選作方法解析的默認算法。Perl 5語言從版本5.10.0起將它作為可選的、非默認的MRO[9]。早期版本Perl 5有稱為Class::C3一個擴展實現曾發布於CPAN[10]。

Python創始人Guido van Rossum這樣總結C3超類線性化：「基本上，在C3背後的想法是，如果你寫下在複雜的類層級中繼承關系所施加的所有次序規則，這個算法將確定出滿足所有這些規則的這些類的一個單調次序。如果不能確定出這樣的次序，這個算法會失敗。」[11]

算法

[編輯]

一個類的C3超類線性化，是這個類加上它的這些父類的線性化和這些父類自身的列表的唯一性歸併的總和。這些父類的列表作為給這個歸併過程的最後實際參數，保持了這些直接父類的局部優先次序。

完成父類的線性化和父類列表的歸併，選擇這些列表的頭部中第一個符合條件者，它不出現在任何這些列表的尾部（一個列表的除了第一個元素的所有元素）之中。注意一個良好頭部，可以同時出現為多個列表的第一個元素，但是禁止它出現在任何其他地方。將選擇的元素從以它作為頭部的所有列表中移除，並將它填加到輸出列表。重複選擇並移除良好頭部並擴展輸出列表的過程，直到所有餘下的列表被竭盡。如果在某一點上，因為所有餘下列表的頭部都出現在某個列表的尾部中，而沒有良好頭部可選，那麼由於在繼承層級中依賴的不一致次序，歸併過程不能計算下去，故而最初類的線性化不存在。

計算一個類的線性化的一種樸素分治法，可以採用遞歸算法來為歸併子例程找到父類的線性化。但是，這將在出現環狀類層級時導致無限循環遞歸。為了檢測這種環並打破無限遞歸，並重新利用前面計算的結果作為一種優化，遞歸調用應當通過緩存或記憶化的方式屏蔽重入以前的實際參數。

這個算法類似於找到拓撲次序。

例子

[編輯]

給定

一個C3線性化的依賴圖例子
 class O
 class A extends O
 class B extends O
 class C extends O
 class D extends O
 class E extends O
 class K1 extends A, B, C
 class K2 extends D, B, E
 class K3 extends D, A
 class Z extends K1, K2, K3

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(A), L(B), L(C), [A, B, C])          // 首先找到K1的父类的线性化L(A)、L(B)和L(C)，接着将它们归并于父类列表[A, B, C]
        = [K1] + merge([A, O], [B, O], [C, O], [A, B, C])    // 类A是第一个归并步骤的良好候选者，因为它只出现为第一个和最后一个列表的头部元素。
        = [K1, A] + merge([O], [B, O], [C, O], [B, C])       // 类O不是第二个归并步骤的良好候选者，因为它还出现在列表2和列表3的尾部中；但是类B是良好候选者
        = [K1, A, B] + merge([O], [O], [C, O], [C])          // 类C是良好候选者；类O仍出现在列表3的尾部中
        = [K1, A, B, C] + merge([O], [O], [O])               // 最后，类O是有效候选者，这还竭尽了所有余下的列表
        = [K1, A, B, C, O]
 
 L(K2) := [K2] + merge(L(D), L(B), L(E), [D, B, E])
        = [K2] + merge([D, O], [B, O], [E, O], [D, B, E])    // 选择D
        = [K2, D] + merge([O], [B, O], [E, O], [B, E])       // 不选O，选择B
        = [K2, D, B] + merge([O], [O], [E, O], [E])          // 不选O，选择E
        = [K2, D, B, E] + merge([O], [O], [O])               // 选择O
        = [K2, D, B, E, O]
 
 L(K3) := [K3] + merge(L(D), L(A), [D, A])
        = [K3] + merge([D, O], [A, O], [D, A])               // 选择D
        = [K3, D] + merge([O], [A, O], [A])                  // 不选O，选择A
        = [K3, D, A] + merge([O], [O])                       // 选择O
        = [K3, D, A, O]
 
 L(Z)  := [Z] + merge(L(K1), L(K2), L(K3), [K1, K2, K3])
        = [Z] + merge([K1, A, B, C, O], [K2, D, B, E, O], [K3, D, A, O], [K1, K2, K3])    // 选择K1
        = [Z, K1] + merge([A, B, C, O], [K2, D, B, E, O], [K3, D, A, O], [K2, K3])        // 不选A，选择K2
        = [Z, K1, K2] + merge([A, B, C, O], [D, B, E, O], [K3, D, A, O], [K3])            // 不选A，不选D，选择K3
        = [Z, K1, K2, K3] + merge([A, B, C, O], [D, B, E, O], [D, A, O])                  // 不选A，选择D
        = [Z, K1, K2, K3, D] + merge([A, B, C, O], [B, E, O], [A, O])                     // 选择A
        = [Z, K1, K2, K3, D, A] + merge([B, C, O], [B, E, O], [O])                        // 选择B
        = [Z, K1, K2, K3, D, A, B] + merge([C, O], [E, O], [O])                           // 选择C
        = [Z, K1, K2, K3, D, A, B, C] + merge([O], [E, O], [O])                           // 不选O，选择E
        = [Z, K1, K2, K3, D, A, B, C, E] + merge([O], [O], [O])                           // 选择O
        = [Z, K1, K2, K3, D, A, B, C, E, O]                                               // 完成

用Python3展示例子

[編輯]

首先，定義一個元類來允許對象通過名字簡明表示： 

class Type(type):
    def __repr__(cls):
        return cls.__name__

class O(object, metaclass=Type): pass

類O通過名字表示自身，而不採用默認表示形式： 

>>> O
O
>>> class X: pass
... 
>>> X
<class '__main__.X'>

下面定義一些基礎類： 

class A(O): pass

class B(O): pass

class C(O): pass

class D(O): pass

class E(O): pass

接着構造這個繼承樹： 

class K1(A, B, C): pass

class K2(D, B, E): pass

class K3(D, A): pass

class Z(K1, K2, K3): pass

然後就可看到結果： 

>>> Z.__mro__
[Z, K1, K2, K3, D, A, B, C, E, O, <class 'object'>]

用Raku展示例子

[編輯]

Raku默認的對類使用C3線性化： 

class A {}
class B {}
class C {}
class D {}
class E {}
class K1 is A is B is C {}
class K2 is D is B is E {}
class K3 is D is A {}
class Z is K1 is K2 is K3 {}
say Z.^mro; # OUTPUT: ((Z) (K1) (K2) (K3) (D) (A) (B) (C) (E) (Any) (Mu))

Any和Mu是所有Raku對象從其繼承的類型。

參考文獻

[編輯]
  1. ^ 1.0 1.1 A Monotonic Superclass Linearization for Dylan. OOPSLA '96 Conference Proceedings. ACM Press: 69–82. 1996-06-28 [2018-02-02]. ISBN 0-89791-788-X. doi:10.1145/236337.236343. （原始內容存檔於2018-12-14）. 
  2. ^ News item on opendylan.org. [2021-12-10]. （原始內容存檔於2020-08-26）. 
  3. ^ Dylan Enhancement Proposal 3: C3 superclass linearization. [2021-12-10]. （原始內容存檔於2017-07-03）. 
  4. ^ Python 2.3's use of C3 MRO. [2018-02-02]. （原始內容存檔於2020-08-20）. 
  5. ^ Tutorial for practical applications of C3 linearization using Python. [2018-02-02]. （原始內容存檔於2020-07-05）. 
  6. ^ Perl 6's use of the C3 MRO. [2018-02-02]. （原始內容存檔於2016-06-17）. 
  7. ^ Parrot uses C3 MRO. [2018-02-02]. （原始內容存檔於2007-02-08）. 
  8. ^ Tantau, Till. The TikZ & PGF Manual (PDF) 3.0.1a. 2015-08-29: 956 [2017-08-14]. （原始內容存檔 (PDF)於2020-08-26）. 
  9. ^ C3 MRO available in Perl 5.10 and newer. [2018-02-02]. （原始內容存檔於2013-09-13）. 
  10. ^ Perl 5 extension for C3 MRO on CPAN. [2018-02-02]. （原始內容存檔於2013-06-06）. 
  11. ^ van Rossum, Guido. Method Resolution Order. The History of Python. 23 June 2010 [18 January 2018]. （原始內容存檔於2018-02-08）. 
取自「https://zh.wikipedia.org/zhwiki/w/index.php?title=C3线性化&oldid=84213182」