Объектно-ориентированное программирование в ограничениях: новый подход на основе декларативных языков моделирования данных

Семенов В.А., Ильин Д.В., Морозов С.В., Сидяка О.В.

Назад Содержание Вперёд

3. Сравнительный анализ подходов к CLP

3.1. Краткий обзор технологий программирования в ограничениях

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

Тем не менее, по-видимому, не претерпели серьезных изменений четыре фундаментальных принципа, а именно: декларативное моделирование ограничений, локальное распространение результатов, эффективный глобальный поиск решений и специализация языковых и математических средств. Начиная со Sketchpad [20], ALICE [21], ThingLab [22], эти принципы успешно эксплуатируются и в современных реализациях.

Принцип декларативности [23] нашел конструктивное воплощение во многих языках функционального и логического программирования ( включая Lisp и Prolog), допускающих описание и решение некоторых задач в ограничениях. Со временем понимание того, что функциональная рекурсия и логический вывод являются лишь отдельными элементами более общей стратегии разрешения ограничений для сложно структурированных неизвестных переменных, привело к появлению CostraintLisp, Prolog III [24] и CHIP [25].

Язык реляционных баз данных SQL [26], предусматривающий развитые декларативные конструкции для описания запросов и ограничений целостности, также несет в себе черты языка программирования в ограничениях. Связь с технологиями управления базами данных становится еще более очевидной при анализе относительно новой концепции Constraint Database (CDВ) [27], которая, расширяя реляционную, дедуктивную и объектно-ориентированную модели, устанавливает непосредственную связь между типами данных и ограничениями, которые их предопределяют.

Принцип локального распространения (в англоязычной литературе соответствующий терминам constraint propagation или consistency inference) [28] имеет долгую историю и многочисленные приложения, в частности, в области интеллектуализации графических интерфейсов пользователя. Спекулятивные попытки предвосхитить результаты поиска путем локальных и циклических уточнений частных решений оказались довольно плодотворными при решении больших систем уравнений и неравенств.

Многочисленные “радужные” воплощения принципа привели к созданию целой палитры методов: Red (красный), Orange (оранжевый), Yellow (желтый), Green (зеленый), Blue (синий), DeltaBlue (инкрементально-синий), SkyBlue (небесно-синий), UltraViolet (ультрафиолет), Purple (фиолетовый), DeepPurple (пурпурный), Indigo (темно-синий) [29–31]. Некоторые из них обеспечивают как полный, так и инкрементальный поиск решений применительно к простым и иерархическим системам ограничений.

Принцип эффективного глобального поиска решений довольно естественен для прикладных задач в ограничениях, большая часть из которых является NP-полными. В отличие от методов распространения, направленных на пропозициональный вывод и локальное улучшение частных решений, методы глобального поиска обеспечивают систематический или стохастический поиск общих решений, удовлетворяющих всем заданным ограничениям. Заметим, что поиск с возвратом (backtracking) в сочетании с локальным распространением нашел применение практически во всех реализациях систем программирования в ограничениях, включая упомянутые выше диалекты языков Lisp и Prolog.

В случаях редукции исходной задачи в ограничениях к типовой математической постановке появляется возможность применения известных и апробированных методов решения. Например, симплекс-метод используется в качестве стандартного математического средства в системе 2LP [32], а метод комбинаторного поиска на конечных доменах — в успешном коммерческом продукте ILOG Solver [33].

В некоторых случаях для усиления выразительности языковых средств, а также для упрощения идентификации математических постановок выделяются специальные типы ограничений, и для них предусматриваются особые математические методики. В частности, в CHIP и ILOG Schedule поддерживаются некоторые типовые ограничения, возникающие в задачах планирования и составления расписаний. Специализация языковых и математических средств является общей чертой для всех известных реализаций систем программирования в ограничениях, каждая из которых охватывает лишь некоторые типы ограничений и порождаемые ими классы задач.

Например, Prolog III обеспечивает решение систем линейных ограничений, условий на логических переменных и списках, CHIP — линейных ограничений, условий на логических переменных и конечных доменах, CHARME [34] — условий на конечных доменах, 2LP — только линейных ограничений, ILOG Solver — линейных ограничений и условий на конечных доменах и интервалах, HELIOS [35] — условий на интервалах, NEWTON [36] — нелинейных уравнений. Схожая ситуация сложилась и в области систем конкурентного программирования в ограничениях CCP, к ярким представителям которых следует отнести AKL [37], Oz [38], CIAO [39], TAO [40]. Для краткости в настоящей работе мы не рассматриваем CCP-технологии, адресуя заинтересованного читателя к обзорам [16, 41].

3.2. О задачах генерации тестовых данных

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

Несмотря на отмеченную общность, технологии генерации тестовых данных развиваются как самостоятельное направление программной инженерии с конца 70-ых – начала 80-ых годов. Как правило, в постановках задач генерации первостепенное внимание уделяется синтаксически адекватному представлению данных, порождаемому заданной формальной грамматикой некоторого целевого языка. Позитивные и негативные тесты строятся как наборы синтаксически корректных и некорректных программ, полнота которых обеспечивается покрытием продукционных правил грамматики. Сформированные таким образом наборы данных могут использоваться, например, для тестирования синтаксических анализаторов.

Понимание важности учета семантики языка при генерации тестов привело к целому ряду работ, основные идеи которых тесно перекликаются с рассмотренными выше принципами программирования в ограничениях. В частности, декларативное описание семантических правил, последовательная локализация решений, применение мутаций при формировании семантически согласованных и рассогласованных наборов данных, стохастический поиск решений могут быть отнесены к рассмотренным выше принципам и методам программирования в ограничениях. Эти идеи нашли применение в рамках концепции тестирования в ограничениях CBT (Constraint-Based Testing) [42].

Отметим роль аппарата атрибутных грамматик Кнута [43] при генерации тестов. Данный аппарат удобен как для описания синтаксиса целевого языка, так и для задания семантических правил. На его основе успешно решаются задачи комплексного тестирования программного обеспечения с учетом синтаксиса и статической семантики целевого языка. В классических работах программы, сгенерированные на основе заданной контекстно-свободной грамматики, подвергаются дополнительным испытаниям для отбора семантически корректных тестов.

В ряде работ предпринимаются попытки внедрить элементы императивного подхода, в частности, явно задавать последовательность и процедуры пересчета атрибутов в дереве синтаксиса для удовлетворения семантических правил языка. Эти элементы применяются, в частности, в технологии тестирования программного обеспечения на основе формальных спецификаций и моделей, развиваемой в ИСП РАН [44–47].

3.3. Основные достоинства предлагаемого подхода

Главной особенностью предлагаемого подхода к объектно-ориентированному программированию в ограничениях является использование универсальных языков моделирования данных EXPRESS, ODL/OQL, UML/OCL, OWL. Язык UML/OCL рассматривается здесь лишь в контексте моделирования данных, хотя его функциональное назначение существенно шире. Язык описания онтологий OWL отнесен к группе объектно-ориентированных языков в силу известного соответствия между конструкциями этих языков и возможности непротиворечивой трансформации описанных на них моделей одна в другую.

Обсуждаемый системный подход к OOCP обладает рядом достоинств по сравнению с упомянутыми выше технологиями, а именно:

• Декларативность описания задачи в ограничениях, исключающая необходимость предварительной проработки редукции исходной постановки к схемам поиска решения на основе функциональной рекурсии и логического вывода. Отметим, что данный этап неизбежно присутствует при использовании языков функционального и логического программирования и, как правило, вызывает наибольшие трудности.
• Выразительность описания задачи в ограничениях, обусловленная непосредственной интерпретацией исходной постановки в терминах информационного моделирования. Вместо определения отдельных переменных и зависимостей между ними пользователь описывает единую согласованную модель данных и ограничений, которая служит входной информацией для системы программирования в ограничениях. Результатом работы системы являются наборы данных, структурированные в соответствии с заданной моделью и удовлетворяющие ее семантическим правилам.
• Универсальность описания задачи в ограничениях, определяемая возможностью его использования при решении разнообразных задач программной инженерии. Спецификации, подготовленные на актуальных языках моделирования, могут применяться для автоматизированной разработки программ с использованием CASE-инструментов. К числу подобных приложений могут быть отнесены задачи генерации схем баз данных, программных интерфейсов доступа к данным, протоколов обмена данными, графических пользовательских интерфейсов на соответствующих реализационных языках. На основе подобных спецификаций может решаться и задача генерации тестовых данных в рамках концепции CBT.

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

4. Вычислительная стратегия программирования в ограничениях

В основе предлагаемой вычислительной стратегии разрешения ограничений лежит несколько конструктивных принципов и идей:

• использование единого метамодельного представления для работы с данными и моделями, специфицированными на языках EXPRESS, ODL/OQL, UML/OCL, OWL; для взаимного преобразования моделей и определяемых ими данных могут быть применены известные трансформации;
• статический анализ спецификаций модели данных и идентификация математических постановок, к которым может быть сведена исходная задача в ограничениях; для простых ограничений формируются альтернативные правила пересчета неизвестных переменных друг через друга, пригодные для использования в методах распространения; для сложных систем ограничений (и их подсистем) осуществляется анализ зависимостей по данным и определяется тип математической задачи, а также возможный метод решения (например, идентификация множества ограничений как системы линейных алгебраических уравнений позволяет использовать известные методы матричной факторизации);
• последовательная редукция исходной задачи в ограничениях к задачам формирования множества неизвестных переменных (расчет необходимого числа объектов каждого типа), установления взаимосвязей (отношений ассоциации, агрегации и композиции между объектами) и определения числовых параметров (значений атрибутов объектов);
• применение методов линейного и квадратичного целочисленного программирования [48–50] для определения кардинальности множеств типизированных объектов; выбор вида функционала позволяет эмулировать содержательные ситуации, когда, например, требуется сформировать минимальные, максимальные или репрезентативные наборы данных;
• применение методов логического вывода [51, 52] (прежде всего, метода резольвент и метода полисиллогистического вывода) для задания взаимосвязей объектов и определения неизвестных логического типа;
• применение методов интервальной арифметики, локализации и распространения для нахождения неизвестных вещественного типа при наличии простых зависимостей по данным;
• применение известных методов символьных преобразований [53, 54] и вычислительной математики для совместного решения систем (линейных, полиномиальных, нелинейных) алгебраических уравнений и неравенств;
• применение метода семантической реконсиляции [55–58] для инкрементального поиска общих решений с учетом всей системы наложенных разнородных ограничений.

Таким образом, в качестве основной стратегии предлагается использовать описанную выше редукционную схему, состоящую в последовательном конструировании необходимого числа типизированных объектов, задании для них взаимосвязей и определении значений их атрибутов. Заметим, что большая часть семантических правил в объектно-ориентированных моделях специфицируется независимым друг от друга образом и не приводит к сложным зависимостям по данным. Это дает основания полагать о конструктивности применения подобной стратегии.

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

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

Ожидается, что применение редукционного подхода в сочетании с методом семантической реконсиляции обеспечит надежное решение задач в классе CLP(O).

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

Рис. 5. Додекаэдр, икосаэдр, тетраэдр

Опишем задачу в ограничениях в виде спецификаций модели данных. Определим абстрактный класс polyhedron для представления произвольного правильного многогранника. Многогранник состоит из граней, ребер и вершин, моделируемых классами face, edge и vertex соответственно. Конкретизации класса polyhedron (см. рис. 5), соответствующие геометрическим моделям:

• тетраэдра – имеет 4 треугольных грани, 6 рёбер, 4 вершины, в каждой сходятся 3 ребра,
• октаэдра – имеет 8 треугольных граней, 8 ребер, 6 вершин, в каждой сходятся 4 ребра,
• гексаэдра – имеет 6 четырехугольных граней, 12 ребер, 8 вершин, в каждой сходятся 4 ребра,
• додекаэдра – имеет 12 пятиугольных граней, 30 рёбер и 20 вершин, в каждой сходятся 3 ребра и
• икосаэдра – имеет 20 треугольных граней, 30 рёбер, 12 вершин, в каждой сходятся 5 ребер,

моделируются классами tetrahedron, octahedron, hexahedron, dodecahedron и icosahedron соответственно. В рассматриваемой постановке абсолютный масштаб многогранника не существенен, поэтому для определенности положим длину ребер равной единице.

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

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

Рис. 6. UML модель для представления многогранников

Для описания этих ограничений воспользуемся языком OCL. Формула Эйлера для многогранника представляется в виде следующего инварианта, распространяемого на экземпляры класса polyhedron:

context polyhedron
inv: self.vertices->size() - self.edges->size() + self.faces->size() = 2

Для задания ограничения выпуклости воспользуемся уравнением плоскости , проходящей через первые три вершины каждой грани и задающей полупространство для локализации остальных вершин многогранника. На языке OCL условие выпуклости многогранника может быть выражено соответствующим инвариантом класса face, в котором используются объявления вспомогательных локальных переменных:

context face
    let secVertices : Sequence(Vertex) = collect(self.v) in
    let first : Vertex = secVertices(1) in
    let second : Vertex = secVertices(2) in
    let third : Vertex = secVertices(3) in

    let A : Real = first.y * (second.z - third.z ) +
                   second.y * (third.z - first.z ) +
                   third.y * (first.z - second.z ) in 
    let B : Real = first.z * (second.x - third.x ) +
                   second.z * (third.x - first.x ) +
                   third.z * (first.x - second.x ) in

    let C : Real = first.x * (second.y - third.y ) +
                   second.x * (third.y - first.y ) +
                   third.x * (first.y - second.y ) in

    let D : Real = first.x * (third.y * second.z - second.y * third.z) +
                   second.x * (first.y * third.z - third.y * first.z) +
                   third.x * (second.y * first.z - first.y * second.z) in

self.owner.vertices->collect( v1 : vertex | not self.vertices->includes( v1 ) )
    ->forAll( v2 : vertex | A * v2.x + B * v2.y + C * v2.z + D > 0 )

Наконец, условие равенства длин ребер прозрачным образом специфицируется средствами языка OCL как инвариант класса edge:

Context edge
inv: (self.v2.x – self.v1.x) * (self.v2.x – self.v1.x) + 
     (self.v2.y – self.v1.y) * (self.v2.y – self.v1.y) + 
     (self.v2.z – self.v1.z) * (self.v2.z – self.v1.z) = 1

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

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

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

Заключение

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

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

Назад Содержание Вперёд