Российская Академия Наук

Институт системного программирования

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

Морозов Алексей Александрович

ЛОГИЧЕСКИЙ АНАЛИЗ ФУНКЦИОНАЛЬНЫХ ДИАГРАММ В ПРОЦЕССЕ ИНТЕРАКТИВНОГО ПРОЕКТИРОВАНИЯ ИНФОРМАЦИОННЫХ СИСТЕМ

05.13.11

математическое и программное обеспечение вычислительных машин, комплексов, систем и сетей

АВТОРЕФЕРАТ

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

Москва - 1998

Работа выполнена в Институте радиотехники и электроники Российской Академии Наук.

Научный руководитель	-	доктор физико-математических наук Обухов Ю.В.
Официальные оппоненты	-	доктор физико-математических наук Жданов А.А.; кандидат технических наук Коновалов С.М.
Ведущая организация	-	Вычислительный центр РАН

Защита состоялась 26 июня 1998 г. в 17 часов на заседании Специализированного Совета Д.200.50.01 по защите диссертаций на соискание учёной степени кандидата наук при Институте системного программирования РАН по адресу:

109004, Москва, ул. Б. Коммунистическая, д. 25.

С диссертацией можно ознакомиться в библиотеке Института системного программирования РАН.

Автореферат разослан 25 мая 1998 г.

Учёный секретарь
Специализированного Совета Д.200.50.01
кандидат физико-математических наук

С.П. Прохоров

Содержание

1. Синтаксис, семантика и проблемы логической интерпретации ФД
2. Метод интерактивного функционального моделирования информационных систем и Акторный Пролог
3. Декларативная и операционная семантика Акторного Пролога
4. Использование Акторного Пролога для анализа ФД информационных систем

Общая характеристика работы

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

Актуальность темы

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

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

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

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

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

Цель и задачи работы

Целью диссертационной работы является исследование и разработка средств логического программирования для анализа ФД в процессе интерактивного проектирования информационных систем.

Для достижения этой цели поставлены и решены следующие задачи:

Разработка логической интерпретации понятий объектно-ориентированного программирования (ООП), отражающей его структурные, динамические и информационные аспекты.
Разработка метода логического анализа ФД в процессе интерактивного проектирования информационных систем.
Разработка объектно- ориентированного логического языка для формализованного описания семантики и анализа ФД.

Методы исследования

В работе использовались аппараты и методы математической логики, логического и объектно-ориентированного программирования.

Научные результаты, вынесенные на защиту

В диссертационной работе получены новые научные результаты:

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

Научная и практическая ценность

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

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

Созданный прототип реализации Акторного Пролога используется для экспериментов с логическим акторным программированием и может служить основой для разработки промышленной версии языка. Результаты работы внедрены в Институте радиотехники и электроники Российской Академии Наук.

Доклады и печатные публикации

Основные положения работы докладывались на первой и второй международных конференциях по логическому программированию в Иркутске (1990г.) и Санкт-Петербурге (1991г.), на 10-й научно-технической конференции "Планирование и автоматизация научных исследований" в Москве (1992г.), на XI международной конференции "Логика, методология, философия науки" в Обнинске (1995г.), на II и IV международных конференциях "Развитие и применение открытых систем" в Петрозаводске (1995г.) и Нижнем Новгороде (1997г.), а также на международной конференции "Дискретные модели в теории управляющих систем" (Красновидово, 1997г.).

По материалам диссертации опубликовано семь печатных работ [1-7]. Результаты диссертации вошли в отчёты по проекту РФФИ 95-01-00822а, проекту ГКНТ "ПИТ" N 05.05.1191, а также ряда хоздоговорных НИР ИРЭ РАН.

Структура и объём диссертации

Диссертация состоит из введения, четырёх глав, заключения и приложений. Объём работы (за исключением приложений) составляет 134 страницы в формате машинописного текста, в том числе 30 рисунков и 2 таблицы. Список литературы содержит 81 наименование.

Краткое содержание работы

1. Синтаксис, семантика и проблемы логической интерпретации ФД

В главе 1 приведён краткий обзор различных видов ФД, обсуждаются семантика ФД и проблемы их логической интерпретации.

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

структурный системный анализ и проектирование (функциональное моделирование) - SA-диаграммы в SADT¹ и IDEF0, диаграммы потоков данных Гейна-Сарсона и др.;
визуальное программирование измерительных информационных систем - диаграммы LabView² и др.

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

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

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

Каждая из этих проблем соответствует отдельной области исследований, со своими задачами и методами их решения.

1.1. Логическая интерпретация объектов и связей

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

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

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

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

1.2. Взаимодействие человека и машины

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

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

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

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

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

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

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

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

1.3. Поддержка согласованности объектов

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

Проблема поддержки согласованности объектов давно изучается в области децентрализованного искусственного интеллекта и нашла отражение в таких подходах как открытые системы искусственного интеллекта⁶, системы поддержки истинности⁷, ограничения целостности баз данных и т.п. В логическом программировании эта проблема обычно не ставится в явном виде⁸ и решается с помощью имитации таких процедурных средств как демоны.

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

2. Метод интерактивного функционального моделирования информационных систем и Акторный Пролог

В главе 2 диссертационной работы предложен метод интерактивного функционального моделирования, который включает следующий план действий:

Одновременно с разработкой ФД информационной системы осуществляется построение программы на специальном логическом языке, описывающей блоки и связи ФД в терминах логического программирования. В диссертации показано, что следует выделить, по крайней мере, три разновидности таких логических программ - мы будем называть их семантическими моделями:
1. семантические модели структуры ФД информационной системы - структурные семантические модели, предназначенные для проверки и логического доказательства правильности соединения компонентов, а также анализа свойств системы;
2. интерактивные семантические модели, обеспечивающие семантическую правильность ФД проектируемой системы в процессе её интерактивного редактирования;
3. имитационные семантические модели для моделирования работы системы, которые могут также рассматриваться в качестве парадигмы объектно-ориентированного логического программирования информационных систем.
Построение семантической модели может происходить частично автоматически, с помощью трансляции разрабатываемой ФД, а частично - "вручную", путём формализации знаний экспертов о семантике составных частей диаграммы.
Начиная с некоторого момента, когда накоплено достаточно информации о блоках и связях, а также о правилах соединения блоков ФД (то есть построение семантической модели, хотя бы в первом приближении, завершено), построенная логическая программа может быть исполнена. В дальнейшем может быть осуществлён один из двух вариантов использования этой программы:
1. Программа исполняется время от времени для анализа заданных параметров информационной системы или проверки правильности соединения функциональных блоков. Такой режим использования лучше подходит, скорее, для структурных и имитационных семантических моделей.
2. Программа реализует интерактивный режим работы проектировщика с машиной, реагируя на изменения, вносимые им в структуру ФД или параметры её составных частей, и проверяя правильность соединения и согласованность режимов работы компонентов моделируемой системы.
Семантическая модель является "отторгаемым продуктом" и может быть передана другому проектировщику, при этом логические правила соединения блоков могут быть сокрыты в описании компонентов ФД, что позволяет использовать их как "чёрные ящики". Более того, могут быть отдельно переданы компоненты семантической модели, разработанные "вручную", что позволит другому проектировщику автоматически (с помощью трансляции своих ФД) строить свои собственные семантические модели.

Для построения и исполнения различных видов семантических моделей в диссертации разработан Акторный Пролог [1,7] - объектно-ориентированный логический язык, реализующий обобщённую логическую акторную модель ФД информационной системы, проектируемой в интерактивном режиме.

2.1. Логическая акторная модель ФД информационных систем

В качестве обобщённой модели ФД информационной системы, проектируемой в интерактивном режиме, разработана логическая акторная модель [4] (см.рис.1), представляющая диаграмму в виде некоторой теоремы на логическом языке, разделённой на логические акторы⁹ - повторно доказываемые подцели (A1, ..., An на рисунке), взаимодействующие через общие переменные (V1, ..., Vm). Доказательство этой теоремы осуществляется в некотором объектно-ориентированном пространстве поиска, состоящем из отдельных миров (W1, ..., Wk), топология которого соответствует структуре ФД моделируемой системы.

Рис.1. Логическая акторная модель ФД.

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

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

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

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

В Акторном Прологе структурные, динамические и информационные аспекты ООП реализованы с помощью:

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

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

Использование названных средств языка в процессе функционального моделирования основано на следующих принципах [6]:

Каждый функциональный блок диаграммы описывается экземпляром некоторого класса логического языка, содержимым которого являются правила, описывающие семантику блока.
Связи между блоками функциональной диаграммы описываются с помощью слотов экземпляров классов. Для этих же целей удобно использовать правила второго порядка [1], имитируемые в Акторном Прологе с помощью недоопределённых множеств [1,7].
Логические акторы и механизм повторного доказательства служат для поддержки интерактивного проектирования функциональных диаграмм.

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

2.2. Структурные семантические модели

Простейшими семантическими моделями, соответствующими понятию "топология пространства поиска" в логической акторной модели ФД, являются структурные семантические модели.

Структурными семантическими моделями названы логические программы, описывающие каждый блок ФД информационной системы в виде некоторого объекта логического языка (точнее, экземпляра класса или "мира", в терминах Акторного Пролога).

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

Понятию "экземпляр класса" процедурного программирования в Акторном Прологе также соответствует аналог. Экземплярами классов ("мирами") в Акторном Прологе называются конкретные применения классов, однако создаются они не в результате выполнения процедурной операции new (как, например, в C++), а в результате доказательства некоторых специальных формул, названных "конструкторами". При этом логическая сущность экземпляров классов в Акторном Прологе приводит к одному весьма существенному отличию от их процедурных аналогов, а именно к тому, что в логическом языке экземпляры классов удаляются в процессе отката программы - точно так же как любые другие результаты логического вывода. Никаких аналогов процедурной операции delete и понятия "деструктор" в Акторном Прологе нет, так как в логическом языке не может быть процедурных операций явного удаления экземпляров классов.

Ещё одной важной особенностью Акторного Пролога является то, что в этом языке (в отличие от процедурных объектно-ориентированных языков типа Smalltalk и C++) осуществлено последовательное разделение понятий "экземпляр класса" и "элемент данных"¹⁰. То что эти понятия действительно соответствуют двум совершенно разным сущностям, видно, по крайней мере, из следующих сопоставлений:

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

Экземпляры классов служат составными частями пространства поиска (закрытыми блоками) во время исполнения программы. Содержимым экземпляра класса являются:

набор предложений соответствующего класса, а также предложений его предков в иерархии наследования;
набор слотов, доступных из всех предложений экземпляра класса.

Механизм наследования в Акторном Прологе является аналогом подобных механизмов в процедурном ООП, однако он имеет несколько иную операционную семантику: иерархия наследования задаёт правила поиска предложений программы, осуществляемого в процессе её исполнения. Например, если в качестве пространства поиска для доказательства некоторого предиката p служит экземпляр класса A, то поиск соответствующего предложения с заголовком p будет осуществляться по очереди среди предложений класса A, затем среди предложений непосредственного предка класса A и так далее, пока не будет найдено подходящее предложение, или пока не закончится иерархия наследования. Таким образом, в Акторном Прологе не происходит перекрытие методов, хотя его можно смоделировать, используя вне-логический оператор отсечения '!'. Кроме того, в Акторном Прологе не используется так называемое множественное наследование - у класса может быть лишь один непосредственный предок, так как иначе было бы непонятно, в каком порядке следует просматривать предложения родительских классов в ходе логического вывода, и пришлось бы назначать этот порядок искусственно, с помощью волевого решения.

Слот - это "глобальная переменная" экземпляра класса или обозначение некоторого мира. Имена слотов названы атрибутами классов.

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

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

class 'ADDER' using 'DEVICE' is
a
b  = 0  -- Определение атрибутов класса.
c1 = 0  -- Слоты b и c1 по умолчанию
sum     -- содержат 0.
c2
[       -- Предложения класса.
table(0,0,F, F,0). table(0,1,0, 1,0).
table(0,1,1, 0,1). table(1,0,0, 1,0).
table(1,0,1, 0,1). table(1,1,F, F,1).
get_state(sum).
goal:-!,
        table(a,b,c1,sum,c2).
]

Класс 'ADDER', изображающий полный двоичный сумматор, является непосредственным потомком класса 'DEVICE'. Атрибуты a, b и c1 обозначают слагаемые сумматора и входной бит переноса, sum и c2 - сумму и выходной бит переноса.

2.3. Интерактивные семантические модели

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

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

В Акторном Прологе определение акторов осуществляется с помощью специального префикса @, действие которого можно проиллюстрировать следующим примером:

goal:-                goal:-
    subgoal_a(X),         @ subgoal_a(X),
    subgoal_b,            subgoal_b,
    user_input(Y),        user_input(Y),
    X := Y.               X := Y.
subgoal_a(1).         subgoal_a(1).
subgoal_a(3).         subgoal_a(3).
subgoal_a(5).         subgoal_a(5).

(a)                   (b)

В случае (a) акторный механизм не используется. В процессе доказательства целевого утверждения goal сначала будет найдено решение subgoal_a(1), переменная X при этом получит значение 1. Затем будут исполнены подцели subgoal_b и user_input(Y) (пользователь введёт значение переменной Y, например, Y=5). Когда очередь дойдёт до отношения X:=Y, то окажется, что оно ложно: 1<>5. Это вызовет откат программы до последней точки ветвления - ей соответствует выбор нового факта для подцели subgoal_a(X). Следующая попытка доказательства (при X=3) точно так же потерпит неудачу. И только с третьего раза (когда X получит значение 5) программа завершится успехом. Заметим, что подцели subgoal_b и user_input(Y) пришлось передоказывать по три раза, хотя они не имеют к переменной X никакого отношения.

В случае (b) подцель доказательства, соответствующая вызову предиката subgoal_a(X), будет объявлена актором. Следовательно, первая же попытка выполнить X:=5 завершится успехом. Последствием этого присваивания станет отмена результатов доказательства подцели subgoal_a(X) - "нейтрализация" актора - и её повторное исполнение (на этот раз будет выбран факт subgoal_a(5), соответствующий значению X=5).

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

2.4. Имитационные семантические модели

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

2.5. Разработка Акторного Пролога

Основные усилия в процессе разработки языка были направлены на получение по возможности более чёткого определения синтаксиса и семантики, допускающего простую и эффективную реализацию. Акторный Пролог отвечает требованиям, предъявляемым к современным языкам программирования, в том числе, требованиям к средствам раздельной трансляции и обработки исключительных ситуаций. Одновременно с разработкой языка были созданы прототипы его интерпретатора, браузера (оболочки для визуального программирования), а также транслятора в исходный текст на языке PDC PROLOG.

В приложении к диссертации приведено полное определение Акторного Пролога [7] от 22 марта 1998 г.

3. Декларативная и операционная семантика Акторного Пролога

В главе 3 рассмотрен метод повторного доказательства подцелей, определены декларативная и операционная семантики Акторного Пролога. Доказаны теоремы, гарантирующие корректность логической интерпретации ООП в Акторном Прологе.

В основе Акторного Пролога лежит метод повторного доказательства подцелей, идея которого заключается в следующем:

В логический язык вводятся специальные обозначения, с помощью которых в программе выделяются некоторые подцели (логические акторы), связанные общими переменными.
Исполнение логических программ осуществляется под управлением специальной стратегии (называемой в Акторном Прологе механизмом повторного доказательства или акторным механизмом), предусматривающей:
1. Возможность изменения значений некоторых общих переменных и последующего повторного доказательства зависящих от них акторов (если это понадобится для восстановления корректности и полноты логического вывода).
2. Возможность параллельного исполнения повторных доказательств акторов, когда это не нарушает корректность и полноту логического вывода.
3. Возможность задержки восстановления состояний некоторых акторов при откате программы, когда это не нарушает корректность и полноту логического вывода (эта идея является основой логической интерпретации необратимых процессов в Акторном Прологе).

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

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

Логическая корректность такой реализации обосновывается доказанными в работе теоремами:

Теорема 3.1.1

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

Теорема 3.1.2

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

Теорема 3.1.3

Вещественные числовые литералы в программе на Акторном Прологе могут быть (эффективно) представлены в виде термов логики предикатов первого порядка.

Теорема 3.1.4

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

Теорема 3.1.5

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

Примечание. Средствами управления Акторного Пролога являются отсечение '!' и другие встроенные операторы, "заголовки внешних предложений", а также специальный акторный префикс "&".

Определение 3.1.6

Декларативной семантикой программы на Акторном Прологе без средств управления является декларативная семантика программы на чистом Прологе, соответствующей по теореме 3.1.5 исходной программе без акторных префиксов.

Теорема 3.1.7 (о корректности)

Механизм повторного доказательства Акторного Пролога с проверкой вхождений, без средств управления является корректной стратегией управления.

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

Пример 3.1.8

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

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

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

Теорема 3.1.9 (о полноте)

Если PA - программа на Акторном Прологе без средств управления, а PS - программа на чистом Прологе, соответствующая по теореме 3.1.5 программе PA без акторных префиксов, то для любого успешного вычисления CS в полном дереве поиска программы PS, исполняемой под управлением стандартной стратегии, в полном дереве поиска программы PA найдётся некоторое успешное вычисление СA, выдающее тот же ответ, что и вычисление CS.

3.1.10. Следствие теоремы о полноте

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

Заметим, что механизм повторного доказательства не является справедливой стратегией управления, поскольку в Акторном Прологе используется поиск в глубину, как в "обычном" Прологе. Программы на Акторном Прологе могут зацикливаться, однако при этом акторный механизм гарантирует, что нейтрализация акторов, сама по себе, никогда не приведёт к зацикливанию программы.

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

4. Использование Акторного Пролога для анализа ФД информационных систем

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

Поддержка в Акторном Прологе средств ООП позволяет использовать преимущества ООП при проектировании и семантическом анализе функциональных диаграмм, а именно:

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

Основные результаты работы

В диссертационной работе получены следующие результаты:

Впервые предложен и исследован метод логического объектно- ориентированного описания и анализа функциональных диаграмм информационных систем, обеспечивающий семантическую правильность функциональных диаграмм в процессе интерактивного проектирования.
Впервые предложена и разработана логическая акторная модель функциональной диаграммы, проектируемой в интерактивном режиме, представляющая диаграмму в виде теоремы на логическом языке, разделённой на повторно доказываемые подцели (логические акторы), взаимодействующие в объектно-ориентированном пространстве поиска.
Впервые предложен и разработан метод повторного доказательства подцелей логической программы, обеспечивающий корректность доказательства теоремы при произвольном порядке доказательства подцелей и позволяющий интерпретировать в логическом языке интерактивный режим, разрушающее присваивание и необратимые процессы.
Впервые предложена и разработана логическая интерпретация объектно- ориентированного программирования на основе метода повторного доказательства подцелей. Разработана парадигма программирования, соответствующая предложенной логической интерпретации объектно-ориентированного программирования.
Разработан объектно- ориентированный логический язык -
Акторный Пролог. Построено полное определение синтаксиса и семантики Акторного Пролога.
Доказаны теоремы, гарантирующие корректность логической интерпретации объектно-ориентированного программирования в Акторном Прологе.
Построено формальное определение операционной семантики последовательной версии Акторного Пролога без средств управления.
Реализованы прототипы интерпретатора, браузера Акторного Пролога, а также транслятора в исходный текст на языке PDC PROLOG. Показана возможность эффективной реализации Акторного Пролога на персональных ЭВМ.

Новые версии определения Акторного Пролога регулярно публикуются на нашем WWW-сервере

http: // www.cplire.ru / Lab144 / index.html

Благодарности

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

Работа выполнена при поддержке Российского Фонда Фундаментальных Исследований (проект 95-01-00822а).

Опубликованы следующие работы:

Морозов А.А. Акторный Пролог // Программирование. - 1994. - N 5. - С.66-78.
Морозов А.А., Обухов Ю.В., Олейников А.Я. Логическое программирование открытых систем // Логика, методология, философия науки: Тез. докл. XI межд. конф. - Обнинск, 1995. - Т.2. - С.153-156.
(http://www.cplire.ru/Lab144/obninsk.html)
Морозов А.А. Решение проблемы фрейма в Акторном Прологе // Прикладная логика - 95: Тез. докл. IV межд. конф. - Иркутск, 1995. - С.55- 56.
Морозов А.А., Обухов Ю.В. Логическая акторная модель прикладных открытых систем // Развитие и применение открытых систем: Тез. докл. II межд. конф. - Петрозаводск, 1995. - С.28-30.
Морозов А.А. Акторный Пролог // Дискретные модели в теории управляющих систем: Тез. докл. II межд. конф. - М.: Диалог-МГУ, 1997. - С.42.
(http: // www.cplire.ru / Lab144 / report1.html)
Морозов А.А., Обухов Ю.В. Семантический анализ функциональных диаграмм информационных систем средствами объектно-ориентированного логического программирования // Развитие и применение открытых систем: Тез. докл. IV межд. конф. - Нижний Новгород, 1997. - С.61-64.
(http: // www.rapros97.nnov.ru / reports / 9.html)
Морозов А.А., Обухов Ю.В. Акторный Пролог. Определение языка программирования. - Москва, 1996. - Препринт ИРЭ РАН 2(613) от 14.06.96. - 57с.
(http: // www.cplire.ru / Lab144 / index.html)

Back to Research Divisions
IRE RAS Homepage