Искусство программирования на языке Пролог: Пер. с англ. -М.: Мир, 1990.-235 с., ил.
ISBN 5-03-000406-8
В книге излагаются основы логического программирования. Дается описание языка Пролог. Обсуждаются ввод-вывод, приемы и средства организации интерактивных программ, вопросы недетерминированного программирования, применения структур данных, допускающих накопление данных, техника грамматического разбора, программирование метаинтерпретаторов. Изложение удачно иллюстрируется примерами программ. Рассматриваются некоторые приложения Пролога: программирование игр, создание экспертных систем и компилятора для языка высокого уровня.
Для системных программистов и инженеров-математиков, разрабатывающих информационно-программное обеспечение ЭВМ.
Предисловие редактора перевода
Программированию на языке Пролог, различным вариантам расширения Пролога и методам его реализации посвящено множество статей, докладов и отчетов. Издано несколько книг по этому широко известному языку, в том числе переводы на русский язык: У. Клоксин, К. Меллиш. Программирование на языке Пролог.-М.: Мир, 1987 и К. Кларк, Ф. Маккейб. Введение в логическое программирование на микро-Прологе.-М.: Радио и связь, 1987. Однако следует подчеркнуть, что предлагаемая вниманию читателей книга сильно отличается от указанных выше не только по содержанию, но и по методу описания языка Пролог.
Авторы книги - известные специалисты, много сделавшие для развития и популяризации логического программирования. В частности, с именем Е. Шапиро связано создание языка Concurrent Prolog. Он является редактором серии по логическому программированию, которую открывает данная книга. Две новые книги этой серии (сборники статей по Concurrent Prolog под ред. Е. Шапиро) изданы MIT Press в 1988 г.
Язык Пролог прошел длинный путь развития (почти 20 лет). Он продолжает весьма быстро распространяться. Появилось значительное число его реализаций, причем наиболее популярный вариант Turbo-Prolog доступен пользователям персональных компьютеров. Существует мнение, что Пролог пропагандируется и используется преимущественно специалистами, решающими задачи из области искусственного интеллекта. Однако, как показывает опыт использования различных Пролог-систем, язык Пролог может успешно применяться для разработки сложных программных систем традиционного назначения. Он нашел применение в системах автоматизированного проектирования, системах символьных вычислений и т. д. Говоря о генезисе Пролога, нельзя не отметить его тесную связь с задачей определения грамматик формальных языков и задачей синтаксического анализа текстов, написанных на этих языках. Обработка текста на естественном языке также является интересным и перспективным применением Пролога.
В данной книге излагаются основы логического программирования, описываются «чистый» и «нечистый» Пролог, разнообразные, порой изящные и «фантастичные» методы и приемы составления логических программ. Большой интерес предстваляют третья и четвертая части книги, где рассматриваются более сложные средства и приемы программирования и приводятся развернутые примеры применения языка для решения практических задач (решатель нелинейных уравнений, экспертная система, компилятор и др.).
Книга, несомненно, окажется полезной для программистов и специалистов по разработке Пролог-систем. Для многих из них особый интерес представляют главы о недетерминированном программировании, метапрограммировании, программировании второго порядка и глава о неполных структурах данных, в которой подробно описана техника использования разностных списков и даны убедительные обоснования эффективности их применения.
Следует отметить, что в области логического программирования у нас терминология не установилась. В настоящее время в отечественной литературе перевод некоторых терминов (например, cut, negation as failure и др.) неоднозначен. Данная книга не является исключением, и внимательный читатель заметит, что коллектив переводчиков предлагает свой вариант перевода некоторых терминов. Что касается перевода имен предикатов переменных и других термов Пролога в Пролог-программах, то было принято компромиссное решение. Везде, где на наш взгляд требовалось облегчить понимание программы, термы давались в переводе на русский язык, в противном случае переводились только комментарии. Имена стандартных предикатов Пролога оставлены без перевода.
Перевод книги выполнили С.Ф. Сопрунов (гл. 1-13), Л.В.Шабанов (гл. 14-23, приложения).
Ю. Г. Дадаев
Оглавление
Предисловие редактора перевода.................... 5
Предисловие .........'.................. 6
Введение ............................. 9
Часть I. ЛОГИЧЕСКИЕ ПРОГРАММЫ
Глава 1. Основные конструкции..................... 13
.1. Факты.......................... 13
.2. Вопросы......................... 14
.3. Логические переменные, подстановки и примеры........... 15
.4. Экзистенциальные вопросы.................. 16
.5. Универсальные факты.................... 16
.6. Конъюнктивные вопросы и общие переменные........... 17
.7. Правила......................... 18
.8. Простой абстрактный интерпретатор............... 21
.9. Значение логической программы................ 23
.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
330 Оглавление
Глава 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. Анализ структуры термов................... НО
9.1. Типовые предикаты..................... 110
Упражнения к разд. 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
1 1 .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. Неполные структуры данных .................. 1°«
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. ПРИЛОЖЕНИЯ Глава 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
Цена: 150руб.
