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

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

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

Содержание

1. Введение

2. Некоторые примеры

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

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

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

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

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

Заключение

Литература

1. Введение

В последние годы наблюдается ренессанс идей логического программирования в ограничениях (CLP) в таких актуальных научных областях и дисциплинах, как интеллектуальные системы принятия решений (логические нейронные сети), компьютерная графика (декларативные сценарные модели и графические интерфейсы), экономические модели (недоопределенные вычисления), системы автоматизированного проектирования (параметрическое моделирование), информационные системы (активные базы данных и управление целостностью), семантический поиск данных (дескриптивные логики), верификация и тестирование программного обеспечения (временные логики), системы коллективной инженерии (полисиллогистический вывод) [1, 2]. Многие крупные индустриальные компании проявляют интерес к этой теме, а ACM признала ее одним из стратегических направлений исследований.

Вместе с тем, следует констатировать, что как технология общего назначения CLP не получило широкое распространение, а в перечисленных выше областях разрабатываются и используются специализированные языки и программные системы. Их главным недостатком и принципиальным ограничением является невозможность специфицировать и решать задачи над сложно структурированными, семантически согласованными данными — в частности, объектно-ориентированными данными, определяемыми актуальными информационными моделями и международными стандартами ISO STEP [3], OMG MDA [4], W3C Semantic Web [5].

Эти факторы обуславливают выработку нового системного подхода, который, с одной стороны, обеспечил бы решение широкого класса задач в ограничениях, а с другой — приблизил бы способы их постановки к популярным универсальным технологиям объектно-ориентированного моделирования. Особую привлекательность приобретает применение для этих целей универсальных языков моделирования данных EXPRESS [6], ODL/OQL [7], UML/OCL [8, 9], OWL [10], получивших признание и распространение в широких научных и индустриальных сообществах.

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

В ряде случаев целесообразным представляется использование стандартных информационных моделей [11–14], разработанных индустриальными консорциумами для таких областей, как программная инженерия, информационные технологии, машиностроение, атомная энергетика, авиационная и космическая промышленность, судостроение, архитектура и строительство, нефтегазовый комплекс, фармацевтика. Постановка и решение задач программирования в ограничениях могут приводить к возникновению новых, индустриально значимых приложений.

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

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

Данный класс, обозначаемый в дальнейшем CLP(O), предполагает дополнительную структуризацию переменных по сравнению с традиционными постановками в булевых, рациональных, вещественных числах CLP(B), CLP(Q), CLP(R) и на конечных доменах CLP(FD) соответственно. Кроме того, возможность алгебраической спецификации произвольных семантических правил приводит к необходимости совместного анализа и разрешения неоднородных ограничений, что крайне затруднительно при использовании традиционных методов, ориентированных на частные математические постановки. Наконец, задание правил на типах данных, а не только на отдельных переменных, порождает проблему формирования множества неизвестных переменных, в данном случае — коллекций объектов и элементов данных, относительно которых задача в ограничениях должна решаться.

Отметим, что как самостоятельная научная дисциплина программирование в ограничениях охватывает три направления, а именно: разрешение ограничений CSP (Constraint Satisfaction Problem) [15], логическое программирование в ограничениях CLP (Constraint Logic Programming) [1] и конкурентное программирование в ограничениях CCP (Concurrent Constraint Programming) [16]. Несмотря на особенности в постановках и методах решения задач, все три направления тесно связаны между собой. В рамках обсуждаемого подхода к OOCP мы не видим причин отказываться ни от одного из них. Применяя обозначение CLP(O), мы лишь подчеркиваем роль методов логического программирования как конструктивной основы для выстраивания перспективных вычислительных стратегий разрешения систем неоднородных ограничений, формально специфицированных на декларативных языках объектно-ориентированного моделирования данных.

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

2. Некоторые примеры

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

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

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

Наконец, спецификации ограничений носят неопределенный характер с точки зрения их алгоритмической разрешимости. Поскольку система ограничений может быть недоопределена или переопределена, постановка задачи в ограничениях априори не предполагает ни существования, ни единственности решения, и его поиск должен вестись с учетом всех этих обстоятельств. Обсудим перечисленные свойства в контексте постановки и решения задач в классе 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. Уточненный список может использоваться в качестве шаблона решения, к которому последовательно применяются правила вывода в рамках общей схемы рекурсивного программирования. Будем считать список координат согласованным, если он определяет позицию, в которой ни один из ферзей не находится под боем. Возможны два случая:

• Случай 1. Список пуст. Очевидно, пустой список является согласованным при отсутствии фигур и возможных атак.
• Случай 2. Список не пуст. Тогда он представим в виде [ x/y | Остальные ], где x/y задает положение первого ферзя, а список “Остальные” — положение остальных. Определим необходимые условия, при которых непустой список является согласованным. Во-первых, список “Остальные” должен быть согласованным. Во-вторых, значения x и y должны принадлежать множеству целых чисел от 1 до 8 включительно. В-третьих, значения x и y, а также их разности ( x-y ) и суммы ( x+y ) не должны совпадать с соответствующими значениями из списка “Остальные”.

Данные условия могут быть описаны на языке Prolog [17] в виде следующей программы (см. рис. 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 [18], представляющим собой расширение стандарта ANSI Common Lisp [19] для программирования в ограничениях. Нововведением в 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) )))))

context Queen
-- (A)
inv: self.AllInstances()->size() = 8
-- (B)
inv: self.x >= 1 and self.x <= 8 and self.y >= 1 and self.y <= 8
-- (C)
inv: self.AllInstances()->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)))