Унификация

ВВОД программ

Введение списка утверждений в Пролог-систему осуществляется с помощью встроенного предиката consult. Аргументом предиката consult является атом, который обычно интерпретируется системой как имя файла, содержащего текст программы на Прологе. Файл от­крывается, и его содержимое записывается в базу данных. Если в файле встречаются управляющие команды, они сразу же выполня­ются. Возможен случай, когда файл не содержит ничего, кроме уп­равляющих команд для загрузки других файлов. Для ввода утверж­дений с терминала в большинстве реализации Пролога имеется спе­циальный атом, обычно user. С его помощью утверждения записыва­ются в базу данных, а управляющие команды выполняются немед­ленно.

Помимо предиката consult, в Прологе существует предикат reconsult. Он работает аналогичным образом. Но перед добавлени­ем утверждений к базе данных из нее автоматически удаляются те утверждения, головные цели которых сопоставимы с целями, со­держащимися в файле перезагрузки. Такой механизм позволяет вводить изменения в базу данных. В Прологе имеются и другие методы добавления и удаления утверждений из базы данных. Не­которые реализации языка поддерживают модульную структуру, позволяющую разрабатывать модульные программы.

В заключение раздела дадим формальное определение синтакси­са Пролога, используя форму записи Бэкуса-Наура, иногда называе­мую бэкусовской нормальной формой (БНФ).

запрос ::- голова утверждения

правило ::– голова утверждения :- хвост утверждения

факт ::- голова утверждения

голова утверждения ::-атом | структура

хвост утверждения ::- атом структура,

термы ::-терм [,термы]

терм ::- число | переменная | атом | структура

структура ::-атом (термы)

Данное определение синтаксиса не включает операторную, спи­сковую и строковую формы записи. Полное определение дано в при­ложении А. Однако, любая программа на Прологе может быть напи­сана с использованием вышеприведенного синтаксиса. Специальные формы только упрощают понимание программы. Как мы видим, син­таксис Пролога не требует пространного объяснения. Но для написа­ния хороших программ необходимо глубокое понимание языка.

Одним из наиболее важных аспектов программирования на Про­логе являются понятия унификации (отождествления) и конкретиза­ции переменных.

Пролог пытается отождествить термы при доказательстве, или согласовании, целевого утверждения. Например, в программе из гл. 1 для согласования запроса ?- собака(Х) целевое утверждение соба­ка (X) было отождествлено с фактом собака (реке), в результате чего переменная Х стала конкретизированной: Х= рекc.

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

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

Терм Х сопоставляется с термом Y по следующим правилам. Ес­ли Х и Y - константы, то они сопоставимы, только если они одинако­вы. Если Х является константой или структурой, а Y - неконкретизи­рованной переменной, то Х и Y сопоставимы и Y принимает значе­ние Х (и наоборот). Если Х и Y - структуры, то они сопоставимы тог­да и только тогда, когда у них одни и те же главный функтор и ар­ность и каждая из их соответствующих компонент сопоставима. Если Х и Y - неконкретизированные (свободные) переменные, то они со­поставимы, в этом случае говорят, что они сцеплены. В (Таблица 2) при­ведены примеры отождествимых и неотождествимых термов.

Таблица 2. Иллюстрация унификации.

Заметим, что Пролог находит наиболее общий унификатор тер­мов. В последнем примере (рис.2.1) существует бесконечное число унификаторов:

X-1, Z-2; X-2, Z-2; ....

но Пролог находит наиболее общий: Х=Z.

Следует сказать, что в большинстве реализации Пролога для по­вышения эффективности его работы допускается существование циклических унификаторов. Например, попытка отождествить тер­мы f(X) и Х приведет к циклическому унификатору X=f(X), кото­рый определяет бесконечный терм f(f(f(f(f(...))))). В программе это иногда вызывает бесконечный цикл.

Возможность отождествления двух термов проверяется с по­мощью оператора =.

Ответом на запрос

?- 3+2=5.

будет

нет

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

?-строка(поз(Х)) -строка(поз(23)).

закончится успехом при

Х=23.

Унификация часто используется для доступа к подкомпонентам термов. Так, в вышеприведенном примере Х конкретизируется пер­вой компонентой терма поз(23), который в свою очередь является компонентой терма строка.

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

?-строка(поз(Х)) --строка (поз (23)).

дает ответ

нет

поскольку подтерм Х в левой части (X - свободная переменная) не идентичен подтерму 23 в правой части, Однако запрос

?- строка (поз (23)) --строка (поз (23)).

дает ответ

да

Отрицания операторов = и - = записываются как \= и \= = соот­ветственно.