Иван Братко - Программирование на языке Пролог для искусственного интеллекта
P :- Q, R; S, T, U.
понимается как:
P :- ( Q, R); (S, T, U).
и имеет тот же смысл, что и два предложения
P :- Q, R.
P :- S, T, U.
Упражнения2.6. Рассмотрим следующую программу:
f( 1, один).
f( s(1), два).
f( s(s(1)), три).
f( s(s(s(X))), N) :-
f(X, N).
Как пролог-система ответит на следующие вопросы? Там, где возможны несколько ответов, приведите по крайней мере два.
(a) ?- f( s( 1), A).
(b) ?- f( s(s(1)), два).
(c) ?- f( s(s(s(s(s(s(1)))))), С).
(d) ?- f( D, три).
2.7. В следующей программе говорится, что два человека являются родственниками, если
(a) один является предком другого, или
(b) у них есть общий предок, или
(c) у них есть общий потомок.
родственники( X, Y) :-
предок( X, Y).
родственники( X, Y) :-
предок( Y, X).
родственники( X, Y) :-
% X и Y имеют общего предка
предок( Z, X),
предок( Z, Y).
родственники( X, Y) :-
% X и Y имеют общего потомка
предок( X, Z),
предок( Y, Z).
Сможете ли вы сократить эту программу, используя запись с точками с запятой?
2.8. Перепишите следующую программу, не пользуясь точками с запятой.
преобразовать( Число, Слово) :-
Число = 1, Слово = один;
Число = 2, Слово = два;
Число = 3, Слово = три.
2.4. Процедурная семантика
Процедурная семантика определяет, как пролог-система отвечает на вопросы. Ответить на вопрос — это значит удовлетворить список целей. Этого можно добиться, приписав встречающимся переменным значения таким образом, чтобы цели логически следовали из программы. Можно сказать, что процедурная семантика Пролога — это процедура вычисления списка целей с учетом заданной программы. "Вычислить цели" это значит попытаться достичь их.
Назовем эту процедуру вычислить. Как показано на рис. 2.9, входом и выходом этой процедуры являются:
входом — программа и список целей,
выходом — признак успех/неуспех и подстановка переменных.
Рис. 2.9. Входы и выходы процедуры вычисления списка целей.
Смысл двух составляющих выхода такой:
(1) Признак успех/неуспех принимает значение "да", если цели достижимы, и "нет" — в противном случае. Будем говорить, что "да" сигнализирует об успешном завершении и "нет" — о неуспехе.
(2) Подстановка переменных порождается только в случае успешного завершения; в случае неуспеха подстановка отсутствует.
ПРОГРАММАбольшой( медведь). % Предложение 1
большой( слон). % Предложение 2
маленький( кот). % Предложение 3
коричневый ( медведь). % Предложение 4
черный ( кот). % Предложение 5
серый( слон). % Предложение 6
темный( Z) :- % Предложение 7:
черный( Z). % любой черный
% объект является темным
темный( Z) :- % Предложение 8:
коричневый( Z). % Любой коричневый
% объект является темным
ВОПРОС?- темный( X), большой( X) % Кто одновременно темный
% и большой?
ШАГИ ВЫЧИСЛЕНИЯ(1) Исходный список целевых утверждений:
темный( X), большой( X).
(2) Просмотр всей программы от начала к концу и поиск предложения, у которого голова сопоставима с первым целевым утверждением
темный( X).
Найдена формула 7:
темный( Z) :- черный( Z).
Замена первого целевого утверждения конкретизированным телом предложения 7 — порождение нового списка целевых утверждений.
черный( X), большой( X)
(3) Просмотр программы для нахождения предложения, сопоставимого с черный( X). Найдено предложение 5: черный ( кот). У этого предложения нет тела, поэтому список целей при соответствующей конкретизации сокращается до
большой( кот)
(4) Просмотр программы в поисках цели большой( кот). Ни одно предложение не найдено. Поэтому происходит возврат к шагу (3) и отмена конкретизации X = кот. Список целей теперь снова
черный( X), большой( X)
Продолжение просмотра программы ниже предложения 5. Ни одно предложение не найдено. Поэтому возврат к шагу (2) и продолжение просмотра ниже предложения 7. Найдено предложение (8):
темный( Z) :- коричневый( Z).
Замена первой цели в списке на коричневый( X), что дает
коричневый( X), большой( X)
(5) Просмотр программы для обнаружения предложения, сопоставимого коричневый( X). Найдено предложение коричневый( медведь). У этого предложения нет тела, поэтому список целей уменьшается до
большой( медведь)
(6) Просмотр программы и обнаружение предложения большой( медведь). У него нет тела, поэтому список целей становится пустым. Это указывает на успешное завершение, а соответствующая конкретизация переменных такова:
Рис. 2.10. Пример, иллюстрирующий процедурную семантику Пролога: шаги вычислений, выполняемых процедурой вычислить.
В главе 1 в разд. "Как пролог-система отвечает на вопросы" мы уже фактически рассмотрели, что делает процедура вычислить. В оставшейся части данного раздела приводится несколько более формальное и систематическое описание этого процесса, которое можно пропустить без серьезного ущерба для понимания остального материала книги.
Конкретные операции, выполняемые в процессе вычисления целевых утверждений, показаны на рис. 2.10. Возможно, следует изучить этот рисунок прежде, чем знакомиться с последующим общим описанием.
Чтобы вычислить список целевых утверждений
G1, G2, …, Gm
процедура вычислить делает следующее:
• Если список целей пуст - завершает работу успешно.
• Если список целей не пуст, продолжает работу, выполняя (описанную далее) операцию 'ПРОСМОТР'.
• ПРОСМОТР: Просматривает предложения программы от начала к концу до обнаружения первого предложения С, такого, что голова С сопоставима с первой целью G1. Если такого предложения обнаружить не удается, то работа заканчивается неуспехом.
Если С найдено и имеет вид
H :- B1, ..., Вn.
то переменные в С переименовываются, чтобы получить такой вариант С' предложения С, в котором нет общих переменных со списком G1, …, Gm. Пусть С' — это
Н' :- B1', ..., Вn'.
Сопоставляется G1 с H'; пусть S — результирующая конкретизация переменных. В списке целей G1, G2, …, Gm, цель G1 заменяется на список В1', …, Вn', что порождает новый список целей:
В1', …, Вn', G2, …, Gm
(Заметим, что, если С — факт, тогда n=0, и в этом случае новый список целей оказывается короче, нежели исходный; такое уменьшение списка целей может в определенных случаях превратить его в пустой, а следовательно, — привести к успешному завершению.)
Переменные в новом списке целей заменяются новыми значениями, как это предписывает конкретизация S, что порождает еще один список целей
В1'', …, Вn", G2', …, Gm'
• Вычисляет (используя рекурсивно ту же самую процедуру) этот новый список целей. Если его вычисление завершается успешно, то и вычисление исходного списка целей тоже завершается успешно. Если же его вычисление порождает неуспех, тогда новый список целей отбрасывается и происходит возврат к просмотру программы. Этот просмотр продолжается, начиная с предложения, непосредственно следующего за предложением С (С — предложение, использовавшееся последним) и делается попытка достичь успешного завершения с помощью другого предложения.
Более компактная запись этой процедуры в обозначениях, близких к Паскалю, приведена на рис. 2.11.
Здесь следует сделать несколько дополнительных замечаний, касающихся процедуры вычислить в том виде, в котором она приводится. Во-первых, в ней явно не указано, как порождается окончательная результирующая конкретизация переменных. Речь идет о конкретизации S, которая приводит к успешному завершению и которая, возможно, уточнялась последующими конкретизациями во время вложенных рекурсивных вызовов вычислить.
procedure вычислить (Прогр, СписокЦелей, Успех)
Входные параметры:
