[科普中国]-C3线性化

C3超类线性化是计算机编程使用的算法用于在多继承时确定继承的方法的顺序（称为"线性化"），也即方法解析顺序（Method Resolution Order，MRO）。

定义名字C3指最终线性化的三种重要的属性：

一致扩展前趋图，

本地前趋序的保持，

适于单调标准

1996年的OOPSLA会议上，论文"A Monotonic Superclass Linearization forDylan"首次提出了C3超类线性化。被Python2.3选作方法解析的默认算法。Perl 6Parrot,,Solidity,PGF/TikZ等面向对象语言。也作为可选的、默认不是MRO的语言如Perl 5从版本5.10.0.早期版本Perl 5的一个扩展实现，称为Class::C3发布于CPAN。1

描述一个类的C3超类线性化是这个类，再加上它的各个父类的线性化与各个父类形成列表的唯一合并的结果。父类列表作为合并过程的最后实参，保持了直接父类的本地前趋序。

各个父类的线性化与各个父类形成列表的合并算法，首先选择不出现在各个列表的尾部（指除了第一个元素外的其他元素）的第一个元素，该元素可能同时出现在多个列表的头部。被选中元素从各个列表中删除并追加到输出列表中。这个选择再删除、追加元素的过程迭代下去直到各个列表被耗尽。如果在某个时候无法选出元素，说明这个类继承体系的依赖序是不一致的，因而无法线性化。2

例子给定

class Oclass A extends Oclass B extends Oclass C extends Oclass D extends Oclass E extends Oclass K1 extends A, B, Cclass K2 extends D, B, Eclass K3 extends D, Aclass Z extends K1, K2, K3Z的线性化计算：

L(O) := [O] // the linearization of O is trivially the singleton list [O], because O has no parentsL(A) := [A] + merge(L(O), [O]) // the linearization of A is A plus the merge of its parents' linearizations with the list of parents... = [A] + merge([O], [O]) = [A, O] // ...which simply prepends A to its single parent's linearizationL(B) := [B, O] // linearizations of B, C, D and E are computed similar to that of AL(C) := [C, O]L(D) := [D, O]L(E) := [E, O]L(K1) := [K1] + merge(L(A), L(B), L(C), [A, B, C]) // first, find the linearizations of K1's parents, L(A), L(B), and L(C), and merge them with the parent list [A, B, C] = [K1] + merge([A, O], [B, O], [C, O], [A, B, C]) // class A is a good candidate for the first merge step, because it only appears as the head of the first and last lists = [K1, A] + merge([O], [B, O], [C, O], [B, C]) // class O is not a good candidate for the next merge step, because it also appears in the tails of list 2 and 3; but class B is a good candidate = [K1, A, B] + merge([O], [O], [C, O], [C]) // class C is a good candidate; class O still appears in the tail of list 3 = [K1, A, B, C] + merge([O], [O], [O]) // finally, class O is a valid candidate, which also exhausts all remaining lists = [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]) // select D = [K2, D] + merge([O], [B, O], [E, O], [B, E]) // fail O, select B = [K2, D, B] + merge([O], [O], [E, O], [E]) // fail O, select E = [K2, D, B, E] + merge([O], [O], [O]) // select O = [K2, D, B, E, O]L(K3) := [K3] + merge(L(D), L(A), [D, A]) = [K3] + merge([D, O], [A, O], [D, A]) // select D = [K3, D] + merge([O], [A, O], [A]) // fail O, select A = [K3, D, A] + merge([O], [O]) // select 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]) // select K1 = [Z, K1] + merge([A, B, C, O], [K2, D, B, E, O], [K3, D, A, O], [K2, K3]) // fail A, select K2 = [Z, K1, K2] + merge([A, B, C, O], [D, B, E, O], [K3, D, A, O], [K3]) // fail A, fail D, select K3 = [Z, K1, K2, K3] + merge([A, B, C, O], [D, B, E, O], [D, A, O]) // fail A, select D = [Z, K1, K2, K3, D] + merge([A, B, C, O], [B, E, O], [A, O]) // select A = [Z, K1, K2, K3, D, A] + merge([B, C, O], [B, E, O], [O]) // select B = [Z, K1, K2, K3, D, A, B] + merge([C, O], [E, O], [O]) // select C = [Z, K1, K2, K3, D, A, B, C] + merge([O], [E, O], [O]) // fail O, select E = [Z, K1, K2, K3, D, A, B, C, E] + merge([O], [O], [O]) // select O = [Z, K1, K2, K3, D, A, B, C, E, O] // done例子的Python实现首先，metaclass允许对象通过名字简明表示而不用2：

class Type(type): def __repr__(cls): return cls.__name__A = Type('A', (object,), {})类A表示自身通过名字：

>>> AA

由于Python 3的metaclass语法改变了，为使例子兼任版本2与3，用metaclass创建对象，如同用type。

A = Type('A', (object,), {})B = Type('B', (object,), {})C = Type('C', (object,), {})D = Type('D', (object,), {})E = Type('E', (object,), {})K1 = Type('K1', (A, B, C), {})K2 = Type('K2', (D, B, E), {})K3 = Type('K3', (D, A), {})Z = Type('Z', (K1, K2, K3), {})等价的Python 2 的类定义是：

class Z(K1, K2, K3): __metaclass__ = Type对于Python 3是

class Z(K1, K2, K3, metaclass=Type): pass最后有：

Z.mro()[Z, K1, K2, K3, D, A, B, C, E, ]本词条内容贡献者为:

王沛 - 副教授、副研究员 - 中国科学院工程热物理研究所