Рекурсивные правила

Введем еще одно отношение в рассматриваемую программу с описанием семьи — отношение predecessor (предок). Это отношение будет определено в терминах от­ношения parent. Его можно представить с помощью двух правил. Первое правило определяет прямых (непосредственных) предков, а второе правило — непрямых предков. Говорят, что некоторый X является непрямым предком некоторого Z, если существует цепочка родительских связей между людьми от X до Z, как показано на рис. 1.5. В примере, приведенном на рис. 1.1, Том является прямым предком Лиз и непрямым предком Пэт.

parent

.-,)

predecessor

parent

 

parent

I predecessor

parent

6)

Рис. 1.5. Примеры отношения predecessor: a) X является прямым предком Z; б) К жмется непря­мым предком Z

Первое правило является простым и может быть сформулировано следующим об­разом: Для всех х и s,

X - предок ъ, если

X - родитель г.

Это утверждение можно сразу же перевести на язык Prolog таким образом:

predecessor! X, Z):-

parent (х, Z).

Второе правило, с другой стороны, является более сложным, поскольку решение задачи представления цепочки родительских связей может вызвать некоторые про­блемы. Одна из попыток определить непрямых предков показана на рис, 1.6. Соглас­но этому рисунку, отношение predecessor должно быть определено как множество следующих предложений:

predecessor [ X, Z):- parent 1 X, Z).

predecessor; х, Z):-parent (X, Y), parent С Y, 2).

predecessor; X, Z):- parent (x, YD, parentt Yl_f 42), parent! У2, 1).

predecessor (X, Z):-parentt X, Yl),

Глава 1, Введение в Prolog

parent [ Yl, Y2), parent [ Y2, Y3), parent Y3, Z).

parent

predecessor

©

parent

parent

predecessor

 

Y2J ' predecessor

parent

©

©

Рис, 1.6. Пары предков и потомков, находящихся друг от друга на разных расстояниях

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

Но для формулировки отношения predecessor можно применить гораздо более изящную и правильную конструкцию. Она является правильной в том смысле, что позволяет находить предков до любого колена. Основная идея состоит в том, что отно­шение predecessor должно быть определено в терминах себя самого. Эта идея иллю­стрируется на рис. 1.7 и выражается в виде следующего логического утверждения:

Для всех л ы Z, X - предок Ъ, если имеется такой Y, что

1) X — родитель Y и

2) Y - предок Z.

Предложение Prolog¹, имеющее такой же смысл, приведено ниже.

predecessor! X, Z):-parent! X, Y), predecessor! Y, Z).

Таким образом, сформулирована полная программа для отношения predecessor, которая состоит из двух правил: первое на них определяет прямых, а вторая — не­прямых предков. Оба правила, записанные вместе, приведены ниже.

predecessor(X, Z) parent (X, Z).

predecessor (x, Z) parent (x, ¥), predecessor! Y, Z).

Ключом к анализу этой формулировки является то, что отношение predecessor используется для определения самого себя. Такая конструкция может показаться на

Часть I, Язык Prolog

первый взгляд непонятной, поскольку возникает вопрос, можно ли определить неко­торое понятие, используя для этого то утверждение, которое само еще не было пол­ностью определено. Подобные определения имеют общее название рекурсивных. С точки зрения логики они являются полностью правильными и понятными; кроме того, они становятся очевидными после изучения схемы, приведенной на рис. 1.7. Но остается нерешенным вопрос, способна ли система Prolog использовать рекурсивные правила. Как оказалась, эта система действительно способна очень легко применять рекурсивные определения. Рекурсивное программирование фактически является одним из фундаментальных принципов программирования на языке Prolog. Без использова­ния рекурсии на языке Prolog невозможно решать какие-либо сложные задачи.

parent

predecessor

predecessor

Рис. 1.7. Рекурсивная формули­ровка отношения predecessor

Возвращаясь к рассматриваемой программе, можно задать системе Prolog вопрос о том, кто является потомками Пэм. Иными словами, для кого Пэм является предком?

?- predecessor^ pam, X). X = bob; X = arm; X = pat; X = j im

Ответы системы Prolog, безусловно, верны и логически следуют из определения отношений predecessor и parent. Тем не менее остается открытым весьма важный вопрос: как фактически система Prolog использует программу для поиска этих ответов?

Неформальное описание того, как эта задача решается в системе Prolog, приведе­но в следующем разделе. Но вначале соединим все фрагменты программы с описани­ем семьи, которая постепенно совершенствовалась путем добавления новых фактов и правил. Окончательная форма этой программы приведена в листинге 1.1. Прежде чем перейти к описанию этого листинга, необходимо сделать следующие замечания: во-первых, дать определение термина процедура, а во-вторых, отметить, как исполь­зуются комментарии в программах.

Листинг 1.1. Программа f a m i l y с описанием семьи

parent! раж, bob)

parent [ torn, bob)

parent! torn, liz)

arm) pat)

parent(bob

parent^ bob,

% Пэм является одним из родителей Боба

 

Глава 1. Введение в Prolog

parent(pat, jim).

male! bob). female[ liz), female [ arm). female (pat). male) jim).

offspring С Y, X):-parent I X, Y),

motherf X Y):-parent! X, Y),

female (X).

grandparent! х, 2):-parent) X, Y), parent (Y Z).

sister:X, Y:-

parent(1, X), parent! Z, 4), f«mal.< X), efferent! X, Y).

predecessor! X Z>:- parent(X, Z).

predecessor! X_r z>:-

predecessor! Y, Z)

% Пэм - женщина % Том - мужчина

% Y является сыном или дочерью X, если % X является одним из родителей Y

% X является матерью У, если

% X является одним из родителей Y и

% X - женщина

% X является дедушкой или бабушкой Z, если i X является одним из родителей Y и у является одним из родителей Z

; X является сестрой Y, если

% X и Y имеют одного и того же родителя и

5 X - женщина -,-.

% X и Y являются разными

Правило

У.

предок Z

Правило Рг;

X

предок Z

В программе, приведенной в листинге 1.1, определено несколько отношений: parent, male, female, predecessor и т.д. Например, отношение predecessor оп­ределено с помощью двух предложений. Принято считать, что оба эти предложения касаются отношения predecessor. Иногда удобно рассматривать как единое целое все множество предложений, касающихся одного и того же отношения. Подобный набор предложений называется процедурой.

В листинге 1.1 два правила, касающиеся отношения predecessor, обозначены разными именами, prl и рг2, которые указаны в виде комментариев к программе. Эти имена будут использоваться в дальнейшем в качестве ссылок на данные правила. Обычно комментарии игнорируются системой Prolog. Они служат лишь в качестве дополнительно пояснения для лица, читающего программу. Комментарии в языке Prolog отделяются от остальной части программы специальными символьными скоб­ками "/*■" и ""*/". Таким образом, комментарии в языке Prolog выглядят следующим образом: /• Это - комментарий */

Еще один метод, более удобный для оформления коротких комментариев, преду­сматривает использование знака процента "I". Все, что находится между знаком " и концом строки, интерпретируется как комментарий. \ это - также комментарий

Упражнение

1.6. Рассмотрим следующее альтернативное определение отношения predecessor:

predecessor! X, Z):-

parent! X, Z).

Часть I. Язык Prolog

predecessor [ X, 2):-parent! Y, Z), predecessor (X, У).

Можно ли это определение отношения predecessor также считать правильным? Откорректируйте схему, приведенную на рис. 1.7, чтобы она соответствовала этому новому определению.

Общие принципы поиска ответов на вопросы системой Prolog

В этом разделе дано неформальное описание процесса поиска ответов на вопросы в системе Prolog. Вопрос к системе Prolog всегда представляет собой последователь­ность из одной или нескольких целей. Чтобы ответить на вопрос, Prolog пытается достичь всех целей. Но что в данном контексте означает выражение "достичь цели"? Достичь цели — это значит продемонстрировать, что цель является истинной, при условии, что отношения в программе являются истинными. Другими словами, вы­ражение достичь цели означает: продемонстрировать, что цель логически следует из фактов и правил, заданных в программе. Если вопрос содержит переменные, система Prolog должна также найти конкретные объекты (вместо переменных), при исполь­зовании которых цели достигаются. Для пользователя отображаются варианты кон­кретизации переменных, полученные при подстановке конкретных объектов вместо переменных. Если система Prolog не может продемонстрировать для какого-то вари­анта конкретизации переменных, что цели логически следуют из программы, то вы­дает в качестве ответа на вопрос слово "по".

Таким образом, с точки зрения математики программу Prolog следует интерпре­тировать так: Prolog принимает факты и правила как набор аксиом, а вопрос пользо­вателя — как теорему, требующую доказательства; затем Prolog пытается доказать теорему, т.е. продемонстрировать, что она является логическим следствием из аксиом.

Проиллюстрируем этот подход к описанию работы системы Prolog на классиче­ском примере. Предположим, что заданы приведенные ниже аксиомы.

Все люди способны ошибаться. Сократ - человек.

Из этих двух аксиом логически следует теорема: Сократ способен ошибаться.

Первая аксиома, приведенная выше, может быть переформулирована следующим образом: Для всех X, если X - человек, то х способен ошибаться.

Соответствующим образом этот пример может быть переведен на язык Prolog, как показано ниже. fallible! X}:- man; X}. % Все люди способны ошибаться

man! socrates). % Сократ -человек

?- fallible! sccrates), % Сократ способен ошибаться?

yes % Да

Более сложный пример, взятый из программы с описанием семьи (см. лис­тинг 1.1), представлен ниже.?- predecessor; torn, pat).

Известно, что в этой программе определен факт parent! bob, pat). Используя этот факт и правило prl, можно прийти к заключению, что имеет место факт predecessor [ bob, pat). Это — производный факт, в том смысле, что его нельзя непосредственно найти в программе, но можно вывести из фактов и правил програм­мы. Этап вывода, подобный этому, можно записать в более компактной форме сле­дующим образом:

Глава 1. Введение в Prolog

parent [ bob, pat) ==> predecessor! bob, pat)

Это выражение можно прочесть так: из факта parent [ bob, pat) следует факт predecessor { bob, pat], согласно правилу prl. Кроме того, известно, что опреде­лен факт parent (torn, bob). Используя этот факт и производный факт predecessor; bob, pat), можно сделать вывод, что имеет место факт predecessor; torn, pat], согласно правилу ri2. Тем самым показано, что целевое выражение predecessor (torn, par } является истинным. Весь этот двухэтапный процесс вывода можно записать следующим образом: parent r bob, pat) - predecessor; bob, pat) parent; torn, bob) и predecessor | bob, pat) ==> predecessor) torn, pat)

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

Prolog ищет последовательность доказательства в порядке, обратном тому, кото­рый был только что использован. Эта система начинает не с простых фактов, задан­ных в программе, а с целей, и с помощью правил заменяет текущие цели новыми до тех пор, пока не обнаружится, что новые цели являются простыми фактами. Рас­смотрим вопрос:?- predecessor; torn, pat).

Система Prolog пытается достичь данной цели. Для этого она предпринимает по­пытки найти в программе предложение, из которого непосредственно может следо­вать указанная выше цель. Очевидно, что в этом случае подходящими являются только предложения prl и рг2. Это — правила, касающиеся отношения predecessor. Говорят, что головы этих правил соответствуют цели.

Два предложения, prl и рг2, представляют собой два альтернативных способа дальнейших действий системы Prolog. Она вначале проверяет предложение, которая находится на первом месте в программе: predecessor! X, Z):- parent (X, Z).

Поскольку целью является факт predecessor; torn, pat), необходимо выпол­нить конкретизацию переменных в этом правиле следующим образом: X = torn, Z • pat

Затем первоначальная цель predecessor; torn, pat) заменяется следующей но­вой целью; parent (torn, pat)

Данный этап использования правила преобразования цели в другую цель, как указано выше, схематически показан на рис. 1.8. В программе отсутствует предло­жение, которое соответствует цели parent; torn, pat), поэтому такая цель непо­средственно не достижима. Теперь система Prolog возвращается к первоначальной цели, чтобы проверить альтернативный способ вывода главной цели predecessor (torn, pat), Поэтому правило рг2 проверяется следующим образом:

predecessor! X, Z):-parent! X, Y),

predecessor; Y, Z).

Как было указано выше, конкретизация переменных X и Z выполняется следую­щим образом: X = ton, Z = pat

Но конкретизация Y еще не выполнена. Верхняя цель predecessor; torn, pat) заменяется двумя следующими целями:

parent (torn, Y), predecessor t Y, pat)

40 Часть I. Язык Prolog

Этот этап выполнения показан на рис. 1.9, который демонстрирует дальнейшее развитие ситуации, представленной на рис. 1.8.

predecessor^ torn, pat)

predecessor! torn, pat)

 

ZS

Л

 

no правилу pr1