Первое правило простое и его можно сформулировать так:
Для всех X и Z,
X — предок Z, если
X — родитель Z.
Это непосредственно переводится на Пролог как
предок( X, Z) :-
родитель( X, Z).
Второе
правило сложнее, поскольку построение цепочки отношений
родитель
может вызвать некоторые трудности. Один из способов определения отдаленных родственников мог бы быть таким, как показано на рис. 1.6. В соответствии с ним отношение предок определялось бы следующим множеством предложений:
предок( X, Z) :-
родитель( X, Z).
предок( X, Z) :-
родитель( X, Y),
родитель( Y, Z).
предок( X, Z) :-
родитель( X, Y1),
родитель( Yl, Y2),
родитель( Y2, Z).
предок( X, Z) :-
родитель( X, Y1),
родитель( Y1, Y2),
родитель( Y2, Y3),
родитель( Y3, Z).
...
Рис. 1.6. Пары предок-потомок, разделенных разным числом поколений.
Эта программа длинна и, что более важно, работает только в определенных пределах. Она будет обнаруживать предков лишь до определенной глубины фамильного дерева, поскольку длина цепочки людей между предком и потомком ограничена длиной наших предложений в определении отношения.
Существует, однако, корректная и элегантная формулировка отношения
предок
— корректная в том смысле, что будет работать для предков произвольной отдаленности. Ключевая идея здесь — определить отношение
предок
через него самого. Рис 1.7 иллюстрирует эту идею:
Для всех X и Z,
X — предок Z, если
существует Y, такой, что
(1) X — родитель Y и
(2) Y — предок Z.
Предложение Пролога, имеющее тот же смысл, записывается так:
предок( X, Z) :-
родитель( X, Y),
предок( Y, Z).
Теперь мы построили полную программу для отношения
предок
, содержащую два правила: одно для ближайших предков и другое для отдаленных предков. Здесь приводятся они оба вместе:
предок( X, Z) :-
родитель( X, Z).
предок( X, Z) :-
родитель( X, Y),
предок( Y, Z).
Рис. 1.7. Рекурсивная формулировка отношения
предок
.
Ключевым моментом в данной формулировке было использование самого отношения
предок
в его определении. Такое определение может
озадачить - допустимо ли при определении какого-либо понятия использовать его же, ведь оно определено еще не полностью. Такие определения называются рекурсивными. Логически они совершенно корректны и понятны; интуитивно это ясно, если посмотреть на рис. 1.7. Но будет ли в состоянии пролог-система использовать рекурсивные правила? Оказывается, что пролог-система очень легко может обрабатывать рекурсивные определения. На самом деле, рекурсия — один из фундаментальных приемов программирования на Прологе. Без рекурсии с его помощью невозможно решать задачи сколько-нибудь ощутимой сложности.
Возвращаясь к нашей программе, можно теперь задать системе вопрос: "Кто потомки Пам?" То есть: "Кто тот человек, чьим предком является Пам?"
?- предок( пам, X).
X = боб;
X = энн;
X = пат;
X = джим
Ответы системы, конечно, правильны, и они логически вытекают из наших определений отношений
предок
и
родитель
. Возникает, однако, довольно важный вопрос: "Как в действительности система использует программу для отыскания этих ответов?"
Неформальное объяснение того, как система это делает, приведено в следующем разделе. Но сначала давайте объединим все фрагменты нашей программы о родственных отношениях, которая постепенно расширялась по мере того, как мы вводили в нее новые факты и правила. Окончательный вид программы показан на рис. 1.8.
При рассмотрении рис. 1.8 следует учесть два новых момента: первый касается понятия "процедура", второй — комментариев в программах. Программа, приведенная на рис. 1.8, определяет несколько отношений —
родитель
,
мужчина
,
женщина
,
предок
и т.д. Отношение
предок
, например, определено с помощью двух предложений. Будем говорить, что эти два предложения входят в состав отношения
предок
. Иногда бывает удобно рассматривать в целом все множество предложений, входящих в состав одного отношения. Такое множество называется процедурой.