Язык логического программирования Пролог был разработан А. Коль-мероером и его сотрудниками в начале 70-х годов и долгое время оставался просто одним из многих языков искусственного интеллекта (ИИ), которым интересовались лишь небольшие группы исследователей. В последнее время положение коренным образом изменилось, и Пролог стал популярен практически во всем мире. Произошло это по многим причинам.
Прежде всего, приобрела особую актуальность проблематика искусственного интеллекта и, как следствие, изменилось отношение к инструментальным средствам ИИ, в первую очередь к языкам ИИ. Все шире получают практическое, промышленное распространение всевозможные экспертные системы и системы, с которыми можно общаться на ограниченном естественном языке. Часто эти системы реализуются на одном из языков ИИ, причем, пожалуй, самым распространенным языком ИИ является именно Пролог, составляющий серьезную конкуренцию классическому Лиспу и тем более таким языкам, как Сетл, KRL, FRL, KL-ONE, SMALLTALK.
Пролог, основанный на самой "старой" и известной модели представления знаний — языке формальной логики предикатов, обеспечивает удобные средства для представления знаний в виде фактов и правил вывода, понятен экспертам-непрограммистам и даже с успехом используется для обучения детей программированию. Наконец, весьма существенную роль в распространении Пролога сыграл выбор этого языка в качестве базового в знаменитом японском проекте вычислительных систем пятого поколения.
Пролог является совершенно уникальным языком программирования, хотя отдельные его возможности присущи и другим языкам. Среди них можно, например, упомянуть Плэнер, в котором также реализован встроенный механизм поиска (планирования) с возвратом, иначе называемого поиском "сначала вглубь", и Снобол с его развитыми средствами сопоставления с шаблоном. Аппарат работы со списками Пролог унаследовал от Лиспа, однако по сравнению с Лиспом Пролог обеспечивает некий новый уровень абстракции: если Лисп скрывает от программиста организацию памяти, то Пролог наряду с этим позволяет в принципе не заботиться о потоке управления. Связано это с тем, что для текста Пролога имеется по крайней мере две равноправные интерпретации. Он рассматривается одновременно и как декларативное описание некоторых закономерностей, в совокупности составляющее спецификацию задачи, и как описание процедур, т- е. программы, решающей задачу. Подобным свойством, кроме Пролога, обладает только один известный нам язык — разработанный в нашей стра-не также в начале 70-х годов Ю. А. Бухштабом и С. С. Камыниным язык Вопрос-Ответ.
<
В настоящее время системы программирования на Прологе эксплуатируются на ЭВМ самых разных типов: IBM-370, Apple, CDC Cyber 73, Odra 7 и др. Большое распространение получил Дек-Пролог для машин PDP 10, PDP 11 под управлением операционной системы UNIX. Начата работа с Прологом на отечественных ЭВМ. В институте программных систем АН СССР (г. Переславль-Залесский) осуществлена мобильная реализация системы микро-Пролог в соответствии со спецификациями, приведенными в книге. Реализация проведена на языке программирования Си и сделана для машин типа СМ4, работающих под управлением операционной системы UNIX, и для персональных ЭВМ фирмы Yamaha (Япония).
Появились сообщения о создании в Японии персональных компьютеров с Прологом производительностью примерно 108 логических выводов в секунду (каждый из которых соответствует примерно 100—1000 машинным командам в секунду). Ожидается появление Пролог-машин производительностью в 10 раз большей, что несомненно будет способствовать росту популярности логического программирования и расширению сферы применения Пролога.
Теперь несколько слов о самой книге. Она вышла в известной компьютерной серии издательства Prentice/Hail, некоторые книги из которой уже переводились на русский язык. Серию редактирует один из ведущих зарубежных специалистов по программированию Ч. Хоар, заложивший совместно с Э. Дейкстрой основы структурного программирования. Его редакционное участие обусловливает высокий научный уровень выходящих в рамках серии книг, который удачно сочетается с популярной формой изложения, рассчитанной на массового читателя. Не является исключением и данная книга, написанная известными специалистами и представляющая собой учебник логического программирования с использованием языка микро-Пролог.
Микро-Пролог — это один из языков семейства Пролог. Приставка "мик-ро" означает лишь то, что этот язык реализован на микрокомпьютере, а не то, что он является урезанной версией "большого" исходного языка. Таким образом, данная книга может служить введением в программирование для любой версии языка Пролог. Незначительные отличия имеются только в синтаксисе высказываний и форме запросов микро-Пролога, но это несущественно. Дело в том, что синтаксис Пролога относительно прост и не идет ни в какое сравнение, скажем, с синтаксисом Алгола или ПЛ/1. Зато семантика средств микро-Пролога и концепций логического программирования в целом чрезвычайно богата и многообразна. Связано это в первую очередь с высоким уровнем абстракции основных понятий языка, что, естественно, порождает широкий спектр их интерпретаций и практических приложений. В этом смысле перед авторами стояла очень непростая задача объяснить читателю глубину семантики языка и показать его возможности. Осложнялась эта задача еще и тем, что нетрадиционность Пролога порождает и нетрадиционность программирования на нем, так что даже опытному программисту достаточно сложно переключиться, скажем, с "фортранов-ского" образа мышления на "прологовский".
6
Авторы нашли решение этих проблем, сосредоточив основное внимание не на формальном синтаксисе языка, а на его семантике и практических приемах программирования, и, на наш взгляд, справились с этой задачей отлично. Книга доступна самому широкому кругу читателей, что в значительной степени объясняется большим опытом преподавания Пролога, накопленным авторами. Более легкому пониманию способствует большое число апробированных примеров и упражнений, создающее при чтении иллюзию работы за дисплеем. Удачна и предложенная авторами форма представления SIMPLE, существенно облегчающая понимание Пролог-программ. Хорошо дополняют книгу главы, посвященные некоторым применениям микро-Пролога и вводящие читателя в круг решаемых на этом языке задач. Обращает на себя внимание усовершенствование популярной экспертной системы MYCIN, реализация различных стратегий поиска на основе встроенной в Пролог стратегии "сначала вглубь". Приведенные в книге элегантные решения известных задач не только интересны сами по себе, но и прекрасно иллюстрируют большие возможности языка.
При подготовке русского издания возникли определенные трудности с переводом неустоявшейся терминологии языка. В связи с этим для важнейших понятий наряду с переводом приводится и их оригинальное английское название. Для большей наглядности переведены не только имена отношений и объектов из примеров и упражнений, но и даны русские эквиваленты определенных в SIMPLE команд. Без перевода оставлены только встроенные примитивы микро-Пролога. Обнаруженные опечатки исправлены и особо не оговариваются.
^ В. В. Мартынюк
А. И. Горлин
ОГЛАВЛЕНИЕ
Предисловие к русскому изданию.............................. с
Предисловие............................................ g
Введение.............................................. IQ
В. 1. Зачем нужно программирование на микро-Прологе............ JQ
В.2. Описание глав................................... 13
ЧАСТЬ I. ОСНОВНЫЕ ПОНЯТИЯ................................ 18
К. Л. Кларк, Дж. Р. Энналс, Ф. Г. Маккейб
Глава 1. Факты и запросы................................... 18
1.1. Создание базы данных из фактов........................ 18
1.2. Запросы....................................... 31
1.3. Арифметические отношения........................... 38
1.4. Выполнение запросов............................... 44
1.5. Эффективные запросы.............................. 54
Глава 2. Правила......................................... 54
2.1. Превращение запросов в правила........................ 55
2.2. Как ищутся ответы на запросы, связанные с правилами......... 63
2.3. Рекурсивные описания отношений....................... 68
Глава 3. Списки......................................... 79
3.1. Списки как объекты............................... 79
3.2. Доступ к элементам списка фиксированной длины............ 80
3.3. Доступ к элементам списка неизвестной длины............... 83
3.4. Длина списка.................................... 90
3.5. Наборы ответов как списки........................... 98
ЧАСТЫ1. ЛОГИЧЕСКОЕ ПРОГРАММИРОВАНИЕ НА МИКРО-ПРОЛОГЕ....... 102
К. П. Кларк, Ф. Г. Маккейб
102 Глава 4. Сложные условия в запросах и правилах....................
4.1. Отрицающие условия...............................
1 А8
4.2. Условие список-всех...............................
4.3. Условие для-всех.................................
4.4. Условие или..................................... „
4.5. Условия с выражениями.............................
4.6. Формулирование запросов пользователю с помощью условия со-общено........................................ ~2
4.7. Комментирующие условия...........................
Г л а в а 5. Работа со списками.................................135
5.1. Отношение "соединение".............................135
5.2. Правила, в которых используется отношение "соединение".......139
5.3. Рекурсивное определение отношения сортированности..........143
5.4. Списочные функции................................147
Глава 6. Введение в грамматический анализ........................148
6.1. Грамматический анализ предложений, представленных как списки слов .........................................149
6.2. Другая программа грамматического анализа................153
6.3. Общий подход к использованию разностных пар..............157
Глава 7. Некоторые практические соображения.....................159
7.1. Ограничение условия одним решением....................159
7.2. Управление поиском с возвратом с помощью условия "/"........162
7.3. Стек запроса и экономия памяти.........................165
7.4. Остаточно-рекурсивные определения.....................167
7.5. Использование модулей.............................170
Глава 8. Металогическое программирование.......................174
8.1. Имена отношений и списки аргументов как переменные.........175
8.2. Метапрограммы для проверки условий применения............179
8.3. Программы обработки других программ..................180
8.4. Унарные отношения как команды.......................188
ЧАСТЫН. ШТАТНЫЙ МИКРО-ПРОЛОГ............................198
К. Л. Кларк, Ф. Г. Маккейб
Глава 9. Стандартный синтаксис микро-Пролога...................198
9.1. Атомы и предложения..............................199
9.2. Программирование по правилам стандартного синтаксиса........201
9.3. Преобразование высказываний в предложения................206
9.4. Метапеременные в программах при стандартном синтаксисе.......209
9.5. Примитив CL доступа к предложениям....................216
ЧАСТЬ IV. ПРИЛОЖЕНИЯ МИКРО-ПРОЛОГА........................219
Глава 10. Программа анализа критического пути....................219
Ф. Кривачек
10.1. Постановка задачи................................220
10.2. Определение понятийна микро-Прологе..................222
10.3. Использование лемм..............................228
10.4. Программа анализа критического пути...................231
Глава 11.1. Микро-Пролог в экспертных системах...................233
П. Хаммонд
11.1. Введение......................................233
11.2. Экспертная система MYCIN..........................233
11.3. Представление знаний на микро-Прологе..................235
311
11.4. Простая диалоговая оболочка.........................237
11.5. Более сложная оболочка............................240
11.6. Объяснения "почему"..............................242
11.7. Объяснения "как"................................246
11.8. Объяснения "почему-нет"............................250
Глава 12. Логика игр двух партнеров............................253
М. X. вон Эмден, К. Л. Кларк
12.1. Введение...................................... 253
12.2. Деревья игр, деревья решений и принцип минимакса.......... 256
12.3. Пороги и сокращение Альфа-Бета...................... 263
12.4. Заключительные замечания.......................... 267
Глава 13. Микро-Пролог для решения задач .......................269
Р. А. Ковалъски, М. Дж. Сарджот
13.1. Решение задач с помощью поиска ......................269
13.2. Другое представление для поиска пути...................273
13.3. Другие стратегии поиска............................279
13.4. Включение средств обнаружения циклов..................283
13.5. Простой поиск и экспертиза . . '........................285
Ответы к упражнениям.............^......................• • 288
Цена: 300руб.
