计算机科学

首页 > 计算机科学

C3线性化

2018-08-31 10:13:36     所属分类:面向对象的程序设计

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

名字C3指最终线性化的三种重要的属性:

  • 一致扩展前趋图英语precedence graph
  • 本地前趋序的保持,
  • 适于单调标准

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

目录

  • 1 描述
    • 1.1 例子
    • 1.2 例子的Python实现
  • 2 参考文献

描述

一个类的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实现

首先,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. ^ A Monotonic Superclass Linearization for Dylan. OOPSLA '96 Conference Proceedings. ACM Press: 69–82. 1996-06-28. ISBN 0-89791-788-X. doi:10.1145/236337.236343. 
  2. ^ Python 2.3's use of C3 MRO
  3. ^ Tutorial for practical applications of C3 linearization using Python
  4. ^ Perl 6's use of the C3 MRO
  5. ^ Parrot uses C3 MRO
  6. ^ Tantau, Till. The TikZ & PGF Manual (PDF) 3.0.1a. 2015-08-29: 956 [2017-08-14]. 
  7. ^ C3 MRO available in Perl 5.10 and newer
  8. ^ Perl 5 extension for C3 MRO on CPAN
  9. ^ van Rossum, Guido. Method Resolution Order. The History of Python. 2010-06-23 [2018-01-18]. 
版权声明:本文由北城百科网创作,转载请联系管理获取授权,未经容许转载必究。https://www.beichengjiu.com/computerscience/340315.html

显示全文

取消

感谢您的支持,我会继续努力的!

扫码支持
支付宝扫一扫赏金或者微信支付5毛钱,阅读全文

打开微信扫一扫,即可进行阅读全文哦


上一篇:包装库
下一篇:基于类编程
广告
相关推荐
爱淘宝