ЛОГИЧЕСКОЕ ПРОГРАММИРОВАНИЕ ОТКРЫТЫХ СИСТЕМ

А.А.Морозов, Ю.В.Обухов, А.Я.Олейников

(Доклад отредактирован)

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

ВВЕДЕНИЕ

Открытыми называют такие информационные системы, для которых характерны развитие и модификация в процессе эксплуатации, противоречивость обрабатываемой информации, децентрализованное принятие решений [1]. Одним из принципиальных отличий открытых систем является невозможность путем логических рассуждений предсказать результаты взаимодействия некоторых ее компонентов и, тем более, характер поступающей извне информации [7,8]. Представляется, что для программирования таких систем необходимы языки, обладающие четкой декларативной семантикой, инвариантной по отношению к возможному недетерминизму функционирования открытой системы. Такими языками, в частности, являются логические языки программирования.

1. ПРОБЛЕМЫ, КОТОРЫЕ НЕОБХОДИМО РЕШИТЬ

К сожалению, распространенные в настоящее время логические языки (различные версии Пролога и другие) не соответствуют идеологии открытых систем по целому ряду весьма важных признаков, что позволило вообще поставить под сомнение пригодность логических языков для программирования открытых систем [1]. Основными проблемами являются:

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

2. ПРИНЦИП ДЕЦЕНТРАЛИЗОВАННОГО ДОКАЗАТЕЛЬСТВА

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

Соответствующий формализм может быть построен, например, на основе принципа децентрализованного доказательства теорем [4], обеспечивающего строгую корректность рассуждений.

Отправной точкой разработки принципа децентрализованного доказательства послужила акторная модель вычислений Хьюитта [6]. Согласно этому принципу, составными частями доказываемой теоремы (в логической программе) считаются "акторы" - выделенные подцели теоремы - и общие переменные, связывающие акторы между собой. Доказательства любых акторов могут быть построены повторно (не передоказывая другие акторы) с целью согласования акторов, взаимодействующих через общие переменные. Например, интерактивный режим с этой точки зрения рассматривается как процесс изменения человеком условий решаемой задачи и повторного доказательства машиной соответствующих подцелей.

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

3. РЕАЛИЗАЦИЯ АКТОРНОГО МЕХАНИЗМА В ЛОГИЧЕСКОМ ЯЗЫКЕ

Рассмотренный принцип был успешно реализован в логическом языке [4,5] в качестве специального акторного механизма, позволяющего доказывать повторно некоторые выделенные ("акторные") подцели логической программы. Достоинством этого механизма является то, что он дает возможность строго корректным образом использовать в логических программах разрушающее присваивание и при этом не ухудшает полноту логического вывода. Предикат разрушающего присваивания ':=' в этом языке интерпретируется просто как логическое утверждение, истинное, если возможно повторное (с самого начала) доказательство некоторых подцелей программы, зависевших от старых значений общих переменных.

Более подробное обсуждение акторного механизма, а также средств определения иерархии классов и динамического построения пространства поиска можно найти в [4,5].

4. ПРОБЛЕМА ФРЕЙМА

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

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

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

5. ИМИТАЦИЯ СЕТЕЙ ВЗАИМОДЕЙСТВУЮЩИХ АГЕНТОВ

Важнейшим требованием, предъявляемым к языку программирования открытых систем, является возможность асинхронного взаимодействия с "внешним миром", то есть, поддержка акторной модели вычислений. Исторически сложилось так, что Пролог не использует эту модель, хотя в последнее время появилось очень много логических языков (Concurrent Prolog, DLP, L2||O2, NUML и другие), обеспечивающих такие возможности.

Опыт разработки логического языка [4,5] показал, что имеют право на существование по крайней мере два подхода к решению этой задачи. Первый из них можно обозначить формулой "взаимодействующий агент = набор предложений языка, сообщение = вызов предиката", второй - "взаимодействующий агент = акторная подцель программы, сообщение = изменение значения глобальной переменной". Этим моделям можно условно поставить в соответствие объектно-ориентированную и акторную модели в процедурных языках программирования, однако выявление строгой логической семантики существенно уменьшило "общность" обоих подходов (первый не обеспечивает возможность модификации значений переменных, а второй не позволяет структурировать пространство поиска), так что соответствующие механизмы оказались в итоге полностью "ортогональными" друг другу и были независимо включены в определение языка.

СПИСОК ЛИТЕРАТУРЫ

1. Хьюитт К. Открытые системы // Реальность и прогнозы искусственного интеллекта. - М.: Мир, 1987. - С.85-102.
2. Тей А., Грибомон П., Луи Ж., Снийерс Д., Водон П., Гоше П., Грегуар Э., Санчес Э., Дельсарт Ф. Логический подход к искусственному интеллекту: от классической логики к логическому программированию. - М.: Мир, 1990. - 432с.
3. Маккарти Д. Общность в системах искусственного интеллекта // Лекции лауреатов премии Тьюринга / Под ред. Р.Эшенхерста. - М.: Мир, 1993. - С.299-312.
4. Морозов А.А. Акторный Пролог // Программирование. - 1994. - N5. - С.66-78.
5. Морозов А.А., Обухов Ю.В. Акторный Пролог. Определение языка программирования. - Москва, 1996. - Препринт ИРЭ РАН 2(613) от 14.06.96. - 57с.
   (http://www.cplire.ru/Lab144/index.html)
6. Hewitt C. Viewing Control Structures as Patterns of Passing Messages // Artificial intelligence. - 1977. - V.8. - N3. - PP.323-364.
7. Hewitt C. Open Information Systems Semantics for Distributed Artificial Intelligence // Artificial intelligence. - 1991. - V.47. - N1/3. - PP.79-106.
8. Gasser L. Social Conceptions of knowledge and action: DAI foundations and open systems semantics // Artificial intelligence. - 1991. - V.47. - N1/3. - PP.107-138.

Back to Research Divisions
IRE RAS Homepage