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

В вычисление, Линеаризация суперкласса C3 является алгоритм используется в основном для получения порядка, в котором методы должны передаваться по наследству при наличии множественное наследование. Другими словами, выход линеаризации суперкласса C3 является детерминированным Порядок разрешения метода (ТОиР).

Линеаризация суперкласса C3 приводит к трем важным свойствам:

• последовательный расширенный граф приоритета,
• сохранение локального порядка приоритета и
• удовлетворяющий критерию монотонности.

Впервые он был опубликован в 1996 г. OOPSLA конференции, в статье под названием «Монотонная линеаризация суперкласса для Дилан ".^[1] Он был адаптирован к реализации Open Dylan в январе 2012 года.^[2] после предложения по расширению.^[3] Он был выбран в качестве алгоритма по умолчанию для разрешения метода в Python 2.3 (и новее),^[4][5] Раку,^[6] Попугай,^[7] Твердость, и PGF / TikZ Модуль объектно-ориентированного программирования.^[8] Он также доступен в качестве альтернативы, не по умолчанию MRO в ядре Perl 5 начиная с версии 5.10.0.^[9] Реализация расширения для более ранних версий Perl 5 с именем Класс :: C3 существует на CPAN.^[10]

Python Гвидо ван Россум резюмирует линеаризацию суперкласса C3 следующим образом:^[11]

По сути, идея C3 заключается в том, что если вы запишете все правила упорядочения, налагаемые отношениями наследования в сложной иерархии классов, алгоритм определит монотонный порядок классов, который удовлетворяет всем из них. Если такой порядок не может быть определен, алгоритм не сработает.

Описание

Линеаризация суперкласса C3 класса - это сумма класса плюс уникальное слияние линеаризаций его родителей и списка самих родителей. Список родителей в качестве последнего аргумента процесса слияния сохраняет локальный порядок приоритета прямых родительских классов.

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

Наивный разделяй и властвуй подход к вычислению линеаризации класса может вызвать алгоритм рекурсивно, чтобы найти линеаризации родительских классов для подпрограммы слияния. Однако это приведет к бесконечной циклической рекурсии при наличии циклической иерархии классов. Чтобы обнаружить такой цикл и прервать бесконечную рекурсию (и повторно использовать результаты предыдущих вычислений в качестве оптимизации), рекурсивный вызов должен быть защищен от повторный вход предыдущего аргумента с помощью кеша или мемоизация.

Этот алгоритм похож на поиск топологический порядок.

Пример

Данный

График зависимостей для примера линеаризации C3.

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

Пример, продемонстрированный на Python 3

Во-первых, метакласс, позволяющий краткое представление объектов по имени вместо, например, <учебный класс '__главный__.А'>:

учебный класс Тип(тип):    def __repr__(cls):        возвращаться cls.__имя__учебный класс О(объект, метакласс=Тип): проходить

Затем строим дерево наследования.

учебный класс А(О): проходитьучебный класс B(О): проходитьучебный класс C(О): проходитьучебный класс D(О): проходитьучебный класс E(О): проходитьучебный класс K1(А, B, C): проходитьучебный класс K2(D, B, E): проходитьучебный класс K3(D, А): проходитьучебный класс Z(K1, K2, K3): проходить

И сейчас:

>>> Z.братан()[Z, K1, K2, K3, D, A, B, C, E, O, ]

Пример продемонстрирован в Raku

Раку по умолчанию использует линеаризацию C3 для классов:

учебный класс А {}учебный класс B {}учебный класс C {}учебный класс D {}учебный класс E {}учебный класс K1 является А является B является C {}учебный класс K2 является D является B является E {}учебный класс K3 является D является А {}учебный класс Z является K1 является K2 является K3 {}сказать Z.^братан; # ВЫХОД: ((Z) (K1) (K2) (K3) (D) (A) (B) (C) (E) (Any) (Mu))

(в Любой и Му являются типами, от которых наследуются все объекты Raku)

Рекомендации

1. «Монотонная линеаризация суперкласса для Дилана». Материалы конференции OOPSLA '96. ACM Press. 1996-06-28. С. 69–82. CiteSeerX  10.1.1.19.3910. Дои:10.1145/236337.236343. ISBN  0-89791-788-X.
2. Новость на opendylan.org
3. Предложение Дилана по усовершенствованию 3: линеаризация суперкласса C3
4. Использование Python 2.3 C3 MRO
5. Учебник для практического применения линеаризации C3 с использованием Python
6. Использование C3 MRO в Perl 6
7. «Попугай использует C3 MRO». Архивировано из оригинал на 2007-02-08. Получено 2006-12-06.
8. Тантау, Тилль (29 августа 2015 г.). Руководство TikZ и PGF (PDF) (3.0.1a ред.). п. 956. Получено 14 августа, 2017.
9. C3 MRO доступен в Perl 5.10 и новее
10. Расширение Perl 5 для C3 MRO на CPAN
11. ван Россум, Гвидо (23 июня 2010 г.). «Порядок разрешения метода». История Python. Получено 18 января 2018.