[an error occurred while processing this directive] [an error occurred while processing this directive]
[an error occurred while processing this directive]
Свободные мысли о свободном софте
[an error occurred while processing this directive]
Logo CitForum CITForum на CD Форумы Газета Море(!) аналитической информации!
[an error occurred while processing this directive]
[an error occurred while processing this directive]
[an error occurred while processing this directive]
IT-консалтинг Software Engineering Программирование СУБД Безопасность Internet Сети Операционные системы Hardware
[an error occurred while processing this directive] [an error occurred while processing this directive]
[an error occurred while processing this directive] [an error occurred while processing this directive] [an error occurred while processing this directive] [an error occurred while processing this directive] [an error occurred while processing this directive]

11.12.2018

Google
WWW CITForum.ru
[an error occurred while processing this directive]

Новости мира IT:

Архив новостей

[an error occurred while processing this directive] [an error occurred while processing this directive]
[an error occurred while processing this directive]
Пятнадцатая техническая конференция «Корпоративные базы данных-2010»
Москва, 22–23 апреля
С Новым годом!

Генеральный спонсор
Техническая конференция
Корпоративные базы данных – 2008
Москва, 24–25 апреля
При поддержке РФФИ

Спонсор
[an error occurred while processing this directive] [an error occurred while processing this directive]
На правах рекламы
2010 г.

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

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

Аннотация. Объектно-ориентированное программирование в ограничениях (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) )))))
Рис. 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 <= 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)))

Рис. 4. Описание задачи о ферзях в виде диаграммы классов и спецификации ограничений на языке UML/OCL

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

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

В рассмотренном примере на ConstraintLisp помимо определения объектной модели данных потребовалось явно сконструировать неизвестные переменные и для них задать схему применения ограничений. Отметим громоздкость подобного функционального способа постановки задач в ограничениях по сравнению с декларациями на UML/OCL.

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

[an error occurred while processing this directive]
[an error occurred while processing this directive]
[an error occurred while processing this directive] [an error occurred while processing this directive]

Планирование сроков проекта и вопросы осуществления лидерством проекта рассматриваются на сайте по управлению проектами.

[an error occurred while processing this directive]
[an error occurred while processing this directive]
[an error occurred while processing this directive] [an error occurred while processing this directive] [an error occurred while processing this directive] [an error occurred while processing this directive] [an error occurred while processing this directive]

Размещение рекламы — тел. +7 495 6608306, ICQ 232284597

[an error occurred while processing this directive] [an error occurred while processing this directive]
[an error occurred while processing this directive] [an error occurred while processing this directive] [an error occurred while processing this directive] [an error occurred while processing this directive] [an error occurred while processing this directive]

Редакция рекомендует:

Последние комментарии:

Что мы знаем об iPhone 4G? (7)
16 июля, 20:25

Подписка на новости CITForum.ru

Новые публикации:

7 июля

  • Управление параллелизмом с низкими накладными расходами для разделенных баз данных в основной памяти

  • Рекурсивные запросы в Oracle

  • Жесткий диск WD10EARS с сектором 4 КБ. Подготовка к эксплуатации в Linux.

    Обзоры журнала Computer:

    Газета:

  • Московские пробки - исследование IBM

  • От Osborne до iPad: эволюция портативных компьютеров

    19 мая

  • Прозрачный механизм удаленного обслуживания системных вызовов

  • Система моделирования Grid: реализация и возможности применения

    Газета:

    Майкл Стоунбрейкер:

  • Ошибки в системах баз данных, согласованность "в конечном счете" и теорема CAP

  • Дискуссия по поводу "NoSQL" не имеет никакого отношения к SQL

    29 апреля

  • Материалы конференции "Корпоративные Базы Данных-2010"

  • Разные облики технологии баз данных (отчет о конференции)

    14 апреля

  • MapReduce: внутри, снаружи или сбоку от параллельных СУБД?

  • Научные вызовы технологиям СУБД

    Обзоры журнала Computer:

    31 марта

  • Рационализация согласованности в "облаках": не платите за то, что вам не требуется

  • Взаимные блокировки в Oracle

  • Архитектура среды тестирования на основе моделей, построенная на базе компонентных технологий

  • Объектное представление XML-документов

    Газета:

  • Microsoft для российских разработчиков: практика с элементами фундаментальности

    10 марта

  • HadoopDB: архитектурный гибрид технологий MapReduce и СУБД для аналитических рабочих нагрузок

  • Классификация OLAP-систем вида xOLAP

  • BGP. Три внешних канала. Балансировка исходящего и входящего трафиков

    Газета:

  • Что мы знаем об iPhone 4G?

    17 февраля

  • MapReduce и параллельные СУБД: друзья или враги?

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

  • Системологический подход к декомпозиции в объектно-ориентированном анализе и проектировании программного обеспечения

    Газета:

  • Эволюция Wine

    3 февраля

  • Дом на песке

  • Реальное переосмысление "формальных методов"

  • Интервью с Найджелом Пендзом

    Газета:

  • iPad. Первый взгляд на долгожданный планшет от Apple

  • Я не верю в iPad [an error occurred while processing this directive]

    20 января

  • SQL/MapReduce: практический подход к поддержке самоописываемых, полиморфных и параллелизуемых функций, определяемых пользователями

  • Данные на лету: как технология потокового SQL помогает преодолеть кризис

    Обзоры журнала Computer:

    2 декабря

  • Сергей Кузнецов. Год эпохи перемен в технологии баз данных

    18 ноября

  • Генерация тестовых программ для подсистемы управления памятью микропроцессора

  • Сравнительный анализ современных технологий разработки тестов для моделей аппаратного обеспечения

    Все публикации >>>


    [an error occurred while processing this directive]
  • [an error occurred while processing this directive] [an error occurred while processing this directive]
    Купить сотовые телефоны в М.Видео
    Отличные цены на сотовые телефоны. Бесплатная доставка. Заказ в интернет-магазине и по телефону (495) 644-28-51
    www.mvideo.ru [an error occurred while processing this directive]

    Регистрация доменов в зонах .ru, .com, .net. Компания Rusonyx.

    IT-консалтинг Software Engineering Программирование СУБД Безопасность Internet Сети Операционные системы Hardware

    [an error occurred while processing this directive]
    Информация для рекламодателей PR-акции, размещение рекламы — тел. +7 495 6608306, ICQ 232284597 Пресс-релизы — pr@citforum.ru
    Послать комментарий
    Информация для авторов

    Редакция раздаёт котят!

    Rambler's Top100 TopList liveinternet.ru: показано число просмотров за 24 часа, посетителей за 24 часа и за сегодня This Web server launched on February 24, 1997
    Copyright © 1997-2000 CIT, © 2001-2009 CIT Forum
    Внимание! Любой из материалов, опубликованных на этом сервере, не может быть воспроизведен в какой бы то ни было форме и какими бы то ни было средствами без письменного разрешения владельцев авторских прав. Подробнее...
    [an error occurred while processing this directive]


    [an error occurred while processing this directive] [an error occurred while processing this directive] реклама:
    Производство и продажа серверов | забронировать гостиницу Санкт Петербурга | платный хостинг | IBM Rational. Аналитика и инструменты
    [an error occurred while processing this directive] [an error occurred while processing this directive]