C3线性化

在计算机科学中，C3算法主要用在多重继承中，确定子类应该继承哪一个父类的方法。换句话说，C3超类线性化的输出是确定性的方法解析次序（MRO：Method Resolution Order）。

描述
C3算法得名于它的实现一致于三种重要性质：扩展（EPG）、局部优先次序和单调性。

在1996年的OOPSLA会议上，发表的论文《Dylan的单调超类线性化》，首次提出了C3超类线性化。它在2012年1月被适配到了Open Dylan实现，跟从了一个增进的提议。Python 2.3、Raku、Parrot、Solidity和的面向对象语言模块等，将它选作方法解析的默认算法。Perl 5语言从版本5.10.0起将它作为可选的、非默认的MRO。早期版本Perl 5有称为Class::C3一个扩展实现曾发布于CPAN。

Python创始人Guido van Rossum这样总结C3超类线性化：“基本上，在C3背后的想法是，如果你写下在复杂的类层级中继承关系所施加的所有次序规则，这个算法将确定出满足所有这些规则的这些类的一个单调次序。如果不能确定出这样的次序，这个算法会失败。”

算法 
一个类的C3超类线性化，是这个类加上它的这些父类的线性化和这些父类自身的列表的唯一性归并的总和。这些父类的列表作为给这个归并过程的最后实际参数，保持了这些直接父类的局部优先次序。

完成父类的线性化和父类列表的归并，选择这些列表的头部中第一个符合条件者，它不出现在任何这些列表的尾部（一个列表的除了第一个元素的所有元素）之中。注意一个良好头部，可以同时出现为多个列表的第一个元素，但是禁止它出现在任何其他地方。将选择的元素从以它作为头部的所有列表中移除，并将它填加到输出列表。重复选择并移除良好头部并扩展输出列表的过程，直到所有余下的列表被竭尽。如果在某一点上，因为所有余下列表的头部都出现在某个列表的尾部中，而没有良好头部可选，那么由于在继承层级中依赖的不一致次序，归并过程不能计算下去，故而最初类的线性化不存在。

计算一个类的线性化的一种朴素分治法，可以采用递归算法来为归并子例程找到父类的线性化。但是，这将在出现环状类层级时导致无限循环递归。为了检测这种环并打破无限递归，并重新利用前面计算的结果作为一种优化，递归调用应当通过缓存或记忆化的方式屏蔽重入以前的实际参数。

这个算法类似于找到拓扑次序。

例子
给定

用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对象从其继承的类型。

参考文献 

面向对象的程序设计
程式語言翻譯