5.4 Простой абстрактный интерпретатор логических программ.

Интерпретатор выполняет вычисления и выдает ответы «да» или «нет». Он анализирует некоторую программу Р и заданный вопрос Q и выдает ответ:

«да», если Q выводится из Р;

«нет» - в противном случае.

Если цель не выводима из программы, то интерпретатор может не выдать никакого ответа.

На каждой стадии вычислений существует текущая унифицируемая цель, называемая резольвентой.

Общий алгоритм работы интерпретатора:

Шаг 1: Положить резольвенту равной Q.

Шаг 2: Цикл: Пока резольвента A₁ ,…, A_n не пуста Do

{выбор A_i 1< i <n и поиск такого основного примера предложения A^*B₂ ,…, B_k (k > 0), что A^* = A_i, т.е. резольвента унифицируема

Е сли  A^* То Exit.

Выбор следующей A_i.

Выполнение подстановки Q к резольвенте.}

Если резольвента пуста То Да.

Пример цели содержится в Q.

Иначе – Нет.

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

Пример вопроса, для которого доказана его истинность, называется решением вопроса.

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

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

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

Дерево вывода состоит из вершин и ребер и отображает цели, снимаемые в процессе вычислений. Цели соответствуют вершинам дерева.

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

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

Пример 5.2

сын(X, Y) :- родитель(Y, X), M(X). % R

? – сын(петя, вася)

1-ая редукция снимает цель и строит 2 производные цели на основе наиболее общего примера R, найденного в программе.

2-ая и 3-я редукции подтверждают поставленные подцели и не создают новых производных целей.

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

с ын(петя, вася)

родитель(вася, петя) М(вася)

Значением логической программы Р называется множество основных единичных целей М(Р), выводимых из программы.

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

Программа Р корректна относительно некоторого заданного значения M_i, если оно является подмножеством всех значений данной программы M_i  M(P). Другими словами, программа корректна, если вычисляет только то, что требуется.

Программа Р называется полной, если она вычисляет все возможные значения программы.

Цель называется истинной относительно подразумеваемого значения, если цель входит в данное значение (выводится из него). В противном случае цель называется ложной.

Унификация является основой автоматической дедукции и логического вывода в задачах искусственного интеллекта. Унификатором 2-х термов А и В называется такая подстановка Q, которая делает их равными: AQ = BQ.

Если существует унификатор 2-х термов, то такие термы называются унифицируемыми.

Каждый унификатор характеризует общий пример терма. Для каждого терма возможно множество общих примеров. Для 2-х унифицируемых термов существует единственный наиболее общий унификатор.

Алгоритм унификации находит наиболее общий унификатор 2-х термов, если таковой существует.

Общая схема алгоритма унификации:

T₁Q = T₂Q. Q - ?

Будем считать, что Q – ячейка памяти.

1. Q = 0. Стек: T₁, T₂, отказ = false.

2. Пока стек не пуст и не отказ

Do

считать X = Y из стека

ветвление:

1. X-переменная, не входящая в терм Y: замена всех Х в стеке и в языке программирования Q на Y.

2. Y-переменная, X-терм: замена Y на X.

3. X = Y:  продолжить

4. X-функтор X = f(q₁, … , q_n) и

Y-функтор Y = f(q₁, … , q_n), т.е.

X и Y – составные термы:

поместить X_i и Y_i  в стек.

3) Если термы не унифицируемы,

то отказ = true

иначе результат хранится в Q.

Этот алгоритм использует стек для хранения входных равенств, подлежащих решению, и язык программирования Q для хранения результата подстановки.

В цикле из стека считается и обрабатывается на каждом шаге одно равенство.