Правила

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

Правило состоит из головы (предиката) и тела (последовательности предикатов, разделенных запятыми). Голова и тело разделены знаком :- и, подобно каждой фразе Пролога, правило должно заканчиваться точкой. Запятая в теле правила означает конъюнкцию (логическое И).

Знак :- есть схематическая запись стрелки (<-) и показывает, что из правой части следует левая. Этот знак читается как "если". Интуитивный смысл правила состоит в том, что цель, являющаяся головой, будет истинной, если интерпретатор Пролога сможет показать, что все выражения (подцели) в теле правила являются истинными. Пример Правило, определяющее отношение ребенок/2 через отношение отец/2, запишется следующим образом:

ребенок(X, Y) :- отец(Y, X).

Это означает, что если человек Y является для человека X отцом, то X является ребенком Y. Здесь X и Y - переменные. Напомним, что запись ребенок/2 показывает, что предикат ребенок является функцией от двух аргументов.

Пример Определим отношение мать/2 через отношения родитель/2 и женщина/1: матерью X для человека Y является его родитель женского рода.

мать(X, Y) :- родитель(X, Y), женщина(X).

Предикаты отличаются друг от друга не только именем, но и количеством аргументов. Так можно определить отношение мать/1 следующим образом:

мать(X) :- родитель(X, _), женщина(X).

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

?- мать(X, Y).

X=анна

Y=юлия

Yes

?- мать(X).

X=анна

Yes

Пример Определим отношение дедушка/2:

дедушка(X, Y) :- отец(X, Z), отец(Z, Y).

дедушка(X, Y) :- отец(X, Z), мать(Z, Y).

Эти правила утверждают, что дедушкой X для человека Y является отец человека Z, который в свою очередь является отцом или матерью человека Y.

16. Работа интерпретатора Пролога.

Интерпретация Пролог-программ. Рассмотрим более детально схему работы интерпретатора Пролог и суть процес­са унификации выражений.

Алгоритм унификации формирует наиболее общий унификатор для конечного множества унифицированных вы­ражений. Он сравнивает соответствующие элементы одновре­менно слева направо, относящиеся ко всем выражениям до первого отличного элемента. Если для различных элементов можно найти замену, то процесс просмотра выражений счита­ется не унифицированным.

Рассмотрим следующую БД:

/*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.

Рис. 4.9. Схема работы интерпретатора Пролог

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

В дед (Х,Y)

Н дед (Х,Y) :- отец(X,Z), отец(Z,Y)

П дед (Х1,Y1) :- отец(X1,Z1), отец(Z1,Y1)

У дед (Х,Y) :- отец(X,Z), отец(Z,Y) [TB0] X=X1,Y=Y1

В отец(X1,Z1)

Н отец(алексей, владимир)

У дед (ал,Y1) :- отец(алексей,Z1), отец(алексей,Y1) [TB1] Х1= алексей , Y1=владимир

В отец(владимир,Y1)

Н Здесь интерпретатор заходит в тупик, так как в БД нет фраз с первым аргументом "владимир". Интерпретатор возвращается в TBO, т е. содержимое стека восстанавливается:

В отец(X1,Z1)

Н отец(андрей, алексей)

У дед (ан,Y1) :- отец(андрей, алексей), отец(ал,Y1) [TB0] Х1=андрей, Z1=алексей

В отец(алексей,Y1)

Н отец(алексей, владимир)

У дед (андрей, владимир) :- отец(андрей, алексей), отец (алексей, владимир)

Y1=владимир

Правило «дед» разрешено, следовательно, выходим на TB0.