С.С. Магазов, Д.О. Чугунов
12
Унификация списков.
Списки <b
1
…b
n
> и <с
1
…с
n
> унифициру-
ются, если U(b
i
,с
i
) для всех i
n.
Списки <b
1
…b
n
> и <с
1
…с
k
|$$X >, где k<n, унифицируются, если
U(b
i
,с
i
) для всех i
k. Переменная $$X конкретизируется списком
<b
k+1
…b
n
>.
Унификация оператора поиска и заголовка правила.
Определим
унификацию заголовка оператора поиска ~.
xlоg_tmpl2.variable
2
,…
с
заголовком правила ~(
xlоg_tmpl1,variable
1
,…
). Заголовок правила и
заголовок оператора поиска унифицируются, если унифицируются
xlоg_tmpl1
и
xlоg_tmp12,
т. е.
U(xlоg_tmpl1,xlоg_tmp12).
Переменные, входящие в
xlоg_tmpl1
или
xlоg_tmpl2
,
после уни-
фикации конкретизируются и связываются согласно рассмотренному
выше правилу унификации XLog-документов. Переменные заголовка
правила и заголовка оператора поиска, не входящие
в
xlоg_tmpl1
и
xlоg_tmp12
, остаются неконкретизированными и несвязанными.
Алгоритм исполнения программы.
XLog включает следующие
механизмы исполнения программы:
унификация, рекурсия и возврат
(backtracking)
.
Алгоритм исполнения программы аналогичен реализованному в
языке PROLOG [4] методу логического вывода, основанного на резо-
люциях.
Реализация программы начинается с выполнения первой преди-
катной конструкции из раздела Goal. Семантика всех конструкций
XLog рассмотрена, за исключением оператора поиска. Рассмотрим
алгоритм исполнения оператора поиска правила.
Оператор поиска последовательно сверху вниз просматривает
список правил, пытаясь унифицироваться с их заголовками. Если та-
кое правило найдется, начинается исполнение операторов тела пра-
вила. Так же, как в языке PROLOG,
правило, с которого начинается
просмотр, определяет
механизм возврата,
т. е. в случае, если опера-
тор в теле правила ложен, происходит переунификация заголовка
правила. Если не находится заголовка, с которым возможна унифи-
кация, оператор поиска считается ложным и происходит возврат
(backtracking) к оператору, стоящему перед ним.
Поясним алгоритм работы XLog-программы на примере 6. В этом
примере первым исполняется оператор поиска ~.“
\ my-
site.html”.
В процессе поиска документ mysite.html унифицируется с шабло-
ном первого правила (см. пример 1). В результате унификации пере-
менные шаблона конкретизируются следующими значениями:
$$X1 – пустая строка;
$$X2 = «Петя послушный мальчик. Петя пошел в школу»;
$$X3 – пустая строка.
