Алгебраические модели иерархий типов для проектирования и рефакторинга

Алгебраические системы предоставляют основу формальных исследований компьютерных программ в различных парадигмах [1-2]. Это относится и к логическому программированию, включая широко распространенные на практике системы продукционного типа [3]. В ряде работ (см. [4] и библиографию в ней) была предложена методология алгебраизации продукционно-логических систем на основе бинарных отношений и решеток. Получены теоретические результаты для обоснования эквивалентных преобразований, верификации и оптимизации таких систем. Решетка с заданным на ней дополнительным продукционным отношением названа LP-структурой (lattice production structure).

Исследования показали применимость данной методологии в различных областях теории программирования. В работе [5] впервые установлено, что отношения обобщения и агрегации типов обладают свойствами продукционно-логического вывода. В результате построен класс LP-структур для моделирования иерархий типов в целях рефакторинга - модернизации кода. В этой модели в LP-структуре из решеточных операций в качестве основной использовалась лишь операция объединения. Данное обстоятельство ограничило возможности теории формализацией единственного метода рефакторинга - поднятия общих атрибутов (общий обзор известных методов содержится в [6, 7]). Статья [8] развивает теорию LP-структур для иерархий типов. В результате «инвертирования» модели [5] получен новый метод рефакторинга. Суть данного метода, не упоминающегося в классическом перечне рефакторингов [6], состоит в замене нескольких атрибутов класса их общим потомком ( совмещение атрибутов ).

Настоящая работа посвящена алгебраической модели, объединяющей функциональность моделей [5] и [8]. Для нового вида LP-структур рассматривается стандартный круг вопросов: логическое замыкание, его архитектура, эквивалентные преобразования, логическая редукция и способ ее построения. Представленные результаты расширяют возможности исследования и модернизации иерархий типов.

Решение родственных задач алгебраическими методами анализа формальных понятий (FCA) представлены в [9], где элементам определенного множества классов предлагается в некотором смысле оптимально назначить наборы атрибутов - элементов другого независимого множества. В соответствии с выбранными назначениями формируется иерархия классов. В постановке, которая рассматривается авторами настоящей работы, в отличие от [9], атрибуты сами относятся к исследуемой иерархии классов (типов), что усложняет задачу и не оставляет возможности непосредственного применения методов FCA.

В разделе 1 работы приводятся необходимые базовые сведения из теории бинарных отношений и математических решеток. Основная часть раздела содержит предварительное обсуждение рассматриваемых задач на конкретных примерах, а также их приложений. Данное обсуждение служит иллюстрацией и отправной точкой для определения LP-структуры в разделе 2, где формулируются основные теоретические результаты. Их доказательства планируются к опубликованию в математическом издании. Тем не менее, ввиду двойственности построенной модели по отношению к рассмотренной в работе [5], общее представление о методике доказательств может быть получено в [5].

В разделе 3 обсуждаются вопросы компьютерной реализации LP-структур на решетках типов, включая оценки вычислительной сложности решаемых задач.

1    Обозначения и решаемые задачи

Необходимые для чтения статьи сведения о решетках содержатся в [10]. Решеткой называется частично упорядоченное множество F , в котором наряду с отношением < («не больше», «содержится») определены также две двуместные операции л («пересечение») и v («объединение»), вычисляющие соответственно точную нижнюю и верхнюю грани любой пары a, b е F . Решетка называется ограниченной, если она содержит общие верхнюю и нижнюю грани - такие два элемента O , I , что O <  a <  I для любого a е F .

Рассмотрим иерархию типов F в объектно-ориентированной программной системе. Между парами типов могут существовать как минимум два вида связей - наследование и агрегация [6].

Отношение наследования порождает на F частичный порядок: если тип b - потомок a (соответственно a - предок b ), то b <  a . Требуется, чтобы для любых a, b е F были определены две «решеточные» операции: пересечение a л b - наибольший общий потомок; объединение a v b - наименьший общий предок a , b .

На решетке F рассмотрим второе, соответствующее агрегации, отношение R : если экземпляр типа a в качестве атрибута содержится в определении типа b , то ( b , a ) е R . Оба отношения (< и R ) имеют общую семантику: в каждом случае, b <  a или( b , a ) е R , тип b получает возможности типа a в виде доступа к его атрибутам. Ясно, что это общее отношение «обладания набором возможностей» (обозначим его <—— ) обязано быть рефлексивным и транзитивным. Обсудим другие свойства введенных отношений.

Пусть для элементов a, bi, b2 е F справедливо b1 < a, b2< a. Тогда по определению решетки [9] имеем b1b2< a. Это естественное для отношения < свойство (согласно [4]) называется v-дистрибутивностью. Посмотрим, что будет означать обладание этим же свойством для отношения <—— . Пусть b1 <—— a и b2 <—— a, то есть каждому типу b1 и b2 доступны возможности типа a. Тогда в силу предполагаемой v-дистрибутивности имеем b1b2 <—— a. Последнее означает, что тип b1b2 также обладает возможностями типа a. С точки зрения проектирования типов это не обязательно. Однако, если более одного типа-наследника (в данном случае - bi и b2) содержат одинаковые атрибуты, то, согласно принципу рефакторинга [6], целесообразно «поднять» общие атрибуты, то есть поместить один такой атрибут в об- щий тип-предок b1b2, после чего каждый b1 и b2 получит возможности а в порядке наследования. В рассмотренной ситуации v-дистрибутивность отношения <—— содержит решение актуальной задачи - устранение дублирования кода.

Указанное свойство исследовано в работе [5]. В частности, показано, что отношение <—— , обладая свойством транзитивности вне зависимости от контекста, не может во всех ситуациях удовлетворять свойству v -дистрибутивности, иначе это приведет к некорректным результатам. Продемонстрируем отмеченное обстоятельство на примерах.

Пример 1 . Для иллюстрации рассмотрим пример: b <— R— а и а <—— а. При v -дистрибутивности <—— выполнялось бы ba <—— а. Согласно принципам объектноориентированного программирования, тип b v а не имеет права что-либо знать о своих наследниках. По этой причине в данной ситуации b v а , являясь общим предком типов а и b , может обладать возможностями типа а лишь в случае, если он совпадает с а (то есть b <  а ). В остальных вариантах соотношение ba <—— а окажется некорректным.

Пример 2. Существуют ситуации, когда выполнение v-дистрибутивности отношения <—— теоретически возможно, однако нецелесообразно с точки зрения качества кода. Пусть при b1 <—R— а, b2 <—R— а элементы b1b2 и а имеют непустое пресечение: (b1b2)a=d^0, причем d< b1b2 и d<а. Если в данном случае допустить (b1b2, а)еR, то окажется, что тип d обладает возможно- стями типа а одновременно по двум линиям, а именно - как его потомок и как потомок типа b1b2, также имеющего возможности а. Недостаток такого кода состоит в его избыточности -разрыв связи d < а (при а # I) не приведет к потере функциональности системы типов.

Пример 3 . Другая подобная ситуация - наличие конфликта. Пусть имеет место ( b₁,a), ( b₂,a), ( b₃,a) е R , причем элементы Ьь b₂, b₃, b₁b₂, b₂b₃ попарно различны и ( b₁b₂)(b₂b₃) = b₂ . Тогда пары ( b₁,a), ( b₂,a) «конфликтуют» с парами ( b₂,a), ( b₃,a) : если в обоих случаях «поднять» атрибуты, то тип b₂ унаследует атрибут типа а одновременно от двух различных предков - b 1 b 2 и b 2 b 3 , что также ухудшит код.

В работе [5] формально описаны ситуации подобных коллизий и построена LP-структура с ограниченным свойством v -дистрибутивности. Данное свойство сохраняется лишь для v -дистрибутивных и так называемых неконфликтных в R троек ( b₁, b₂, a) элементов решетки. Принятая стратегия предполагает отказ от «поднятия» общих атрибутов при наличии описанных ситуаций (невыполнение v -дистрибутивности).

Как известно, в основанных на решетках алгебраических системах операции объединения и пересечения порождают двойственные свойства (например, законы де Моргана). Подобная закономерность имеет место и в стандартных LP-структурах [4], где наряду с v -дистрибутивностью бинарных отношений рассмотрено симметричное свойство - л -дистрибутивность. Выясним, что означает свойство л -дистрибутивности применительно к отношению <—— .

Предположим, что для элементов а₁,а₂,b е F выполнено b <  а₁, b <  а₂ . Тогда по определению решетки справедливо b <  а 1 а 2 . Такое свойство частичного порядка < на решетке называется л -дистрибутивностью [4]. Распространим его на отношение <—— . Пусть b <—— а₁ и b <—— а₂ , то есть тип b обладает возможностями типов а₁ и а₂ . В силу предполагаемой л -дистрибутивности получим b <— R— а₁а₂ . Таким образом, тип b также обладает возможностями типа а 1 а 2 . Как и выше, с точки зрения проектирования типов последнее соотношение обязательным не является. Его семантика такова: если тип имеет два или более различных атрибута, то эти атрибуты можно заменить единственным атрибутом, относящимся к ближайшему общему потомку типов исходных атрибутов. Нетрудно увидеть, что такая реорганизация делает определение типа-контейнера более компактным с сохранением его функциональности.

Данный метод рефакторинга был назван «совмещением атрибутов» [8]. Он применим лишь для иерархий типов с множественным наследованием, однако его актуальность оправдана популярностью языка C++.

Выясним далее вопрос о том, насколько в данной алгебраической модели типов свойство л -дистрибутивности отношения <—— универсально, и не окажутся ли его ограничения двойственными по отношению к описанным выше ограничениям v -дистрибутивности.

Пример 4 . Для иллюстрации рассмотрим случай двойственности по отношению к примеру 1: b <—— а и b <—— b. При л -дистрибутивности отношения <—— должно быть выполнено b <— R— ba. Аналогично исходному примеру 1, тип b не имеет права что-либо знать о своем типе-наследнике b л а . По этой причине тип b , являясь предком типа b л а , может обладать его возможностями лишь в случае b <  а , иначе соотношение b <—— ba окажется некорректным.

Пример 5 . Пусть при b <—— а 1 , b <—— а₂ элементы b и а 1 а₂ имеют объединение b ( a 1 a₂)=d ^ I , причем b < d и а 1 а₂ < d . Если в данном случае допустить ( b, а 1 а₂) g R , то окажется, что тип b обладает возможностями другого типа d одновременно по двум линиям, а именно -и как его потомок, и как контейнер типа а 1 а 2 , также имеющего возможности d в порядке наследования. Недостатки такого кода (подобно примеру 2) заключаются в его избыточности -разрыв связи а 1 а₂ < d не приведет к потере функциональности системы типов.

Пример 6 . Рассмотрим конфликтную ситуацию, двойственную по отношению к примеру 3. Пусть ( b, а 1 ) , ( b, а₂), ( b, а₃) g R , причем элементы а 1 , а₂ , а₃ , а 1 а₂ , а₂а₃ попарно различны и ( а 1 а₂ )( а₂а₃ ) =а₂ . Тогда пары ( b, а 1 ), ( b, а₂) «конфликтуют» с парами ( b, а₂), ( b, а₃) . Этот факт означает, что если в обоих случаях совместить атрибуты (применив свойство л -дистрибутивности), то тип b получит возможности типа а 2 одновременно посредством двух атрибутов - а 1 а 2 и а 2 а 3 , что также ухудшит код.

В работе [8] формально описаны ситуации, в которых отношение <—— не сохраняет свойство л -дистрибутивности, и построена LP-структура с его ограничением. Данное свойство выполняется только для л -дистрибутивных и так называемых неконфликтных в - троек ( b, а 1 , а 2 ) элементов решетки. Принятая стратегия предполагает отказ от «совмещения» общих атрибутов при наличии описанных ситуаций (невыполнение л -дистрибутивности). Теоретически возможны и другие подходы, более тонко учитывающие особенности конкретных систем.

Анализируя примеры 4–6 в сравнении с соответствующими примерами 1–3, нетрудно прийти к выводу о двойственном характере ограничений свойств л -дистрибутивности и v -дистрибутивности отношения <—— , которые необходимы для адекватного моделирования иерархий типов. Отмеченный факт служит подтверждением естественности разрабатываемых алгебраических моделей, и, в частности, вводимых ограничений дистрибутивности.

Заметим, что с помощью LP-структур рассматривается некоторая обобщенная постановка задач «распределения возможностей» между типами. Варианты, когда типы по каким-либо практическим соображениям содержат в виде атрибутов представителей одних и тех же типов с различными идентификаторами, в расчет не принимаются. На практике тип может содержать много атрибутов, но не все они одинаково существенны при построении иерархии. Кроме того, алгебраические модели в большей степени предназначены для автоматизированного рефакторинга, чем автоматического, то есть окончательное решение о конкретных преобразованиях типов остается за программистом.

2    Основные результаты

На основе представленных выше соображений в данном разделе определяется понятие логического бинарного отношения на ограниченной решетке. Оно отражает свойство «обладания набором возможностей» в иерархии типов.

Логическое замыкание произвольного бинарного отношения на решетке предоставляет все такие пары ( b , a ), что в типе b доступны возможности типа a. Решив задачу построения логического замыкания, можно автоматизировать верификацию системы типов. К таким задачам, в частности, относится исследование LP-структуры на наличие циклов. Исходя из предметной области, можно также формулировать правила, которым должна удовлетворять система типов, и контролировать их выполнение. Например, возможна проверка системы на наличие необходимых или отсутствие запрещенных логических связей.

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

Определение 1. Бинарное отношение на решетке называется ограниченно дистрибутивным, если оно ограниченно v -дистрибутивно [5] и ограниченно л -дистрибутивно [8].

Определение 2. Отношение называется логическим, если оно содержит <, транзитивно и ограниченно дистрибутивно. Логическим замыканием R называется наименьшее логическое отношение, содержащее R .

Два отношения R 1 и R 2 , определенные на общей решетке, называются эквивалентными, если их логические замыкания совпадают. Логической редукцией отношения R называется минимальное эквивалентное ему отношение R 0 . При этом не требуется вложения R 0 с R . Можно говорить о некотором отношении R 0 как логической редукции вообще, не относя этот факт к какому-либо другому отношению R . Это означает, что при изъятии любой пары «меньшее» отношение не будет эквивалентно R 0 .

Теорема 1. Для произвольного бинарного отношения R на решетке логическое замыкание существует.

Теорема 2. Пусть R - бинарное отношение на решетке. Тогда каждая из следующих операций на R приводит к эквивалентному отношению:

добавление или исключение пары ( b , a ), если b <  a ;

добавление пары ( b 1 b₂, a) , если тройка ( b 1 ,b₂, a) v -дистрибутивна и неконфликтна в R ;

добавление пары ( b , a 1 a₂) , если тройка ( b , a 1 , a₂) л -дистрибутивна и неконфликтна в R ;

добавление или исключение пары ( b , a ) при наличии пар ( b , c ),( c , a ) e ( R u <), где a , b , c попарно различны.

В [4] и других работах для стандартных структур показано, что логическое замыкание отношения R совпадает с транзитивным замыканием другого отношения R о R , построенного в виде некоторого многообразия над R . Этот факт позволяет свести ряд вопросов, касающихся логических отношений, к соответствующим проблемам транзитивных отношений. В частности, построение логического замыкания или редукции можно осуществить с помощью быстрых алгоритмов (типа Уоршолла) [11]. В рамках модели, основанной на ограниченной дистрибутивности, также удается разделить процесс построения логического замыкания на этапы дистрибутивного и транзитивного замыканий.

Для отношения R на решетке рассмотрим отношение R , построенное последовательным выполнением следующих шагов:

для каждой неконфликтной v -дистрибутивной тройки ( b 1, b₂, a)(b i # b₂) добавить к исходному отношению пару ( b 1 b 2 , a) ;

для каждой неконфликтной л -дистрибутивной тройки ( b , a 1 , a₂)(a 1 # a₂) добавить к исходному отношению пару( b , a 1 a₂) ;

к полученному отношению добавить отношение <.

Заметим, что по теореме 2 отношение R эквивалентно R .

Теорема 3. Логическое замыкание отношения R совпадает с транзитивным замыканием R* соответствующего отношения R.

Изучен вопрос о существовании и построении логической редукции LP-структур на решетках типов. Справедлива следующая теорема.

Теорема 4. Пусть для отношения R построено соответствующее отношение R. Тогда, если для R существует транзитивная редукция R 0 , то отношение R 0 , полученное исключением из R 0 всех пар вида b <  a , представляет собой логическую редукцию исходного отношения R .

3    Вопросы реализации

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

Заметим, что разработка алгоритмов на абстрактных решетках и получение оценок их сложности в общем случае не приносят оптимистичных результатов. Например, популярный вид решетки булеан при количестве атомов n состоит из 2 ⁿ различных элементов, со всеми вытекающими «алгоритмическими последствиями».

Для общих решеток разработаны методы их представления деревьями и битовыми векторами [12]. В частности, булеан может быть представлен множеством битовых векторов размерности n . Каждому атому решетки соответствует вектор с одной единицей в соответствующей позиции и остальными нулями. Вычисление решеточных операций сводится к вычислению побитовых логических операций сложения и умножения над компонентами векторов. Нельзя сказать, что операция над двумя векторами будет выполняться за константное время, поскольку разрядность компьютера (например, 32 или 64) может оказаться недостаточной для представления битового вектора единственным словом памяти. Тем не менее, сложность операции n / 32 или n / 64 приемлема при общем количестве элементов решетки 2 ⁿ .

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

Теорема 5 . Задачи нахождения логического замыкания и логической редукции LP-структуры на решетке типов решаются за полиномиальное время, не превышающее O ( N), где N - общее число элементов решетки.

Заключение

Представленные результаты создают теоретическую основу для автоматизированных исследований иерархий типов в объектно-ориентированных информационных системах, включая эквивалентные преобразования, верификацию и оптимизацию. Они могут быть использованы для практического проектирования или модернизации иерархий типов.