Унификация

Этот параграф был исправлен в связи с тем, что версия SWI-Prolog (Multi-threaded, 32 bits, Version 6.0.2) изменила формат ответа на запрос, хотя, по сути, он остался прежним.

Одна из самых мощных особенностей Пролога - его встроенный алгоритм сопоставления с образцом, унификация. Реализация механизма поиска решений – это и есть реализация алгоритма унификации.

Важность унификации состоит в том, что посредством её происходит передача аргументов и возврат значений из процедур.

Чтобы разобраться с унификацией, мы обсудим встроенный предикат равенства =/2, который успешен, если оба его параметра унифицируются и не успешен, в противном случае. Как оператор он записывается следующим образом.

arg1 = arg2

Надо заметить, что знак "=" не является присваиванием, как в большинстве языков программирования, и не вызывает арифметических действий. Он вызывает действие унификации.

Унификация между двумя сторонами знака "=" точно такая же, как унификация, которая происходит, когда Пролог пробует согласовывать цель с головой предложения.

При отслеживании в обратном порядке, связывания переменных с их значениями, уничтожаются, также, как это происходит, когда Пролог делает отслеживание в обратном порядке при работе с предложениями.

6.1 Самая простая форма унификации встречается между двумя константами.

Если они идентичны, то унификация успешна. Если это не так, тогда неуспешна и унификация.

?- 1 = 1. true.?- a = a. true.?- a = b.false.?- фрукты(яблоки, груши) = фрукты(яблоки, груши). true.?- фрукты(яблоки, груши) = фрукты(сливы, груши). false.

?- a(b,c(d,e(f,g))) = a(b,c(d,e(f,g))).

True.

?- a(b,c(d,e(f,g))) = a(b,c(d,e(g,f))).

false.

6.2 Другая форма унификации - между переменной и константой.

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

В этом случае переменная просто «забирает» свое значение, что делает унификацию успешной.

?- Z = 1. Z = 1.?- X = a. X = a.?- 4 = Y. Y = 4.?- 2+3 = X. X = 2+3.

Интересно, что переменные могут находиться как слева, так и справа от знака '='.

?- X+2 = Y+3. false.?- X+2 = 3+Y. X = 3,Y = 2.

?- фрукты(яблоки, груши) = фрукты(X, груши).

X = яблоки.

Вот примеры, когда несколько переменных одновременно связываются со своими значениями.

?- фрукты(X,Y) = фрукты(яблоки, груши).

X = яблоки,

Y = груши.

?- фрукты(яблоки, X) = фрукты(Y, груши).

X = груши,

Y = яблоки.

6.3 Переменные могут также унифицироваться друг с другом.

Каждая переменная имеет уникальное внутреннее представление Пролога. А когда две переменные унифицируются друг с другом, Пролог должны связать их с одним и тем же значением, что достигается, если расположить переменные в одном и том же месте памяти, т.е. присвоить им одинаковый адрес (или имя).

?- X = X.
true. ?- X = Y. X = Y.

Никаких значений переменные при этом не получают, но между ними устанавливается связь, таким образом, что в дальнейшем они будут выступать в качестве синонимов.

Обратите внимание, что значение для X и Y в конце концов будет одно и то же.

Такие переменные называют сцепленными переменными т.е. расположенными в одном и том же месте памяти.

(Их нельзя путать со связанными, потому что связанная переменная означает то же, что "конкретизированная" или "означенная" переменная, то есть "переменная, получившая значение"),

?- фрукты(X, груши) = фрукты(Y, груши). X = Y.

Пролог запоминает факт, что переменная связана, и, если необходимо, вспоминает это позже, в процессе унификации.

?- X = Y, Y = hello. X = Y, Y = hello.?- X = Y, a(Z) = a(Y), X = hello.

X = Y, a(Z) = a(Y), X = hello.

То, что мы видим, воспринимается Прологом как «запрос на утверждение»: а правда ли, что …? Пролог просто повторяет ввод, сообщая, что, мол, как написано, так и есть, поскольку из имеющихся у него знаний по данному запросу никаких противоречий он не обнаружил.

Вот ещё два примера.

?- a(Z) = a(Y), X = hello. Z = Y,X = hello. ?- X = Y, Y = 3, write(X). 3X = Y, Y = 3.

Последний пример очень важен для понимания процесса унификации.

Он иллюстрируетглавное различие между унификациями переменных в Прологе
и присваиванием (эта операция есть в большинстве языков программирования) переменным каких-либо значений,

Если у нас предварительно будет описан факт: пища(капуста)., то состоится такая унификация:?- X = Y, пища(X), write(Y). капуста X = Y, Y = капуста.

6.4 Унификация структур

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

?- X = a(b,c). X = a(b,c)?- a(b,X) = a(b,c(d,e)). X = c(d,e)?- a(b,X) = a(b,c(Y,e)).

X = c(Y, e).

В этих примерах надо увидеть, как отношения между переменными сохраняются. Они изменяются только в случае, как только происходят новые связывания переменных.

?- a(b,X) = a(b,c(Y,e)), Y = hello. X = c(hello, e)Y = hello К факту пища(капуста). добавим ещё один факт вкусно(яблоко). и попробуем унифицировать следующее выражение:

?- еда(X,Y) = Z, write(Z), nl, пища(X), вкусно(Y), write(Z).

еда(_G541,_G542)

еда(капуста,яблоко)

X = капуста,

Y = яблоко,

Z = еда(капуста, яблоко).

Два раза отрабатывает оператор WRITE, но каждый раз по-разному!!! Но каждый раз он выдаёт те значения, которые получаются на текущей стадии унификации.

Здесь мы видим появление в ответе «странных» переменных.

Дело в том, что такие обозначения в принятые SWI-Prolog’е для обозначения внутренних переменных, а именно: _ Gnnn.
Два символа _ G – это признак внутренней переменной, а nnn является целым числом, задающий её порядковый номер.

Если значение, назначенное переменной, вступает в противоречие в более поздних целях, то итоговая цель считается неуспешной. Например,

?- a(b,X) = a(b,c(Y,e)), X = hello.

false.

Здесь вторая цель получается неуспешной, поскольку не существует никакого значения Y, которое позволит hello унифицировать с c(Y,e). А вот такой пример даст успех.

?- a(b,X) = a(b,c(Y,e)), X = c(hello, e). X = c(hello, e)Y = hello

Если невозможно дать переменной никакого значения, то унификация получается неуспешной.

?- a(X) = a(b,c). false.?- a(b,c,d) = a(X,X,d). false.

Последний пример терпит неудачу, потому что образец просит, чтобы первые два параметра были те же самые, и они - различны.

Вот два успешных примера

?- a(b,X,d) = a(X,X,d).

X = b.

?- a(b,X,d) = a(X,b,d).

X = b.

Пример неуспеха.

?- a(c,X,X) = a(Y,Y,b). false.

Это происходит потому что, во-первых, сопоставление первого параметра связывает Y с c. Далее, второй параметр заставляет X и Y иметь то же самое значение, в нашем случае c. Третий параметр просит, чтобы X связали с b, а он уже связан к c. И, значит, никакое значение X и Y не позволит этим двум структурам унифицироваться.

Переменная без имени _ - особая переменная. Многократное её написание не подразумевает её одинаковые значения.

?- a(c,X,X) = a(_,_,b). X = b.

Подведем итог.

Унификация происходит явно, когда используется встроенный предикат равенства (=),
и неявно, когда Пролог ищет голову предложения, которая соответствует какой-то цели.

Упражнения

Предскажите результаты таких запросов унификации.

Вопрос	Ответ
a(b,c) = a(X,Y).	X = b Y = c
a(X,c(d,X)) = a(2,c(d,Y)).	X = 2 Y = 2
a(X,Y) = a(b(c,Y),Z).	X = b(c, Z), Y = Z.
tree(left,root,Right) = tree(left,root,tree(a, b, tree(c,d,e))).	Right = tree(a, b, tree(c, d, e))

Дата добавления: 2015-07-12