Для того, чтобы узнать, кто является дедом Михаила по материнской линии, нужно задать вопрос отец(Х,Y), мать(Y,михаил). Чтобы получить, решение, Пролог должен решить первую часть вопроса до запятой и только потом - вторую. Следовательно, будет анализироваться факт "отец(Х,Y)". В нашей БД имеется только один факт с предикатом "отец" и поэтому Х=павел, Y=юлия. Затем Пролог ищет предикат "мать(Y,михаил)" более точно. Поскольку значение Y - "юлия" было только что найдено, то нужно искать факт "мать(юлия, михаил)". Последний имеется в БД и поэтому выдается решение: Х=павел, т.е. "Павел - дед Михаила".
Можно улучшить данное описание БД, объединив цели "отец", "мать" в одно правило:
дед(Х,Y) :- отец(Х,Z), мать(Z,Y).
которое читается так:
Х является дедом Y, если Х является отцом Z и Z является матерью Y.
Заметим, что приведенное выше правило можно представить в виде факта "дед(Х,Y)". Нетрудно видеть, что правило является более компактным описанием, чем множество фактов.
Правила, состоящие из фактов и правил. Имеется возможность определить правила, которые состоят из правил, а последние, в свою очередь, тоже могут состоять из правил, и т.д.
Рассмотрим такую БД:
domains
имя=symbol
predicates
отец(имя.имя)
супруг(имя,имя)
дед(имя,имя)
мать(имя,имя)
clauses
/*1*/ отец(андрей, алексей).
/*2*/ отец(федор, мария).
/*3*/ отец(алексей, лариса).
/*4*/ отец(алексей, владимир).
/*5*/ супруг(алексей, мария).
/*6*/ дед(Х,Y) :- отец(Х,Z), отец(Z,Y).
/*7*/ дед(Х,Y) :- отец(Х,Z), мать(Z,Y).
/*8*/ мать(Х,Y) :- супруг (Z,X), отец(Z,Y).
Правило 8 говорит о том, что мать (X) ребенка (Y) является супругой отца (Z) этого ребенка. И на запрос
мать(Х,Y)
Пролог выдает решение:
Х=мария, Y=лариса
Х=мария, Y=владимир
Правила б и 7 называют соответственно деда по отцу и деда по матери.
Рассмотрим в БД факт или правило, которые могут быть унифицированы с запросом дед(Х,Y). Вначале он находит правило 6 и выдает ответ:
Х=андрей,Y=лариса
Х=андрей,Y=владимир
Затем в соответствии с принципом выбора всех решений Пролог переходит к правилу 7 и анализирует первую подцель правила: "отец(андрей, алексей)", и вторая подцель "мать(алексей,Y)" приводит к тупику.
Рассмотрим более детально на уровне переменных, как подцель "мать(Z,Y)" унифицируется с правилом
мать(Х,Y) :- супруг(Z,X), отец(Z,Y).
Для унификации нужно, чтобы Z стало Х и Y=Y, т. е. можно говорить, что все экземпляры Х из правила станут экземплярами Z. Однако переменная Z уже имеется в правиле и не должна смешиваться с новой переменной Z. Поэтому интерпретатор переименовывает переменные: X1 вместо X, Y1 вместо Y и т.д. Заметим, что в нашем примере Y подцели случайно совпала с Y из правила. Интерпретатор в памяти строит таблицу соответствия новых и старых переменных.
Рассмотрим процесс унификации, когда Z заменяется Xl, a Y-Yl:
В результате унификации переменных правило 7 в БД будет иметь следующий вид:
дед(Х,Y1) :- отец(Х,Х1), супруг (Z1,X1), отец (Z1,Y1).
Для запроса "мать(Z,Y)" интерпретатор найдет Х=федор, Х1=мария, Z1=алексей и два значения Y: Y=лариса и Y=владимир.
Работа интерпретатора Пролога
Интерпретация Пролог-программ. Рассмотрим более детально схему работы интерпретатора Пролог и суть процесса унификации выражений.
Алгоритм унификации формирует наиболее общий унификатор для конечного множества унифицированных выражений. Он сравнивает соответствующие элементы одновременно слева направо, относящиеся ко всем выражениям до первого отличного элемента. Если для различных элементов можно найти замену, то процесс просмотра выражений считается не унифицированным.
Рассмотрим следующую БД:
domains
имя=symbol
predicates
отец(имя,имя)
дед(имя,имя)
clauses
/*1*/
отец(алексей, владимир).
/*2*/ отец(андрей, алексей).
/*3*/ дед(Х,Y):-отец(Х,Z),
отец(Z,Y).
Пусть имеется вопрос
/*4*/дед(Х,Y).
В первом цикле вопросов интерпретатор просматривает фразы программы в последовательности 1-3. Более точно он пытается унифицировать первый литерал из фразы 4 (вначале он единственный) с первым литералом фраз 1-3. В БД только правило 3 может быть унифицировано с фразой 4. Перед унификацией интерпретатор переименовывает переменные правила 3 (X,Y,Z) в X1, Y1, Z1 соответственно. Процесс унификации предполагает замену: Х вместо X1, Y вместо Y1. После сравнения литерала из стека с правилом 3 содержимое стека будет:
/*4а*/ отец (X,Z1), отец (Z1,Y).
Во втором цикле первый литерал (4а) унифицируется с фактом 1, "алексей" заменяет X, а "владимир" - Z1. После этого стек содержит:
/*4б*/отец(владимир,Y).
В третьем цикле литерал (4б) не унифицируется ни с одним из первых литералов фраз 1, 2 или 3. Интерпретатор оказывается в тупике и поэтому выполняет возврат, т.е. содержимое стека, существовавшее до выполнения непосредственно предыдущего цикла, восстанавливается и принимает опять вид состояния 4а.
В четвертом цикле первый литерал (4а) унифицируется с фактом 2, "андрей" заменяется X, а "алексей" - Z1. Стек содержит:
/*4с*/отец (алексей,Y).
В пятом цикле литерал (4с), оставшийся в стеке, унифицируется с фактом 1 и "владимир" заменяется Y. Стек вопросов становится пустым, что вынуждает интерпретатор выводить значения переменных, указанных в вопросе. В данном случае: Х=андрей, Y=владимир.
Затем интерпретатор путем возврата пытается другими способами исчерпать стек вопросов. Но, начиная со стека < содержимым в состоянии 4с, других возможных решений нет Не имеется других решении, если начинать с содержимого стека в состоянии 4а или 4, поэтому интерпретатор заканчивает работу.
Описанная схема работы интерпретатора представлена на Рис. 4.9.
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.