Конкретизация переменных

Рис. 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, что приводит к получению еще одного списка целей: В1¹ \ . . ., 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 осуществляется сканирование не всех предложений программы; рассматриваются только предложения, касающиеся данно­го отношения в текущей цели.