Как и было обещано, рассмотрим более подробный пример генеалогического древа - на этот раз древа греческих богов.
Прежде всего, основываясь на диаграмме, зададим известные нам факты - определим границы мира текущей сессии Пролога. Итак,
Распределим мужские и женские роли:
male(cronus). female(rhea).
male(poseidon). male(zeus). female(hera).
male(ares). female(hebe). male(hephaestus).
Установим родительские отношения:
father(cronus, poseidon). father(cronus, zeus).
mother(rhea, poseidon). mother(rhea, zeus).
father(zeus, ares). father(zeus, hebe). father(zeus, hephaestus).
mother(hera, ares). mother(hera, hebe). mother(hera, hephaestus). (Программировать на Прологе - одно удовольствие!)
А теперь супружеские отношения:
spouse(cronus, rhea). spouse(zeus, hera).
Мир богов Олимпа полностью задан (заметьте: "полностью", как и следовало ожидать, означает "в рамках поставленной задачи").
Пришло время определить правила. С некоторыми из них мы уже знакомы:
parent(P, C) :- (mother(P, C) ; father(P, C)).
child(C, P) :- parent(P, C).
son(C, P) :- parent(P, C), male(C).
daughter(C, P) :- parent(P, C), female(C).
Синтаксис первого правила нуждается в объяснении. Если, как вы помните, запятая обозначает союз и, то точка с запятой в Прологе обозначает союз или. То есть, правило буквально гласит: P является родителем C, если P - отец C или P - мать C.
Продолжаем упражнения.
Жена - это "один из супругов, который к тому же ещё и женщина". Нетрудно догадаться, что муж - это супруг-мужчина. Обратите внимание, что в этих правилах тоже используется или, потому что порядок расположения супругов в факте spouse не имеет значения:
wife(W, P) :- (spouse(W, P);spouse(P, W)), female(W).
husband(H, P) :- (spouse(H, P);spouse(P, H)), male(H).
Следующие правила для "предков" и "потомков" интересны тем, что определяются рекурсивно. Чтобы вспомнить, что такое рекурсивное определение, вернитесь к главе, рассказывающей о Лиспе. Так, например, определение списка - рекурсивно. Список - это первый элемент (голова), за которым следует список остальных элементов (хвост).
Взгляните на правила ancestor. Первое правило - это базисный случай рекурсии, то есть тот случай, не требующий дальнейшего обращения к той же самой структуре, определение которой мы строим. В нашем случае - "родитель" - это тоже "предок". Определяя понятие "предок" через понятие "родитель", мы не должны более беспокоиться о дальнейших поисках - они заканчиваются на факте parent[1]:
ancestor(A,P) :- parent(A,P).
Так, например, на вопрос ancestor(cronus, zeus) Пролог ответит утвердительно, испытав для начала parent(cronus, zeus), который немедленно разрешится положительно с помощью факта father(cronus, zeus). Однако на вопрос ancestor(cronus, ares) ответить Прологу будет не так-то просто. Для таких случаев не прямого потомства используется второе правило ancestor.
Основное, не базисное правило для определения "предка" не так просто понять. Здесь присутствует дополнительная переменная X. Без неё мы бы никак не смогли обозначить промежуточное звено в нашем генеалогическом древе - а именно, некоего человека X, который, как видно из правила, является родителем P (искомого потомка)[2]. В самом деле, А является предком P, если он одновременно является и предком родителя P, то есть X. А что, если он не просто предок родителя P, а сам родитель P ?! Нет ничего проще - см. правило первое для ancestor.
Таким образом:
ancestor(A, P) :- parent(X, P), ancestor(A, X).
В приведённом выше примере в роли X будет выступать Зевс. Попробуем заменить все переменные в нашем правиле на имена богов:
ancestor(cronus, ares) :- parent(zeus, ares), ancestor(cronus, zeus).
В самом деле, мы уже видели, что вопрос ancestor(cronus, zeus) разрешается положительно, а ответ на вопрос parent(zeus, ares) также не вызывает сомнений, принимая во внимание существующий факт father(zeus, ares). Всё сходится!
Примерно то же самое происходит и в определении "потомка". Разница в том, что в качестве "вспомогательной персоны" X здесь используется человек, наиболее высоко стоящий в иерархии по отношению к предку P, тогда как для определения "потомка" в качестве X использовался самый низший до потомка P в иерархии представитель семейства:
descendent(D, P) :- parent(P, D).
descendent(D, P) :- parent(P, X), descendent(D, X).
На самом деле, определить предка и потомка можно многими способами, и приведённый здесь - лишь один из возможных вариантов.
Чтобы у читателя не осталось уже никаких сомнений в способах определения отношений "предок"-"потомок" в Прологе, ему стоит взглянуть на рисунок.
Двигаемся дальше. Чтобы определить "брата" и "сестру", введём несколько вспомогательных правил: sibling (брат или сестра), full_sibling (брат или сестра по отцу и по матери) и half_sibling (брат или сестра только по отцу или только по матери).
Итак, full_sibling - это братья или сёстры, у которых один отец и одна мать, но они не являются одним и тем же человеком. Этот последний факт выражен с помощью оператора Пролога "не равно" \= :
full_sibling(S1, S2) :- mother(M, S2), mother(M, S1), S1 \= S2,
father(F, S1), father(F, S2).
Определение half_sibling состоит из двух правил - в одном различаться должны только матери, в другом - только отцы:
half_sibling(S1, S2) :- mother(M, S2), mother(M, S1), S1 \= S2,
father(F1, S1), father(F2, S2), F1 \= F2.
half_sibling(S1, S2) :- father(F, S2), father(F, S1), S1 \= S2,
mother(M1, S1), mother(M2, S2), M1 \= M2.
Просто sibling - это или full_sibling или half_sibling:
sibling(S1, S2) :- (full_sibling(S1, S2);half_sibling(S1, S2)).
Теперь нет ничего проще, чем определить правила для братьев и сестёр:
sister(S,P) :- sibling(S, P), female(S).
brother(B,P) :- sibling(B, P), male(B).
Настала очередь дядюшек, тётушек, племянников и племянниц:
uncle(U, X) :- parent(P, X), brother(U, P).
aunt(A, X) :- parent(P, X), sister(A, P).
В качестве вспомогательной переменной здесь используется P - родитель X. Так, чтобы ответить на вопрос uncle(poseidon, hebe), Пролог быстро найдёт, что утверждение parent(zeus, hebe) - истинно, а в результате сложных поисков обнаружит, что и brother(poseidon, zeus) тоже верно. Таким образом Посейдон будет справедливо признан дядей Гебы.
Примерно так же определяются понятия "племянника" и "племянницы" за одним исключением. Как видите, в этих правилах прямо указывается, что "племянник" должен быть мужского рода, а "племянница" - женского, в отличие от "дяди" и "тёти", где этого сделано не было. Почему ? Дело в том, что "дядя" и "тётя" определялись с помощью правил "сестра" и "брат", которые косвенно уже определены с помощью фактов male и female.
nephew(N, X) :- sibling(S, X), parent(S, N), male(N).
niece(N, X) :- sibling(S, X), parent(S, N), female(N).
В качестве самостоятельного упражнения читателю предлагается разобраться в том, как устроены отношения между бабушками, дедушками и внуками:
grandmother(GM, X) :- parent(P, X), mother(GM, P).
grandfather(GF, X) :- parent(P, X), father(GF, P).
grandparent(GP, X) :- parent(P, X), parent(GP, P).
grandson(GS, X) :- grandchild(GS, X), male(GS).
granddaughter(GD, X) :- grandchild(GD, X), female(GD).
grandchild(GC, X) :- parent(X, C), parent(C, GC).
[1] Сравните базисный случай рекурсивного определения списка: "пустой список - это тоже список". Определение на этом заканчивается.
[2] Заметьте, что сам по себе человек X нас никоим образом не интересует. Он служит в качестве некоей опоры Прологу в поисках по дереву родства.