оглавление

дискуссия

Работа поддержана РФФИ (гранты NN 00-01-0560 и 03-01-00256)

Получена 19 ноября 2003 г.

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

Введение *

1. Постановка задачи и основная идея её решения *

2. Объектно-ориентированное логическое программирование интеллектуальных агентов *

2.1. Классы, миры и наследование *

2.2. Повторное доказательство логических акторов *

2.3. Доказательство логического актора в динамической среде Интернет *

2.4. Пример реализации логического агента Интернет *

3. Построение многоагентных логических систем *

3.1. Основные элементы модели параллельных асинхронных вычислений *

3.1.1. Процессы *

3.1.2. Сообщения *

3.1.3. Резиденты *

3.1.4. Пример графического описания агента *

3.2. Декларативная семантика многоагентных систем *

3.3. Принципы построения логических систем взаимодействующих агентов *

3.4. Визуальное программирование агентов Интернет *

4. Сравнение с другими подходами к декларативному программированию агентов Интернет *

4.1. Декларативная семантика агентов Интернет *

4.2. Визуальное программирование агентов Интернет с помощью функциональных диаграмм *

4.3. Параллельное программирование агентов *

4.4. Модифицируемые рассуждения в многоагентных системах *

4.5. Опережающие вычисления в многоагентных системах *

Заключение *

Список литературы *

Приложение 1. Пример построения теоретико-модельной семантики параллельной программы *

Приложение 2. Пример агента Интернет *

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

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

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

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

В настоящее время не существует общепринятого определения агентов. Однако агентами принято называть программы, демонстрирующие свойства автономности, реактивности (реагирующие на внешние стимулы), проактивности (выполняющие действия по собственной инициативе), и (в случае многоагентных систем) обладающие социальным поведением [8,9].

Логическое программирование агентов Интернет является одним из наиболее интересных направлений в области поиска и распознавания информации в Сети, активно развиваемым в течение последнего десятилетия. Перспективность этого подхода была продемонстрирована в ряде исследовательских и коммерческих проектов (см. обзоры [12,14,40]). Показано, что логические языки, вследствие своих высоких выразительных и дедуктивных возможностей, являются удобным средством анализа сложных гипертекстовых структур Сети.

Можно выделить следующие достоинства логического подхода к программированию агентов Интернет:

1. Наличие декларативной семантики делает логические языки средством представления и запросов информации очень высокого уровня абстракции.
2. Идеология большинства логических языков основана на принципе поиска по дереву ("поиска с откатом"), напоминающем поведение человека при поиске информации в Интернет.
3. Синтаксис логических языков оказывается проще и выразительнее, чем у императивных языков, потому что:
1. Они не нуждаются в явном использовании указателей.
2. Их операционная семантика основана на понятиях рекурсии и отката (в противоположность императивным языкам, основанным на использовании цикла и ветвления).
3. Любой сложный элемент данных в логическом языке имеет ясное и однозначное текстовое представление.
4. Простота синтаксиса и операционной семантики логических программ делает их удобным объектом для автоматического построения, анализа и преобразования.
5. Логические языки хорошо приспособлены для обработки текстов на естественном языке.

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

В последнее десятилетие было разработано большое количество методов и средств логического программирования агентов Интернет, основанных на различных модификациях и расширениях языка Пролог, а также неклассических логиках (линейной, модальной и др.) [8,10,12,40]. Тем не менее, до сих пор не был создан математический аппарат, который обеспечивал бы свойства корректности и полноты логических программ (агентов), работающих в динамическом внешнем окружении (т.е. в условиях постоянного изменения и пополнения информации в Интернет).

Для решения этой проблемы мы разработали математический аппарат логического программирования агентов Интернет [40-44,46,47,49]. Созданный математический аппарат включает:

1. Модель интеллектуальных агентов, работающих в динамическом внешнем окружении.
2. Декларативную семантику агентов.
3. Стратегии исполнения агентов Интернет, корректные и (при определённых условиях) полные относительно декларативной семантики этих агентов.

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

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

Рассмотрим упрощённую модель логического интеллектуального агента, осуществляющего поиск и распознавание информации в Интернет.

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

1. Работает ли агент с некоторыми заранее определёнными ресурсами Интернет, или выбор ресурсов осуществляется в ходе исполнения программы и зависит от поступающих данных?
2. Как долго должен работать агент? Некоторые агенты используются лишь эпизодически для осуществления разовых операций поиска в Сети, а некоторые могут работать непрерывно в течение недель, месяцев и даже лет.

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

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

Разработанный нами аппарат является альтернативой немонотонным логическим системам. Его идею можно проиллюстрировать с помощью канонического примера про страуса Тити [2].

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

При отсутствии в базе данных факта страус("Тити") доказательство утверждения not страус("Тити") завершится успехом, и Пролог выдаст Ответ = "да" - Тити может летать. Однако после добавления факта страус("Тити") это отрицание станет невыводимым, и Пролог ответит, что Тити летать не может.

Второй способ основан на использовании разработанного нами аппарата логических акторов [34-36,38,39,49]. Логическими акторами мы называем подцели логической программы, которые могут доказываться повторно без отката логической программы. В дальнейшем мы будем обозначать логические акторы с помощью префикса @.

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

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

Отряд := "страусы"

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

Второй способ формализации обладает следующими достоинствами:

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

Реализация механизма логических акторов требует создания соответствующей стратегии логического вывода, поддерживающей повторное доказательство подцелей программы. В [38] доказано, что существуют такие стратегии, обладающие свойствами полноты (при условии отсутствия зацикливаний) и корректности.

На основе разработанного подхода мы создали объектно-ориентированный логический язык Акторный Пролог [34,36,38,39,49]. В следующем разделе будут рассмотрены основные принципы логического программирования на Акторном Прологе, а также пример логического агента Интернет.

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

Проблема соотношения логического и объектно-ориентированного программирования имеет давнюю историю и обширную библиографию (см., например, обзоры [6,7,11]). Исследуя эту область, мы пришли к выводу, что интуитивное программистское понятие "объект" не имеет однозначного соответствия в логике. При попытке перенести его в логическое программирование, оно распадается, по крайней мере, на три аспекта, каждый со своими выразительными возможностями, теоретическими проблемами и средствами реализации:

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

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

1. Классы, миры и наследование.
2. Повторное доказательство логических акторов, а также параллельные процессы.
3. Простые и составные термы (в том числе, так называемые "недоопределённые множества").

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

В этом разделе мы рассмотрим два основных средства Акторного Пролога - классы и логические акторы. Описание недоопределённых множеств можно найти в [34,39,49] или в определении языка [36].

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

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

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

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

1. Все предложения класса и его предков в иерархии наследования.
2. Набор "слотов".

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

Таким образом, в Акторном Прологе не происходит перекрытие предложений, определённых в суперклассах, хотя его можно смоделировать, используя нелогический оператор отсечения '!'. Кроме того, в Акторном Прологе не используется множественное наследование. У класса может быть лишь один непосредственный предок, так как иначе было бы непонятно, в каком порядке следует просматривать предложения родительских классов в ходе логического вывода.

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

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

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

Доказательство конструктора (конструктора экземпляра некоторого класса C) включает следующие стадии:

1. Формирование экземпляра класса:
1. Построение соответствующего пространства поиска. В состав пространства поиска входят предложения самого класса C, а также предложения всех его предков.
2. Формирование слотов экземпляра класса. Каждый слот получает некоторое начальное значение, если задан соответствующий инициализатор. Если инициализатором слота является конструктор, значением такого слота становится новый мир, прошедший первую стадию построения (формирование). Если слот не имеет инициализатора, его начальным значением становится анонимная переменная "_".
2. Доказательство предиката goal во всех мирах, сформированных на этапе (1).

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

В приведённом выше примере конструктор

('ADDER', a= 1, b= 1, sum= Result)

создаст новый экземпляр класса 'ADDER' и присвоит значение переменной Result=0.

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

target ? p(A,B,C,...)

- "исполнить процедуру p в мире target".

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

В [38] доказана теорема, устанавливающая математическую корректность механизма классов, рассмотренного выше.

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

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

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

В Акторном Прологе логическая программа рассматривается как теорема, разделённая на логические акторы. Логические акторы - это повторно доказываемые подцели A₁,...,A_N (рис. 2), взаимодействующие через общие переменные V₁,...,V_M. Доказательство этой теоремы осуществляется в некотором объектно-ориентированном пространстве поиска, состоящем из отдельных миров W₁,...,W_K. Например, прямоугольник A₄ на рисунке обозначает актор, подцели которого исполняются в мирах W₂ и W₃.

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

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

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

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

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

Термин "актор" мы позаимствовали из акторной модели вычислений Хьюитта [3], однако механизм повторного доказательства подцелей реализует иной принцип взаимодействия между акторами. Вот основные отличия разработанной модели вычислений:

1. Передача информации между акторами осуществляется (только) через общие переменные, с помощью разрушающего присваивания.
2. Логический актор не знает, какие именно акторы будут затронуты в результате выполняемого им разрушающего присваивания. Таким образом, логические акторы не обязаны знать друг друга "по имени", и, следовательно, программа на Акторном Прологе является сильно распределённой системой.
3. В Акторном Прологе реализован (стандартный) откат.
4. Ещё одним интересным свойством разработанной модели является то, что в ней отсутствует буферизация передачи информации между акторами. Значение общей переменной может успеть несколько раз измениться, прежде чем начнётся повторное доказательство зависящего от неё актора.
5. Ограничением разработанной модели является то, что результаты предыдущего доказательства актора становятся недоступными в программе после того, как произошло повторное доказательство этого актора.

Детальное описание акторного механизма можно найти в определении Акторного Пролога [36]. Определение абстрактной машины последовательного Акторного Пролога приведено в [38].

Определение декларативной семантики программ на Акторном Прологе без параллельных процессов основано на теореме 2.1.1:

Определение 2.2.1. Декларативной (теоретико-модельной) семантикой программы на Акторном Прологе без параллельных процессов и нелогических встроенных предикатов является декларативная семантика программы на чистом Прологе, соответствующей в смысле теоремы 2.1.1 исходной программе, после удаления всех префиксов @.

В [38] доказаны следующие теоремы о корректности и полноте акторного механизма относительно декларативной семантики 2.2.1:

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

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

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

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

В ходе доказательства логический актор обращается к ресурсам Интернет R₁-R_x. Предположим, что доказательство этой подцели закончилось успехом, а именно, в ходе логического вывода была успешно пройдена ветвь A-B-C. Это означает, что построенное доказательство зависит от ресурсов Интернет R₂, R₃, R₅, использованных при прохождении ветви A-B-C, и не зависит от других ресурсов Интернет, к которым программа, возможно, обращалась при прохождении иных ветвей И-ИЛИ дерева. Следовательно, повторное доказательство рассматриваемого актора необходимо произвести (только) при изменении какого-либо из ресурсов R₂, R₃, R₅, а все остальные ресурсы можно не учитывать.

Предположим теперь, что доказательство актора завершилось неудачей. В этом случае значительно труднее определить, какие из использованных ресурсов Интернет оказали решающее влияние на результат доказательства, потому что при прохождении различных ветвей ИЛИ дерева использовались разные ресурсы, и, кроме того, сочетание данных из различных ресурсов Интернет могло повлиять на негативный результат при прохождении отдельных ветвей ИЛИ дерева. В общем случае, каждый из ресурсов Интернет R₁-R_x мог повлиять на (неудачный) исход логического вывода.

Таким образом, для осуществления корректного управления повторными доказательствами, в ходе доказательства логического актора необходимо запоминать:

1. Полный список ресурсов Интернет, к которым актор обращался во время обхода всех пройденных им ветвей И-ИЛИ дерева.
2. Список ресурсов Интернет, к которым актор обращался во время прохождения текущей ветви ИЛИ дерева.

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

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

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

Целевое утверждение (1) программы указывает, что исполнение программы начинается с построения экземпляра класса 'Example2'. Класс 'Example2' (2-16) является прямым потомком предопределённого класса 'Report', реализующего управление текстовыми окнами. Экземпляр класса 'Example2' обладает тремя слотами node1, node2 и node3, содержащими экземпляры класса 'ResourceChecker'. Каждому экземпляру класса 'ResourceChecker' передаются три аргумента - название некоторой организации, её адрес в Интернет и ссылка на сам экземпляр класса 'Example2' (с помощью предопределённого слота self). Класс 'ResourceChecker' (17-36) является потомком предопределённого класса 'Receptor', реализующего взаимодействие программы с Интернет. Режим работы экземпляра класса 'Receptor' задаётся с помощью следующих слотов. Аргумент revision_period (21) задаёт повторную проверку ресурса Интернет, расположенного по адресу location, через каждые 3 дня. Аргумент max_waiting_time (22) означает, что если во время обращения к ресурсу ответ не придёт в течение 12 секунд, будет считаться, что обращение к ресурсу закончилось ошибкой. В каждом экземпляре класса 'ResourceChecker' создаётся актор goal (24). Он выполняет следующие действия: предикат get_parameters (25) возвращает параметры заданного ресурса Интернет, а предикат write_parameters (26) выводит на экран соответствующее сообщение.

Принцип работы программы заключается в следующем: создаются три экземпляра класса 'ResourceChecker' и три соответствующих им актора goal. Каждый из акторов является логическим утверждением о некотором ресурсе Интернет. Это утверждение можно прочитать декларативно следующим образом: "Информация о текущем состоянии ресурса location выведена на экран". В терминах логического программирования можно сказать, что исполнение программы есть доказательство конъюнкции этих логических утверждений. При этом принципиальное отличие программы на Акторном Прологе от программы на стандартном Прологе состоит в том, что через некоторое время, когда состояние ресурсов Интернет изменится, логическая истинность утверждений программы на "обычном" Прологе будет нарушена. Однако, в отличие от стандартного Пролога, Акторный Пролог автоматически выявит произошедшее изменение ресурса (в приведённом примере - не позже чем через 3 дня) и восстановит корректность доказательства, повторно доказав те (и только те) акторы, ресурсы которых подверглись изменению.

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

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

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

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

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

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

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

(('ClassName', attribute1=Value1,..., attributeN=ValueN))

Передача информации между процессами в нашей модели осуществляется с помощью следующих механизмов:

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

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

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

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

Примечание. В определении Акторного Пролога [36] дополнительно рассматривается ещё одно, вспомогательное, состояние, возникающее в ходе построения процесса.

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

Отличие между потоковыми и прямыми сообщениями состоит в следующем:

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

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

Потоковые сообщения в Акторном Прологе обрабатываются следующим образом. При изменении значения общей переменной V, связывающей принимающий процесс P с другими процессами, в процессе P осуществляется разрушающее присваивание V := NewValue. Результатом этой операции становится повторное доказательство некоторых акторов процесса P. На рисунке 5 приведены графические символы, которые мы используем для обозначения потоковых сообщений.

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

(('ClassName',..., protecting: attributeN=ValueN,...))

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

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

(('ClassName',..., suspending: attributeN=ValueN,...))

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

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

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

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

Target << predicate(A,B,...,C)

Target <- predicate(A,B,...,C)

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

Инфикс << обозначает так называемые "информационные" прямые сообщения, а <- "переключающие" прямые сообщения. Эти разновидности прямых сообщений отличаются тем что:

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

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

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

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

slot = target_world ?? function(A,B,...,C)

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

1. Владелец резидента. Владельцем резидента является создавший его процесс.
2. Атомарная формула function(A,B,...,C). Эта формула обозначает вызов некоторой функции (в общем случае, недетерминированной), которая должна быть исполнена в целевом процессе. Функции в Акторном Прологе реализованы с помощью стандартной техники разглаживания программ [45].
3. Целевой процесс резидента target_world.
4. Некоторая общая переменная slot. Через эту переменную резидент посылает собранную информацию своему владельцу.

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

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

На рисунке 8 приведено графическое обозначение резидентов, которое мы используем в нашей модели вычислений.

Рассмотрим пример графического описания агента Интернет, собирающего данные с помощью поисковых машин Google и Rambler. На рисунке 9 изображена функциональная диаграмма, использующая рассмотренные выше обозначения.

Процесс 1 осуществляет взаимодействие с пользователем. Он принимает список ключевых слов и посылает процессам 2 и 3 переключающее прямое сообщение, запускающее процесс поиска. Процессы 2 и 3 взаимодействуют с соответствующими поисковыми машинами и накапливают полученные адреса в локальных базах данных. Собранные адреса с помощью резидентов собираются в списки и в виде потоковых сообщений передаются в процесс 4. Процесс 4 объединяет списки адресов и передаёт их в процесс 5, который осуществляет дополнительную фильтрацию полученных ссылок. Необходимый метод проверки Веб страниц реализован в процессе 6. Обратите внимание, что процесс 6 передаёт в процесс 5 самого себя с помощью потокового сообщения, чтобы процесс 5 использовал его в качестве инструмента фильтрации. Список проверенных адресов передаётся в процесс 7, который показывает найденные адреса в диалоговом окне и позволяет пользователю просмотреть найденные ресурсы с помощью стандартного Веб браузера.

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

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

1. Корректность алгоритмов. Как будет показано далее, Акторный Пролог обеспечивает корректность программ (в том числе, параллельных) относительно их теоретико-модельной семантики. Таким образом, мы можем быть уверены, что программа никогда не вычислит (некорректные) значения, не принадлежащие её теоретико-модельной семантике.
2. Полноту алгоритмов. При выполнении определённых условий мы можем гарантировать полноту логической программы. Это означает, что программа реализует исчерпывающий перебор и найдёт все существующие решения поставленной задачи. К сожалению, далеко не все логические программы являются полными относительно своей декларативной семантики.

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

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

Для построения искомой программы P' выполним следующие преобразования:

1. Удалим из текста программы P все нелогические встроенные предикаты.
2. Заменим все конструкторы процессов в тексте программы обычными конструкторами экземпляров классов (то есть, заменим в конструкторах процессов двойные круглые скобки на одинарные). Тем самым параллельная логическая программа будет преобразована в последовательную.
3. Работу отключающих портов процессов промоделируем с помощью вспомогательных предикатов. Например, поведение процесса с целевым утверждением goal и двумя отключающими портами x и y будет смоделировано с помощью переопределения целевого утверждения. Новое целевое утверждение goal' будет определено следующим образом:

goal':-
	x == #.
goal':-
	y == #.
goal':-
	ground_term(x),
	not x == #,
	ground_term(y),
	not y == #,
	goal.	- - Старое целевое утверждение

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

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

4. Работу резидентов мы смоделируем также с помощью переопределения целевых утверждений и вспомогательных предикатов. Например, если инициализатором одного из слотов класса является конструктор резидента вида slot = target ?? function(a,b,...,c), переопределим целевое утверждение goal этого класса:

goal':-
	setof(a,b,...,c,[],Results),
	slot == Results,
	goal.	- - Старое целевое утверждение

Операция построения списка решений, возвращаемых функцией function(A,B,...,C), будет реализована по следующей схеме:

setof(A,B,...,C,Results,Total):-
	Result== target ? function(A,B,...,C),
	ground_term(Result),
	not is_element(Result,Results),
	setof(A,B,...,C,[Result|Results],Total).
setof(A,B,...,C,Results,Total):-
	not has_another_solution(A,B,...,C,Results),
	sort(Results,Total).
has_another_solution(A,B,...,C,Results):-
	Result== target ? function(A,B,...,C),
	ground_term(Result),
	not is_element(Result,Results).

Вспомогательный предикат is_element проверяет, содержится ли значение Result в списке. Вспомогательный предикат sort упорядочивает элементы списка и удаляет из него повторяющиеся элементы. Для сортировки элементов списка будем использовать лексикографическое упорядочение. Вспомогательный предикат ground_term гарантирует корректность использования оператора not.

5. Удалим из текста программы все операции отправления прямых сообщений. Как уже отмечалось, прямые сообщения в нашей модели являются строго асинхронными и всегда заканчиваются успехом. Таким образом, с точки зрения декларативной семантики, эти сообщения могут не учитываться.
6. Удалим из текста программы ключевые слова protecting.
7. Мы получили последовательную объектно-ориентированную программу. Объектно-ориентированные конструкции Акторного Пролога можно легко смоделировать на чистом Прологе с помощью простого переименования предикатов и добавления некоторых вспомогательных аргументов. В [38] приведён подробный алгоритм таких преобразований.

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

В приложении 1 приведён подробный пример преобразования параллельной логической программы.

Набросок доказательства. Рассматривая И-дерево программы P в ходе преобразований (1)-(7), можно убедиться, что оно может только сокращаться (конкретно, на шаге 1). Таким образом, И-дерево программы P' будет покрывать никак не меньше решений, по сравнению с программой P. То есть, программа P не может вычислить решения, не покрываемые программой P' (и, следовательно, некорректные относительно теоретико-модельной семантики).

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

Набросок доказательства. Существует пять возможных причин неполноты параллельной программы относительно декларативной семантики. Первая причина - неполнота вычислений, осуществляемых внутри какого-либо процесса. Для устранения этой причины введены условия (1) и (3). Второй возможной причиной является невозможность передачи отката между процессами. Условия (5) и (6) гарантируют, что, если процесс вычислил и передал некоторое решение в другой процесс, другого решения не существует. Следовательно, в откате нет необходимости, так как он всё равно не помог бы найти другие решения. Третья возможная причина неполноты - замена несвязанных переменных константой #, осуществляемая при передаче информации между процессами. Эту причину устраняет условие (8). Четвёртая причина, это бесконечные вычисления, которые могут возникнуть в ходе исполнения программы. Такие зацикливания программы предотвращают условия (3), (4) и (7). Пятая возможная причина - наличие нескольких успешных конечных состояний у программы. Конкретно, у программы может оказаться несколько конечных состояний, если (a) в ней используются прямые сообщения, порядок обработки которых является, в общем случае, непредсказуемым; (b) между процессами осуществляется циклическая передача данных, и невозможно предсказать заранее, в каком порядке будут исполнены процессы, связанные общими переменными. Для предотвращения этих случаев введены, соответственно, условия (2) и (7). Следовательно, при выполнении перечисленных условий (1)-(8), программа будет полной относительно теоретико-модельной семантики.

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

Разработанная логическая объектно-ориентированная модель вычислений формирует определённый стиль программирования и принципы проектирования прикладных систем:

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

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

Мы разработали экспериментальные средства визуального логического программирования агентов Интернет. В их основе лежит использование SADT-диаграмм [5,37,38,49]. SADT-диаграммы являются разновидностью функциональных диаграмм и широко используются для анализа и проектирования сложных систем [5].

Система визуального программирования реализует следующую схему разработки интеллектуальных агентов:

1. Разрабатывается графическое описание интеллектуального агента средствами SADT. SADT-описание представляет собой иерархию блоков, принимающих и передающих потоки информации (см. пример описания внутреннего устройства одного блока SADT диаграммы на рис. 10).
2. Каждому элементарному блоку SADT-модели ставится в соответствие логическое описание в виде некоторого класса Акторного Пролога. Исходный текст на Акторном Прологе может быть подготовлен программистом или взят из библиотеки повторно используемых модулей.
3. Графическое описание агента автоматически транслируется в текст на Акторном Прологе. Выразительные средства Акторного Пролога позволяют представить блочно-иерархическую структуру и связи между блоками диаграммы в виде взаимодействующих процессов.
4. Объединив созданный автоматически текст с описаниями элементарных блоков, мы получаем готовую программу на Акторном Прологе. В приложении 2 приведён полный листинг агента Интернет, упомянутого на на рис. 10.

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

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

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

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

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

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

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

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

Идея визуального программирования агентов Интернет с помощью функциональных диаграмм ранее была успешно реализована Москони и Порта. Разработанная ими система VIPERS [22] построена на основе специальной разновидности диаграмм потоков данных. По сравнению с нашей системой визуального программирования агентов, система VIPERS обладает более проработанным графическим интерфейсом, однако реализация блоков диаграмм осуществляется на императивном языке. Таким образом, система VIPERS не поддерживает декларативную семантику агентов Интернет и не решает вопросы математической строгости процедур поиска и распознавания информации в динамической среде Интернет.

Целесообразность использования потокового параллелизма для разработки языков программирования агентов Интернет была продемонстрирована также в проектах WebL Кистлэра и Мэйрэйса [23] (на основе комбинаторов Кадэли и Дэйвиза [24]), Webstream Хонга и Кларка [25], WebScript Занга и Кэшев [26], схемах получения информации Баиша и Кноблока [27]. Перечисленные языки программирования являются императивными и, таким образом, обладают тем же недостатком, что и упомянутая ранее система VIPERS.

В области логического программирования Интернет также были разработаны модели параллельных вычислений, основанные на различных принципах взаимодействия агентов. Разработанные ранее логические языки программирования агентов Интернет, такие как concurrent LogicWeb Дэйвисона и Лока [13], W-ACE Понтэли и Гупты [17], Jinni Поля Таро [19], OZ [18], созданный под руководством Герта Смолки, DLP Илиёнса и Де Винка [21], ObjVProlog-D Мэйлэнфэнта, Лэйпэлма, Воче [29] и др. [12], обеспечивают существование декларативной семантики агентов, однако не поддерживают модификацию логического вывода в динамическом внешнем окружении и, следовательно, также не обеспечивают математическую строгость агентов Интернет.

Дэйвисон и Лок [13] предложили модель параллельных вычислений, основанную на описании взаимодействующих процессов с помощью рекурсивных предложений (средствами параллельного логического языка Парлог). Отличительной особенностью разработанной модели являются гибкие средства обработки аварийных ситуаций, характерных для работы в Интернет. На основе разработанной модели авторы реализовали средства параллельного программирования в своей системе логического программирования Интернет LogicWeb [14].

Понтэли и Гупта [17] разработали систему логического программирования W-ACE, также основанную на описании процессов с помощью рекурсивных предложений. В языке W-ACE введены средства структурирования пространства поиска на основе модальных операторов.

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

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

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

В качестве перспективного подхода к логическому программированию агентов в динамическом внешнем окружении принято рассматривать использование неклассических (и, в особенности, немонотонных) логических систем [2,10,30,31]. Мы пошли по принципиально иному пути, строго придерживаясь формализма классической логики первого порядка. В нашей модели вычислений модификация рассуждений, необходимая для корректной логической интерпретации изменений, происходящих во внешнем мире, осуществляется с помощью специальной стратегии исполнения логических программ, основанной на принципе повторных доказательств. Это позволило нам математически строго интерпретировать динамический характер среды Интернет, не теряя при этом выразительные и дедуктивные возможности классической логики предикатов первого порядка. Заметим, что разработанный нами подход свободен от недостатков немонотонных логических систем, таких как необщезначимость (в классическом смысле) выводимых формул, зависимость результата от порядка применения правил вывода и повышенная вероятность зацикливания логических программ.

Одним из наиболее интересных направлений в программировании агентов являются опережающие вычисления. Используя этот принцип для управления процессом получения данных из Интернет, Баиш и Кноблок [27] получили значительное увеличение скорости работы агентов Интернет. Эта же идея на более высоком уровне абстракции исследована в работах Иноу, Кавагучи, Ханеда [32], а также Сэйто и Ямамото [33]. Необходимо отметить также, что идея опережающих вычислений используется в языке OZ [18] вместо отката.

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

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

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

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

Я благодарен д.ф.-м.н. Юрию Владимировичу Обухову за помощь и поддержку в осуществлении проекта, акад. Юрию Ивановичу Журавлёву и проф. Владимиру Анатольевичу Захарову, которые принимали участие в обсуждении проблемы описания декларативной семантики многоагентных систем, а также к.ф.-м.н. Сергею Валерьевичу Ремизову, программное обеспечение которого помогло нам при отладке прототипа Акторного Пролога.

1. Горелик А.Л., Гуревич И.Б., Скрипкин В.А. Современное состояние проблемы распознавания. - М.: "Радио и связь", 1985.
2. Thayse A., Gribomont P., Hulin G., Pirotte A., Roelants D., Snyers D., Vauclair M., Gochet P., Wolper P., Gregoire E., Delsarte Ph. Approche Logique de l'Intelligence Artificielle, vol. 2 : De la Logique Modale a la Logique des bases de donnees. - Paris: Dunod, 1989. [Имеется перевод: Логический подход к искусственному интеллекту: От модальной логики к логике баз данных / Тейз А., Грибомон П., Юлен Г. и др. - М.: Мир, 1998.]
3. Hewitt C. Viewing Control Structures as Patterns of Passing Messages // Artificial intelligence. - 1977. - V. 8. - No. 3. - PP. 323-364.
4. Hewitt C. The Challenge of Open Systems // Byte. - 1985. - April. - PP. 223-233.
5. Marca D.A., McGowan C.L. SADT Structured Analysis and Design Technique. - N.Y.: McGraw-Hill, 1988.
6. Alexiev V. Mutable Object State for Object-Oriented Logic Programming: A Survey: Technical report TR93-15 / Dep. of Computing Science, University of Alberta. - Alberta, Canada, 1993. - 23 p.
   (ftp://ftp.cs.ualberta.ca/pub/TechReports/1993/TR93-15.ps.Z)
7. Fernandes A.A., Paton N.W., Williams M.H., Bowles A. Approaches to deductive object-oriented databases // Information and Software Technology. - 1992. - V. 34. - No. 12. - PP. 787-803.
8. Sadri F., Toni F. Computational Logic and Multiagent Systems: a Roadmap. - 1999.
   (http://citeseer.nj.nec.com/sadri99computational.html)
9. Huang Z., Eliens A., van Ballegooij A., de Bra P. A Taxonomy of Web Agents // IEEE Proc. of the First Intern. Workshop on Web Agent Systems and Applications (WASA 2000). - 2000.
   (http://wasp.cs.vu.nl/wasp/papers/wasa2000.ps)
10. Eiter T., Fink M., Sabbatini G., Tompits H. Using Methods of Declarative Logic Programming for Intelligent Information Agents // Theory and Practice of Logic Programming. - 2002. - Vol. 2. - No. 6. - PP. 645-709.
    (http://arxiv.org/abs/cs.MA/0108008)
11. Davison A. A Survey of Logic Programming-based Object-Oriented Languages // P. Wegner, A. Yonezawa, G. Agha (editors), Research Directions in Concurrent Object Oriented Programming. - MIT Press, 1993. - PP. 42-106.
    (http://www.cs.mu.oz.au/tr_db/mu_92_03.ps.gz)
12. Davison A. Logic Programming Languages for the Internet // A. Kakas, F. Sadri (editors), Invited Submission for Computational Logic: From Logic Programming into the Future. - Springer, 2001.
    (http://fivedots.coe.psu.ac.th/~ad/papers/summBob.ps.gz)
13. Davison A., Loke S.W. A Concurrent Logic Programming Model of the Web: Technical Report 98/23 / Department of Computer Science, University of Melbourne. - Melbourne, Australia, 1998.
    (http://www.cs.mu.oz.au/tr_submit/test/tr_db/mu_TR_1998_1-cp.ps.gz)
14. Loke S.W. Adding Logic Programming Behaviour to the World Wide Web: Ph.D. Thesis. - Department of Computer Science, The University of Melbourne, 1998.
    (http://goanna.cs.rmit.edu.au/~swloke/writings/phd-loke.pdf)
15. Kowalski R., Sadri F. From Logic Programming to Multi-agent systems / Department of Computing, Imperial College. - London, 1999.
    (http://www-lp.doc.ic.ac.uk/UserPages/staff/rak/papers/lpmas.pdf.gz)
16. Costantini S. Towards Active Logic Programming // Proc. of COCL'99 workshop. - Paris, 1999.
    (http://citeseer.nj.nec.com/318212.html)
17. Pontelli E., Gupta G. W-ACE: A Logic Language for Intelligent Internet Programming / Department of Computer Science, New Mexico State University. - Las Cruces, US, 1997.
    (http://www.cs.nmsu.edu/lldap/download/web.ps.Z)
18. Smolka G. The Oz Programming Model // In J. van Leeuwen (ed), Computer Science Today. LNCS 1000. - Springer, 1995. - PP. 324-343.
    (http://www.mozart-oz.org/papers/abstracts/volume1000.html)
19. Tarau P. Jinni: Intelligent Mobile Agent Programming at the Intersection of Java and Prolog // Proc. of PAAM'99. - London, 1999.
    (http://citeseer.nj.nec.com/tarau99jinni.html)
20. Tarau P. Fluents: A Refactoring of Prolog for Uniform Reflection and Interoperation with External Objects / Department of Computer Science, University of North Texas. - Denton, Texas, USA, 2000.
    (http://logic.csci.unt.edu/tarau/research/2000/fluents_cl2000.ps.gz)
21. Eliens A., de Vink E.P. Asynchronous rendez-vous in distributed logic programming // J.W. de Bakker, W.P. de Roever, G. Rozenberg (editors), Semantics: Foundations and Applications. - Springer, 1993. - PP. 174-203.
    (http://citeseer.nj.nec.com/50346.html)
22. Mosconi M., Porta M. A Visual Approach to Internet Applications Development // Proc. of the 8-th Intern. Conf. on Human-Computer Interaction (HCI'99). - Munich, Germany, 1999. - Vol. 1. - PP. 600-604.
    (http://vision.unipv.it/research/papers/99p-webappl/webappl.pdf)
23. Kistler T., Marais H. WebL - a programming language for the Web // Proc. of WWW7. - Elsevier, 1998. - PP. 259-270.
    (http://gatekeeper.research.compaq.com/ pub/DEC/SRC/technical-notes/SRC-1997-029-html/)
24. Cardelli L., Davies R. Service Combinators for Web Computing // Software Engineering. - 1999. - Vol. 25. - No. 3. - PP. 309-316.
    (http://citeseer.nj.nec.com/cardelli97service.html)
25. Hong T.W., Clark K.L. Concurrent programming on the web with Webstream: Technical Report / Department of Computing. Imperial College. - 2000.
    (http://www-lp.doc.ic.ac.uk/~klc/webstream.html)
26. Zhang Y., Keshav S. WebScript - A Scripting Language for the Web: Technical Report / Cornell CS Technical Report TR99-1742. - 1999.
    (http://www.research.att.com/~yzhang/papers/webscript-tr99.pdf)
27. Barish G., Knoblock C.A. Speculative Execution for Information Gathering Plans // Proc. of the 6-th Intern. Conf. on AI Planning and Scheduling (AIPS-2002). - Toulouse, France, 2002.
    (http://www.isi.edu/info-agents/papers/barish02-aips.pdf)
28. Pontelli E., Gupta G. W-ACE: A Logic Language for Intelligent Internet Programming / Department of Computer Science, New Mexico State University. - Las Cruces, US, 1997.
    (http://www.cs.nmsu.edu/lldap/download/web.ps.Z)
29. Malenfant J., Lapalme G., Vaucher J. ObjVProlog-D: distributed object-oriented programming in logic // Object Oriented Systems. - 1996. - Vol. 3. - No. 2. - PP. 61-86.
    (http://compscinet.dcs.kcl.ac.uk/OO/PDFPapers/oo030202.pdf)
30. Alferes J.J., Pereira L.M., Logic Programming Updating - a guided approach // In A. Kakas and F. Sadri (editors), Computational Logic: From Logic Programming into the Future - Essays in honour of Robert Kowalski. - Springer, 2002. - Vol. 2. - PP. 382-412.
    (http://citeseer.nj.nec.com/alferes02logic.html)
31. Dix J., Furbach U., Niemelae I. Nonmonotonic Reasoning: Towards Efficient Calculi and Implementations // In A. Voronkov and Robinson (editors) Handbook of Automated Reasoning.- Elsevier, 2001. - Vol. 2. - Chapter 18. - PP. 1121-1234.
    (http://www.cs.man.ac.uk/~jdix/Papers/01_Handbook_AR.ps.gz)
32. Inoue K., Kawaguchi S., Haneda H. Controlling Speculative Computation in Multi-Agent Environments // Proc. of the Second Intern. Workshop on Computational Logic in Multi-Agent Systems (CLIMA-01). - 2001. - PP. 9-18.
    (http://citeseer.nj.nec.com/inoue01controlling.html)
33. Satoh K., Yamamoto K. Speculative computation with multi-agent belief revision // Proc. of the first intern. joint conf. on Autonomous agents and multiagent systems (Bologna, Italy). - ACM Press, 2002. - PP. 897-904.
    (http://agents.umbc.edu/papers/satoh.pdf)
34. Морозов А.А. Акторный Пролог // Программирование. - 1994. - No. 5. - С. 66-78.
35. Морозов А.А., Обухов Ю.В., Олейников А.Я. Логическое программирование открытых систем // Логика, методология, философия науки: Тез. докл. XI межд. конф. - Обнинск, 1995. - С. 153-156.
    (http://www.cplire.ru/Lab144/obninsk.html)
36. Морозов А.А., Обухов Ю.В. Акторный Пролог. Определение языка программирования. - Москва, 1996. - Препринт ИРЭ РАН 2(613). - 57 с.
    (Новая версия определения языка опубликована на нашем сайте http://www.cplire.ru/Lab144/index.html)
37. Морозов А.А., Обухов Ю.В. Семантический анализ функциональных диаграмм информационных систем средствами объектно-ориентированного логического программирования // Развитие и применение открытых систем: Тез. докл. IV межд. конф. - Нижний Новгород, 1997. - С. 61-64.
    (http://www.cplire.ru/Lab144/rapros97.html)
38. Морозов А.А. Логический анализ функциональных диаграмм в процессе интерактивного проектирования информационных систем: Дис. ... канд. физ.-мат. наук. - Москва, 1998. - 199 с.
    (http://www.cplire.ru/Lab144/auto.html)
39. Morozov A.A. Actor Prolog: an Object-Oriented Language with the Classical Declarative Semantics // Proc. of IDL'99 workshop. - Paris, 1999.
    (http://www.cplire.ru/Lab144/paris.pdf)
40. Morozov A.A., Obukhov Yu.V., Gulyaev Yu.V. On the Problem of Using Logic Object-Oriented Programming in the World Wide Web // Proc. of the Special Russian Session "The Internet Developments in Russia". First IEEE/Popov Workshop on Internet Technologies and Services. - Moscow, 1999. - PP. 54-59.
    (http://www.cplire.ru/Lab144/internet.pdf)
41. Морозов А.А., Обухов Ю.В. О проблеме логического программирования интеллектуальных агентов Интернет // Дискретные модели в теории управляющих систем: Труды IV межд. конф. - М.: "МАКС Пресс", 2000. - С. 78-83.
42. Морозов А.А., Обухов Ю.В. О задаче логического распознавания в динамической среде Internet // Распознавание образов и анализ изображений: новые информационные технологии: Тез. докл. V межд. конф. - Самара, 2000. - С. 745-749.
43. Morozov A.A., Obukhov Yu.V. On the Problem of Logical Recognition in the Dynamic Internet Environment // Pattern Recognition and Image Analysis. - 2001. - Vol. 11. - No. 2. - PP. 454-457.
    (http://www.cplire.ru/Lab144/pria5.pdf)
44. Morozov A.A., Obukhov Yu.V. An Approach to Logic Programming of Intelligent Agents for Searching and Recognizing Information on the Internet // Pattern Recognition and Image Analysis. - 2001. - Vol. 11. - No. 3. - PP. 570-582.
    (http://www.cplire.ru/Lab144/pria570m.pdf)
45. Morozov A.A. On Semantic Link Between Logic, Object-Oriented, Functional, and Constraint Programming // Proc. of MultiCPL workshop. - Ithaca, USA, 2002.
    (http://www.cplire.ru/Lab144/multicpl.pdf)
46. Морозов А.А., Обухов Ю.В. Разработка математического аппарата логического программирования интеллектуальных агентов Интернета // Искусственный интеллект. - 2002. - N4. - С. 580-587.
    (http://www.cplire.ru/Lab144/ai2002.pdf)
47. Morozov A.A., Obukhov Yu.V. Development of the Methods and Tools for Mathematically Correct Logic Programming of Internet Agents // Pattern Recognition and Image Analysis. - 2003. - Vol. 13. - No. 2. - PP. 225-227.
    (http://www.cplire.ru/Lab144/pria225.pdf)
48. Морозов А.А. Логическая объектно-ориентированная модель асинхронных параллельных вычислений // Искусственный интеллект. - 2003. - N4. - С. 12-17.
    

    Электронная публикация:

49. Морозов А.А. Введение в Акторный Пролог. - М.: ИРЭ РАН, 2002.
    (http://www.cplire.ru/Lab144/start/r_index.html)

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

• Исходный текст программы. Результаты работы программы приведены на рис. A1.

  

  Рис. A1: Результаты работы исходной параллельной программы.

• Шаг 1. Из текста программы удаляются все нелогические встроенные предикаты.
• Шаг 2. Все конструкторы процессов в тексте программы заменяются обычными конструкторами экземпляров классов. Тем самым параллельная программа преобразуется в последовательную.
• Шаг 3. Моделирование отключающих портов.
• Шаг 4. Моделирование резидентов.
• Шаг 5. Удаление операций отправления прямых сообщений.
• Шаг 6. Удаление ключевых слов protecting.
• Шаг 7. Получена последовательная объектно-ориентированная программа на Акторном Прологе.
• Тест. Вычисление фрагмента теоретико-модельной семантики. Результаты работы тестовой программы приведены на рис. A2.

  

  Рис. A2: Результаты работы (упрощённой) последовательной программы.

Построенная последовательная программа удовлетворяет условиям теоремы 3.2.4, но не удовлетворяет условиям теоремы 3.2.5. Следовательно, гарантируется корректность исследуемой параллельной программы относительно её теоретико-модельной семантики, но при этом не гарантируется её полнота.

Здесь можно увидеть полный листинг агента Интернет, приведённого в качестве примера в разделе 3.4. Визуальное программирование агентов Интернет. Первую половину листинга (51% текста) занимает код, созданный автоматически для описания связей между блоками визуальной программы. Вторая половина листинга (49% текста) включает содержимое отдельных блоков, взятое из повторно используемых пакетов. В тексте программы условно указаны наименования и локальные адреса пакетов, содержимое которых было использовано при создании агента.

оглавление

дискуссия