В книге излагаются основы логического программирования. Дается описание языка Пролог. Обсуждаются ввод-вывод, приемы и средства организации интерактивных программ, вопросы недетерминированного программирования, применения структур данных, допускающих накопление данных, техника грамматического разбора, программирование метаинтерпретаторов. Изложение удачно иллюстрируется примерами программ. Рассматриваются некоторые приложения Пролога: программирование игр, создание экспертных систем и компилятора для языка высокого уровня.
Author(s): Стерлинг Л., Шапиро Э.
Publisher: Мир
Year: 1990
Language: Russian
Pages: 337
City: Москва
Предисловие редактора перевода 5
Предисловие 6
Введение 9
Часть I. ЛОГИЧЕСКИЕ ПРОГРАММЫ
Глава 1. Основные конструкции 13
1.1. Факты 13
1.2. Вопросы 14
1.3. Логические переменные, подстановки и примеры 15
1.4. Экзистенциальные вопросы , . . . 16
1.5. Универсальные факты 16
1.6. Конъюнктивные вопросы и общие переменные 17
1.7. Правила 18
1.8. Простой абстрактный интерпретатор 21
1.9. Значение логической программы 23
1.10. Резюме 24
Глава 2. Программирование баз данных 27
2.1. Простые базы данных 27
Упражнения к разд. 2.1 30
2.2. Структурированные и абстрактные данные 30
Упражнения к разд. 2.2 32
2.3. Рекурсивные правила 32
Упражнения к разд. 2.3 34
2.4. Логические программы и модель реляционной>базы данных 34
2.5. Дополнительные сведения 35
Глава 3. Рекурсивное программирование 36
3.1. Арифметика 36
Упражнения к разд. 3.1 43
3.2. Списки 43
Упражнения к разд. 3.2 49
3.3. Построение рекурсивных программ 50
Упражнения к разд. 3.3 54
3.4. Бинарные деревья 54
Упражнения к разд. 3.4 57
3.5. Работа с символьными выражениями 57
Упражнения к разд. 3.5 61
3.6. Дополнительные сведения 62
Глава 4. Вычислительная модель логических программ 62
4.1. Унификация 62
Упражнения к разд. 4.1 65
4.2. Абстрактный интерпретатор логических программ 65
Упражнения к разд. 4.2 70
4.3. Дополнительные сведения 70
Глава 5. Теория логических программ 71
5.1. Семантика 71
5.2. Корректность программы 73
Упражнения к разд. 5.2 74
5.3. Сложность 74
Упражнения к разд. 5.3 75
5.4. Деревья поиска 75
Упражнения к разд. 5.4 77
5.5. Отрицание в логическом программировании 78
5.6. Дополнительные сведения 78
Часть II. ЯЗЫК ПРОЛОГ
Глава 6. Чистый Пролог 80
6.1. Вычислительная модель Пролога 80
Упражнения к разд. 6.1 84
6.2. Сравнение с традиционными языками программирования 84
6.3. Дополнительные сведения 86
Глава 7. Программирование на чистом Прологе 86
7.1. Порядок правил 87
Упражнения к разд. 7.1 88
7.2. Проблема завершения программ 88
Упражнения к разд. 7.2 90
7.3. Порядок целей 90
Упражнения к разд. 7.3 92
7.4. Избыточные решения 92
7.5. Рекурсивное программирование в чистом Прологе 94
Упражнения к разд. 7.5 99
7.6. Дополнительные сведения 100
Глава 8. Арифметика 100
8.1. Системные арифметические предикаты 100
8.2. Повторное рассмотрение арифметических логических программ 102
Упражнения к разд. 8.2 103
8.3. Замена рекурсии итерацией 104
Упражнения к разд. 8.3 109
8.4. Дополнительные сведения 109
Глава 9. Анализ структуры термов 110
9.1. Тйповые предикаты ПО
Упражнения к разд. 9.1 112
9.2. Составные термы 112
Упражнения к разд. 9.2 118
9.3. Дополнительные сведения 118
Глава 10. Металогические предикаты 118
10.1 Тйповые металогические предикаты 119
Упражнения к разд. 10.1 122
10.2. Сравнение неосновных термов 122
10.3. Использование переменных в качестве объектов 124
10.4. Доступность метапеременных 126
10.5. Дополнительные сведения 127
Глава 11. Отсечения и отрицание 127
11.1. Зеленые отсечения: выражение детерминизма 127
Упражнения к разд. 11.1 132
11.2. Оптимизация остатка рекурсии ! 132
11.3. Отрицание 133
Упражнения к разд. 11.3 136
11.4. Красные отсечения: устранение явных условий 136
Упражнения к разд. 11.4 139
11.5. Правила по умолчанию 139
11.6. Дополнительные сведения 140
Глава 12. Внелогические предикаты 141
12.1. Ввод-вывод ' 141
Упражнения к разд. 12.1 144
12.2. Доступ к программам и обработка программ 144
12.3. Запоминающие функции 146
Упражнения к разд. 12.3 147
12.4. Интерактивные программы 147
Упражнения к разд. 12.4 152
12.5. Циклы, управляемые отказом 152
Упражнения к разд. 12.5 153
12.6. Дополнительные сведения 153
Глава 13. Практические рекомендации 154
13.1. Эффективность программ на Прологе 155
13.2. Программистские трюки 156
13.3. Стиль программирования и запись программ 160
13.4. Разработка программ 161
13.5. Дополнительные сведения 163
Часть III. СОВРЕМЕННЫЕ МЕТОДЫ ПРОГРАММИРОВАНИЯ НА ПРОЛОГЕ
Глава 14. Недетерминированное программирование 164
14.1. Метод «образовать и проверить» 165
Упражнения к разд. 14.1 173
14.2. Недетерминизм с произвольным выбором альтернативы и недерминизм с
неизвестным выбором альтернативы 174
14.3. Моделирование недетерминированных вычислений 179
Упражнение к разд. 14.3 182
14.4. Классические интеллектуальные программы: ANALOGY, ELIZA и McSAM 182
Упражнения к разд. 14.4 188
14.5. Дополнительные сведения 188
Глава 15. Неполные структуры данных 190
15.1. Разностные списки 190
Упражнения к разд. 15.1 196
15.2. Разностные структуры 196
Упражнения к разд. 15.2 197
15.3. Справочники 198
15.4. Очереди 200
15.5. Дополнительные сведения 202
Глава 16. Синтаксический анализ для грамматик, задаваемых определительными предложениями 203
Упражнения к гл. 16 210
16.1. Дополнительные сведения 210
Глава 17. Программирование второго порядка 210
17.1. Множественные выражения 211
Упражнения к разд. 17.1 215
17.2. Применения множественных выражений 215
Упражнения к разд. 17.2 221
17.3. Другие предикаты второго порядка 221
17.4. Дополнительные сведения 223
Глава 18. Методы поиска 224
18.1. Поиск на графах пространства состояний 224
Упражнения к разд. 18.1 233
18.2. Игровые деревья поиска 233
18.3. Дополнительные сведения 238
Глава 19. Метаинтерпретаторы 238
19.1. Простые метаинтерпретаторы 239
Упражнения к разд. 19.1 245
19.2. Усовершенствованные метаинтерпретаторы для экспертных систем . . . . 245
Упражнения к разд. 19.2 251
19.3. Усовершенствованные метаинтерпретаторы для отладки программ . . . . 252
19.4. Дополнительные сведения 259
Часть IV. ПРИЛОЖЕНИЯ 261
Глава 20. Игровые программы
20.1. «Выдающийся ум» 261
20.2. Игра Ним 264
20.3. Игра в калах 268
20.4. Дополнительные сведения 274
Глава 21. Экспертная система для кредитных операций 274
21.1. Дополнительные сведения 279
Глава 22. Решатель уравнений 281
22.1. Обзор методов решения уравнений 282
22.2. Факторизация 284
22.3. Метод изоляции 284
22.4. Полиномиальные уравнения 292
22.5. Гомогенизация 294
Упражнения к гл. 22 295
22.6. Дополнительные сведения 295
Глава 23. Компилятор 296
23.1. Обзор компилятора 296
23.2. Синтаксический анализатор 301
23.3. Генератор кода 305
23.4. Ассемблер 309
Упражнения к гл. 23 310
23.5. Дополнительные сведения 311
Приложение
A. Использование Пролог-системы 312
B. Системные предикаты 312
C. Предварительно определяемые операторы 316
Литература 318
Предметный указатель 324
