Хоггер К. - Введение в логическое программирование [1988, DjVu, RUS]

Предисловие редактора перевода................5
Предисловие........................J
Предисловие автора.....................®
Введение..........................11
I. Представление знаний и рассуждения..........16
1.1. Индивидуумы................. . . 16
1.2. Отношения....................['
1.3. Предикаты, связки и формулы.......... . . I»
1.4. Переменные....................20
1.5. Предложения...................22
1.6. Примеры представлений...............
1.7. Интерпретация предложений........... . . 26
1.8. Логическое следствие................30
1.9. Логический вывод..............* * * о?
1.10. Общая резолюция сверху вниз............35
1.11. Решение задач................. • 39
I. 12. Извлечение ответа.................42
I. 13. Резюме.....................45
1.14. Исторический очерк.................46
t
II. Логические программы ................51
II. 1. Программы, вычисления и исполнение программ.....51
II. 1.1. Утверждения в программах...........51
II. 1.2. Назначение и структура программ........54
II. 1.3. Исполнение программ.............65
II. 1.4. Вычисления.................56
II. 2. Процедурная интерпретация..............57
II. 2.1. Структура целевого утверждения........57
II. 2.2. Структура процедуры............ . . 57
II. 2.3. Операция вызова процедуры..........58
II. 2.4. Вход в процедуру и выход из процедуры.....60
II. 2.5. Выбор вызова . . .............61
II. 2.6. Выбор процедуры . ...........62
II. 3. Пространство вычислений..............63
И. 3.1. Классификация вычислений ............63
II. 3.2. Полное пространство вычислении........64
II. 3.3. Действие правил выбора............64
II. 4. Стандартная стратегия управления...........68
II. 4.1. Недетерминированность и поиск.........68
II. 4.2. Правило вычислений.............69
II. 4.3. Правило поиска . ..............71
И. 4.4. Станлаотная ......................73
11.5. Поведение программы в ходе вычислений........74
II. 5.1. Обработка данных..............74
II. 5.2. Упорядочение................77
II. 5.3. Ветвление..................80
II. 5.4. Итерация..................82
II. 5.5. Рекурсия..................86
II. 6. Встроенные средства................87
II. 6.1. Встроенные процедуры.............88
II. 6.2. Встроенные функции..............89
II. 7. Исторический очерк......................90
III. Стиль программирования...............94
III. 1. Логика и управление...............95
III. 2. Итерация и рекурсия...............99
III. 3. Поведение сверху вниз и снизу вверх . ........101
III. 3.1. Вычисления факториалов...........102
III. 3.2. Нахождение путей в графах.........104
III. 3.3. Задача нахождения собственных значений и собственных векторов матрицы ..........106
III. 4. Детерминизм и недетерминизм............НО
III. 4.1. Поиск в списке...............ПО
III. 4.2. Обнаружение пика..............112
III. 4.3. Задача о подстроке.............114
III. 5. Отрицание . ...................118
III. 6. Согласование параметров..............124
III. 7. Переключатели..................126
III. 8. Исторический очерк................127
IV. Структуры данных •..................131
IV. 1. Представление и выборка данных...........132
IV. 1.1. Термы и факты...............132
IV. 1.2. Прямой и косвенный доступ..........134
IV. 2. Представления посредством структурированных термов . . 135
IV. 2.1. Некоторые общие типы данных .........135
IV. 2.2. Программы нахождения следующего элемента ... 137
IV. 2.3. Программы для задачи о палиндроме......139
IV. 2.4. Контроль соответствия типов.........142
IV. 3. Представления посредством фактов..........143
IV. 3.1. Общие принципы..............144
IV. 3.2. Контроль соответствия типов .........145
IV. 3.3. Индексирование...............146
IV. 3.4. Массивы и индексы.............148
IV. 4. Обработка данных в виде фактов...........150
IV. 4.1. Имена как выходные данные.........150
IV. 4.2. Факты как выходные данные: метод, используемый в
Прологе.................151
IV. 4.3. Факты как выходные данные: порождение лемм . . 154
IV. 4.4. Имена для структур данных, представленных в
виде фактов................158
IV. 4.5. Еще раз о задаче нахождения собственных значений
и собственных векторов...........160
IV. 5. Исторический очерк................163
V. Верификация программ................165
V. 1. Вычисляемые и специфицируемые отношения.......165
V. 1.1. Обозначения и терминология . .........166
V. 1.2. Вычисляемое отношение............168
V. 2. Правильность программ: определения.........169
V. 2.1. Частичная правильность............170
V. 2.2. Полнота..................172
V. 2.3. Полная правильность . . ...........173
V. 3. Правильность программ: достаточные условия......174
V. 4. Разрешимость...................179
V. 5. Правильность алгоритмов: определения.........181
V. 5.1. Производимость................181
V. 5.2. Сравнение трех алгоритмов...........182
V. 5.3. Завершаемость.................186
V. 5.4. Определения правильности логических алгоритмов . .188
V. 6. Правильность алгоритмов: достаточные условия......189
V. 7. Пример верификации................190
V. 7.1. Выбор критериев...............191
V. 7.2. Выбор спецификации..............192
V. 7.3. Преобразование определяющих..........192
V. 7.4. Выбор процедур...............193
V. 7.5. Доказательство завершаемости..........196
V. 8. Ограничения на верификацию.............197
V. 9. Исторический очерк.................198
VI. Формальный синтез программ............203
VI. 1. Правильность программ.............. 203
VI. 2. Синтез логических программ.............204
VI. 3. Синтез программ при помощи вывода процедур.....205
VI. 4. Пример с использованием резолюции......... . 208
VI. 5. Пример с использованием нерезолютивного вывода . . . .213
VI. 5.1. Исходная программа.............213
VI. 5.2. Изменение представления данных.......214
VI. 5.3. Схема новой программы...........215
VI. 5.4. Спецификация................217
VI. 5.5. Эквивалентная подстановка..........217
VI. 5.6. Вывод новых процедур............219
VI. 5.7. Дальнейшие усовершенствования программы . . . .221
VI. 6. Исторический очерк................223
VII. Реализация.....................226
VII. 1. Представление состояния управления.........227
VII. 1.1. Механизм исполнения............227
VII. 1.2. Фреймы.................230
VII. 1.3. Механизм возврата..... .......233
VII. 1.4. Шаг вызова процедуры...........235
VII. 1.5. Алгоритм управления............237
VII. 2. Представление присваиваний данных.........239
VII. 2.1. Одностековое представление.........239
VII. 2.2. След...................243
VII. 2.3. Представление данных.......... . 245
VII. 2.4. Совместное использование структур......247
VII. 3. Экономия памяти.................252
VII. 3.1. Восстановление пространства после успешного выхода из процедуры............ . 252
VII. 3.2. Двухстековое представление.........254
VII. 3.3. Механизм восстановления при успешном выходе из
процедуры................257
VII. 3.4. Оптимизация последнего вызова........259
VII. 4. Экономия времени обработки данных .........265
VII. 4.1. Системы без совместного использования структур 266
VII. 4.2. Компиляция................269
VII. 4.3. Унификация................270
VII. 5. Исторический очерк....................273
VIII. Вклад логического программирования в теорию
v 077
вычислении.......................
VIII. 1. Теория вычислений................277
VIII. 1.1. Представимость и вычислимость.......278
VIII. 1.2. Семантика...............281
VIII. 1.3. Корректность и полнота стратегии исполнения 286
VIII. 1.4. Отрицание...............288
VIII. 1.5. Рассуждения на метауровне........292
VIII. 2. Вычислительная практика.............298
VIII. 2.1. Методология программирования . ...... 298
VIII. 2.2. Приложения...............304
VIII. 2.3. Обучение................313
VIII. 3. Вычислительная техника............... . 315
VIII. 3.1. Логика как нефоннеймановскнй язык программирования .................316
VIII. 3.2. Проект создания ЭВМ пятого поколения .... 324
Литература........................328
Предметный указатель...................339