4.2. Вычислительная модель логической программы.

4.2.1. Унификация термов.

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

Термы унифицируются по следующим правилам:

1. Если термы Т1 и Т2 — константы, то они унифицируются только в том случае, когда они одинаковы. Целые и вещественные числа сопоставимы только с равными им числам. Атомы сопоставимы только с идентичными атомами. Строки сопоставимы с одинаковыми строками.

2. Если терм Т1—константа или составной терм, а Т2 — неконкретизированная переменная, не содержащаяся в Т1, то Т1 и Т2 унифицируются, причем в результате переменная Т2 конкретизируется значением Т1.

3. Если термы Т1 и Т2 — неконкретизированные переменные, то их унификация успешна всегда, причем в результате унификации эти переменные становятся сцепленными, то есть при конкретизации одной из них, другая одновременно конкретизируется тем же значением.

4. Если Т1 и Т2 составные термы, то Т1 и Т2 унифицируются успешно, когда они имеют одинаковые главные функторы и арности, и каждая пара соответствующих компонент составных термов успешно унифицируется.

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

Однако, у программиста имеется возможность задать в качестве одной из целей явное выполнение унификации двух термов с помощью операции сопоставления ‘=’. Знак ‘\=’ является знаком отрицания сопоставления. Пусть Т1 и Т2  произвольные термы. Выражение Т1=Т2  истина, когда термы Т1 и Т2 унифицируемы (сопоставимы). Выражение Т1\=Т2 истина, когда Т1 и Т2 не сопоставимы.

Рассмотрим примеры использования операций сопоставления и отрицания сопоставления.

Пример 4.2.1.

?2+1=1+2.

no

Составные термы 2+1 и 1+2 не сопоставимы, и операция сопоставления этих термов неуспешна.

Пример 4.2.2.

?2+1\=1+2.

yes

Операция отрицания сопоставления термов 2+1 и 1+2 успешна.

Пример 4.2.3.

Операцию отрицания сопоставления можно использовать в правилах. Например, надо написать правило с заголовком sister(X,Y). Предикат sister(X,Y)истинен, если Xсестра Y.

Правило записывается следующим образом:

sister(X,Y) :parent(Z,X),parent(Z,Y),person(X,’ж’,_),X\=Y.

Если в Прологпрограмме записаны утверждения примера в пункте 3.2.5, то в ответ на вопрос, кто является сестрой Y? мы получим 3 ответа: ?sister(X,Y). X=’Элизабет’ ответ 1 Y=’Джон’>; X=’Анна’ ответ 2 Y=’Пат’>; X=’Пат’ ответ 3 Y=’Анна’>; no

Ответ 2 читается как“Анна  сестра Пат”, а ответ 3 означает “Пат  сестра Анны”. Это два различных ответа, с точки зрения выше приведенной программы.

4.2.2. Общая схема согласования целевых утверждений.

Самым общим случаем Прологпрограммы является программа, включающая как факты, так и правила. Рассмотрим процесс вычисления запроса на основе такой логической программы. Процесс вычисления начинается с некоторого исходного вопроса Q, который в общем случае может быть конъюнктивным, и завершается получением одного из двух результатов:

• успешного согласования целей вопроса;

• неуспеха (или неудачи).

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

Допустим, что логическая программа P состоит из фактов и правил, а вопрос Q  конъюнктивный и содержит цели G₁,G₂,…G_n. Интерпретатор языка Пролог будет вычислять ответ на вопрос согласно следующим принципам, на которых он реализован:

• Цели запроса обрабатываются слева направо, G₁ будет согласовываться первой, а G_n последней.

• Предложения программы просматриваются интерпретатором сверху вниз.

• Если цель G_i сопоставима с заголовком правила H_j, то она должна быть сопоставима с предикатами в правой части правила. Интерпретатор заменяет цель G_i на правую часть правила H_j. Это действие называется редукцией. Другими словами, Редукцией цели G с помощью программы P называется замена цели G_i на тело правила C_j, заголовок которого H_j унифицируется с целью G_i. Вычисление вопроса выполняется в виде последовательности редукций, цепочки преобразований исходного вопроса. На каждом этапе вычисления существует некоторая конъюнкция целей (или одна цель), называемая резольвентой. Цели, которые добавляются в запрос в результате редукции, называются производными целями от цели G_i и правила C_j. Если цель G_i сопоставима с заголовком правила H_j, то список целей в запросе увеличивается.

• Если цель G_i сопоставима с фактом, то конкретизируются переменные этой цели, и общие переменные цели G_i и других целей, входящих в вопрос, затем осуществляется переход к сопоставлению следующей цели G_i+1 , и, таким образом, список целей, подлежащих согласованию уменьшается.

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

Процедуру Вычислить можно представить более формализовано на языке описания алгоритмов (псевдокоде) в следующем виде:

ПРОЦЕДУРА Вычислить (Прогр, СписокЦелей, ПризнакУспеха)

Входные параметры: Прогр: список предложений на языке Пролог; СписокЦелей: запрос;

Выходной параметр: ПризнакУспеха: истина, если СписокЦелей истинен; ложь, в противном случае.

Локальные переменные: Цель: предикат; ДругиеЦели: список целей; Достигнуты: истинностное значение; Конкрет: конкретизация переменных; H, H’, B₁, B₁’, ……B_n,B_n’: цели;

Вспомогательные функции: пустой(L): возвращает значение «истина», если L пустой список; голова(L): возвращает первый элемент списка L; хвост(L): возвращает остальные элемент списка L; конкат(L1,L2): присоединяет список L2 к концу списка L1; сопоставление(T1,T2,Сопоставимы, Конкрет): пытается унифицировать термы Т1 и Т2; если они унифицируются, то переменной Сопоставимы присваивается значение “истина”, а Конкрет представляет собой конкретизацию переменных; подстановка (Конкрет, Цели): производит подстановку переменных в Цели согласно Конкрет;

НАЧАЛО_ПРОЦЕДУРЫ ЕСЛИ пустой(СписокЦелей) ТО ПризнакУспеха=истина

ИНАЧЕ Цель:=голова(СписокЦелей);

ДругиеЦели:=хвост(СписокЦелей);

Достигнуты:=ложь;

ЦИКЛ ПОКА (Достигнуты=ложь И

“в программе есть еще предложения”)

ЕСЛИ следующее предложение в Прогр есть H:B₁,B₂,…B_n. ТО создать вариант этого предложения H’: B’₁,B’₂,…B’_n. путем переименования переменных; сопоставление(Цель, H’, Сопоставимы, Конкрет);

ЕСЛИ Сопоставимы ТО НовыеЦели:= конкат([B’₁,B’₂,…B’_n,],ДругиеЦели);

НовыеЦели:= подстановка(Конкрет,НовыеЦели); Вычислить(Прогр,НовыеЦели,Достигнуты);

КОНЕЦ_ЕСЛИ КОНЕЦ_ЕСЛИ ИНАЧЕ найден факт H;

создать вариант этого факта H’ путем переименования переменных;

сопоставление(Цель, H’, Сопоставимы, Конкрет);

ЕСЛИ Сопоставимы ТО НовыеЦели:= ДругиеЦели;

НовыеЦели:= подстановка(Конкрет,НовыеЦели); Вычислить(Прогр,НовыеЦели,Достигнуты);

КОНЕЦ_ЕСЛИ КОНЕЦ_ЦИКЛА

КОНЕЦ_ЕСЛИ ПризнакУспеха:=Достигнуты;

КОНЕЦ_ПРОЦЕДУРЫ

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

big(‘медведь’). %предложение 1

big(‘слон’). %предложение 2

little(‘кот’). %предложение 3

little(‘мышь’). %предложение 4

black(‘кот’). %предложение 5

grey(‘слон’). %предложение 6

grey(‘мышь’). %предложение 7

brown(‘медведь’). %предложение 8

dark(Z):black(Z). %предложение 9

dark(Z):brown(Z). %предложение 10

Для вычисления запроса “?  dark(X),big(X). “ интерпретатор выполняется следующие действия:

Шаг 1. Текущая резольвента Q1 есть исходный запрос  dark(X),big(X).

Шаг 2. Текущая резольвента Q2 является конъюнкцией целей dark(X),big(X). Выбираем первую цель G21dark(X) и, просматривая программу с первого предложения, находим предложение 9, сопоставимое с целью G21, является правилом

dark(Z):black(Z). переименовываем переменную Z на Х и вместо цели G21 подставляем правую часть правила 9. Получаем текущую резольвенту Q3black(X),big(X)

Шаг 3. Текущая резольвента Q3 является конъюнкцией целей black(X),big(X). Выбираем первую цель G31black(X) и, просматривая программу с первого предложения, находим предложение 5, сопоставимое с целью G31, black(‘кот’). при подстановке {X=’кот’}. Предложение 5 является фактом, поэтому список целей в резольвенте сократится, так как цель G31 удаляется , а в цель G32 при подстановке {X=’кот’} примет вид big(‘кот’). Получаем текущую резольвенту Q4: big(‘кот’).

Шаг 4 Текущая резольвента Q4 включает одну цель G41 big(‘кот’). Просматривая программу с первого предложения, не находим ни одного предложения, сопоставимого с целью G41, поэтому выполняется возврат на шаг 3.

Шаг 3. Текущая резольвента Q3 является конъюнкцией целей black(X),big(X). Выбираем первую цель G31black(X) и, просматривая программу с предложения 6 до конца программы, и не находим ни одного предложения 5, сопоставимого с целью G31, поэтому выполняется возврат на шаг 2.

Шаг 2. Текущая резольвента Q2 является конъюнкцией целей dark(X),big(X). Выбираем первую цель G21dark(X) и, просматривая программу с предложения 10, находим предложение 10, сопоставимое с целью G21, является правилом

dark(Z):brown(Z). переименовываем переменную Z на Х и вместо цели G21 подставляем правую часть правила 9. Получаем текущую резольвенту Q5 brown (X),big(X).

Шаг 5. Текущая резольвента Q5 является конъюнкцией целей brown(X),big(X). Выбираем первую цель G51 brown(X) и, просматривая программу с первого предложения, находим предложение 8, сопоставимое с целью G51, brown(‘медведь’). при подстановке {X=’медведь’}. Предложение 8 является фактом, поэтому список целей в резольвенте сократится, так как цель G51 удаляется , а в цель G52 при подстановке {X=’медведь’} примет вид big(‘медведь’). Получаем текущую резольвенту Q6: big(‘медведь’).

Шаг 6 Текущая резольвента Q6 включает одну цель G61 big(‘медведь’). Просматривая программу с первого предложения, находим предложение 1, сопоставимое с целью G61, которое является фактом, поэтому цель G61 удаляется из текущей резольвенты, и она становится пустой, Q7=.

Шаг 7. Текущая резольвента Q7 есть пустой дизъюнкт, это указывает на успешное завершение вычисления запроса Q1. Интерпретатор выдает конкретизацию переменной {X=’медведь’} как результат вычисления запроса.

Процесс вычисления запроса удобно представить в виде дерева поиска. Дерево поиска ответа на любой запрос строится следующим образом.

• Корнем дерева является исходный вопрос Q.

• Вершины дерева соответствуют целям (резольвентам), которые в общем случае являются конъюнктивными. В каждой выделяется одна цель.

• Для каждого утверждения программы, заголовок которого унифицируется с выделенной в вершине целью имеется ребро, выходящее из этой вершины.

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

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

Рассмотрим пример построения дерева поиска для запроса: dark(X),big(X).

Когда выполнение программы достигает тупиковой вершины, отмеченной словом "неуспех", автоматически происходит возврат на предыдущий уровень дерева поиска, так как в Прологсистему встроен механизм возврата (backtracing). Выполнение алгоритм поиска решения можно представить как обход лабиринта, где на каждой развилке приходится выбирать новый путь. При попадании в тупик, т.е. на безуспешную вершину (лист дерева поиска), надо следовать в обратном направлении до первого перекрестка, и выбирать другой не опробованный путь, Процесс продолжается до тех пор, пока не встретится успешная вершина или будут пройдены все пути дерева поиска.

В вычислительной модели языка Пролог приняты правила просмотра целей в запросе слева направо и поиска сопоставимых правил и фактов в программе сверху вниз. Такой принцип поиска называется поиском в глубину. Рассмотрим теперь механизм поиска с возвратом.