Дубинин В.Н., Зинкин С.А. Языки логического программирования в проектировании вычислительных систем и сетей
Подождите немного. Документ загружается.
Министерство общего и профессионального образования
Российской Федерации
_________________________
Пензенский государственный технический университет
__________________________________________________
В. Н. Дубинин, С. А. Зинкин
ЯЗЫКИ ЛОГИЧЕСКОГО ПРОГРАММИРОВАНИЯ
В ПРОЕКТИРОВАНИИ ВЫЧИСЛИТЕЛЬНЫХ
СИСТЕМ И СЕТЕЙ
Учебное пособие
Пенза 1997
УДК 681.3.06 : 519.68
Д 79
Дубинин В. Н. Зинкин С.А. Языки логического программирования в
проектировании вычислительных систем и сетей: Учеб. пособие. - Пенза:
Изд-во Пенз. гос. техн. ун-та, 1997. - 100 с.: 18 ил., библиогр. 64 назв.
Рассматриваются вопросы использования языка логического
программирования Пролог в сетевой технологии проектирования
распределенных вычислительных систем и сетей. Приводится описание
предикатных сетей, интерпретируемых на языке Пролог, примеры
спецификации и моделирования вычислительных систем, процессов и
сетевых протоколов с использованием данного сетевого формализма.
Представлено описание временной логики для верификации
вычислительных систем и процессов, подробно описана реализация
временных операторов на Прологе, приводятся примеры формулировки и
доказательства свойств рассмотренных в пособии вычислительных систем,
процессов и сетевых протоколов.
Учебное пособие подготовлено на кафедре "Вычислительная техника"
и предназначено для студентов специальности 22.01.00, изучающих
дисциплины "Языки логического программирования", "Вычислительные
комплексы, системы и сети", "Системы искусственного интеллекта",
"Прикладная математика".
Рецензенты: кафедра "Прикладная математика и информатика" Пенз.
гос. пед. ун-та им. В. Г. Белинского (зав. кафедрой - д-р техн. наук, проф. В.
М. Линьков);
В. М. Михайлов, д-р техн. наук, гл. инж. НИИВТ
Издательство Пензенского государственного технического университета,
1997
В. Н. Дубинин, С. А. Зинкин, 1997
Введение
Идея использовать логику в качестве языка программирования
возникла впервые в начале 70-х годов. Первыми исследователями,
разрабатывавшими эту идею, были Роберт Ковальский (теоретические
аспекты) и Маартен ван Эмдем (экспериментальная демонстрационная
система). Наибольшую популярность из языков, основанных на логике,
завоевал язык логического программирования Пролог. Название Пролог
(PROLOG) образовано из первых частей английских слов PROgramming и
LOGic, что означает программирование в терминах логики. Данный язык
относится к языкам сверхвысокого уровня.
Основные особенности языка:
- является языком логического программирования. Теоретической
основой Пролога является логика предикатов. Модель логической
программы основана на подмножестве хорновских дизъюнктов логики
предикатов;
- в Прологе имеется мощный встроенный механизм логического
вывода с поиском и возвратом, встроенный механизм сопоставления с
образцом. В Пролог-системах реализован обратный вывод (от цели) методом
поиска вглубь;
- Пролог ориентирован на работу с символьной информацией;
- в Прологе единообразно представляются программы и данные, что
позволяет модифицировать программу во время ее работы;
- Пролог поддерживает декларативный стиль программирования.
Пролог-программы определяют "что" надо сделать, а не "как" это делается;
- в Прологе существует как декларативная, так и процедурная
семантика программ.
В настоящее время не существует стандарта на Пролог. Все же
реализация, описанная в книге [18], может быть принята за неофициальный
стандарт ядра "чистого" Пролога. Известны ряд версий и реализаций языка
Пролог, например, Arity Prolog, Turbo Prolog, CProlog, Quintus Prolog, Prolog-
2 и др. [11]. Возможна реализация Пролога на языке Лисп [52].
Области применения Пролога:
- программная инженерия, быстрая разработка прототипов
прикладных программ [18];
- создание динамических реляционных баз данных [19,22];
- быстрая разработка компиляторов [2,11,18,30];
- создание естественно-языковых интерфейсов [22];
- перевод с одного языка на другой;
- представление знаний, реализация экспертных систем (ЭС) и
оболочек ЭС [6,11,19,36];
- создание пакетов символьных вычислений для решений уравнений,
дифференцирования и интегрирования;
- автоматическое доказательство теорем и системы искусственного
интеллекта [6];
- управление производственными процессами.
Можно отметить, что в зарубежной и отечественной литературе
незаслуженно мало внимания уделено использованию языка Пролог в
проектировании. Внедрение методов искусственного интеллекта в процесс
проектирования, усложнение процедур поиска решений несомненно повысят
интерес к Прологу.
Данное учебное пособие посвящено использованию языка Пролог в
проектировании вычислительных систем и сетей в рамках сетевой
технологии проектирования. Под сетевой технологией понимается
технология проектирования на основе сетевых моделей, берущих свое начало
от хорошо известных сетей Петри (СП) [23].
На рис. 1 приведена схема сетевой технологии проектирования
распределенных вычислительных систем (РВС), разработанной авторами
учебного пособия. На данном рисунке прямоугольниками с прямыми углами
представляется начальный, конечный или промежуточные результаты, а
прямоугольниками с округленными краями - действия (этапы)
технологической цепочки. Разработан ряд программных инструментальных
средств, поддерживающих те или иные этапы данной технологии. К ним
можно отнести системы СИМС, СИМС-М, комплекс программ СИМС-
ГРАФ, а также библиотеку программ "Распределенная обработка - 1" (РО-1).
Аппаратной платформой для реализации РВС могут служить локальные сети
типа Ethernet на основе персональных ЭВМ, совместимых с IBM PC, а также
глобальная сеть Internet, предоставляющая разработчику широкий спектр
коммуникационных услуг. В обозначениях действий на рис. 1 в круглых
скобках отмечены те программные средства, которые поддерживают данное
действие технологической цепочки. В данном случае под обозначением
WWW понимаются средства гипертекстовой технологии WWW (World Wide
Web) глобальной сети Internet. Если для какого-либо этапа не отмечены
программные средства, то это означает, что в настоящий момент данный этап
не автоматизирован и действия должны производиться разработчиком
вручную. Из приведенной схемы видны место и роль языка Пролог в сетевой
технологии. В данном случае Пролог и средства, разработанные на его
основе, используются для спецификации и верификации систем, а также для
интерпретации результатов исследования сетевых моделей. Реализация этапа
интерпретации результатов сопряжена со следующими трудностями:
неформализованностью или слабой формализованностью данного этапа,
неинтерпретированностью сетевой модели. Последняя трудность выражается
в необходимости проекции свойств сетевой модели на свойства системы.
Этап интерпретации результатов исследования проводится с использованием
методов искусственного интеллекта, а автоматизация данного этапа - с
привлечением ЭС, реализованной на языке Пролог.
Ðèñ.1.Ñåòåâàÿ òåõíîëîãèÿ ïðîåêòèðîâàíèÿ ðàñïðåäåëåííûõ âû÷èñëèòåëüíûõ
ñèñòåì
В первой главе учебного пособия дано краткое описание предикатных
сетей, интерпретируемых на языке Пролог. Использование этого сетевого
формализма позволяет в значительной мере сократить и формализовать
описание параллельных систем со сложными видами
межпроцессных взаимодействий. Для спецификации и моделирования
параллельных взаимодействующих интеллектуальных систем предлагается
модификация предикатных сетей, связанная с введением структурированных
меток, меток с атрибутами-переменными, а также с использованием
способности к саморазвертыванию и самоизменению сетевой модели [37].
Примеры спецификации и моделирования вычислительных систем и
процессов с использованием предикатных сетей представлены во второй
главе. Приводится достаточно полное описание ряда типовых задач
синхронизации: задачи взаимного исключения, задачи об обедающих
философах, а также задачи некорректного разделения общих ресурсов.
Дается конечноавтоматное представление результатов моделирования
алгоритма взаимного исключения в распределенной вычислительной системе
и альтернативно-битового протокола.
В третьей главе представлено описание особенностей построения
языка временной логики, используемого для исследования сетевых моделей.
В пособии подробно описывается реализация временных операторов и
приводятся примеры формулировки и доказательства свойств рассмотренных
в пособии вычислительных систем и сетей.
1. МОДЕЛИРОВАНИЕ ПАРАЛЛЕЛЬНЫХ ДИСКРЕТНЫХ
СИСТЕМ С ИСПОЛЬЗОВАНИЕМ ПРЕДИКАТНЫХ СЕТЕЙ,
ИНТЕРПРЕТИРУЕМЫХ НА ЯЗЫКЕ ПРОЛОГ
В данной главе рассматривается метод моделирования параллельных
дискретных систем с помощью высокоуровневых сетей Петри,
интерпретируемых на языке Пролог. Данный класс систем характеризуется:
1) параллельным и асинхронным функционированием компонентов системы;
2) наличием сложных межкомпонентных взаимодействий и 3) дискретным
изменением параметров системы при ее работе. Примеры подобных систем
можно найти в технике и экономике. Весьма показательным примером
являются вычислительные сети и распределенные вычислительные системы
(РВС).
РВС - это полносвязная целевая система, представляющая
совокупность обрабатывающих узлов с распределенными по ним данными,
процессами обработки информации и управления и взаимодействующих
через каналы связи путем обмена сообщениями. Динамика работы РВС
характеризуется параллельностью и асинхронностью протекающих в
системе процессов, сложностью межпроцессных взаимодействий. РВС
могут быть реализованы на основе сети ЭВМ, предоставляющей
пользователю широкий круг коммуникационных услуг.
Основой архитектуры вычислительных сетей и РВС являются
коммуникационные протоколы (КП) - наборы правил взаимодействия систем
на различных уровнях иерархии. Протоколы определяют многие важные
аспекты работы сетей: надежность доставки данных, количество и качество
услуг, совместимость с другими сетями. Пристальный интерес к протоколам
и полученные в последние годы результаты позволяют говорить о
формировании новой научной дисциплины. Для точного и однозначного
описания КП разрабатываются методы формального описания. Модели,
лежащие в основе того или иного метода формального описания, позволяют
выполнить анализ (верификацию) описаний, а также автоматизировать
процесс трансляции этих описаний непосредственно в реализацию.
Анализ работ по протокольной тематике показал, что в качестве основы
языков и методов формального описания использовался самый
разнообразный математический аппарат [26,27,28,35].
Среди многих существующих методов моделирования сложных
параллельных дискретных систем выделяется подход, основанный на
использовании сетевых моделей, берущих свое начало от сетей Петри (СП)
[23]. Сетевые модели имеют следующие преимущества:
1) большие выразительные способности в представлении параллельных
асинхронных систем; способность представления локального
управления, параллельных, конфликтных, недетерминированных и
асинхронных событий; графическое представление сети; понятность
модели и легкость ее изучения;
2) возможность иерархического моделирования на их основе;
неинтерпретированность сетевой модели; возможность описания
системы на различных уровнях абстракции; возможность представления
системной иерархии;
3) возможность машинной поддержки в проектировании;
недетерминированность реализации сетевой модели; наличие методов
аналитического исследования сетевой модели.
В дальнейшем для моделирования параллельных дискретных систем
будут использоваться сети «предикат-переход» (Predicat/Transition Net) [32],
называемые в дальнейшем просто предикатными сетями. Причиной
введения предикатных сетей явилась необходимость компактного
представления больших и сложных систем без потери формальных основ
сетей Петри, на базе которых они разработаны. Для каждой предикатной
сети может быть построена уникальная сеть Петри, эквивалентная ей в том
смысле, что она моделирует ту же самую систему. С другой стороны,
существует множество возможностей свернуть сеть Петри в эквивалентную
ей предикатную сеть. Сжатость представления с помощью предикатной сети
объясняется тем, что элементы предикатной сети - переходы, позиции и дуги
представляют целый класс элементов эквивалентной сети Петри.
Количественно и качественно переход от сетей Петри к предикатным сетям
сравним с переходом от логики высказываний к логике предикатов
первого порядка. Также как и цветные сети Петри, предикатные сети
относятся к высокоуровневым сетям Петри. Эти два вида сетевых моделей
близки друг другу и являются взаимозаменяемыми. Существует тесная связь
между предикатными сетями и логическим программированием. Любую
логическую программу, представленную набором хорновских дизъюнктов
(например, Пролог-программу), можно представить в виде предикатной сети
и использовать при верификации программы методы анализа сетевых
моделей.
В данной главе рассматривается интерпретация предикатных сетей на
языке Пролог. В качестве инструментальной Пролог-системы используется
интегрированная система Arity Prolog [22], разработанная фирмой Arity
Corporation для РС-совместимых персональных ЭВМ и работающая под
управлением операционной системы MS-DOS. В отличие от широко
известного языка Turbo Prolog [8], также используемого при
программировании на ПЭВМ, язык Arity Prolog обладает перед первым
преимуществами в том плане, что он близок к классической Эдинбургской
версии языка Пролог и, таким образом, избавлен от ограничений языка Turbo
Prolog, что позволяет более эффективно решать задачи спецификации и
верификации. Синтаксис Arity Prolog аналогичен синтаксису DEC-10
Пролога [18]. Arity Prolog обладает следующими двумя особенностями,
которые облегчают разработку больших программ: 1) наличие виртуальной
памяти и 2) возможность разделения программы на сегменты.
1.1 Предикатные сети
Предикатная сеть состоит из следующих компонентов [32]:
1) Ориентированной сети (Р, T, F), где Р – множество позиций; Т –
множество переходов; F ⊆ P ×T ∪ T ×P – отношение потока. Позиции сети
представляют предикаты, истинное значение которых определяется их
маркировкой.
2) Структуры ∑, состоящей из множества индивидуальностей (цветов),
операций и отношений.
3) Разметки всех дуг сети формальными суммами кортежей,
составленных из переменных и индивидуальностей. Длина кортежа есть
арность предиката, ассоциированного с дугой. Кортеж нулевой длины
указывает на предикат без аргументов и обозначается специальным
символом ⊄ . Примеры пометок дуг представлены на рис. 1.1,а.
4) Логических формул, приписанных некоторым переходам. Данные
формулы строятся с помощью индивидуальностей, операций и отношений
структуры ∑, а также переменных. Свободные переменные в формуле
перехода должны встречаться на соседних дугах этого перехода. Истинность
логической формулы влияет на возможность срабатывания перехода при
данной маркировке. Примеры переходов с приписанными им логическими
формулами приведены на рис. 1.1,б. Если формула, приписанная переходу,
имеет форму v = trm & ..., где v – переменная и trm – терм, то все вхождения
переменной v для данного перехода могут быть заменены на терм trm.
(рис 1.2).