автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.11, диссертация на тему:Логическое программирование в ограничениях: семантический подход

РГБ ОА

и

ВЫЧИСЛИТЕЛЬНЫЙ ЦЕНТР СИБИРСКОГО

ОТДЕЛЕНИЯ РАН

На правах рукописи

МАНЦИВОДА Андрей Валерьевич

С

УДК 519.68

Логическое программирование в ограничениях: семантический подход

Специальность 05.13.11 - Математическое и программное обеспечение вычислительных машин, комплексов, систем и

сетей

Автореферат диссертации на соискание ученой степени доктора физико-математических наук

Новосибирск - 1995

Работа выполнена в Иркутском государственном университете

Официальные оппоненты: доктор физико-математических наук, профессор ГОНЧАРОВ С.С.

доктор физико-математических наук, профессор ПОТТОСИН И.В.

доктор физико-матеиатических наук, профессор РЫБАКОВ В.В.

Ведучая организация: Институт прикладной математики и«. Келдыша

Защита состоится 25 апреля 1995г. в 15.00 часов

на заседании диссертационного совета Д 002.10.02 при Вычислительном центре СО РАН по адресу: проспект Академика Лаврентьева, 6

С диссертацией мохно ознакомиться в читальном зале библиотеки Вычислительного центра СО РАН

Автореферат разослан ___1995г.

Ученый секретарь диссертационного совета

Г.И. Забиняко

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

Методы исследования. Настоящая работа использует средства двух активно развивающихся областей прикладной логики. Во-первых, ото семантическое (Е-) программирование, предложенное в работах ЮЛ. Ершова, С.С. Гончарова и Д.И. Свириденко1 2. Во-вторых, это логическое программирование в ограничениях, развитое в работах Ж.-Л. JIacce, Джафара, В. Сарасвата, II. ван Хентенрика3 и других.

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

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

1Ю.Л. Ершов. Е-определимость на допустим¡,гх .множествах. ДАН, 285(1985), 1, 792-794

2С.С.Гончаров, Д.И. Сиириденко. ^-программирование Вычислительные системы, 107, Новосибирск, 1985, с.24-51.

3См., напр., P. Van Henteiiryck. Constraint Satisfaction in Logic Programming. The MIT Press, Cambridge, 1989.

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

Апробация работы. Результаты работы докладывались на международных конференциях по математической логике, прикладной логике, логическому программированию и других. Было сделано 2 приглашенных (PLILP'93, Эстония, NSL'94, Япония), 6 пленарных и несколько секционных докладов. Доклады делались на семинарах ИМ СО РАН, МГУ, ИПМ, КГУ, ИрВЦ, ИГУ и многих других. По результатам исследований была проведена серия докладов в Немецком центре искусственного интеллекта (Кайзерслаутерн, 1992).

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

Публикации. Результаты диссертации опубликованы в работах [1-27].

Структура и объем работы. Диссертационная работа изложена на 183 страницах и состоит из введения, четырех глав, заключения и списка литературы (150 наименований).

СОДЕРЖАНИЕ РАБОТЫ

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

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

В первой главе диссертации дается обоснование метода. В качестве теоретической основы используются идеи семантического (£-) программирования. Б первом пункте главы даны постановка проблемы и краткий обзор результатов. Во втором пункте анализируются свойства одного из ключевых понятий - конечных областей (доменов).

В третьем пункте вводится понятие Е-программы (являющейся теоретическим аналогом программ, написанных на Флэнге) и описывается ее денотационная семантика. Пусть сг является множеством функциональных и предикатных символов, a Ji - модель сигнатуры а. Расширим а множеством новых предикатных символов {pi,• ■ ■обозначив сг* = a U {pi,... ,Рк}- Новые предикатные символы будут обозначать предикаты, определенные E-npoi раммами.

Определение 1 (Терм) Перемениая и константа термы. Если ¿1,... ,tn - термы п f п-местный функциональный символ, то /(¿1,... ,t„) ~ терм.

Определение 2 (Е-формула) Атомарная формула выражение вида p(ti,.. ., in), где р - п-мссгиып предикатный символ, a t{ - термы. Мы говорим, что р предикатный символ этой формулы.

(i) Атомарная формула есть Е-формула;

(ii) если F и G T,-формулы и H - формула сигнатуры а без неограниченных: кванторов, тогда F ¿i G, FVG, Н —+ F, (Б.Г G y)F, (V;r е y)F, (3x)F есть 1,-формулы.

F является формулой сигнатуры a (а*) если все функциональные и предикатные символы, входящие в F, принадлежат <т (a"). Обозначим через Var(F) множество всех свободных переменных F. Выражение Р <£> F назовем определением предиката, если Р - атомарная формула с предикатным символом р G a* \ а и F - Е-формула сигнатуры о* такая, что Var(F) С Var(P). И-программа есть множество {Di,..., Dk, Fi,...,Fm} такое, что Di есть определения предикатов, a Fi - Е-формулы. Fi играют роль запросов (ограничений). Мы будем обозначать программы Г, Д,.. ..

Понятие истинности формулы на модели 3? определяется как обычно. Поскольку переменные в ^-формулах могут обозначать не только элементы модели 9?, но также и множества элементов, для определения (денотационной) семантики Е-формул необходимо расширить модель 3?. Это расширение достигается введением понятия наследственно конечной надстройки над К4.

Теорема 1 ([1]) Пусть - модель сигнатуры сг. Тогда для любой Е-программы Г сигнатуры а" соответствующий оператор 'Р[- имеет наименьшую неподвижную точку.

Г(Л) будет обозначать расширение 9?, в котором все р, £ a*\cr определены как наименьшие неподвижные точки 7-Y-

В четвертом пункте вводится базовое Е-исчисление, описывающее поведение Е-формул. Выводимыми объектами в Е-исчисленин являются только замкнутые формулы. Правила

4 J.Barwise. Admissible Sets and Structures. Springer Verlag, 1975.

вывода:

(правило дизъюнкции)

F G

FV G FWG

(правило конъюнкции)

F_G

Ft G

(правила импликации)

G JtfiF

F —► G F-+G

(правило для встроенных предикатов)

true

Р

зе |= р

Р атомарная формула со встроенным предикатом; Р не содержит свободных переменных.

(правила \/-ограничения)

true

(Vi е0)F

(Ух £ {iu...,lm})F(х) F(I) (Vz e {t,tu---,tm})F(x)

(3x)F{x)

F(t)

P(t)

если (p(x) О F(r)) принадлежит программе.

Выводимость формулы F ио программы Г определяется стандартно и обозначается Г Ь^ F. Индукцией по построению неподвижной точки и наследственно-конечной надстройки доказывается следующая

Теорема 2 ([1]) Для любой замкнутой Е-формулы F, выполняется:

Г Не F тогда и только тогда, когда, Г(Э?) f=F.

В пятом пункте первой главы рассматривается модификация концепции сс-программирования, разработанной В. Сарасватом0. Сс-программирование является методологической основой построения процедурной семантики Е-программ.

Следующие пункты посвящены построению абстрактной Е+-машипы, вычисляющей Е-программы. В шестом пункте

5V.Saraswat. Concurrent Constraint Programming, the MIT Press, 1993, 486p.

вводится первая версия машины. Эта машина имеет переборную природу и близка по семантике параллельному Прологу. Седьмой пункт посвящен общей стратегии выполнения программ. В пункте 8 диссертации вводится абстрактная Е+-машина. Эта машина описывает "реальную" процедурную семантику Е-программ. Е^-машина является частным случаем сс-машины. 2-формулы играют в £+ -машине роль параллельных процессов. С логической точки зрения эти формулы представляют собой ограничения, наложенные на искомое решение. Память машины содержит Е-программу и логически равносильна конъюнкции формул из этой программы. В процессе вычислении -машина преобразует свою память до тех пор, пока ей не удается накопить достаточно информации для получения решения. Информация о значениях переменных накапливается с помощью добавления подстановочных равенств вида X — I, где X - переменная, а ( - терм.

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

Поскольку память

Е+ -машины содержит Е-программы, ее содержимое мы также будем обозначать с помощью букв Г и Д. Через {Г | Г} будем обозначать память Г, расширенную формулой Кроме того нам понадобится следующее

Определение 3 Наоовем X — /] V ... V .V = доменовой

дпвъюнкиней для переменной X.

Приведем несколько примеров правил переходов £+-машины (полностью они описаны в диссертационной работе):

Правила замыкания (3-удаление)

{(3X)F | Г} - {F | Г}

если в Г нет формул, в которые входит X (иначе, X должна быть переименована)

{(ЗХ g {h, ■ . • ,tk})F | Г} ~ {(X = h V ... V X = tk), F | Г}

(то есть ограниченный квантор заменяется доменовой дизъюнкцией);

{{ЗХ е 0)F(X) | Г} ^ {false} (ask-операция: —»-удаление)

Г К F__{F 1 Г) h false

{F — G | Г} {G | Г} {F G j Г} Г

(локальная совместность)

А С Г {F | A}h {false}

{FvG | | Г}

(конструктивная дизъюнкция — идея)

А С Г {F 1 А} А Лх {(? j А} А Л2 {F V G | r}b»{fvG | Г}и(Л!ПЛ2)

В последних двух правилах Д обозначает множество доме-ноаых дизъюнкций для всех переменных, входящих в F V G. Символ обозначает оператор замыкания, а Г U Д и Г П Д обозначают неформальные понятия объединения и пересечения информации, точное определение которых приведено в диссертации и опущено здесь в связи с: их громоздкостью.

Ключевое свойство правил замыкания заключается в том, что они вместе определяют в Е+-машине отношение непосредственной выводимости К

Правило выбора (V-удаление)

{F V G | Г} >-> {G | Г} Мы не различаем F V С и G V /'.

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

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

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

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

В десятом пункте рассматриваются проблемы полноты и корректности абстрактной £+-машины.

Определение 4 (реализуемость) Пусть Г = {С\,... , Оь, ,. .., Пщ} - память -машины, где -Е-формулы, а О, - определения предикатов. Будем говорить, что Г является Е+-реализуемой, если существует корректная последовательность преобразований Е+ -машины с памятью Г, приводящая к машине с памятью {Х\ = —

Т/., 1)\,.. ., От}, где Х\ = Тх,. ..,Хк = Тк — подстановочные равенства, причем не более одного на каждую переменную. Формула У Е + -реализуема в Е-программе Г, если множество {У | Г) -реализуемо.

Следующая теорема показывает, что Е+-машина корректна:

Теорема 3 (о корректности [10]) Пусть Г - множество определений предикатов (программа), а Р - Е-формула. Тогда, если {У | Г} Е+-реализуемо, то Г Ье У.

Проблема полноты может быть сформулирована следующим образом:

Определение 5 Пусть Г = {])г,... ,Пк}. Е+-машина является полной,

если для любой £ -программы {С1.. .., 0-,п . !)\.... . } выполняется следующее утверждение: если Г(^) |= Сп & • • • & то программа. {С [,.. ., Ст, ,.. ., О к } -реализуема.

Следующая теорема описывает очень важный случай, когда Е+-машина является полной:

Теорема 4 полнота [10]) Если ¡1 конечная модель, то Е-формула Е+ -реализуема программой Г тогда я только тогда, когда Г(Й) |= Г.

Эта теорема позволяет использовать данный метод для решения конечномерных комбинаторных задач.

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

Во второй главе рассматривается функционально-логический язык Флэнг [3, 16], являющийся конкретным воплощением абстрактного Е-языка. Флэнг предназначен для обработки символьной информации и решения задач высокой комбинаторной сложности. Программы на Флэнгс являются примером Е-программ, поэтому денотационная и процедурная семантики Фланга описываются с помощью £+-

машины. В главе дается описание основных идей, заложенных во Флэнг.

В пункте 1 главы дается описание синтаксиса и структуры Флэнг-программ. Во втором пункте описывается функционально-логическое ядро языка и приводится ряд определений на, Фланге.

Фланг основан на идее яедетермшшровашгойфункции. Недетерминированные функции являются обобщением "обычных" функций по следующим направлениям:

• допускается вычисление функций с неуточненными аргументами;

• при вычислениях используется стратегия вычислений "в глубину": если система не может редуцировать цель, она возвращается и ищет иные альтернативные пути вычислений.

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

Примером "чисто" функциональной программы может служить определение факториала:

О! 1;

X! <= Х>0, X * (Х-1) ! ;

Поскольку Пролог является подмножеством Флэнга, на Флэнге легко пишутся логические программы. Однако обычно наиболее удобно использовать смешанный стиль написания программ. Простой пример смешанной функционально-логической программы - определение функции предок:

родитель(борис, егор) ; родитель(борис, федор); родитель(федор, роман);

предох(Х, У) родитель(X, У), [X, У];

предох (X, У) -<= родит ель (X, Ъ) , [X ¡предох(г, У)];

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

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

В этом же пункте вводится понятие активной дизъюнкции [1, 15, 23], которое позволяет обобщит!» эффективную

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

В четвертом пункте рассматривается хорошо известная и эффективная стратегия - принцип "чем хуже, тем раньше" (the first fail principle) 6. Его основная идея заключается в том, что при поиске решения на каждом шаге следует выбирать тот объект, который наиболее жестко "скован" имеющимися в памяти ограничениями. В пункте этот принцип обобщается на произвольные дизъюнкции.

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

В восьмом пункте показывается, как стратегия глубокого возврата, введенная в первой главе (пункт 11), реализуется во Фланге. Приводятся результаты тестирования стратегии, демонстрирующие ее эффективность.

В девятом пункте вводится понятие прооранного возврата [1]. Основная идея, рассматриваемая в этом пункте, состоит в том, чтобы сделать управление бэкрэкингом доступным программисту. Дается описание того, как прозрачный возврат реализован во Флэнге.

6J.Bitncr, Е.М. Rein gold. Backtrack Programming Techniques. 1975, 18:651-655.

Наконец, в десятом пункте рассматривается ряд вспомогательных средств, используемых в языке.

Третья глава посвящена технике реализации Фланга. Нами проводились исследования как в области реализации функционально-логического ядра Фланга [2, 13, 18, 19 и др.], так и всего языка, включая ограничения, коночные области и активные дизъюнкции [20, 24, 7, 11 и др.]. Принципиальному повышению производительности Фланг-системы способствовали две ключевые идеи, развитые в рамках этих исследований. Во-первых, была разработана техника глобального анализа программ [19]. Идея заключается в том, что перед компилированием Флэнг-программы осуществляется ее "вычисление" на некоторой абстрактной области данных. Информация, полученная в процессе этого "вычисления". используется во время компиляции и позволяет резко повысить эффективность продуцируемого кода. Насколько нам известно, компилятор функционально-логического ядра Фланга, реализованный с использованием глобального анализа, продуцирует самый быстрый код среди всех систем логического программирования, работающих на IBM PC (в частности, некоторые Флэнг-программы транслируются этим компилятором даже в более быстрый код, чем кол соответствующих программ на Паскале, оттранслированных в системе TurboPascal). Основная же проблема глобального анализа состоит в нахождении компромисса между эффективностью самого процесса анализа и количеством информации о программе, которую можно в этом процессе получить.

Вторая идея, развитая нами - новый способ восстановления значений переменных в процессе бэктрэкинга [20]. Этот способ принципиально отличается от механизма возврата в абстрактной машине Уоррена (машина Уоррена яв-

7D.H.D.Warren. An Abstract Prolog Instruction Set. Technical Note 309, SRI International, Menlo Park. С A, October 1983.

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

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

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

сивные.

Идея нашего метода восстановления заключается в том, чтобы помечать переменные (в общем случае - объекты, под-

На рисунке: если процесс поиска решения находится в вершине *, то альтернативы Ь и с! живые (причем, с! - активная), а а и с - пас-

• *

вергающиеся изменениям) именем (номером) ак'1'инной альтернативы. Теперь в процессе восстановления (бэктрекинга), для восстановления переменных не надо делать ничего. Просто при использовании переменной нужно проверить, именем какой альтернативы она помечена. Если эта альтернатива -живал, то переменная до сих пор "испорчена''. Ксли же это имя пассивной альтернативы, то переменная свободна. Лемма ([7]) Метод альтерната янляатся корректным.

Глава 3 диссертационной работы, посвященная методам реализации Флэнга, состоит из восьми пунктов. В первом пункте главы вводятся основные понятия и модификация абстрактной машины Уоррена, которую мы использовали для реализации функционально-логического ядра Флэнга. Второй пункт посвящен глобальному анализу Флэнг-программ и основным этапам компиляции. Представлены результаты сравнений эффективности Фланг-компилятора с компиляторами Aritv и Turbo Пролога. Несмотря на. то, что Флэнг содержит Пролог как подмножество, скорость выполнения Флэнг-программ в среднем на порядок выше соответствующих Пролог-программ, оттранслированных компилятором Arity, и от 1.2 до 7 раз (на разных примерах) быстрее кода Turbo Пролога.

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

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

В последней четвертой главе приводятся результаты апробирования возможностей нашей логической системы для решения классических и практических задач высокой сложности. Демонстрируется, что компактность и гибкость Флэнг-программ, решающих сложные комбинаторные задачи, не противоречат эффективности процесса поиска решения. Например. описываемая в пункте 1 программа, решающая задачу о п ферзях (которые должны быть расставлены на доске пХп так, чтобы не бить друг друга) состоит всего из нескольких строк. Тем не менее, она очень эффективна. В частности, эта программа расставляет 420 ферзей на доске 420 X 420 за 2 секунды. Количество ограничений в этом случае составляет 264600. Во втором пункте рассматривается еще одна классическая комбинаторная проблема - минимальной раскраски графа. П оказывается, что Флэнг-система способна раскрашивать за реальное время графы, размер и структура которых соответствуют сложным практическим задачам.

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

238В). Дело осложняется тем, что формулировки ограничений, наложенных на решение, имеют сложную логическую структуру и поэтому не поддаются решению н рамках стандартных методов. Заметим, что именно попытки решить эту гзадачу привели нас к понятию активной дизъюнкции, поскольку известными средствами нам решить ее никак не удавалось. И только с использованием активных дизъюнкций и обобщенного принципа :'чем хуже, тем раньше" задача была полностью решена.

В пункте 4 рассматривается хорошо известная задача о строительстве моста, которая состоит в поиске оптимального расписания строительства. Она рассматривалась многими исследователями, в частности. II. ван Хентенриком. В первоначальной формулировке эта задача, не представляет больших трудностей, поэтому мы рассматривали ее усложненный вариант. Этот вариант нам также удалось решить лишь с помощью активных дизъюнкций [1].

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

Диссертационная работа завершается заключением и библиографическим списком.

Основными результатами диссертационной работы являются:

1. На базе семантического программирования построена единообразная теория широкого класса, языков логического программирования в ограничениях.

2. Построена эффективная процедурная семантика Е-программ.

3. Разработан функционально-логический язык Флэнг, работающий в ограничениях.

1. Разработан ряд эффективных стратегий поиска вывода: обобщенная локальная совместность, глубокий возврат и другие.

5. Разработана техника компиляции логических программ, основанная на явной нумерации точек выбора.

Огромное влияние на автора оказал А.И.Кокорин. Автор также благодарен за поддержку О.В.Васильеву, С.С.Гончарову, И.В.Горской, А.С.Морозову, Н.А.Перязеву, И.В.Поттосину, С.В.Яблонскому и Ю.И.Янову. Многие результаты были бы невозможны без совместной работы в научно-исследовательской группе по логическому программированию Иркутского университета. Автор признателен И.С. Абдрахимову, А.И. Вайману и В.А. Петухину.

РАБОТЫ АВТОРА ПО ТЕМЕ ДИССЕРТАЦИИ

1. A.B. Манцивода. £-программированиеи проблемы дискретной оптимизации. Иркутск, 1994, 245с.

2. A.Ii. Маннивода, В.А. Петухин. Компилятор функционально-логического языка Флэнг. - Выч. системы, вып. 146, 1992, с. 61-75.

3. A.B. Манцивода. Флэнг - язык искусственного интеллекта. Кибернетика, 1993, No. 5, с.350-367.

4. A.B. Манцивода. Компилятор функционально-логического языка Фланг.- Выч. системы, т.146, 1992, с.61-75.

5. A.B. Манцивода. Комбинаторные проблемы и логическое программирование. Тезисы 10-ой Всероссийской конференции по по проблемам теор. кибернетики, 1993, Саратов, с.120-123.

6. И. Абдрахимов, A.B. Манцивода. Полнота локальной совместности. Тезисы международной конф. по математической логике, 199-1, Новосибирск, с.3-5.

7. A.B. Манцивода. А.И. Вайман. Восстановление переменных при поиске в глубину. Тезисы международной конф. по математической .логике, 1994, Новосибирск, с.35-37.

8. II. Абдрахимов, A.B. Манцивода. Активные дизъюнкции во Фланге. В: "Компьютерная алгебра, логика и управление интеллектуальными системами'', Иркутск 1994, т.1, с. 158-17-1.

9. A.B. Манцивода. Ограничения в логическом программировании. В: Алгебра, логика и приложения.- Иркутский университет, 1994. с.150-181.

10. И.С. Абдрахимов, A.B. Манцивода. Полнота и корректность Е-.vra шины. Ii: Алгебра, логика и приложения.-Иркутский университет. 1994. с. 1 -г>()-181.

11. A.B. Манцивода. А.И. Вайман. Компиляция дизъюнктивных ограничении. В: Алгебра, логика и приложения.- Иркутский университет. 1994. с. 185-203.

12. A.B. Манцивода. Флонг-проект. Препринт Хо.02-03/9-3, Иркутский университет, 1993. 27с.

13. A.B. Манцивода, В. Пстухин. Компиляции языка Флэнг. Препринт, Иркутский университет, 1990. 30с.

14. A.B. Манцивода. ФЛЭНГ: функционально-логический язык программирования. Препринт, Иркутский университет, 1990, 28с.

15. A. Mantsivoda. Disjunctive Constraints as Generalization of Finite Domains. NATO ASI Symp. on Constraint Programming (eds. B.Mayoh, J.Penjam, E.Tyugu). Parnu, Estonia, August 1993, p.138-147.

16. A. Mantsivoda Fiang: A Functional-Logic Language. Lecture Notes in Comp.Sei., 567, Processing Declarative Knowledge (eds. H.Boley and M.M. Richter), Springer,

1992, p.257-270.

17. A. Mantsivoda. Fiang and its Implementation. PLILP'93, Lecture Notes in Comp. Sei., 714, Springer, 1993, p. 151 -16«.

18. A. Mantsivoda, V. Petukhin. Compiling Fiang.- Proceedings of 2nd Russian Conference on Logic Programming, St.Petersburg, 1991, number 592 in Lect. Notes in Comp.Sei., pp. 286-293, Springer, 1992.

19. A. Mantsivoda, V. Petukhin Compiling Fiang II. Lecture Notes in Comp.Sei., 641, 1992, Compiler Construction (eds. U.Kastens, P.Pfahler), p.297-311.

20. A. Mantsivoda, V. Petukhin, A. Weimann. Memory Management of Constraints in Fiang. Proc. of 10th Int. Conf on Logic Programming, (ed. by D.S.Warren), MIT Press,

1993, p.633-646.

21. I. Abdrakhimov and A. Mantsivoda. Intelligent Backtracking in Fiang. International Workshop on Constraint Processing at CSAM'93, St. Petersburg (ed. M. Meyer), DFKI Document D-93-14, p.215-221 DFKI Kaiserslautern, Germ a ny.

22. A. Mantsivoda. Flung: the Main Ideas and Features. COLOG'88, Tallinn. 1988, Part II. p. 1 о 1-158.

23. A. Mantsivoda. Disjunctive Constraints and Unite Domains. Препринт No.25-07/93, Иркутский университет, 1993. Юр.

24. A. Mantsivoda. Avoiding Trailing in Logic Programming. Препринт No.15-07/93, Иркутский университет. 1993. Юр.

25. A. Mantsivoda. Logic and Large Combinatorial Problems (invited talk).- Workshop on Non-standard Logics and Logical Aspects of Computer Science, Kanazawa, Japan, December 5-8, 1994, p.24.

26. A. Mantsivoda, V. Petukhin. Implementation of 1be Functional-Logic Language Flung. Lecture Notes in Comp.Sci., 567, Processing Declarative Knowledge (eds. H.Boley and M.M. Richter). Springer. 1992, p.420-421.

27. A. Mantsivoda Flang-system: a New Version. Lecture Notes in Comp.Sci., 841. Springer. 1994. p.467-468.