Центральное место в вычислительной модели логических программ составляет алгоритм унификации. Унификация является основой автоматической дедукции и логического вывода в задачах искусственного интеллекта. Введем необходимую для математического описания алгоритма терминологию.
Например, термы pair(“Петр I”, X) и pair(Y, ”Екатерина I”)унифицируемы: унификатором для них будет подстановка {X= ”Екатерина I”, Y= “Петр I”}, дающая в результате терм pair(“Петр I”, ”Екатерина I”) (см. рис. 2).
Рис. 2. Наиболее общий унификатор
Алгоритм унификации находит наиболее общий унификатор двух термов, если такой существует. Если термы не унифицируемы, алгоритм сообщает об отказе.
При согласовании целевого утверждения с базой данных делается попытка унификации этого утверждения с каким-либо фактом или правилом путем их сопоставления. В роли образцов при этом выступают термы, являющиеся аргументами сравниваемых предикатов, имена которых, естественно, должны совпадать. При сравнении образцов приняты следующие соглашения:
●1. Если оба сравниваемых образца– константы, для успешного сопоставления они должны совпадать:
?– man("Петр I").
Yes
●2. Если один из сравниваемых образцов не конкретизированная переменная, т.е. переменная, которой не приписано никакое значение, то второй образец может быть любым термом. При этом если этот терм– константа или константная структура, то переменная, выступающая в роли первого образца, конкретизируется: ей приписывается значение, которое является вторым образцом. Если второй образец– другая не конкретизированная переменная, то между первой и второй переменными устанавливается прямая связь: в случае дальнейшего означивания одной из них вторая автоматически получает то же значение. Если же второй образец является структурой, содержащей другие переменные, между ними и исходной переменной устанавливается более сложная «функциональная» связь. Так, сравнение образцов homo_sapiens(man(Y)) и homo_sapiens(X) приводит к сопоставлению переменной X и структуры man(Y). Дальнейшая конкретизация переменной Y, например, в результате подстановки Y= “Адам” приведет к конкретизации X= man(“Адам”)
●3. Если оба сравниваемых образца– структуры, для их успешного сопоставления должны совпадать имена этих структур, а также сопоставляться между собой все компоненты этих структур по приведенным выше правилам.
●4. Конкретизированные переменные при сопоставлении ведут себя точно так же, как и их значения– константы или константные структуры.
Например:
?– pair( _ , _ ).
Yes
В отличие от:
?– pair(X, X).
No
Неформально процесс работы логической программы может быть описан следующим образом. Он начинается с исходного (возможно конъюнктивного) вопроса G и завершается одним из двух результатов: успешное завершение
или отказ. Работа развивается с помощью редукции цели.
Этапы редукции можно отразить в протоколе логической программы, в который включаются результаты применения редукции и наиболее общий унификатор.
Рассмотрим протокол логической программы относительно вопроса:
?– father(S, “Павел I”).
Вопрос редуцируется с использованием предложения father(X, Y):- child(Y, X), man(X). Наиболее общий унификатор– {X=S, Y=“Павел I”}. Применение подстановки дает новую резольвенту child(“Павел I”, S), man(S). Это конъюнктивная цель. В качестве очередной цели можно выбрать одну из двух. Выбор child(“Павел I”, S) приводит к тому, что цель унифицируется с фактом child(“Павел I”, “Петр III”), и вычисление продолжается с заменой S на “Петр III”. Новая резольвента man(“Петр III”), совпадает с фактом из базы данных. Больше резольвент, подлежащих согласованию нет. Протокол вычисления приводится ниже[11]:
father(S, “Павел I”)
child(“Павел I”, S),
man(“Петр III”)
S= “Петр III”
Yes
Yes
Приведенный протокол не является единственным. К такому же решению приводит и другой протокол:
father(S, “Павел I”)
man(S)
S= “Петр III”
child(“Павел I”, “Петр III”)
Yes
Yes
Обращение к более сложному правилу приводит к усложнению протокола.
?– grandfather(S, “Петр III”).
grandfather(S, “Петр III”)
father(S, A),
child(A, S),
man(“Петр I”)
Yes
Yes
A= ”Анна Петровна”, S= “Петр I”
child(“Петр III”, A= ”Анна Петровна)
Yes
Yes
Другой вариант приводит к этому же решению:
grandfather(S, “Петр III”)
child(“Петр III”, A)
father(S, ”Анна Петровна”)
A= ”Анна Петровна”
child(”Анна Петровна”, S)
man(“Петр I”)
Yes
Yes
S= “Петр I”
Yes
В представленной модели работы интерпретатора имеется два выбора: выбор цели для редукции и выбор предложения. Природа этих выборов совершенно различна. Выбор цели произволен, как видно из приведенных выше протоколов, для успешного вычисления несущественно какая цель выбрана.
Выбор же предложения для редукции является недетерминированным. Не каждый выбор приводит к успеху. Например, при ответе на вопрос
?– father(S, “Павел I”).
мы могли на одном из шагов сделать неверный выбор:
father(S, “Павел I”)
child(“Павел I”, S)
man(“Екатерина II”)
No
S= “Екатерина II”
Альтернативные выборы, которые может сделать интерпретатор при попытке доказать цель, неявно определяют дерево поиска. Задача интерпретатора попытаться найти в дереве поиска путь, соответствующий доказательству цели. Большинство версий Пролога осуществляет полный обход в глубину конкретного дерева поиска цели.
Приведем подробный протокол ответа на вопрос
?– father(S, “Павел I”).
демонстрирующий работу механизма возврата:
grandfather(S, “Павел I”)
father(S, A)
child(A, S)
A= "Петр III", S= “Елизавета Петровна”
man(“Елизавета Петровна”)
No
срабатывает механизм возврата к ближайшей альтернативе
child(A, S)
A= "Алексей Петрович", S= “Петр I”
man(“Петр I”),
Yes
child(“Петр III”, A= ”Алексей Петрович”)
No
срабатывает механизм возврата к ближайшей альтернативе
child(A, S)
A= "Анна Петровна", S= “Петр I”
man(“Петр I”)
Yes
child(“Петр III”, A= ”Анна Петровна”)
Yes
Yes
Наличие механизма унификации наряду с механизмом возвратов является характерной особенностью Пролога.
Контрольные вопросы
1 Что называется доменом?
2 В чем состоят особенности выполнения внутренней цели?
3 В чем состоят особенности выполнения внешней цели?
