Содержание к диссертации
Введение
1. Методы реализации систем декларативного программирования 12
1.1. Декларативная парадигма программирования 12
1.1.1. Функциональное программирование 13
1.1.2. Логическое программирование 14
1.1.3. Функционально-логическое программирование 15
1.1.4. Формализм направленных отношений 17
1.2.Виды и модели вычисления декларативных программ 18
1.2.1. Функциональные программы 19
1.2.2. Логические программы 20
1.2.3. Функционально-логические программы 22
1.2.3.1. Спрямление 22
1.2.3.2. Сужение 23
1.2.3.3. Логика 24
1.2.3.4. Декларации режимов вычислений 25
1.3.Реализация моделей вычисления 28
1.3.1. SECD-машина 26
1.3.2. Виртуальная машина Уоррена (WAM) 27
1.4.Вычисление направленных отношений 28
1.4.1. Вид программы 28
1.4.2. Внутреннее представление 28
1.4.3. Модели вычислений 29
1.4.4. Задачи редукции сетей 31
1.4.5. Реализация вычисления 32
1.5.Визуальное программирование 33
1.5.1. Логическое программирование на Акторном Прологе 33
1.5.2. Функциональное программирование в LabView 34
1.5.3. Система программирования для языка СИПРОЛ 35
1.5.4. Программирование на основе СПНО 35
1.5.5. Вопросы автоматического построения изображения сетей 36
Основные результаты и выводы 38
2. Модели и методы вычисления направленных отношений 39
2.1.Основные понятия теории НО 39
2.2. Алгебраическое определение НО 40
2.3.Сетевое представление НО 41
2.3.1. Размеченные сети 41
2.3.2. Графическая нотация 43
2.3.3. Синтаксические операции над сетями 45
2.3.4. Трансформационные операции над сетями 47
2.3.4.1. Подстановка 47
2.3.4.2. Редукция 48
2.3.5. Операции композиции сетей 50
2.4.Базовая модель вычисления НО 52
2.4.1. Цель и задачи вычисленияНО 52
2.4.2. Сетевой язык 52
2.4.3. Применение редукции сетей 54
2.4.4. Виды запросов 56
2.4.5. Стратегии вычислений 57
2.4.5.1. Поиск в глубину 57
2.4.5.2. Поиск в ширину 58
2.4.5.3. Смешанные стратегии 58
2.5.Логический вывод 60
2.5.1. Логика предикатов и НО 60
2.5.2. Модификация базовой модели вычисления НО 60
2.5.3. Мультиправила 61
2.5.4. Стратегии вывода 63
2.6.Вопросы оптимизации вычислений 64
2.6.1. Редукция «по фронту» 64
2.6.2. Кольцевая подстановка 66
2.6.3. Подстановка с контекстом 67
2.6.4. Оптимизация последнего вызова 68
2.6.5. Оптимизация порядка применения правил 68
2.7. Абстрактная машина вычисления НО 69
2.7.1. Базовый набор вычислительных операций 69
2.7.2. Алгоритм работы машины 72
Основные результаты и выводы 73
3. Подсистема исполнения запросов СФЛП 74
3.1.Цели и задачи 74
3.2.Внутреннее представление сетевых программ 74
3.2.1. Представление сетевой грамматики 75
3.2.2. Представление сетей 75
3.2.3. Разметка сетей 77
3.2.4. Графическое представление 79
3.2.5. Формат хранения во внешней памяти 79
3.3.Базовые механизмы вычисления 80
3.3.1. Подстановка 80
3.3.2. Редукция 84
3.4.Оптимизация вычислений 87
3.4.1. Кольцевая подстановка 88
3.4.2. Оптимизация последнего вызова 89
3.4.3. Упорядочивание правил 89
3.4.4. Анализ подстановочной разметки 90
3.4.5. Мультиправила 90
3.4.6. Эффективность оптимизации 90
3.5. У правление процессом вычисления 91
3.5.1. Поиск в глубину 91
3.5.2. Поиск в ширину 93
3.5.3. Маски вычислимости 94
З.б.Системные отношения и типы данных 95
3.6.1. Натуральные числа, списки и строки 95
3.6.2. Функциональные системные отношения 96
3.7.0тладка программ и отображение результатов вычисления 97
3.7.1. Дерево отладки 97
3.7.2. Статистика вычисления 99
3.7.3. Отображение результатов вычисления 100
3.8.Режимы вычисления 101
3.8.1. Режим вычислений с разметкой 101
3.8.2. Генерация языка по КССГ 102
3.8.3. Логический вывод 102
3.8.4. Компиляция программ языка S-FLOGOL 102
3.9.Импорт программ на языке Пролог 103
3.9.1. Ограничения на импортируемые программы 103
3.9.2, Системные предикаты и списки 105
Основные результаты и выводы 106
4. Графический редактор СФЛП 108
4.1.Технология графического программирования 108
4.1.1. Формирование грамматики 108
4.1.2. Построение правил грамматики 111
4.1.2.1. Операции формирования структуры тела правила 111
4.1.2.2. Вспомогательные структурные операции 113
4.1.2.3. Вспомогательные графические операции 115
4.2.Графический редактор 116
4,2.1. Основные требования к редактору 116
4.2.2. Принципы построения 118
4.2.3. Архитектура редактора 119
4.2.4. Интерфейс пользователя 120
4.2.5. Основные подсистемы редактора 123
4.3.Особенности реализации графического редактора 126
4.3.1. Формирование и прорисовка изображения 127
4.3.2. Построение дуг между объектами сети 128
4.4. Автоматическое формирование графического изображения сети 131
4.4.1. Этапы построения графического изображения сети 132
4.4.2. Учет геометрических размеров объектов сети 134
4.4.3. Минимизация объема вычислений методом оболочек 137
4.4.4. Формирование сил отталкивания 139
4.4.5. Отслеживание колебательного движения объектов 139
Основные результаты и выводы 141
Заключение. Основные результаты работы 142
Список сокращений 143
Список литературы
- Функциональное программирование
- Алгебраическое определение НО
- Модификация базовой модели вычисления НО
- Формат хранения во внешней памяти
Введение к работе
Разработка языков и сред программирования, предназначенных для представления знаний, и лежащих в их основе формальных систем является актуальной задачей. Известные уже достаточно давно языки функционального программирования Лисп и логического программирования Пролог создавались на основе теории вычислимых функций и логики предикатов как средства программирования и эффективного решения задач искусственного интеллекта, обработки сложно организованных данных на основе формального, как правило, аксиоматического задания их свойств и взаимосвязи. В проектах создания вычислительных систем нового поколения автоматизация и эффективность логических доказательств были и остаются центральными проблемами.
Указанные языки легли в основу направления декларативного программирования, которое предполагает определение программы в виде совокупности формального описания объектов и зависимостей между ними, характеризующего некоторую предметную область, и запроса на нахождение (построение) объектов с конкретными заданными свойствами. Декларативный подход к построению программ позволяет получать интересующую пользователя информацию о предметной области с помощью некоторой процедуры автоматического вывода без явного указания последовательности действий, которые необходимо выполнить вычислительной машине для получения результата.
В настоящее время ведутся активные исследования в области создания реляционных формализмов и языков, которые должны существенно расширить возможности представления и обработки данных и знаний. В работах [35,36] разработана теория направленных отношений (НО), которая объединяет логический, реляционный и функциональный формализмы. Созданный на этой основе язык функционально-логического программирования [46] позволяет перейти к практической реализации высокоуровневых сред и систем программирования, отличающихся высоким уровнем автоматизации процессов разработки
8 программ, широким использованием средств графического представления при построении и структурных преобразованиях программ. В рамках выполнения проекта РФФИ № 01-01-00690 «Разработка теоретических основ построения вычислительных сред и интеллектуальных систем, ориентированных на функционально-логический стиль программирования» была поставлена задача создания на базе языка FLOGOL системы функционально-логического программирования (СФЛГТ), решение которой рассматривается как цель проводимых в диссертации исследований.
В указанных выше работах по теории НО, наряду с составляющим основу построения языка FLOGOL алгебраическим (композиционным) подходом к построению схем НО, разработано сетевое представление схем НО в форме множеств особым образом определенных сетей (сетевых языков). Между сетевым представлением и представлением НО в форме системы реляционных уравнений существует взаимный переход, сохраняющий их эквивалентность в интерпретации. С одной стороны, сетевое представление является естественной и наглядной формой программирования в терминах НО, с другой, один из основных компонентов СФЛП - подсистема исполнения запросов (ПСИЗ) непосредственно базируется на сетевом представлении НО и фундаментальных свойств базисных НО. Учитывая вышесказанное, можно сформулировать перечень основных научно-практических задач, решаемых в диссертационной работе:
критический анализ известных моделей вычислений программ языков декларативного программирования и их реализаций с целью оценки возможности их применения при разработке СФЛП;
разработка и исследование моделей вычислений на основе сетевого представления НО (СПНО);
программная реализация подсистемы исполнения запросов СФЛП на основе разработанных моделей вычислений НО;
разработка технологии корректного и комфортного для пользователя графического построения программ в сетевой форме;
исследование и оптимизация метода автоматического построения графического изображения СПНО;
программная реализация интерфейсного модуля СФЛП, предназначенного для создания сетевых программ графическим способом, поддержки их выполнения и отладки.
Методы исследования. При выполнении работы использованы методы теории направленных отношений, математической логики, теории формальных языков, теории алгоритмов, объектно-ориентированного программирования, тестирования программных продуктов.
Достоверность полученных результатов. Достоверность полученных результатов и выводов подтверждается результатами тестирования реализованной СФЛП на наборе типовых задач функционального и логического программирования.
Научная новизна. Научная новизна работы заключается в следующем:
Введено понятие размеченной сети на основе расширения понятия сети, определенного в теории НО. Предложены новые правила редукции для размеченных сетей и разработана сетевая модель вычисления НО.
Предложены модификации основных механизмов и стратегий вычисления НО, позволяющие повысить эффективность ПСИЗ, в частности, выполнения вычислительных операций подстановки и редукции сетей. Разработан алгоритм сетевой подстановки линейной сложности.
Разработана оригинальная технология графического построения программ на уровне СПНО, обеспечивающая корректность формируемой программы на каждом шаге ее построения.
Предложена модификация метода построения изображения сети на основе взаимных силовых воздействий ее объектов, повышающая адекватность формируемого изображения и снижающая вычислительные затраты на его построение.
Практическая значимость. Практическая значимость полученных научных результатов определяется их использованием при построении СФЛП, реализованной совместно с Бебчиком Ал.М., которая предоставляет средства программирования с естественным сочетанием функционального, реляционного и логического стилей программирования, возможность структурного сетевого представления программ, упрощающего их анализ и преобразования с использованием формализма НО. Практическая значимость работы подтверждается внедрением СФЛП в учебный процесс МИРЭА, МЭИ и МАИ, о чем имеются акты о внедрении.
Апробация работы. Основные результаты диссертации докладывались и обсуждались на научно-технических конференциях МИРЭА (Москва, 2002, 2003, 2004), международных конференциях «Информационные средства и технологии» (Москва, 2003, 2004), всероссийской межвузовской научно-технической конференции «Микроэлектроника и информатика - 2004» (Зеленоград, 2004), международной научно-технической конференции «Информационные технологии в науке, образовании и производстве» (Орел, 2004), международной конференции «Континуальные алгебраические логики, исчисления и нейроинформатика в науке и технике» (Ульяновск, 2004), международной научно-технической конференции «Компьютерное моделирование 2004» (Санкт-Петербург, 2004) и «Девятой Национальной конференции по искусственному интеллекту с международным участием КИИ-2004» (Тверь, 2004).
Реализованная СФЛП демонстрировалась на выставке программных продуктов «Девятой Национальной конференции по искусственному интеллекту с международным участием КИИ-2004».
Публикации. Основные результаты, полученные при выполнении диссертационной работы, опубликованы в 9 печатных работах.
Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения, списка литературы, включающего 94 наименования, и при-
11 ложений. Диссертация содержит 152 страницы машинописного текста без учета приложений.
В первой главе проводится анализ современных подходов к построению языков и систем декларативного программирования. Особое внимание уделяется моделям вычислений, используемым в системах функционального и логического программирования, и методам их реализации с целью оценки возможностей их применения при создании СФЛП. Рассматриваются вопросы графического построения программ.
Во второй главе кратко излагаются основные понятия теории НО, вводится понятие размеченной сети, разрабатывается базовая модель вычисления НО и предлагаются ее модификации. Для повышения эффективности вычислений вводятся соответствующие оптимизационные преобразования. Разрабатывается абстрактная машина вычисления НО.
В третьей главе определяются цель и задачи подсистемы исполнения запросов (ПСИЗ) и рассматриваются вопросы ее реализации. Приводится формат внутреннего представления сетевых программ и разрабатываются вопросы реализации основных вычислительных механизмов. Вводятся системные типы данных и системные НО. Описывается импорт программ на языке Пролог.
В четвертой главе исследуются вопросы графического программирования. Предлагается технология графического построения программ, гарантирующая корректность формируемой программы на каждом шаге ее построения. Рассматриваются архитектура и вопросы реализации графического редактора. Описываются модификации метода автоматического построения изображения сетей и его реализация.
В заключении приводятся основные результаты работы.
1. МЕТОДЫ РЕАЛИЗАЦИИ СИСТЕМ ДЕКЛАРАТИВНОГО
Функциональное программирование
В настоящее время среди большого числа стилей и систем программирования можно выделить два крупных направления - императивное программирование и декларативное программирование. Императивное программирование основано на определении программы в виде пошаговой инструкции, описывающей порядок выполнения действий, необходимых для решения задачи. Возникновение и развитие такого подхода к программированию обусловлено в первую очередь широкой распространенностью машин, построенных на принципах архитектуры Фон-Неймана. Основным достоинством императивного программирования является высокая эффективность выполнения скомпилированного на машинный язык кода. Это объясняется тем, что императивный язык высокого уровня, по сути, есть лишь своего рода «надстройка» над машинным языком, позволяющая использовать средства построения и отладки программ более высокого уровня абстракции. Несмотря на высокую эффективность выполнения программ на языках императивного типа, такой подход имеет и недостатки. Основным из них является то, что программист вынужден разрабатывать алгоритм решения задач, зачастую отдаляясь от семантики взаимосвязей объектов предметной области и логики решаемой задачи. 1.1. Декларативная парадигма программирования.
Принципиально иным подходом к программированию является декларативное программирование, в основе которого лежит определение программы в виде формального описания задачи с последующим извлечением решения согласно вычислительной модели выбранного формализма.
Основным достоинством декларативного подхода является то, что программист может сосредоточить внимание на формальном описании решаемой задачи, а не на методах ее решения, которые автоматически выбираются некоторым вычислителем. Программа декларативного языка описывает взаимосвязь исходных данных и результата решения, вследствие чего она имеет ясную семантику, естественно отражающую логику решаемой задачи. Еще одним преимуществом является возможность естественного распараллеливания процесса вычисления программ большинства декларативных языков, в то время как программы императивных языков, изначально рассчитанные на последовательное выполнение, крайне плохо поддаются распараллеливанию.
Несмотря на очевидные преимущества декларативного подхода, он также имеет и недостатки, к которым можно отнести сравнительно невысокую эффективность выполнения программ и предъявление высоких требований к объему доступной оперативной памяти. Однако наметившийся в последнее время быстрый рост объема оперативной памяти вычислительных машин (ВМ) и интенсивное развитие направления параллельных вычислений позволяют по-новому взглянуть на указанные недостатки и снижают их значимость в свете проблем, возникающих при распараллеливании программ императивных языков. 1.1.1. Функциональное программирование. В основе функционального программирования (ФП) лежит понятие математической функции, определяющей зависимость между исходными данными и результатом вычисления. Программа, записанная на функциональном языке, представляет собой совокупность описаний, в общем случае, частичных рекурсивно-определенных функций, одна из которых используется в качестве целевой функции вычисления. Важным преимуществом таких языков по сравнению с языками императивной парадигмы является отсутствие переменных с возможностью переопределения их значений («разрушающего» присваивания). Переменная в функциональном языке - это лишь обозначение некоторого, пока не известного, объекта.
В силу того, что в основе функциональных языков, как правило, лежат строгие математические формализмы, семантика таких программ представляется достаточно ясной и хорошо поддается формальному анализу.
Первым языком ФП считается язык Лисп, который был создан Маккарти в 1958г. [79] и с тех пор не претерпел существенных изменений. Современные диалекты этого языка отличаются, в основном, наборами примитивных функций и используемыми моделями вычисления. Так, в отличие от Лиспа, имеющего энергичную модель вычисления и динамическое связывание, язык LispKit имеет ленивую модель вычисления, а язык CommonLisp поддерживает как динамическое, так и статическое связывание [89]. Отличительной чертой языка CommonLisp и некоторых других диалектов является возможность использования разрушающего присваивания, массивов, циклов и других элементов императивного программирования, повышающих гибкость программирования, но нарушающих чистоту языка.
Другими направлениями развития языков ФП являются введение строгой статической типизации (языки Норе [57], Haskell [82], Miranda [91]) и техники сопоставления с образцом (Refal [90], Норе), а также использование Pascal-подобного синтаксиса (Haskell, ML) и декларативных подсистем ввода-вывода (Haskell, ML). Кроме этого, практически все современные языки имеют развитые средства поддержки многомодульного программирования, что наряду с перечисленными выше возможностями позволяет рассматривать их как языки промышленного уровня.
Логическое программирование. Еще одним видом декларативного подхода к программированию является логическое программирование (ЛП). В основе классического понимания ЛП лежит исчисление или логика предикатов первого порядка. Исчисление предикатов, предложенное Г. Фреге, оказалось весьма удобным формализмом для описания объектов и отношений между ними. Логическая программа, по сути, представляет собой описание некоторой предметной области в виде множества истинных утверждений (аксиом), называемое также базой знаний. Вычисление программы состоит в попытке доказательства выводимости утверждения, называемого запросом, из утверждений рассматриваемой базы знаний. При этом, как правило, выполняется построение объектов, указанных в запросе в качестве искомых.
Алгебраическое определение НО
Формально, языки НО строятся как индуктивно определяемые множества интерпретированных схем, причем основу каждого языка НО составляют в некотором смысле универсальное множество так называемых комбинаторных констант и операций композиции НО и множество исходных базисных НО, образующих область значений свободных переменных схем НО. Замыкание множества базисных НО и констант относительно множества операций композиции НО и определяет конкретный язык НО. В общем виде НО определяется через систему реляционных уравнений: ( ) Д.(п,"Лі) =?., І = 1,2,...,п, где г. - (mr,rtf)-арные термы, представляемые как конечные композиции базисных НО, комбинаторных констант и переменных НО Ri} і = 1,2,...,и. В интерпретации система уравнений ( ) задает кортеж НО /?1min,...,i?nmin - минимальное (относительно отношения включения НО) решение системы реляционных уравнений ( ). Последовательной композицией НО Rl и R2 называется произведение их графиков: (Д . " )(« ) = {(а,Д)3/((«,/)є &(/,/?) є Д2)}. Операция последовательной композиции является ассоциативной.
Параллельной композицией НО R] и R2 называется раздельное декартово произведение компонентов их графиков: (Д, Яі)#Д2("2 ) + 1+) {( а ДД)! (аг,,Д)єЛ, &(а2,/?2)єЛ2}. Операция параллельной композиции также является ассоциативной.
Объединением HO ІЇ, и ії2 называется их теоретико-множественное объединение как графиков и обозначается через R vjR2.
Сетевое представление НО.
Сетевое представление НО (СПНО) является естественной и наглядной формой определения НО, а также основой для создания эффективных моделей их вычисления. На базе СПНО реализованы графический редактор (глава 4) и ПСИЗ СФЛП (глава 3). Отметим, что между сетевым представлением и представлением НО в форме системы реляционных уравнений существует взаимный переход, сохраняющий их эквивалентность в интерпретации. 2.3.1. Размеченные сети. Вводимое в работе понятие размеченной сети, в основном, опирается на понятие сети из [46]. В нем появляется еще один - семантический - компонент, т.н. разметка точек сети, предполагающая, что известен носитель D, множество НО на котором является областью реляционной интерпретации размеченных сетей и соответствующих сетевых языков. Фактически, размеченная сеть представляет собой частично интерпретированную сеть.
Базисом элементов В называется тройка (X,fit ,/л"), где X -конечное множество сортов элементов; //,// : X —»0.. - функции, задающие арность (ju (x\ ju (x)) элементов каждого сорта хеХ; //(л) называется количеством входов, а ц"{х) - количеством выходов элементов сорта х. В дальнейшем, для краткости, базисы рассматриваются как множества сортов элементов с указанием в качестве верхних индексов их арностей.
Размеченной сетью S арности (п\пя), п\п" 0, в базисе элементов В называется шестерка P,I,O,E,U,o 0 , где Р — конечное множество точек сети, т0 - частичное отображение точек сети на носитель D {начальная разметка точек сети); 1,0 є Р - кортежи входных и выходных точек сети, /1= п и О \= п"; EczBxP xP - множество элементов сети, такое, что для всех e= xje,0e eE I IS І = ju {x), \Ое\= /J"(X) ; х = (е) - сорт элемента є сети iS, Іе - кортеж его входных, а Ое кортеж его выходных точек; U - граф семантического различия точек сети, сокращенно, dif—граф сети (точнее, U — множество ребер этого графа, & Р — множество его вершин). Подмножество точек сети - область определения о"0 - обозначим dom(a0). Иногда удобно считать, что отображение сг0 определено для каждой точки сети, полагая, что для неразмеченных точек р .dom(a(j) значением сг0(р) является особый элемент _LgD. Сети рассматриваются с точностью до изоморфизма относительно множества точек сети; множества точек различных сетей не пересекаются.
Семантика сети выражена в ее реляционной интерпретации как НО на носителе D. Фиксируем интерпретацию (р сортов элементов из базиса В так, что для всех Xі" "} є В p\xl- НО арности {п\п") на носителе D. Интерпре ІГ тация Ч S сети S = P,I,O,E,U,a0 , индуцированная интерпретацией р, есть {(а ,а")\ (3сг:Р- D)((Vpєdonicr ))(а(р) = cr0(р))&а =a(I)&а" = а(0)& №/}Е[/)(ф а{/))&(УЄ, е)Ое єМе))(т(0())Є ]))} Интерпретация множества 2 размеченных сетей есть J 2 = (J I .
Иными словами, график НО определяется возможными способами доопределения начальной разметки, удовлетворяющими требованиям, предъявляемыми к разметке биографом и множеством элементов сети при заданной интерпретации элементов базиса. При этом, если начальная разметка уже не удовлетворяет этим требованиям, то сеть интерпретируется как пустое НО (обозначается 0). Заметим также, что семантика размеченной сети не изменится, если множество ребер dif-графа дополнить любым подмножеством из множества ребер {{р\р } р є dom((T0) &р"є dom(a0)& aQ(p ) Ф т0(/»")}
Модификация базовой модели вычисления НО
Для повышения эффективности вычислений в СФЛП требуется применять специальные методы оптимизации. В данном параграфе речь идет об оптимизации вычислительных механизмов, а не об оптимизации программ. 2.6.1. Редукция «по фронту». Эффективность процедуры редукции существенно влияет на производительность ПСИЗ в целом, так как редукция выполняется на каждом шаге вычисления. При выполнении редукции можно выделить две основные задачи - анализ сети на применение некоторого правила редукции и, собственно, применение этого правила. Затраты на анализ сети могут быть естественным образом уменьшены за счет сокращения области сети, в которой ведется поиск применимости правил редукции. Несложно заметить, что однажды приведенная к НФ сеть может быть выведена из НФ только внесением некоторых изменений, а именно, выполнением подстановки тела правила вместо некоторого элемента сети, так как после подстановки в сети могут оказаться новые элементы (или по-иному связанные прежние элементы), которые нарушают НФ, Таким образом, определив границу изменений, мы можем сократить и участок сети, на котором, возможно, нарушена НФ. Начало выполнения редукции с точек, лежащих на границе возможных изменений, сокращает (обычно, достаточно существенно), область поиска фрагментов сети для применения правил редукции. Граница изменений определяется точками, связанными с замещаемым при подстановке элементом, поэтому естественно начинать анализ именно с этих точек, продолжая его в «направлениях» их связей. Множество точек (обозначим его W), подлежащих анализу, образуют «фронт» редукции. Выполнение анализа указанным способом напоминает распространение «фронта», благодаря чему предложенная в работе форма организации редукции получила название редукции «по фронту».
Так как W, в общем случае, содержит более одной точки, возникает вопрос, какую точку выбрать для анализа ее окрестности на применимость правил редукции. Можно выделить две основные стратегии поиск в ширину и поиск в глубину, которые можно охарактеризовать следующим образом. Пусть WQ -исходное состояние W, Wx — множество вновь внесенных точек после выполнения анализа точки weJF0 и т.д, а щ -\W0 \,щ -\WX \,... . Поиск в ширину предполагает выполнение сначала п0 шагов анализа для всех точек W0, после чего выполняется анализ для всех л,. точек, таких что we[j . и т.д. Такая i=l 1=2 стратегия соответствует постепенному продвижению анализа вглубь сети.
Поиск в глубину предполагает анализ сначала одной точки из WQ, затем одной точки из Wx и т.д. до тех пор, пока на к -м шаге множество Wk не окажется пустым. После этого выбирается одна точка из Wk_l и так до тех пор, пока множество W не окажется пустым. Эта стратегия соответствует просмотру сети «вглубь» до тех пор, пока существует возможность применения правил.
Рассмотрим стратегии редукции при реализации анализа применимости правил. При использовании поиска в глубину мы обеспечиваем последовательный анализ каждого из «аргументов вызова». При реализации же поиска в ширину мы обеспечиваем равномерный «постепенный» анализ всех аргументов. Легко представить случаи, когда поиск в ширину оказывается предпочтительнее поиска в глубину, и наоборот, однако для реализации в ПСИЗ СФЛП был выбран именно поиск в ширину, поскольку обычно для определения применимости правила требуется не очень глубокий анализ аргументов и, следовательно, равномерность их анализа в этой ситуации является предпочтительной для быстрого отсекания не применимых правил. Заметим, что после того, как точка проанализирована, она удаляется из W, однако в случае, если после применения редукции ее окрестность изменяется, точка вновь включается в W.
Кольцевая подстановка. Для выполнения подстановки производится копирование исходной сети и тела правила и, если при анализе некоторых из них выяснится, что сеть интерпретируется как пустое НО, то затраты, произведенные на копирование других элементов, окажутся непродуктивными. В случае достаточно больших сетей, интерпретацией которых является пустое НО, суммарные затраты на обработку объектов сети, не понадобившихся для определения этого факта, могут быть весьма существенными. Для решения данной проблемы предложен особый способ копирования сети и выполнения подстановки, основанный на отказе от копирования элементов сетей вплоть до появления в этом необходимости, и названный кольцевой подстановкой. Схема выполнения кольцевой подстановки приведена на рис. 2.12.
Формат хранения во внешней памяти
Формат хранения внутреннего представления должен, с одной стороны, позволять с приемлемой скоростью сохранять и загружать программы, а, с другой, по возможности, обеспечивать минимальный размер сохраняемого файла. Для сохранения внутреннего представления был выбран двоичный тип файла с последовательной записью, сначала объектов-сортов, а затем - объектов-сетей КССГ. Для обеспечения обратной совместимости программ для каждого объекта (и файла в целом) записывается номер версии процедуры сохранения. При попытке прочитать файл, запи санный процедурой сохранения предыдущей версии, отсутствующие свойства задаются по умолчанию, а существующие, в случае необходимости, преобразуются к нужному виду. 3.3. Базовые механизмы вычисления.
Общая схема работы ПСИЗ соответствует приведенному в главе 2 алгоритму работы абстрактной машины вычисления НО (АМНО), построенной на основе небольшого набора команд, которые условно можно разделить на две группы — поисковые и трансформирующие. Механизмы, на основе которых выполняются трансформирующие команды, назовем базовыми и отнесем к ним копирование сетей, подстановку и редукцию [12].
Подстановка. Разработка и реализация эффективного алгоритма выполнения подстановки является важным аспектом обеспечения высокой эффективности ПСИЗ в целом. Для выполнения подстановки разработан алгоритм линейной сложности относительно числа связей входов и выходов замещаемого элемента и входов и выходов тела правила, использующий особенности оригинального внутреннего представления сети.
Ключевой особенностью операции подстановки, положенной в основу разработки соответствующего алгоритма, является полное совпадение количества входов и выходов у замещаемого элемента и тела правила. Исходя из этого, естественно выполнять подстановку путем отождествления точек для каждой из пар вход замещаемого элемента, вход тела правила , выход замещаемого элемента, выход тела правила (далее такие пары будем называть подстановочными парами).
Одной из основных сложностей, возникающих на пути реализации данного метода, является то, что подстановочные пары могут быть связаны друг с другом посредством общих (отождествленных) точек. Например, два входа в теле правила могут быть объединены общей точкой. Наличие таких связанных подстановочных пар не позволяет рассматривать их независимо друг от друга и значительно усложняет алгоритм. Исходя из этого, выполнение подстановки производится путем последовательного перебора подстановочных пар и отождествлением их точек с учетом изменений, произведенных на предыдущих шагах. Учет изменений реализован на основе некоторых специфических особенностей, возникающих в структурах данных после отождествления связанных подстановочных пар, без явного ведения какой-либо «истории».
В процессе отождествления точек подстановочных пар необходимо производить корректировку связей, соединяющих эти точки с другими объектами сети. Для повышения эффективности вычислений в процессе подстановки дополнительных связей не создается - вместо этого используется перепривязывание существующих связей на нужные объекты. Связи, соединяющие точки с замещаемым элементом и рамкой тела правила, удаляются.
После отождествления точек подстановочных пар выполняется завершающий этап подстановки, на котором удаляются замещаемый элемент и рамка тела применяемого правила. Для удаления этих объектов используется простое освобождение памяти вместо достаточно сложной стандартной процедуры удаления элементов сетей, так как на данном этапе их внутреннее представление отличается от обычного отсутствием каких-либо связей.
