НАЗАД
Вспомогательные функции:
пуcтой(L): возвращает истину, если L - пустой список
голова(L): возвращает первый элемент списка L
хвост(L): возвращает остальную часть списка L
конкат(L1,L2): создает конкатенацию списков - присоединяет список L2 к концу списка L1
сопоставление( T1, Т2, Сопоставились, Конкрет): пытается сопоставить термы Т1 и Т2; если они сопоставимы, то Сопоставились - истина, а Конкрет представляет собой конкретизацию переменных
подставитъ(Конкрет,Цели): производит подстановку переменных в Цели согласно Конкрет}
begin
if пустой( СписокЦелей) then Успех := истина
else
begin
Цель :- голова(СписокЦелей);
ДругиеЦели := хвост(СписокЦелей);
Достигнута := ложь;
while not Достигнута and
«в программе есть еще предложения» do
begin
Пусть следующее предложение в Прогр есть
Н :- В1, ..., Вп.
Создать вариант этого предложения
Н' :- B1', ..., Вn'.
сопоставление(Цель, Н', Сопоставились, Конкрет)
if Сопоставились then
begin
НовыеЦели:=конкат([В1',..., Вn' ], ДругиеЦели);
НовыеЦели :=подставить(Конкрет, НовыеЦели);
вычислить( Прогр, НовыеЦели, Достигнуты)
end
end;
Успех := Достигнуты
end;
end.
Всякий раз, как рекурсивный вызов процедуры вычислить приводит к неуспеху, процесс вычислений возвращается к ПРОСМОТРУ и продолжается с того предложения C, которое использовалось последним. Поскольку применение предложения C не привело к успешному завершению, пролог-система должна для продолжения вычислений попробовать альтернативное предложение. В действительности система аннулирует результаты части вычислений, приведших к неуспеху, и осуществляет возврат в ту точку (предложение С), в которой эта неуспешная ветвь начиналась. Когда процедура осуществляет возврат в некоторую точку, все конкретизации переменных, сделанные после этой точки, аннулируются. Такой порядок обеспечивает систематическую проверку пролог - системой всех возможных альтернативных путей вычисления до тех пор, пока не будет найден путь, ведущий к успеху, или же до тех пор, пока не окажется, что все пути приводят к неуспеху.
Мы уже знаем, что даже после успешного завершения пользователь может заставить систему совершить возврат для поиска новых решений. В нашем описании процедуры вычислить эта деталь была опущена.
Конечно, в настоящих реализациях Пролога в процедуру вычислить добавлены и еще некоторые усовершенствования. Одно из них - сокращение работы по просмотрам программы с целью повышения эффективности. Поэтому на практике пролог-система не просматривает все предложения программы, а вместо этого рассматривает только те из них, которые касаются текущего целевого утверждения.
В вычислительной модели языка Пролог приняты правила просмотра целей в запросе слева направо и поиска сопоставимых правил и фактов в программе сверху вниз. Такой принцип поиска называется поиском в глубину. Рассмотрим теперь механизм поиска с возвратом.
НАЗАД
