維基百科

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/w/index.php?title=C3线性化&oldid=84213182"