Назад | Содержание| Вперёд 1. 3. Рекурсивное определение правил Д...

Назад | Содержание| Вперёд

1. 3. Рекурсивное определение правил

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

Рис 1. 7. Рекурсивнаяформулировка отношения предок.

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

Возвращаясь к нашей программе, можно теперьзадать системе вопрос: "Кто потомки Пам?" Тоесть: "Кто тот человек, чьим предком являетсяПам ?"

?- предок( пам, X).

X = боб;

X = энн;

X = пат;

X = джим

Ответы системы, конечно, правильны, и онилогически вытекают из наших определенийотношений предок и родитель.Возникает, однако, довольно важный вопрос: "Какв действительности система использует программудля отыскания этих ответов?"

Неформальное объяснение того, как система этоделает, приведено в следующем разделе. Но сначаладавайте объединим все фрагменты нашей программыо родственных отношениях, которая постепеннорасширялась по мере того, как мы вводили в нееновые факты и правила. Окончательный видпрограммы показан на рис. 1.8.

При рассмотрении рис. 1.8 следует учесть двановых момента: первый касается понятия"процедура", второй - комментариев впрограммах. Программа, приведенная на рис. 1.8,определяет несколько отношений - родитель,мужчина, женщина, предоки т.д. Отношение предок, например,определено с помощью двух предложений. Будемговорить, что эти два предложения входят в составотношения

родитель( пам, боб). % Пам - родитель Боба

родитель( том, боб).

родитель( том, лиз).

родитель( бoб, энн).

родитель( боб, пат).

родитель( пат, джим).

женщина( пам). % Пам - женщина

мужчина( том). % Том - мужчина

мужчина( боб).

женщина( лиз).

женщина( энн).

женщина( пат).

мужчина( джим).

отпрыск( Y, X) :- % Y - отпрыск X, если

родитель( X, Y). %X - родитель Y

мать( X, Y) :- %X - мать Y, если

родитель(X, Y), %X - родитель Y и

женщина(X). %X - женщина

родительродителя( X, Z) :-

% X - родитель родителя Z, если

родитель(X, Y), %X - родитель Y и

родитель(Y, Z). %Y - родитель Z

сестра( X, Y) :- % X - сестра Y

родитель(Z, X),

родитель( Z, Y)

% X и Y имеют общего родителя

женщина(X, Y), %X - женщина и

различны(X, Y). % Xотличается от Y

предок( X, Z) :- %Правило пр1: X - предок Z

родитель(X, Z).

предок( X, Z) :- %Правило пр2: X - предок Z

родитель( X, Y),

предок( Y, Z).

Рис. 1. 8. Программа ородственных отношениях.

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

На рис. 1.8 два предложения, входящие в состав отношения предок, выделеныименами "пр1" и "пр2", добавленными впрограмму в виде комментариев.Эти имена будут использоваться в дальнейшем дляссылок на соответствующие правила. Вообщеговоря, комментарии пролог-системойигнорируются. Они нужны лишь человеку, которыйчитает программу. В Прологе комментарииотделяются от остального текста программыспециальными скобками "/*" и "*/". Такимобразом, прологовский комментарий выглядит так

/* Это комментарий */

Другой способ, более практичный для короткихкомментариев, использует символ процента %. Все,что находится между % и концом строки,расценивается как комментарии:

% Это тоже комментарий

Упражнение

1. 6. Рассмотрим другойвариант отношения предок:

предок( X, Z) :-

родитель( X, Z).

предок( X, Z) :-

родитель( Y, Z).

предок( X, Y).

Верно ли и такое определение? Сможете ли Выизменить диаграмму на рис. 1.7 таким образом, чтобыона соответствовала новому определению?

Посмотреть ответ

Назад | Содержание| Вперёд

Оглавление