Объектно-ориентированное программирование в ограничениях
Краткий обзор технологий программирования в ограничениях
Программирование в ограничениях как самостоятельное научное направление сложилось в конце 60-х – начале 70-х годов прошлого века. Примечательно, что первыми приложениями были задачи обработки изображений и параметрического моделирования пространственно-двумерных сцен. С тех пор направление существенно эволюционировало, охватывая новые классы задач и выдвигая новые подходы к их решению.Тем не менее, по-видимому, не претерпели серьезных изменений четыре фундаментальных принципа, а именно: декларативное моделирование ограничений, локальное распространение результатов, эффективный глобальный поиск решений и специализация языковых и математических средств. Начиная со Sketchpad , ALICE , ThingLab , эти принципы успешно эксплуатируются и в современных реализациях.
Принцип декларативности нашел конструктивное воплощение во многих языках функционального и логического программирования ( включая Lisp и Prolog), допускающих описание и решение некоторых задач в ограничениях. Со временем понимание того, что функциональная рекурсия и логический вывод являются лишь отдельными элементами более общей стратегии разрешения ограничений для сложно структурированных неизвестных переменных, привело к появлению CostraintLisp, Prolog III и CHIP .
Язык реляционных баз данных SQL , предусматривающий развитые декларативные конструкции для описания запросов и ограничений целостности, также несет в себе черты языка программирования в ограничениях. Связь с технологиями управления базами данных становится еще более очевидной при анализе относительно новой концепции Constraint Database (CDВ) , которая, расширяя реляционную, дедуктивную и объектно-ориентированную модели, устанавливает непосредственную связь между типами данных и ограничениями, которые их предопределяют.
Принцип локального распространения (в англоязычной литературе соответствующий терминам constraint propagation или consistency inference) имеет долгую историю и многочисленные приложения, в частности, в области интеллектуализации графических интерфейсов пользователя.
Спекулятивные попытки предвосхитить результаты поиска путем локальных и циклических уточнений частных решений оказались довольно плодотворными при решении больших систем уравнений и неравенств.
Многочисленные “радужные” воплощения принципа привели к созданию целой палитры методов: Red (красный), Orange (оранжевый), Yellow (желтый), Green (зеленый), Blue (синий), DeltaBlue (инкрементально-синий), SkyBlue (небесно-синий), UltraViolet (ультрафиолет), Purple (фиолетовый), DeepPurple (пурпурный), Indigo (темно-синий) . Некоторые из них обеспечивают как полный, так и инкрементальный поиск решений применительно к простым и иерархическим системам ограничений.
Принцип эффективного глобального поиска решений довольно естественен для прикладных задач в ограничениях, большая часть из которых является NP-полными. В отличие от методов распространения, направленных на пропозициональный вывод и локальное улучшение частных решений, методы глобального поиска обеспечивают систематический или стохастический поиск общих решений, удовлетворяющих всем заданным ограничениям. Заметим, что поиск с возвратом (backtracking) в сочетании с локальным распространением нашел применение практически во всех реализациях систем программирования в ограничениях, включая упомянутые выше диалекты языков Lisp и Prolog.
В случаях редукции исходной задачи в ограничениях к типовой математической постановке появляется возможность применения известных и апробированных методов решения. Например, симплекс-метод используется в качестве стандартного математического средства в системе 2LP , а метод комбинаторного поиска на конечных доменах — в успешном коммерческом продукте ILOG Solver .
В некоторых случаях для усиления выразительности языковых средств, а также для упрощения идентификации математических постановок выделяются специальные типы ограничений, и для них предусматриваются особые математические методики. В частности, в CHIP и ILOG Schedule поддерживаются некоторые типовые ограничения, возникающие в задачах планирования и составления расписаний.Специализация языковых и математических средств является общей чертой для всех известных реализаций систем программирования в ограничениях, каждая из которых охватывает лишь некоторые типы ограничений и порождаемые ими классы задач.
Например, Prolog III обеспечивает решение систем линейных ограничений, условий на логических переменных и списках, CHIP — линейных ограничений, условий на логических переменных и конечных доменах, CHARME — условий на конечных доменах, 2LP — только линейных ограничений, ILOG Solver — линейных ограничений и условий на конечных доменах и интервалах, HELIOS — условий на интервалах, NEWTON — нелинейных уравнений. Схожая ситуация сложилась и в области систем конкурентного программирования в ограничениях CCP, к ярким представителям которых следует отнести AKL , Oz , CIAO , TAO . Для краткости в настоящей работе мы не рассматриваем CCP-технологии, адресуя заинтересованного читателя к обзорам .
Некоторые примеры
Напомним, что задачи в ограничениях обычно описываются путем определения множества неизвестных переменных и зависимостей между ними. При этом процесс решения заключается в локализации областей значений переменных или в поиске значений, удовлетворяющих заданным зависимостям. Перечислим основные особенности постановки таких задач.Спецификации ограничений в рассматриваемых задачах носят декларативный характер, исключающий явное описание способов решения задачи (в качестве исключения здесь следует указать императивные языки ограничений, на которых пользователь описывает и некоторые методики решения). Спецификации обладают свойством нейтральности по отношению к неизвестным переменным и возможным альтернативным способам выражения и пересчета их друг через друга.
Спецификации обладают также свойством аддитивности, предполагающим, что порядок задания ограничений не существенен для постановки исходной задачи, логические условия которой всегда могут быть представлены в эквивалентной конъюктивной форме. Исключение составляют так называемые иерархические системы, в которых разрешение ограничений осуществляется поэтапно в соответствии с предварительно назначенными приоритетами.
Наконец, спецификации ограничений носят неопределенный характер с точки зрения их алгоритмической разрешимости. Поскольку система ограничений может быть недоопределена или переопределена, постановка задачи в ограничениях априори не предполагает ни существования, ни единственности решения, и его поиск должен вестись с учетом всех этих обстоятельств. Обсудим перечисленные свойства в контексте постановки и решения задач в классе CLP(O).
С этой целью рассмотрим классическую математическую задачу о ферзях и приведем возможные способы ее описания и решения на языках логического, функционального и объектно-ориентированного программирования. Задача формулируется следующим образом: необходимо расставить на шахматной доске восемь ферзей так, чтобы ни один из них не оказался под боем остальных фигур. Один из вариантов решения приведен на рисунке 1.
Рис. 1. Один из вариантов решения задачи о восьми ферзях
Положение каждой фигуры на шахматной доске характеризуется парой координат x/y, каждая из которых принимает целые значения от 1 до 8 (здесь мы отступим от традиционной буквенно-цифровой нотации ходов в шахматной партии, подобной “e2-e4”, и будем использовать оператор «/» для объединения координат в один элемент списка). Тогда шахматная позиция представляется списком вида [xl/yl, x2/y2, x3/y3, x4/y4, x5/y5, x6/y6, x7/y7, x8/y8]. В этом представлении решение на рис. 1 выглядит, как [1/4, 2/2, 3/7, 4/3, 5/6, 6/8, 7/5, 8/1].
Если принять во внимание необходимость расположения ферзей на разных вертикалях (или на разных горизонталях), то представление списка можно сразу уточнить, как [l/yl, 2/y2, 3/y3, 4/y4, 5/y5, 6/y6, 7/y7, 8/y8]. Таким образом, задача сводится к определению горизонтальных (или вертикальных) координат, исключающих расположение нескольких фигур на одних и тех же линиях шахматной доски.
Обсудим, каким образом задача может быть описана и решена на языке логического программирования Prolog. Уточненный список может использоваться в качестве шаблона решения, к которому последовательно применяются правила вывода в рамках общей схемы рекурсивного программирования. Будем считать список координат согласованным, если он определяет позицию, в которой ни один из ферзей не находится под боем. Возможны два случая:
Данные условия могут быть описаны на языке Prolog в виде следующей программы (см. рис. 2).
?- шаблон( S), решение( S). решение( [ ] ). решение( [x/y | Остальные ] ) :- % Первый ферзь на поле x/y, % остальные ферзи на полях из списка Остальные решение( Остальные ), принадлежит( y, [1, 2, 3, 4, 5, 6, 7, 8] ), не_бьет( x/y | Остальные ). % Первый ферзь не бьет остальных не_бьет( x/y, [ ]). % Некого бить не_бьет( x/y, [x1/y1 | Остальные] ) :- y =\= y1, % Разные y-координаты y1 - x1 =\= y - x, % Разные диагонали y1 + x1 =\= y + x, не_бьет( x/y, Остальные). принадлежит( x, [x | L] ). принадлежит( x, [y | L] ) :- принадлежит( x, L). % Шаблон решения шаблон( [1/y1, 2/y2, 3/y3, 4/y4, 5/y5, 6/y6, 7/y7, 8/y8] ).
Рис. 2. Программа решения задачи о ферзях на языке Prolog
Обсудим возможность описания этой же задачи на языке ConstraintLisp , представляющим собой расширение стандарта ANSI Common Lisp для программирования в ограничениях. Нововведением в ConstraintLisp является набор функций, который позволяет описывать арифметические ограничения в рамках функциональной и объектно-ориентированной парадигм, поддерживаемых языком ANSI Common Lisp.
В программе на рис. 3 определяется класс Queen с двумя атрибутами x и y для задания положения фигуры на шахматной доске. Для представления шахматной позиции используется массив Сhessboard, в котором хранится восемь экземпляров класса Queen. Массив конструируется и инициализируется в результате вызова соответствующей функции make-queens. Отметим, что содержательные ограничения задачи определяются в виде вспомогательной функции constraints с формальными параметрами, соответствующими координатам анализируемых фигур. При этом фактическое назначение ограничений объектам массива Сhessboard осуществляется в теле вложенного цикла, где описанный вид ограничений применяется ко всем парам итерируемых объектов. Решение генерируется и выводится на печать при вызове специальных функций generateObjs и printArrayObjs.
;;; определение класса Queen (defclass Queen ( ) (( x :initarg :x :accessor x ) ;;; координата по горизонтали ( y :initarg :y :accessor y))) ;;; координата по вертикали ;;; основная процедура поиска решения (define Queens ( ) (let ((Chessboard ( make-queens)) ) ;;; создаем массив из восьми ферзей (cldotimes ( I 7 ) ;;; начальное значение переменной I 0 (cldotimes ( J (- 7 I )) ;;; начальное значение переменной J 0 (constraints ( x (aref Chessboard I )) ( x (aref Chessboard (+ J I 1 ))) (1+ I) (+ J I 2 )))) ( generateObjs Chessboard ) ;;; генерация решения ( printArrayObjs Chessboard ))) ;;; вывод результатов ;;; ограничения отсутствия вертикальных и диагональных атак (define constraints (x1 x2 y1 y2) (constr (/= x1 x2)) ;;; по вертикали (constr (/= (+ x1 y1 ) (+ x2 y2 ))) ;;; по главной диагонали (constr (/= (- x1 y1 ) (- x2 y2 )))) ;;; по второй диагонали ;;; создаем массив ферзей (defun make-queens ( ) (let ( (queen-array (make-array 8 ))) (dotimes (I 8 queen-array ) (setf (aref queen-array I ) (make-instance 'queen :x (make-cvar-in '((1 ,8 ))) :y (1+ I) )))))
Рис. 3. Программа решения задачи о ферзях на языке ConstraintLisp
Наконец, опишем задачу о ферзях, используя декларативный язык объектно-ориентированного моделирования UML/OCL. Для этого определим необходимые объектные типы данных и инвариантные условия на них. На диаграмме классов языка UML (см. рис. 4) представлен объектный тип Queen с соответствующими целочисленными атрибутами x и y, задающими положение фигуры на шахматной доске. В виде инвариантов контекста Queen на языке OCL описаны исходные условия задачи о ферзях. Инвариант A задает необходимое число фигур на шахматной доске. Инвариант B определяет допустимую область значений для координат фигур, ограниченных полем 8x8 клеток. Условие расположения ферзей на разных вертикалях и горизонталях выражается инвариантом C, а условие расположения ферзей на разных диагоналях — инвариантом D.
context Queen -- (A) inv: self.AllInstances()->size() = 8 -- (B) inv: self.x >= 1 and self.x = 1 and self.y forAll(q1, q2 | q1 <> q2 implies (q1.x <> q2.x and q1.y <> q2.y)) -- (D) inv: self.allInstances()->forAll(q1, q2 | q1 <> q2 implies ((q1.x – q1.y) <> (q2.x – q2.y) and (q1.x + q1.y) <> (q2.x + q2.y)))
Рис. 4. Описание задачи о ферзях в виде диаграммы классов и спецификации ограничений на языке UML/OCL
Несмотря на декларативность всех языков, использованных в примерах, спецификации на языке UML/OCL обладают большей выразительностью для моделирования данных и постановки соответствующих задач в ограничениях. Для описания задачи о ферзях потребовалось лишь структурировать данные и определить ограничения, которым они должны удовлетворять. Подобный способ исключает задание каких-либо вспомогательных методик или схем решения, присущих языкам логического и функционального программирования.
В самом деле, вычислительная модель Prolog подразумевает редукцию исходной постановки к рекурсивной или итерационной схеме поиска решений на основе определяемых пользователем правил логического вывода и целей. Заметим, что порядок определения правил и целей может существенно влиять на ход решения.
В рассмотренном примере на ConstraintLisp помимо определения объектной модели данных потребовалось явно сконструировать неизвестные переменные и для них задать схему применения ограничений. Отметим громоздкость подобного функционального способа постановки задач в ограничениях по сравнению с декларациями на UML/OCL.
О задачах генерации тестовых данных
Обсуждаемый класс задач программирования в ограничениях довольно широк и охватывает самые разнообразные приложения. Безусловно, к ним могут быть отнесены и задачи генерации данных, возникающие при тестировании разного рода программного обеспечения, начиная с протоколов обмена данными и заканчивая трансляторами языков программирования.Несмотря на отмеченную общность, технологии генерации тестовых данных развиваются как самостоятельное направление программной инженерии с конца 70-ых – начала 80-ых годов. Как правило, в постановках задач генерации первостепенное внимание уделяется синтаксически адекватному представлению данных, порождаемому заданной формальной грамматикой некоторого целевого языка. Позитивные и негативные тесты строятся как наборы синтаксически корректных и некорректных программ, полнота которых обеспечивается покрытием продукционных правил грамматики. Сформированные таким образом наборы данных могут использоваться, например, для тестирования синтаксических анализаторов.
Понимание важности учета семантики языка при генерации тестов привело к целому ряду работ, основные идеи которых тесно перекликаются с рассмотренными выше принципами программирования в ограничениях. В частности, декларативное описание семантических правил, последовательная локализация решений, применение мутаций при формировании семантически согласованных и рассогласованных наборов данных, стохастический поиск решений могут быть отнесены к рассмотренным выше принципам и методам программирования в ограничениях. Эти идеи нашли применение в рамках концепции тестирования в ограничениях CBT (Constraint-Based Testing) .
Отметим роль аппарата атрибутных грамматик Кнута при генерации тестов. Данный аппарат удобен как для описания синтаксиса целевого языка, так и для задания семантических правил. На его основе успешно решаются задачи комплексного тестирования программного обеспечения с учетом синтаксиса и статической семантики целевого языка. В классических работах программы, сгенерированные на основе заданной контекстно-свободной грамматики, подвергаются дополнительным испытаниям для отбора семантически корректных тестов.
В ряде работ предпринимаются попытки внедрить элементы императивного подхода, в частности, явно задавать последовательность и процедуры пересчета атрибутов в дереве синтаксиса для удовлетворения семантических правил языка. Эти элементы применяются, в частности, в технологии тестирования программного обеспечения на основе формальных спецификаций и моделей, развиваемой в ИСП РАН .
Объектно-ориентированное программирование
Семенов В.А., Ильин Д.В., Морозов С.В., Сидяка О.В.Аннотация. Объектно-ориентированное программирование в ограничениях (OOCP) сочетает две ортогональные, но комплементарные парадигмы программирования, а именно: объектно-ориентированное программирование (OOP) и логическое программирование в ограничениях (CLP). Несмотря на привлекательность идеи синтеза парадигм и известные попытки реализации, до сих пор не существует единого понимания, какие конструктивные очертания она может приобрести при дальнейшей проработке и развитии. Ключевыми вопросами при этом остаются выразительность описания прикладной задачи в ограничениях и ее алгоритмическая разрешимость. В настоящей работе предлагается и обсуждается новый системный подход к реализации OOCP на основе использования декларативных языков моделирования данных.
Семенов В.А., Ильин Д.В., Морозов С.В., Сидяка О.В.
Семенов В.А., Ильин Д.В., Морозов С.В., Сидяка О.В.
Основные достоинства предлагаемого подхода
Главной особенностью предлагаемого подхода к объектно-ориентированному программированию в ограничениях является использование универсальных языков моделирования данных EXPRESS, ODL/OQL, UML/OCL, OWL. Язык UML/OCL рассматривается здесь лишь в контексте моделирования данных, хотя его функциональное назначение существенно шире. Язык описания онтологий OWL отнесен к группе объектно-ориентированных языков в силу известного соответствия между конструкциями этих языков и возможности непротиворечивой трансформации описанных на них моделей одна в другую.Обсуждаемый системный подход к OOCP обладает рядом достоинств по сравнению с упомянутыми выше технологиями, а именно:
Естественно, общность предлагаемого подхода при описании задач в ограничениях на декларативных языках объектно-ориентированного моделирования порождает проблемы алгоритмического характера, связанные с необходимостью разрешения больших систем разнородных алгебраических ограничений. Выработка единой вычислительной стратегии для удовлетворения подобных ограничений и решения задач в обсуждаемом классе CLP(O) представляется наиболее критичной.
Вычислительная стратегия программирования в ограничениях
В основе предлагаемой вычислительной стратегии разрешения ограничений лежит несколько конструктивных принципов и идей:Таким образом, в качестве основной стратегии предлагается использовать описанную выше редукционную схему, состоящую в последовательном конструировании необходимого числа типизированных объектов, задании для них взаимосвязей и определении значений их атрибутов. Заметим, что большая часть семантических правил в объектно-ориентированных моделях специфицируется независимым друг от друга образом и не приводит к сложным зависимостям по данным. Это дает основания полагать о конструктивности применения подобной стратегии.
В более сложных ситуациях, когда основная стратегия не обеспечивает нахождение общего решения, предлагается использовать оригинальный метод семантической реконсиляции для коррекции уже найденных частных решений. Ключевые элементы этого метода были успешно апробированы в приложениях коллективной инженерии, к которым предъявляются близкие требования целостности и корректности результирующего представления данных. Применительно к обсуждаемому классу задач CLP(O) метод семантической реконсиляции предполагает следующие этапы:
Ожидается, что применение редукционного подхода в сочетании с методом семантической реконсиляции обеспечит надежное решение задач в классе CLP(O).
Проиллюстрируем применение описанной вычислительной стратегии на примере задачи о правильном многограннике. Задача формулируется следующим образом: в трехмерном пространстве требуется построить правильный многогранник с заданным числом граней. Отметим, что в подобной постановке решение может и не существовать (известным фактом, например, является невозможность построения правильного пятигранника), поэтому желателен анализ существования решения.
Рис. 5. Додекаэдр, икосаэдр, тетраэдр
Опишем задачу в ограничениях в виде спецификаций модели данных. Определим абстрактный класс polyhedron для представления произвольного правильного многогранника. Многогранник состоит из граней, ребер и вершин, моделируемых классами face, edge и vertex соответственно. Конкретизации класса polyhedron (см. рис. 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), сочетающая в себе ряд конструктивных идей и принципов.В дальнейшем предполагается детальная алгоритмическая проработка предложенного подхода и полнофункциональная реализация системы объектно-ориентированного программирования в ограничениях на основе декларативных языков моделирования данных.
Программирование: Языки - Технологии - Разработка
- Программирование
- Технологии программирования
- Разработка программ
- Работа с данными
- Методы программирования
- IDE интерфейс
- Графический интерфейс
- Программирование интерфейсов
- Отладка программ
- Тестирование программ
- Программирование на Delphi
- Программирование в ActionScript
- Assembler
- Basic
- Pascal
- Perl
- VBA
- VRML
- XML
- Ada
- Lisp
- Python
- UML
- Форт
- Языки программирования