Конкретизация переменных
Рис. 2.9. Описание входов и выходов процедуры., которая выполняет
список целей
Значение двух выходных результатов описано ниже.
1. Индикатор успех а/неудачи принимает значение "yes", если цели являются достижимыми, и "по" в противном случае. Принято говорить, что "yes" указывает на успешное завершение, а "по" — на неудачное.
2. Конкретизация переменных вырабатывается только в случае успешного завершения; в случае неудачи конкретизация отсутствует.
В главе 1, в разделе 1.4, "Общие принципы поиска ответов на вопросы системой Prolog", по сути было приведено неформальное описание того, что выполняет процедура execute. Б остальной части этого раздела приведено более формальное и систематическое описание данного процесса, и его можно пропустить без серьезных опасений, что из-за этого будет затруднено понимание остального материала книги.
Конкретные операции процесса выполнения цели иллюстрируются на примере, приведенном в листинге 2.1. Прежде чем переходить к чтению следующего общего описания, следует ознакомиться с данным листингом.
Для выполнения следующего списка целей:
•31, G2, ..., Gm
процедура execute осуществляет описанные ниже действия.
 |  | ||
| (следующей) операции, |
Если список целей пуст, то завершается успешно. Если список целей не пуст, то продолжает работу зываемой "SCANNING".
SCANNING. Сканировать предложения в программе от начала до конца до тех пор, пока не будет обнаружено первое предложение С, такое, что голова С согласуется с первой целью G1. Если такое предложение отсутствует, процедура оканчивается неудачей.
Если есть такое предложение С в форме
Н :- В1, . . . , Б.ч.
| для получения варианта С Gm не имеют общих пере- |
то процедура переименовывает переменные в С предложения С, такого, что С и список G1, менных. Допустим, что С имеет вид
:- В1 '................
| допустим, что ре- |
Процедура согласовывает цель G1 и голову предложения зультирующей конкретизацией переменных является S.
В списке целей Gl, G2, ..., Gm процедура заменяет цель G1 списком В1', что приводит к получению нового списка целей:
В1\ ___ Вп», G2, ..., Gm
Глава 2. Синтаксис и значение программ Prolog
(Следует отметить, что если предложение С представляет собой факт, то п = 0 и новый список целей становится короче, чем первоначальный; такое сокращение списка целей может в конечном итоге привести к получению пустого списка и, тем самым, к успешному завершению.)
Затем процедура подставляет вместо переменных в новом списке целей новые значения, которые заданы в конкретизации S, что приводит к получению еще одного списка целей: В11 \ . . ., Bn'' , G2' . . . Gm'
После этого происходит переход к выполнению (рекурсивно, с помощью той же процедуры) этого нового списка целей. Если выполнение этого нового списка целей завершается успешно, то выполнение первоначального списка целей также завершается успешно. Если же выполнение нового списка целей оканчивается неудачей, то происходит отказ от этого нового списка целей и возврат через всю программу к операции SCANNING. Сканирование продолжается с предложения, которое непосредственно следует за предложением С (С — это предложение, которое использовалась перед этим), и осуществляется попытка достичь успешного завершения с помощью некоторого другого предложения.
Листинг 2.1. Пример, иллюстрирующий процедурное значение Prolog: трассировка выполнения П р оцедур Ы execute
"> Программа big{ bear). big( elephant). small[ cat) .
brown( bear).
black[ cat). gray< elephant).
dark( Z> :-black( Z) .
% Предложение 1 * Предложение 2 % Предложение 3
% Предложение 4 % Предложение S
% Предложение 6
Предложение 1 - все звери имеют темную окраску
с черной шерстью
| I Предложение S - все звери с коричневой шерсть» % имеют темную окраску |
dark( Z) :-brown(Z). » Вопрос
| Какой из зверей большой и имеет темную окраску? |
? - dark (X) , big (X) . 4 Трассировка выполнения
1) Начал ьнкй список целей: dark (X) , big<X) .
2) Сканировать программу сверху вниз, отыскивая предложение, голова которого согласуется с первой целью, dark(X). Обнаружено предложение 7:
dark(Z) ;- black [ Z) .
Подставить вместо первой цели конкретизированное тело предложения 7, что
приводит к получению нового списка целей;.
black ( X) , big{ X)
3) Сканировать программу, чтобы найти согласование с целью black( X). Найдено
предложение 5: black(cat). Это предложение не имеет тела, поэтому список
целей после соответствующей конкретизации сокращается до
big( cat)
4] Сканировать программу, чтобы найти цель big( cat), не обнаружено ни одного
предложения. Поэтому возвратиться к шагу (3) и отменить конкретизацию
х = cat. Теперь список целей снова принимает вид black ( X) , big( X)
Продолжить сканирование программы ниже предложения 5. Не обнаружено ни одного предложения. Поэтому вернуться к шагу (2) и продолжить сканирование ниже предложения 7. Обнаружено предложение S: dark( Z> :- brown ( Z>.
Подставить brown( X) вместо первой цели в списке целей, что приводит к получению списка
Часть I. Язык Prolog
brown( X) , biglX) .
5) Сканировать программ;- чтобы согласовать цель Ьгонп(X}, что приводит
к обнаружению цели brown( bear).Это предложение не имеет тела, поэтому список целей сокращается до big( bear)
6) Сканировать программу, что приводит к обнаружению предложения big(bear).
Оно не имеет тела, поэтому список целей сокращается до пустого. Это
указывает на успешное завершение, и соответствующая конкретизация переменной
ике етвид
X= bear
Эта процедура записана более компактно в листинге 2.2 с использованием системы обозначений, аналогичной языку Pascal.
Здесь уместно привести несколько дополнительных замечаний, касающихся используемой формы представления процедуры execute. Прежде всего, в ней не было явно описано, как вырабатывается конечная результирующая конкретизация переменных. К успешному завершению привела именно конкретизация 5, которая, возможно, могла быть в дальнейшем уточнена с помощью дополнительных конкретизации, выполненных во вложенных рекурсивных вызовах процедуры execute.
При каждом неудачном завершении рекурсивного вызова execute выполнение возвращается к операции SCANNING и работа продолжается с того предложения С программы, которое использовалось перед этим в последнюю очередь. А поскольку использование предложения С не привело к успешному завершению, система Prolog вынуждена предпринять попытку перейти к обработке альтернативного предложения. При этом фактически происходит следующее: система Prolog отказывается от всей этой части неудачного выполнения и возвращается к той точке (к предложению С), с которой началась данная неудачная ветвь выполнения. После того как процедура возвращается к определенной точке, отменяются все конкретизации переменных, которые были выполнены после этой точки. Такая организация работы гарантирует, что Prolog систематически исследует все возможные альтернативные пути выполнения до тех пор, пока не будет найден тот из них, который в конечном итоге приведет к успеху, или пока не будет продемонстрировано, что все эти путл завершаются неудачей.
Как уже было сказано, даже после некоторого успешного завершения пользователь может вынудить систему вернуться к поиску дополнительных решений. В приведенном выше описании процедуры execute эта деталь была опущена.
Безусловно, в фактических реализациях Prolog необходимо добавить к процедуре execute несколько других усовершенствований. Одно из них состоит в сокращении объема сканирования предложений программы для повышения эффективности. Поэтому в практических реализациях Prolog осуществляется сканирование не всех предложений программы; рассматриваются только предложения, касающиеся данного отношения в текущей цели.