Программирование на языке Пролог - Клоксин У., Меллиш К

У.Клоксин, К.Меллиш

ПРОГРАММИРОВАНИЕ НА ЯЗЫКЕ ПРОЛОГ

Книга английских специалистов, содержащая описание основ логического программирования и особенностей языка Пролог — базового языка ЭВМ пятого поколения. Области применения этого языка связаны с разработкой экспертных систем, интеллектуальных баз данных, обработкой естественного языка, разработкой компиляторов ЭВМ. Книга полезна для первого ознакомления с

языком Пролог.
Для программистов и пользователей ЭВМ.
ОГЛАВЛЕНИЕ
Предисловие редакторов перевода	9
Предисловие ко второму изданию	10
Предисловие к первому изданию	11
Глава 1. Введение	16
1.1. Факты	18
1.2. Вопросы	20
1.3. Переменные	22
1.4. Конъюнкции	25
1.5. Правила	31
1.6. Заключение и упражнения	38
Глава 2. Более детальное описание	39
2.1. Синтаксические правила	39
2.2. Литеры	46
2.3. Операторы	47
2.4. Равенство и установление соответствия	49
2.5. Арифметика	51
2.6. Общая схема согласования целевых утверждений	56
Глава 3. Использование структур данных	63
3.1. Структуры и деревья	63
3.2. Списки	65
3.3. Принадлежность элементов списку	69
3.4. Пример: преобразование предложений	74
3.5. Пример: упорядочение по алфавиту	78
3.6. Использование предиката «присоединить» и спецификация деталей	80
Глава 4. Возврат и отсечение	84
4.1. Порождение множественных решений	85
4.2. Отсечение	91
4.3. Общие случаи использования отсечения	96
4.4. Проблемы, связанные с использованием отсечения	109
Глава 5. Ввод и вывод	112
5.1. Ввод и вывод термов	114
5.2. Ввод и вывод литер	119
5.3. Ввод предложений	121
5.4. Чтение файлов и запись в файлы	123

5.5. Объявление операторов	127
Глава 6. Встроенные предикаты	130
6.1. Ввод новых утверждений	131
6.2. Выполнение и невыполнение целевого утверждения	133
-6.3. Классификация термов	134
6.4. Работа с утверждениями как с термами	136
6.5. Создание структур и работа с компонентами структур	140
6.6. Воздействие на процесс возврата	145
6.7. Формирование составных целевых утверждений	147
6.8. Равенство	151
6.9. Ввод и вывод данных	152
6.10. Обработка файлов	154
6.11. Вычисление арифметических выражений	155
6.12. Сравнение чисел	157
6.13. Наблюдение за выполнением программы на Прологе	158
Глава 7. Еще несколько примеров программ	160
7.1. Словарь в виде упорядоченного дерева	161
7.2. Поиск в лабиринте	164
7.3. Ханойские башни ~	168
7.4. Справочник комплектующих деталей	169
7.5. Обработка списков	171
7.6. Представление и обработка множеств	174
7.7. Сортировка	177
7.8. Использование базы данных: random, генатом, найтивсе	181
7.9. Поиск по графу	187
7.10. Просеивай Двойки. Просеивай Тройки	193
7.11. Символьное дифференцирование	194
7.12. Отображение структур и преобразование деревьев	196
7.13. Применение предикатов clause и retract	200
Глава 8. Отладка пролог-программ	205
8.1. Расположение текстов программ	206
8.2. Типичные ошибки	209
8.3. Модель трассировки	212
8.4. Трассировка и контрольные точки	219
8.5. Фиксация ошибок	230
Глава 9. Использование грамматических правил в Прологе	234
9.1. Проблема синтаксического анализа	234
9.2. Описание синтаксического анализа на языке Пролог	238
9.3. Запись грамматических правил в Прологе	244
9.4. Присоединение дополнительных аргументов	247
9.5. Введение дополнительных условий	252
9.6. Заключение	255
Глава 10. Пролог и математическая логика	260
10.1. Краткое введение в исчисление предикатов	260

10.2. Приведение формул к стандартной форме		264
10.3. Форма записи дизъюнктов		271
10.4. Принцип резолюций и доказательство теорем		273
10.5. Хорновские дизъюнкты		277
10.6. Пролог		279
10.7. Пролог и логическое программирование		282
Глава 11. Программные проекты на Прологе		286
11.1. Простые проекты		286
11.2. Более сложные проекты		289
Приложение А. Ответы к некоторым упражнениям		294
Приложение В. Программа приведения формул исчисления предикатов к		299
стандартной форме
Приложение С. Различные версии языка Пролог		305
Приложение D. Пролог для ЭВМ DEC system10		309
Приложение Е. Микро-Пролог		319
Приложение F. Система МПролога		"324
Предметный указатель		335
Предметный указатель
Аксиомы 273	rules) 234, 244
Алгоритм Евклида (Euclid's	Граничные условия (boundary
algorithm) 194	conditions) 71
Альфа-бета алгоритм (alpha-beta	Дерево (tree) 63
algorithm) 288	— разбора (parse tree) 237
Анонимная переменная (anonimous	—- синтаксическое (syntax tree) 290
variable) 44	— упорядоченное (sorted tree) 162
Аргумент (argument) 19, 261	Деревьев преобразование
Атом (atom) 42	(transforming) 196
Атомарное высказывание (формула)	Дизъюнкт (clause) 269
(atomic proposition) 262	Дизъюнкция (целевых утверждений)
База данных (data base) 20	(disjunction) 148, 202
Ввод/вывод (input/output) 112 Ввод	Дисплей (display) 17
программ (consulting) 126, 131	Доказательство теорем (proving
Возврат (backtracking) 27, 56	theorems) 273
Возврата механизм (процесс)	Доказать целевое утверждение (prove
(backtracking) 56, 59	goal) 22, 56
Возвратный ход (backtracking) 176	Импликация (implication) 262
Вопрос (question) 17, 20, 279	Интерпретатор (interpretator) 201, 307
Высказывание (proposition) 260	Интерпретация (имен, предикатов,
Гипотезы (hypothese) 273	программ) interpretation 19, 32,
Глагол (verb) 235	201, 275, 307
Глагола группа (verb group) 234	Квантор общности (universal
Грамматика контекстно-свободная	quantifier) 263
(context free grammar) 234, 249	существования (existential quantifier)
Грамматические правила (grammar	263

Клавиатура (keyboard) 17 Ковальский (Kovalsky R.) 282 Колмерауэр A. (Kolmerauer A.) 261

Комментарий (comment) 36

Компилятор (compiler) 307, 314

Конкретизировать переменную

(instantiate) 23 Константа (constant) 41

Контрольные точки (spy points) 158, 219

Конъюнктивная нормальная форма

(conjunctive normal form) 267 Конъюнкция (conjunction) 25, 262

Линеаризация списка (flattening a list) 286

Литерал (literal) 265 Литеры (characters) 41, 46

—непечатаемые (non-printing) 46

—печатаемые (printing) 46

Логика более высокого порядка

(higher order logic) 284

Логика математическая (logic) 260 Логические связки (logical

connectives) 262

Логическое программирование logic programming 12, 260, 282

Маркер (place marker) 24

Множество (set) 174 МПролог 324 Микро-Пролог

319

Несовместность (множества дизъюнктов) (irconsistence) 275

Нетерминальный символ (nonterminal symbol) 255

Объект (object) 16 Оператор (operator) 47

—инфиксный (infix) 48

—постфиксный (postfix) 48

—префиксный (prefix) 48

—левоассоциативный (left associative) 49

—правоассоциативный

(rightassociative) 49

Оператора позиция (position) 48, 127

—приоритет (precedence class) 48, 127

—ассоциативность (associability) 48, 127

Операторов объявление (declaring operators) 127

Определитель (determiner) 234

Отладка программ (program debugging) 158, 205 Отношение (relationship) 16

Отображение структур (mapping structures) 196

Отрицание (negation) 262

Отсечение (cut) 91 Передоказать (вновь согласовать

целевое

утверждение) (re-satisfy goal) 59 Переменная (variable) 22, 43

Переменной область действия (scope variable) 33

Побочные эффекты (side effects) 119, 130

Поиск вглубь (depth first search) 188, 190

Поиск вширь (breadth first search) 190

—по графу (searching graphs) 187

—по критерию первый — лучший

(best—first search) 191

Правила вывода (inference rules) 260, 273

продукций (production rules) 291 Правило (rule) 17, 31

— ловушка (catch-hall rule) 76 Предикат (predicate) 20, 262

Предикатов исчисление (predicat calculus) 260

Предикаты встроенные (built-in predicat) 51, 130

Предложение (sentence) 234, 238

Программирование

недетерминированное

(relational programming) 172, 179

Программирование логическое (logic

programming) 12, 260, 282,	Структур отображение (mapping
Процедура (procedure) 76, 206	structures) 196
Равенство (equality) 49 Резолюций	Структура (structure) 41, 44
принцип (resolution princple)	Структуры функтор (functor of
273	structure) 45
Резолюция входная линейная (linear	— компоненты (componentsof
input resolution) 279	structure) 45
Рекурсия (recursion) 63	Существительное (noun) 235
— левосторонняя (left recursion) 72	Сцепленные переменные (shared
Решето Эратосфена (sieve of	variables) 35, 51
Eratosphenes) 193	Текущий входной/выходной поток
Робинсон Дж. A. (Robinson J. A.) 273	(current input/output stream) 124
Семантика декларативная (declarative	Терм (term) 12, 41, 261
semantic) 282	— составной (compound term) 261
— процедурная (procedural semantic)	Терминальный символ (terminal
22	symbol)
Семантические характеристики	255 Трассировка программ (program
(semantic) 249	tracing)
Символьное дифференцирование	158
(symbolic	— управляемая (leashed tracing) 220
differentiation) 194	Трассировки модель (tracing model)
Синтаксис (syntax) 306	212
Синтаксический анализатор (parser)	Унификация (unification) 275
237	Управляемое событие (leashed event)
Синтаксического разбора задача	223
(parsing problem) 237	Утверждение (clause) 36, 279
Сколемизация (skolemising) 265	Файл (file) 124
Сколемовские константы (skolem	Факт (fact) 17, 18
constants) 265	— ловушка (catch hall fact) 76
Следствие (consequence) 273	Формула (formulae proposition) 262
Совокупность (collection) 269	Функтор (functor) 45
Согласовать вновь (re-satisfy goal) 59	Функциональный символ (function
— (с базой данных) целевое	symbol) 261
утверждение (satisfy goal) 24,	Хорнопский дизъюнкт (Horn clause)
25, 56	277
Соответствия установление	Цель (goal) 25, 279
(matching) 21, 49	Целевое утверждение (goal) 25, 279
Сопоставление (цели с	— — выполняется (goal sucseeds) 29,
утверждением) (matching) 21, 49	30
Список (list) 65	— — не выполняется (goal fails) 29,
Списка голова (head of list) 67	30
— хвост (tail of list) 67	— — не согласуется (с базой данных)
Стандартная форма (clausal form)	(goal fails) 26
264, 269	— — согласуется с базой данных

(goal	nonvar 135 nospy 159
is satisfied) 26	not 150
Целевой дизъюнкт (goal statement)	notrace 158
276	op 154
Цели предшественники (ansestors)	or 228
224	phrase 246
Цепочка доказательств (flow of	put 119, 153
satisfaction) 57, 59	read 118, 153
Частотный словарь (concordance)	reconsult 132
287	repeat 145
Эквивалентность (equivalence) 262	retract 139
abort 229	retry 227
arg 142	see 126, 154
ASCII 47	seeing 126, 155
asserta, assertz 139	seen 126, 155
atom 135	skip 153, 226
atomic 136	spy 158
break 229	tab 114, 154
call 149	tell 125, 155
clause A 138	telling 125, 155
consult 126, 131	told 125, 155
creep 226	trace 158
debugging 159	true 133
display 117, 154	var 134
fail 133, 228	write 114, 154
functor 141	= ..143
get 120, 153	! 92
get 20, 153	; 148
halt 229	, 148
integer 136	= 49, 52, 151, 157
is 55, 156	\ = 52, 151, 157
leap 226	= = 152
listing 137	\== 152
mod 48, 55, 156	+ — * 48, 55, 156
name 144 nl 114, 153	< > > = =< 52, 157
nodebug 152, 159