Линеаризация C3
«В объектно-ориентированных системах с множественным наследованиемдолжен использоваться какой-то механизм для разрешения конфликтов при наследовании разных определений одного и того же свойства.из нескольких суперклассов». [1] Линеаризация суперкласса C3 — это алгоритм, используемый в первую очередь для получения порядка, в котором методы должны наследоваться при наличии множественного наследования . Другими словами, результатом линеаризации суперкласса C3 является детерминированный порядок разрешения метода ( MRO ).
Линеаризация суперкласса C3 называется C3, потому что она «согласуется с тремя свойствами»: [1]
- последовательный расширенный граф приоритетов ,
- сохранение порядка локального приоритета и
- соответствие критерию монотонности.
Впервые он был опубликован на конференции OOPSLA в 1996 году в статье под названием «Монотонная линеаризация суперкласса для Дилана ». [1] Он был адаптирован к реализации Open Dylan в январе 2012 года. [2] после предложения по улучшению. [3] Он был выбран в качестве алгоритма по умолчанию для разрешения методов в Python 2.3 (и новее). [4] [5] Раку , [6] Попугай , [7] Solidity и PGF/TikZ . модуль объектно-ориентированного программирования [8] Он также доступен в качестве альтернативы MRO, отличной от используемой по умолчанию, в ядре Perl 5, начиная с версии 5.10.0. [9] Реализация расширения для более ранних версий Perl 5 под названием Class::C3 существует на CPAN . [10]
из Python Гвидо ван Россум резюмирует линеаризацию суперкласса C3 следующим образом: [11]
По сути, идея C3 заключается в том, что если вы запишете все правила упорядочивания, налагаемые отношениями наследования в сложной иерархии классов, алгоритм определит монотонный порядок классов, который удовлетворяет им всем. Если такой порядок не может быть определен, алгоритм потерпит неудачу.
Описание
[ редактировать ] | Эта статья может сбивать с толку или быть непонятной читателям . ( Апрель 2018 г. ) |
Линеаризация суперкласса 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 , К2 линеаризация 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 ( C ) , L ( B ) , L ( A ) , [ C , A , B ]) // сначала находим линеаризацию родителей K1, L(C), L(B) и L(A), и объединяем их со списком родителей [C, A, B] = [ K1 ] + merge ([ C , O ] , [ B , O ] , [ A , O ] , [ C , A , B ]) // класс C является хорошим кандидатом для первого шага слияния, потому что он появляется только как глава первого и последнего списков = [ K1 , C ] + merge ([ O ] , [ B , O ] , [ A , O ] , [ A , B ]) // класс O не является хорошим кандидатом на следующий шаг слияния, поскольку он также появляется в хвостах списков 2 и 3, класс B тоже не годится; но класс A — хороший кандидат = [ K1 , C , A ] + merge ([ O ] , [ B , O ] , [ O ] , [ B ]) // класс B — хороший кандидат; класс O все еще появляется в конце списка 2 = [ K1 , C , A , B ] + merge ([ O ] , [ O ] , [ O ]) // наконец, класс O является допустимым кандидатом, который также исчерпывает все оставшиеся списки = [ K1 , C , A , B , 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 ] + merge ([ B , O ] , [ D , O ] , [ E , O ] , [ B , D , E ]) // выбираем B = [ K2 , B ] + merge ([ O ] , [ D , O ] , [ E , O ] , [ D , E ]) // неудача O, выберите D = [ K2 , B , D ] + merge ([ O ] , [ O ] , [ E , O ] , [ E ]) // неудача O, выберите E = [ K2 , B , D , E ] + merge ([ O ] , [ O ] , [ O ]) // выберите O = [ K2 , B , D , E , O ] L ( Z ) := [ Z ] + объединить ( L ( K1 ) , L ( K3 ) , L ( K2 ) , [ K1 , K3 , K2 ]) = [ Z ] + объединить ([ K1 , C , A , B , O ] , [ K3 , A , D , O ] , [ K2 , B , D , E , O ] , [ K1 , K3 , K2 ]) // выбираем K1 = [ Z , K1 ] + merge ([ C , A , B , O ] , [ K3 , A , D , O ] , [ K2 , B , D , E , O ] , [ K3 , K2 ]) // выбираем C = [ Z , K1 , C ] + merge ([ A , B , O ] , [ K3 , A , D , O ] , [ K2 , B , D , E , O ] , [ K3 , K2 ]) // неудача A, выберите K3 = [ Z , K1 , C , K3 ] + объединить ([ A , B , O ] , [ A , D , O ] , [ K2 , B , D , E , O ] , [ K2 ]) / / select A = [ Z , K1 , C , K3 , A ] + merge ([ 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 ] + merge ([ O ] , [ D , O ] , [ D , E , O ]) // неудача O, выберите D = [ Z , K1 , C , K3 , A , K2 , B , D ] + merge ([ O ] , [ O ] , [ E , O ]) // неудача O, выберите E = [ Z , K1 , C , K3 , A , K2 , B , D , E ] + merge ([ O ] , [ O ] , [ O ]) // выбираем O = [ Z , K1 , C , K3 , A , K2 , B , D , E , O ] // готово . Пример, продемонстрированный на Python 3
[ редактировать ]Во-первых, метакласс, позволяющий кратко представлять объекты по имени вместо значения REPR класса по умолчанию:
class Type ( type ): def __repr__ ( cls ): # Сделаем так, чтобы repr(O) был "O" вместо "<__main__.O>", # и то же самое для любых подклассов O. return 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 ): пройти И теперь:
>>> З. mro () [Z, K1, C, K3, A, K2, B, D, E, O, <класс 'объект'>] Пример, продемонстрированный в Раку
[ редактировать ]Раку по умолчанию использует линеаризацию C3 для классов:
класс А {} класс Б {} класс С {} класс Д {} класс Е {} класс K1 — это C, это A, это B {} класс K3 — A — D {} класс K2 — это B — это D — это E {} класс Z есть K1 есть K3 есть K2 {} скажи Z .^ mro ; # ВЫХОД: ((Z) (К1) (С) (К3) (А) (К2) (Б) (D) (Е) (Любой) (Мю)) ( Any и Mu являются типами, от которых наследуются все объекты Raku, поэтому Any стоит на месте О)
Ссылки
[ редактировать ]- ^ Jump up to: а б с Ким Барретт, Боб Касселс, Пол Хаар, Дэвид А. Мун, Кейт Плейфорд, П. Такер Витингтон (28 июня 1996 г.). «Монотонная линеаризация суперкласса для Дилана». Материалы конференции OOPSLA '96 . АКМ Пресс . стр. 69–82. CiteSeerX 10.1.1.19.3910 . дои : 10.1145/236337.236343 . ISBN 0-89791-788-Х .
{{cite conference}}: CS1 maint: несколько имен: список авторов ( ссылка ) - ^ Новость на opendylan.org
- ^ Предложение Дилана по улучшению 3: линеаризация суперкласса C3
- ^ Использование C3 MRO в Python 2.3
- ^ Учебное пособие по практическому применению линеаризации C3 с использованием Python.
- ^ Использование C3 MRO в Perl 6.
- ^ «Попугай использует C3 MRO» . Архивировано из оригинала 8 февраля 2007 г. Проверено 6 декабря 2006 г.
- ^ Тантау, Тилль (29 августа 2015 г.). Руководство TikZ и PGF (PDF) (изд. 3.1.9a). п. 1062 . Проверено 15 мая 2021 г.
- ^ C3 MRO доступен в Perl 5.10 и новее.
- ^ Расширение Perl 5 для C3 MRO на CPAN
- ^ ван Россум, Гвидо (23 июня 2010 г.). «Порядок разрешения метода» . История Питона . Проверено 18 января 2018 г.