68 Введение в логическое программирование- Пер с англ. — М.: Мир, 1988.— 348 с., ил. ISBN 5-03-000490-4
Книга написана английским специалистом по программированию и знакомит читателей с фундаментальными идеями и методологией логического программирования. В ней много внимания уделено вопросам синтеза программ, реализации языков логического программирования и их применения. Материал тщательно отобран, приводится много примеров, облегчающих усвоение материала.
Для математиков-прикладников, специалистов по информатике программистов, аспирантов и студентов. '
Предисловие редактора перевода
Основная трудность программирования задач для ЭВМ связана не столько с различием языков человека и машины, сколько с различием их «мышления». Долгое время считалось, что машина способна правильно воспринимать и исполнять только алгоритмы, т. е. детерминированные формальные исчисления директивного типа. В то же время первоначальная формулировка задачи имеет, как правило, описательный характер. Неформальный этап построения подходящего алгоритма и запись его на определенном формальном языке требует от программиста не только значительных затрат времени, но и достаточно высокой квалификации. Этот и некоторые другие недостатки алгоритмического подхода стимулировали поиск иных возможностей. Осознание того, что вычисление есть частный случай логического вывода, а алгоритм — это аксиоматическое задание функции, привело к идее так называемого логического программирования, первая реализация которой была осуществлена в начале 70-х годов в виде системы Пролог. Суть этой идеи состоит в том, что машине в качестве программы можно предоставить не алгоритм, а формальное описание предметной области и задачи (функции) в виде аксиоматической системы, и тогда построение решения задачи в виде вывода в этой системе можно поручить самой машине. Таким образом, от программиста уже не требуется построения алгоритма, решающего задачу, поскольку нужный алгоритм порождается интерпретатором, строящим вывод по определенной стратегии. Теперь основная задача программиста— удачно аксиоматизировать, т. е. описать в виде системы логических формул предметную область и такое множество отношений на ней, которые с достаточной степенью полноты описывают задачу. Следует сразу отметить, что этот подход был бы нереален, если бы не существовало методов автоматического поиска доказательств.
Практическая эффективность логического программирования зависит не только от удачной аксиоматизации задачи, но в еще большей мере от качества интерпретатора, реализующего поиск доказательства. Поэтому кроме техники программирования очень важно совершенствовать методы автоматического доказа-
Оглавление
Предисловие редактора перевода ................ 5
Предисловие........................ '
Предисловие автора..................... °
Введение ......................... И
I. Представление знаний и рассуждения.......... 16
1.1. Индивидуумы................. . • 16
1.2. Отношения.................... I'
1.3. Предикаты, связки и формулы............ 19
1.4. Переменные .................... 20
1.5. Предложения................... 22
1.6. Примеры представлений............... 23
1.7. Интерпретация предложений............. 26
1.8. Логическое следствие................ 30
1.9. Логический вывод............... . • 32
1.10. Общая резолюция сверху вниз............ 35
1.11. Решение задач................. . 39
1.12. Извлечение ответа................. 42
1.13. Резюме..................... 45
I. 14. Исторический очерк................. 46
II. Логические программы................51
II. 1. Программы, вычисления и исполнение программ.....51
II. 1.1. Утверждения в программах........... 51
II. 1.2. Назначение и структура программ........ 54
II. 1.3. Исполнение программ............. 55
П. 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
П. 2.6. Выбор процедуры . ............. 62
II. 3. Пространство вычислений.............. 63
II. 3.1. Классификация вычислений........... 63
II. 3.2. Полное пространство вычислений........ 64
П. 3.3. Действие правил выбора............ 64
II. 4. Стандартная стратегия управления.......... 68
II. 4.1. Недетерминированность и поиск......... 68
II. 4.2. Правило вычислений.............69
II. 4.3. Правило поиска ...............71
II. 4.4. Стандартная стратегия.............73
II. 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
П. 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. Поиск в списке............... 110
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. Имена для структур данных, представленных в *1Ч
виде фактов................ 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
/\, Формальный синтез программ............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
/II. Реализация.....................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. Вклад логического программирования в теорию вычислений.......................277
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
Цена: 150руб.
