Механизм возврата

Процесс реализации вывода

Пример.

domains

number, product = integer

goal

fact (3, Rez), write ("Факториал 3=", Rez), nl.

clauses

fact (1, 1):-!.

fact (N, R):- Next_N = N - 1,

fact (Next_N, P):- R = N * P.

Таблица 3.1.

Вызов предиката	Подстановки	Вычисления	Хвостовые вычисления	Результат вычислений
fact(3, Rez)	N=3, Rez=R	Next_N=N-1=2	R=N*P	Rez=R=3*2=6
fact(2, P)	N=2, P=R^1	Next_N^1=N^1-1=1	R^1=N^1*P^1	P^*=R^1=2*1=2
fact(1, P^1)	1=1, P=1

Абстрактный интерпретатор Пролог выполняет вычисления, получая вопрос Р и последовательность резольвент Q. Если Р выводится из Q, то результат «yes», если не выводится, то − «no». Возможен также и третий вариант, когда результат непредсказуем.

В процессе реализации логического вывода в Пролог-программе используются следующие механизмы:

· унификации;

· сопоставления (согласования, совпадения);

· прямой трассировки;

· возврата.

Сопоставление – это процесс проверки двух термов на их соответствие друг другу. Термы сопоставимы в двух случаях: если они идентичны, либо, если они становятся идентичными при конкретизации своих переменных.

Если термы тождественны (идентичны), то процесс терпит успех, и неуспех – в противном случае.

При попытке согласования целевого утверждения из БД выбирается единичное утверждение, голова которого сопоставима с целевым утверждением. Если такое утверждение найдено, то из БД выбирается следующее утверждение, которое сопоставляется со следующим целевым утверждением. Если такой процесс терпит успех, то есть все целевые утверждения согласуются путем прямого продвижения по программе, то он называется прямой трассировкой.

Примечание. Даже если все утверждения согласованы в поставленной цели один раз путем прямой трассировки, то можно получить другие доказательства той же цели, используя механизм возврата (управление процессом вывода с помощью предикатов fail, «!» и repeat).

Процесс согласования конъюнкций подцелевых утверждений в теле резольвенты осуществляется слева направо:

(голова) цель: – (тело) подцель_1, подцель_2,..., подцель_N.

Каждая подцель согласуется с фактом, хранящимся в БД, или уже доказанным утверждением. Однако может возникнуть ситуация, когда одна из подцелей не может быть согласована. При этом осуществляется сдвиг влево на одну подцель предшествующую и выполняется её сопоставление с новыми значениями из БД, и так до тех пор, пока не будет найдена сопоставимая подцель. Если она найдена, то процесс продолжается дальше слева направо до тех пор, пока не будет доказано целевое утверждение.

Если подцелей больше нет и факты в БД исчерпаны, то доказательства заканчиваются неудачей. При осуществлении механизма возврата значения всех переменных очищаются.

Дата добавления: 2014-12-29