Правила

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

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

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

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

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

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

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

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

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

Рассмотрим более детально процесс отсечения. Мы зна­ем, что для получения решения нужно проанализировать, как минимум, одну цель, т.е. найти в БД один факт. Также известно, что если правило является конъюнкцией целей, то для по­лучения решения требуется просмотреть, как минимум, две цели. В Прологе это происходит следующим образом:

1) разрешается (если возможно) первая цель для перво­го соответствующего факта;

2) разрешается (если возможно) вторая цель для всех соответствующих фактов;

3) далее интерпретатор возвращается назад по цепочке целей, как только все факты удовлетворили (или не удовлетво­рили) второй цели.

С помощью встроенного предиката "!" (воскли­цательный знак) - средства "отсечения" - можно воспрепятст­вовать движению назад.

Например, на запрос

отец(Х,Y),!.

Пролог находит первое решение:

X = a, Y = b и переходит ко второй цели, которая указыва­ет, что невозможно возвращаться назад, и процесс прекраща­ется.

Пусть имеется четыре цели:

цель-1 ,цель-2,! ,цель-3,цель-4.

Пролог последовательно анализирует одну за другой четыре цели, а затем: возвращается назад, как только нет решения для цели-4; возвращается назад, как только нет решения для це-ли-3 (или вновь направляется вперед к цели-4 в случае, если имеется решение для цели-3); после этого интерпретатор останавливается на предикате "!", т.е. возвращение к цели-2 и цели-1 невозможно.

Приведем примеры применения предиката "!".