C3-линеаризация

12.12.2020

C3-линеаризация суперкласса (англ. C3 superclass linearization) — алгоритм, используемый преимущественно для получения устойчивой линеаризации иерархии множественного наследования в объектно-ориентированном программировании. Данная линеаризация используется для определения порядка, в котором должны наследоваться методы, что часто в англоязычной литературе обозначается как «MRO» (сокращение от «Method Resolution Order», то есть «порядок разрешения метода»). C3 в названии указывает на три главные особенности итоговой линеаризации: устойчивый и расширяющийся (по старшинству) граф, сохранение локального порядка старшинства, а также монотонность. Данная теория впервые была представлена в 1996 году в рамках конференции OOPSLA, в документе, озаглавленном «Монотонная линеаризация суперкласса для языка Dylan». Впоследствии данный алгоритм был выбран как алгоритм по умолчанию для разрешения методов в языке программирования Python 2.3 (и последующих версиях), Perl 6 и виртуальной машине Parrot. Он также доступен в виде альтернативы (не являясь MRO по умолчанию) в ядре Perl 5, начиная с версии 5.10.0. Расширенная реализация для более ранних версий Perl 5 носит название Class::C3 и существует в CPAN.

Пример

Для

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] // линеаризация O тривиальна, это список из одного элемента [O], потому что у O нет родителей L(A) := [A] + merge(L(O), [O]) // линеаризация A это A плюс соединение линеаризаций родителей А и родителей А = [A] + merge([O], [O]) = [A, O] L(B) := [B, O] // линеаризация B, C, D и E 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]) // вначале найдем линеаризации родителей K1: L(A), L(B) и L(C); и соединим их со списком из родителей [A, B, C] = [K1] + merge([A, O], [B, O], [C, O], [A, B, C]) // класс A подходит для первого шага merge, потому что он появляется только в начале всех списков = [K1, A] + merge([O], [B, O], [C, O], [B, C]) // класс O не подходит, так как он содержится в хвостах списков 2 и 3, но... = [K1, A, B] + merge([O], [O], [C, O], [C]) = [K1, A, B, C] + merge([O], [O], [O]) // в конце концов, класс O остается единственным и последним кандидатом = [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]) // выбрать D = [K2, D] + merge([O], [B, O], [E, O], [B, E]) // O не подходит, выбрать B = [K2, D, B] + merge([O], [O], [E, O], [E]) // O не подходит, выбрать E = [K2, D, B, E] + merge([O], [O], [O]) // выбрать O = [K2, D, B, E, O] L(K3) := [K3] + merge(L(D), L(A), [D, A]) = [K3] + merge([D, O], [A, O], [D, A]) = [K3, D] + merge([O], [A, O], [A]) = [K3, D, A] + merge([O], [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]) // выбрать K1 = [Z, K1] + merge([A, B, C, O], [K2, D, B, E, O], [K3, D, A, O], [K2, K3]) // A не подходит, выбрать K2 = [Z, K1, K2] + merge([A, B, C, O], [D, B, E, O], [K3, D, A, O], [K3]) // A не подходит, D не подходит, выбрать K3 = [Z, K1, K2, K3] + merge([A, B, C, O], [D, B, E, O], [D, A, O]) // A не подходит, выбрать D = [Z, K1, K2, K3, D] + merge([A, B, C, O], [B, E, O], [A, O]) // выбрать A = [Z, K1, K2, K3, D, A] + merge([B, C, O], [B, E, O], [O]) // выбрать B = [Z, K1, K2, K3, D, A, B] + merge([C, O], [E, O], [O]) // выбрать C = [Z, K1, K2, K3, D, A, B, C] + merge([O], [E, O], [O]) // O не подходит, выбрать E = [Z, K1, K2, K3, D, A, B, C, E] + merge([O], [O], [O]) // выбрать O = [Z, K1, K2, K3, D, A, B, C, E, O] // ответ

Обозначения:

L(Class) - линеаризация класса Class [A,B,C] - список из трех элементов, где голова это A, а хвост [B,C] merge - слияние списков

Функция merge осуществляет слияние списков таким образом, чтобы каждый элемент встречался в результате ровно один раз, этим она похожа на слияние множеств, но тут важен порядок следования элементов в списке. Функция merge работает следующим образом - она перебирает списки-аргументы по порядку упоминания (слева направо), выбирая первый элемент, который может быть первым в нескольких списках, но нигде не упоминается вторым и далее, и перемещает его в список-результат, исключая из списков-аргументов, повторяя эту процедуру несколько раз, пока все элементы не переместятся из списков-аргументов в список-результат. Если на каком-то этапе возникает ситуация, что нельзя выбрать элемент-кандидат, удовлетворяющий указанному условию, т.е. если во всех списках-аргументах первые элементы встречаются в других списках-аргументах не первыми, итоговый список не создаётся.


Имя:*
E-Mail:
Комментарий: