C3线性化

在计算机科学中,C3算法主要用于确定多重继承时,子类应该继承哪一个父类的方法,即方法解析顺序(Method Resolution Order,MRO)。

C3算法实现了三种重要特性:

  • 保持继承拓扑图的一致性,
  • 保证局部优先原则(比如A继承B和C,C继承B,那么A读取父类方法,应该优先使用C的方法而不是B的方法),
  • 保证单调性原则(即子类不改变父类的方法搜索顺序),

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

描述

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

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


例子

给定

一幅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]                                                // the linearization of O is trivially the singleton list [O], because O has no parents

L(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 linearization

L(B)  := [B, O]                                             // linearizations of B, C, D and E are computed similar to that of 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])          // 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实现

以下为C3算法Python实现的一个例子

def c3MRO(cls):
    if cls is object:
    #讨论假设顶层基类为object,递归终止
        return [object]

    #构造C3-MRO算法的总式,递归开始
    mergeList = [c3MRO(baseCls) for baseCls in cls.__bases__]
    mergeList.append(list(cls.__bases__))
    mro = [cls] + merge(mergeList)
    return mro

def merge(inLists):
    if not inLists:
    #若合并的内容为空,返回空list
    #配合下文的排除空list操作,递归终止
        return []
    
    #遍历要合并的mro
    for mroList in inLists:
        #取头
        head = mroList[0]
        #遍历要合并的mro(与外一层相同),检查尾中是否有头
        ###此处也遍历了被取头的mro,严格地来说不符合标准算法实现
        ###但按照多继承中地基础规则(一个类只能被继承一次),
        ###头不可能在自己地尾中,无影响,若标准实现,反而增加开销
        for cmpList in inLists[inLists.index(mroList) + 1:]:
            if head in cmpList[1:]:
                break
        else:
        #筛选出好头
            nextList = []
            for mergeItem in inLists:
                if head in mergeItem:
                    mergeItem.remove(head)
                if mergeItem:
                #排除空list
                    nextList.append(mergeItem)
            #递归开始
            return [head] + merge(nextList)
    else:
    #无好头,引发类型错误
        raise TypeError

首先,metaclass允许对象通过名字简明表示而不用<class '__main__.A'>:

class Type(type):
    def __repr__(cls):
        return cls.__name__
A = Type('A', (object,), {})

A表示自身通过名字:

>>> A
A

由于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, <type 'object'>]

参考文献

  1. . . ACM Press: 69–82. 1996-06-28 [2018-02-02]. ISBN 0-89791-788-X. doi:10.1145/236337.236343. (原始内容存档于2018-12-14).
  2. . [2018-02-02]. (原始内容存档于2020-08-20).
  3. . [2018-02-02]. (原始内容存档于2020-07-05).
  4. . [2018-02-02]. (原始内容存档于2016-06-17).
  5. . [2018-02-02]. (原始内容存档于2007-02-08).
  6. Tantau, Till. (PDF) 3.0.1a. 2015-08-29: 956 [2017-08-14]. (原始内容存档 (PDF)于2020-08-26).
  7. . [2018-02-02]. (原始内容存档于2013-09-13).
  8. . [2018-02-02]. (原始内容存档于2013-06-06).
  9. van Rossum, Guido. . The History of Python. 2010-06-23 [2018-01-18]. (原始内容存档于2018-02-08).
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.