C3 선형화

C3 linearization

컴퓨팅에서, "객체 지향 언어, 객체는 클래스의 인스턴스다... 다중 상속과 객체 지향 시스템에서,는 어떤 메카니즘을 사용하면 복수의 superclasses에서 동일한 속성에 대한 서로 다른 정의를 승계하는 분쟁을 해결할를 사용하여야 한다."[1]C3슈퍼 선형화는 알고리즘은 주로는 방법 다중 상속의 앞에서 상속되야 할 순서를 가져오는 데 사용된다.. 즉, C3 슈퍼클래스 선형화의 출력은 결정론적 방법해결 순서(MRO)이다.

C3 슈퍼클래스 선형화는 "3가지 특성과 일치한다"[1]는 이유로 C3라고 불린다.

  • 일관된 확장 우선 순위 그래프,
  • 지역 우선 순위 보존
  • 단일성 기준 적합.

1996년 OOPSLA 회의에서 "딜런을 위한 단조로운 슈퍼클래스 선형화"[1]라는 제목의 논문에서 처음 발표되었다. 강화 제안에 따라 2012년[2] 1월 오픈 딜런 구현에 맞춰 개조됐다.[3] Python 2.3([4][5]이상 버전), Raku,[6]Parrot,[7] Solidity, PGF/TikZ의 Object-Oriented Programming 모듈에서 메서드 해상도의 기본 알고리즘으로 선택되었다.[8] 버전 5.10.0으로 시작하는 Perl 5의 코어에 있는 대체 비기본 MRO로도 이용할 수 있다.[9] 이전 버전의 Perl 5에 대한 확장 구현 이름 지정 Class::C3 CPAN에 존재한다.[10]

파이썬의 귀도 판 로섬은 C3 슈퍼클래스 선형화를 다음과 같이 요약하고 있다.[11]

기본적으로 C3의 이면에 있는 아이디어는 상속관계로 부과되는 모든 순서 규칙을 복잡한 계급 계층 구조로 적으면 알고리즘이 그 모두를 만족시키는 클래스의 단조로운 순서를 결정한다는 것이다. 이러한 순서를 결정할 수 없으면 알고리즘이 실패한다.

설명

클래스의 C3 슈퍼클래스 선형화는 클래스의 합과 클래스의 부모의 선형화와 학부모 자체의 목록을 합친 것이다. 병합 프로세스의 마지막 주장인 부모 목록은 직접 부모 클래스의 로컬 우선 순위 순서를 보존한다.

부모의 선형화와 부모목록의 병합을 위해서는 어떤 리스트의 꼬리 부분(첫 번째를 제외한 리스트의 모든 요소)에 나타나지 않는 리스트의 첫 번째 헤드를 선택한다. 좋은 머리는 동시에 여러 목록의 첫 번째 요소로 나타날 수 있지만, 다른 곳에서는 나타나는 것이 금지되어 있다는 점에 유의한다. 선택한 요소가 헤드로 표시되는 모든 목록에서 제거되고 출력 목록에 추가된다. 출력 목록을 확장하기 위해 좋은 헤드를 선택하고 제거하는 과정은 나머지 목록이 모두 소진될 때까지 반복된다. 만약 어느 시점에서 좋은 헤드를 선택할 수 없다면, 나머지 모든 리스트의 헤드가 리스트의 한 꼬리에 나타나기 때문에, 병합은 상속 계층의 종속성 순서가 일관되지 않고 원래 클래스의 선형화가 존재하지 않기 때문에 계산이 불가능하다.

클래스의 선형화 계산에 대한 순진한 분할 및 정복 접근방식은 알고리즘을 반복적으로 호출하여 병합 서브루틴에 대한 상위 클래스의 선형화를 찾을 수 있다. 그러나, 이것은 순환 계급 계층 구조에서 무한히 반복적인 재귀 현상을 야기할 것이다. 그러한 주기를 탐지하고 무한 재귀(그리고 이전 계산의 결과를 최적화로 재사용하기 위해)를 깨기 위해, 재귀 호출은 캐시나 메모화를 통해 이전 인수의 재입력으로부터 보호되어야 한다.

이 알고리즘은 위상학적 순서를 찾는 것과 비슷하다.

예

주어진

C3 선형화 예제에 대한 종속성 그래프.
 계급 O  계급 A 연장하다 O  계급 B 연장하다 O  계급 C 연장하다 O  계급 D 연장하다 O  계급 E 연장하다 O  계급 K1 연장하다 C, A, B  계급 K3 연장하다 A, D  계급 K2 연장하다 B, D, E  계급 Z 연장하다 K1, K3, K2

Z의 선형화는 다음과 같이 계산된다. 

 L(O)  := [O]                                                // O의 선형화는 사소한 것으로 싱글톤 리스트 [O]이다. 왜냐하면 O는 부모가 없기 때문이다.    L(A)  := [A] + 합병하다(L(O), [O])                             // A의 선형화는 A와 더불어 부모들의 선형화와 부모들의 목록을 합친 것이다...         = [A] + 합병하다([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] + 합병하다(L(C), L(B), L(A), [C, B, A])          // 먼저 K1의 부모, L(C), L(B), L(A)의 선형화를 찾아 부모 목록[C, B, A]과 병합한다.         = [K1] + 합병하다([C, O], [B, O], [A, O], [C, B, A])    // 클래스 C는 첫 번째 및 마지막 목록의 수장으로만 표시되므로 첫 번째 병합 단계의 좋은 후보임         = [K1, C] + 합병하다([O], [B, O], [A, O], [B, A])       // O등급은 목록 2와 3의 꼬리 부분에도 나타나기 때문에 다음 합병 단계에는 적합하지 않지만, B등급은 좋은 후보군이다.         = [K1, C, B] + 합병하다([O], [O], [A, O], [A])          // A등급이 좋은 후보군; O등급은 여전히 3등급의 꼬리 부분에 나타난다.         = [K1, C, B, A] + 합병하다([O], [O], [O])               // 마지막으로, O등급이 유효한 후보군. 이 후보군 역시 남은 리스트를 모두 소진한다.         = [K1, C, B, A, O]    L(K3) := [K3] + 합병하다(L(A), L(D), [A, D])         = [K3] + 합병하다([A, O], [D, O], [A, D])               // A 선택         = [K3, A] + 합병하다([O], [D, O], [D])                  // O 실패, D 선택         = [K3, A, D] + 합병하다([O], [O])                       // O 선택         = [K3, A, D, O]    L(K2) := [K2] + 합병하다(L(B), L(D), L(E), [B, D, E])         = [K2] + 합병하다([B, O], [D, O], [E, O], [B, D, E])    // B 선택         = [K2, B] + 합병하다([O], [D, O], [E, O], [D, E])       // O 실패, D 선택         = [K2, B, D] + 합병하다([O], [O], [E, O], [E])          // O 실패, E 선택         = [K2, B, D, E] + 합병하다([O], [O], [O])               // O 선택         = [K2, B, D, E, O]    L(Z)  := [Z] + 합병하다(L(K1), L(K3), L(K2), [K1, K3, K2])         = [Z] + 합병하다([K1, C, B, A, O], [K3, A, D, O], [K2, B, D, E, O], [K1, K3, K2])    // K1 선택         = [Z, K1] + 합병하다([C, B, A, O], [K3, A, D, O], [K2, B, D, E, O], [K3, K2])        // C 선택         = [Z, K1, C] + 합병하다([B, A, O], [K3, A, D, O], [K2, B, D, E, O], [K3, K2])        // 실패 B, 실패 A, K3 선택         = [Z, K1, C, K3] + 합병하다([B, A, O], [A, D, O], [K2, B, D, E, O], [K2])            // B 실패, B 선택         = [Z, K1, C, K3, A] + 합병하다([B, O], [D, O], [K2, B, D, E, O], [K2])               // 실패 B, 실패 D, K2 선택         = [Z, K1, C, K3, A, K2] + 합병하다([B, O], [D, O], [B, D, E, O])                     // B 선택         = [Z, K1, C, K3, A, K2, B] + 합병하다([O], [D, O], [D, E, O])                        // O 실패, D 선택         = [Z, K1, C, K3, A, K2, B, D] + 합병하다([O], [O], [E, O])                           // O 실패, E 선택         = [Z, K1, C, K3, A, K2, B, D, E] + 합병하다([O], [O], [O])                           // O 선택         = [Z, K1, C, K3, A, K2, B, D, E, O]                                               // 완료

Python 3에서 예시된 예

첫째, 예를 들어, 개체들을 이름별로 짧게 표현할 수 있는 메타클라스. <class '__main__.A'>: 

계급 유형(타자를 치다):     반항하다 __repr___(cls):         돌아오다 cls.__name__  계급 O(반대하다, 메타클라스=유형): 통과하다

그런 다음 상속 트리를 만든다. 

계급 A(O): 통과하다  계급 B(O): 통과하다  계급 C(O): 통과하다  계급 D(O): 통과하다  계급 E(O): 통과하다  계급 K1(C, A, B): 통과하다  계급 K3(A, D): 통과하다  계급 K2(B, D, E): 통과하다  계급 Z(K1, K3, K2): 통과하다

그리고 이제: 

>>> Z.mro() [Z, K1, C, K3, A, K2, B, D, E, O, <클래스 '객체']

라쿠에서 입증된 예

Raku는 기본적으로 클래스에 C3 선형화를 사용한다. 

클래스 A {} 클래스 B {} 클래스 C {} 클래스 D {} 클래스 E {} 클래스 K1은 C이고 A는 {} 클래스 K3, A는 {} 클래스 K2는 D는 E {} 클래스 Z는 K1이고 K3은 K2는 Z라고 한다.^mro; # 출력: (Z) (K1) (C) (K3) (A2) (B) (E) (Any) (Mu))

(더) Any 그리고 Mu 모든 Raku 객체가 상속되는 유형)

참조

  1. ^ a b c Kim Barrett, Bob Cassels, Paul Haahr, David A. Moon, Keith Playford, P. Tucker Withington (1996-06-28). "A Monotonic Superclass Linearization for Dylan". OOPSLA '96 Conference Proceedings. ACM Press. pp. 69–82. CiteSeerX 10.1.1.19.3910. doi:10.1145/236337.236343. ISBN 0-89791-788-X.{{cite conference}}: CS1 maint : 복수이름 : 작성자 목록(링크)
  2. ^ opendylan.org의 뉴스 항목
  3. ^ 딜런 강화 제안 3: C3 슈퍼클래스 선형화
  4. ^ Python 2.3의 C3 MRO 사용
  5. ^ Python을 이용한 C3 선형화의 실용화를 위한 자습서
  6. ^ Perl 6의 C3 MRO 사용
  7. ^ "Parrot uses C3 MRO". Archived from the original on 2007-02-08. Retrieved 2006-12-06.
  8. ^ Tantau, Till (August 29, 2015). The TikZ & PGF Manual (PDF) (3.0.1a ed.). p. 956. Retrieved August 14, 2017.
  9. ^ Perl 5.10 이상에서 C3 MRO 사용 가능
  10. ^ CPAN의 C3 MRO에 대한 Perl 5 확장
  11. ^ van Rossum, Guido (23 June 2010). "Method Resolution Order". The History of Python. Retrieved 18 January 2018.