Prolog
Шрифт:
В1', ..., Вn', G2, ..., Gm
(Заметим, что, если С - факт, тогда n=0, и в этом случае новый список целей оказывается короче, нежели исходный; такое уменьшение списка целей может в определенных случаях превратить его в пустой, а следовательно, - привести к успешному завершению.)
В1'', .... Вn", G2', ..., Gm'
Вычисляет (используя рекурсивно ту же самую процедуру) этот новый список целей. Если его вычисление завершается успешно, то и вычисление исходного списка целей тоже завершается успешно. Если же его вычисление порождает неуспех, тогда новый список целей отбрасывается и происходит возврат к просмотру программы. Этот просмотр продолжается, начиная с предложения, непосредственно следующего за предложением С (С - предложение, использовавшееся последним) и делается попытка достичь успешного завершения с помощью другого предложения.
Более компактная запись этой процедуры в обозначениях, близких к Паскалю, приведена на рис. 2.11.
Здесь следует сделать несколько дополнительных замечаний, касающихся процедуры вычислить в том виде, в котором она приводится. Во-первых, в ней явно не указано, как порождается окончательная результирующая конкретизация переменных. Речь идет о конкретизации S, которая приводит к успешному завершению и которая, возможно, уточнялась последующими конкретизациями во время вложенных рекурсивных вызовов вычислить.
procedure вычислить (Прогр, СписокЦелей, Успех)
Входные параметры:
Прогр: список предложений
СписокЦелей: список целей
Выходной параметр:
Успех: истинностное значение; Успех принимает значение
истина, если список целевых утверждений
(их конъюнкция) истиннен с точки зрения Прогр
Локальные переменные:
Цель: цель
ДругиеЦели: список целей
Достигнуты: истинностное значение
Сопоставились: истинностное значение
Конкрет: конкретизация переменных
Н, Н', B1, B1', ..., Вn ,
Вспомогательные функции:
пycтой( L): возвращает истину, если L - пустой список
голoвa( L): возвращает первый элемент списка L
хвост( L): возвращает остальную часть списка L
конкат( L1, L2): создает конкатенацию списков - присоединяет
список L2 к концу списка L1
сопоставление( T1, T2, Сопоставились, Конкрет): пытается
сопоставить термы Т1 и T2; если они сопоставимы, то
Сопоставились– истина, а Конкрет представляет
собой конкретизацию переменных
подставить( Конкрет, Цели): производит подстановку переменных
в Цели согласно Конкрет
begin
if пустой( СписокЦелей) then Успех : = истина
else
begin
Цель : = голова( СписокЦелей);
ДругиеЦели : = хвост( СписокЦелей);
Достигнута : = ложь;
while not Достигнута and
"в программе есть еще предложения" do
begin
Пусть следующее предложение в Прогр есть
Н :- B1, .... Вn.
Создать вариант этого предложения
Н' :- В1', .... Вn'.
сопоставление( Цель, Н',
Сопоставились, Конкрет)
if Сопоставились then