ПРОГРАММИРОВАНИЕ, 2010, No 5, с. 24-37
ТЕОРЕТИЧЕСКИЕ ОСНОВЫ ПРОГРАММИРОВАНИЯ
УДК 681.3.06
О КОМПЛЕМЕНТАРНЫХ ПРИНЦИПАХ ОБЪЕКТНО-ОРИЕНТИРОВАННОГО ПРОГРАММИРОВАНИЯ
В ОГРАНИЧЕНИЯХ
© 2010 г. В. А. Семенов, К. В. Драгалов, Д. В. Ильин, С. В. Морозов, О. В. Сидяка
Институт системного программирования РАН 109004 Москва, ул. Солженицына, 25 E-mail: sem@ispras.ru Поступила в редакцию 16.03.2010 г.
Статья посвящена проблемам реализации парадигмы объектно-ориентированного программирования в ограничениях (OOCP), сочетающей в себе комплементарные идеи и принципы объектно-ориентированного программирования (OOP) и логического программирования в ограничениях (CLP). Несмотря на привлекательность идеи и известные попытки ее реализации с использованием логических и функциональных языков, до сих пор не существует единого понимания, какие конструктивные очертания она приобретет при дальнейшей проработке и развитии. Приводится обзор существующих технологий программирования в ограничениях, а также обсуждается новый системный подход к реализации OOCP на основе использования декларативных языков моделирования данных. На примере классической математической задачи о ферзях показываются преимущества подхода, связанные с выразительностью и универсальностью описания задач в ограничениях, а также определяется общая алгоритмическая стратегия для их решения.
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. НЕКОТОРЫЕ ПРИМЕРЫ
Рис. 1. Один из вариантов решения задачи о восьми ферзях.
Напомним, что задачи в ограничениях обычно описываются путем определения множества неизвестных переменных и зависимостей между ними. При этом процесс решения заключается в локализации областей значений переменных или в поиске значений, удовлетворяющих заданным зависимостям. Перечислим основные особенности их постановки.
Спецификации ограничений в рассматриваемых задачах носят декларативный характер, исключающий явное описание способов решения задачи (в качестве исключения здесь следует указать императивные языки ограничений, на которых пользователь описывает и некоторые методики решения). Спецификации обладают свойством нейтральности по отношению к неизвестным переменным и возможным альтернативным способам выражения и пересчета их друг через друга. Спецификации обладают также свойством аддитивности, предполагающим, что порядок задания ограничений не существенен для постановки исходной задачи, логические условия которой всегда могут быть представлены в эквивалентной конъюнктивной форме. Исключение составляют так называемые иерархические системы, в которых разрешение ограничений осуществляется поэтапно в соответствии с предварительно назначенными приоритетами. Наконец, спецификации ограничений носят неопределенный характер с точки зрения их алгоритмической разрешимости. Поскольку система ограничений может быть недоопределена или переопределена, постановка задачи в ограничениях априори не предполагает ни существования, ни единственности решения, и его поиск должен вестись с учетом всех этих обстоятельств. Обсудим перечисленные свойства в контексте
постановки и решения задач в классе CLP(O).
С этой целью рассмотрим классическую математическую задачу о ферзях и приведем возможные способы ее описания и решения на языках логического, функционального и объектно-ориентированного программирования. Задача формул
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.