|
Документ взят из кэша поисковой машины. Адрес
оригинального документа
: http://www.cplire.ru/Lab144/1251/04010000.html
Дата изменения: Mon Sep 24 14:54:40 2007 Дата индексирования: Tue Oct 2 01:38:35 2012 Кодировка: Windows-1251 Поисковые слова: п п п п п п п п п п п п п п п п п п п р п р п р р п п р п п р п п р п п р п п р п п р п п р п п р п п р п п р п п р п п р п п р п п р п п р р п р п п р п |
ЛОГИЧЕСКОЕ ПРОГРАММИРОВАНИЕ ОТКРЫТЫХ СИСТЕМА.А.Морозов, Ю.В.Обухов, А.Я.Олейников(Доклад отредактирован)Для программирования открытых информационных систем [1], отличительным признаком которых является принципиальная непредсказуемость результатов взаимодействия компонентов, представляется целесообразным использовать идеи и методы логического программирования, которое, в дополнение к обычной операционной семантике, поддерживает также декларативную семантику, инвариантную по отношению к возможному недетерминизму функционирования открытой системы. ВВЕДЕНИЕОткрытыми называют такие информационные системы, для которых характерны развитие и модификация в процессе эксплуатации, противоречивость обрабатываемой информации, децентрализованное принятие решений [1]. Одним из принципиальных отличий открытых систем является невозможность путем логических рассуждений предсказать результаты взаимодействия некоторых ее компонентов и, тем более, характер поступающей извне информации [7,8]. Представляется, что для программирования таких систем необходимы языки, обладающие четкой декларативной семантикой, инвариантной по отношению к возможному недетерминизму функционирования открытой системы. Такими языками, в частности, являются логические языки программирования. 1. ПРОБЛЕМЫ, КОТОРЫЕ НЕОБХОДИМО РЕШИТЬК сожалению, распространенные в настоящее время логические языки (различные версии Пролога и другие) не соответствуют идеологии открытых систем по целому ряду весьма важных признаков, что позволило вообще поставить под сомнение пригодность логических языков для программирования открытых систем [1]. Основными проблемами являются:
2. ПРИНЦИП ДЕЦЕНТРАЛИЗОВАННОГО ДОКАЗАТЕЛЬСТВАПонятно, что логическая система, предусматривающая постоянное поступление новой информации, обязательно должна обеспечивать возможность отказа от построенных ранее заключений, если их предпосылки в какой-то момент отвергаются. Однако никак невозможно согласиться с мнением [2], что модифицируемые рассуждения не могут быть формализованы в рамках дедуктивных систем логики из-за присущего таким системам свойства монотонности. Соответствующий формализм может быть построен, например, на основе принципа децентрализованного доказательства теорем [4], обеспечивающего строгую корректность рассуждений. Отправной точкой разработки принципа децентрализованного доказательства послужила акторная модель вычислений Хьюитта [6]. Согласно этому принципу, составными частями доказываемой теоремы (в логической программе) считаются "акторы" - выделенные подцели теоремы - и общие переменные, связывающие акторы между собой. Доказательства любых акторов могут быть построены повторно (не передоказывая другие акторы) с целью согласования акторов, взаимодействующих через общие переменные. Например, интерактивный режим с этой точки зрения рассматривается как процесс изменения человеком условий решаемой задачи и повторного доказательства машиной соответствующих подцелей. Заметим, что предложенный подход свободен от недостатков немонотонных логических систем, таких как необщезначимость (в классическом смысле) выводимых формул, зависимость результата от порядка применения правил вывода и повышенная вероятность зацикливания в определениях и интерпретации отношения выводимости. 3. РЕАЛИЗАЦИЯ АКТОРНОГО МЕХАНИЗМА В ЛОГИЧЕСКОМ ЯЗЫКЕРассмотренный принцип был успешно реализован в логическом языке [4,5] в качестве специального акторного механизма, позволяющего доказывать повторно некоторые выделенные ("акторные") подцели логической программы. Достоинством этого механизма является то, что он дает возможность строго корректным образом использовать в логических программах разрушающее присваивание и при этом не ухудшает полноту логического вывода. Предикат разрушающего присваивания ':=' в этом языке интерпретируется просто как логическое утверждение, истинное, если возможно повторное (с самого начала) доказательство некоторых подцелей программы, зависевших от старых значений общих переменных. Более подробное обсуждение акторного механизма, а также средств определения иерархии классов и динамического построения пространства поиска можно найти в [4,5]. 4. ПРОБЛЕМА ФРЕЙМАИнтересно, что принцип децентрализованного доказательства может рассматриваться в качестве решения проблемы фрейма [3], сущность которой заключается в том, что в процессе развития открытой системы, когда появляются новые правила модификации ее состояния, необходимо каким-то образом определять также соответствующие этим правилам инварианты (аксиомы фреймов). В случае использования в логической программе акторного механизма такими инвариантами становятся все предложения, использованные для построения модифицируемых структур данных, а семантика этих инвариантов соответствует декларативной семантике чистого Пролога. Необходимо отметить, однако, что практическая возможность модифицировать структуры данных в ходе децентрализованного доказательства вовсе не обеспечивает, в общем случае, возможность повторного использования оперативной памяти компьютера. На самом деле, требование полноты доказательства теоремы приводит к необходимости сохранять все структуры данных, которые могут стать доступными в случае отката программы. Таким образом, децентрализованные доказательства можно назвать лишь частичным решением проблемы фрейма, хотя, как показали практические эксперименты с реализацией логического языка, в программах, теряющих в некоторые моменты времени полноту логического вывода (важный частный случай - имитация сетей взаимодействующих агентов), удается организовать простой и достаточно эффективный алгоритм управления памятью. 5. ИМИТАЦИЯ СЕТЕЙ ВЗАИМОДЕЙСТВУЮЩИХ АГЕНТОВВажнейшим требованием, предъявляемым к языку программирования открытых систем, является возможность асинхронного взаимодействия с "внешним миром", то есть, поддержка акторной модели вычислений. Исторически сложилось так, что Пролог не использует эту модель, хотя в последнее время появилось очень много логических языков (Concurrent Prolog, DLP, L2||O2, NUML и другие), обеспечивающих такие возможности. Опыт разработки логического языка [4,5] показал, что имеют право на существование по крайней мере два подхода к решению этой задачи. Первый из них можно обозначить формулой "взаимодействующий агент = набор предложений языка, сообщение = вызов предиката", второй - "взаимодействующий агент = акторная подцель программы, сообщение = изменение значения глобальной переменной". Этим моделям можно условно поставить в соответствие объектно-ориентированную и акторную модели в процедурных языках программирования, однако выявление строгой логической семантики существенно уменьшило "общность" обоих подходов (первый не обеспечивает возможность модификации значений переменных, а второй не позволяет структурировать пространство поиска), так что соответствующие механизмы оказались в итоге полностью "ортогональными" друг другу и были независимо включены в определение языка. СПИСОК ЛИТЕРАТУРЫ
Back to Research Divisions
|