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

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

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

fig1_5.gif (1998 bytes)

Рис. 1. 5.  Пример отношения предок:
(а)    X - ближайший предок Z;     (b)    X - отдаленный предок Z.

между собой отношением родитель-ребенок, как показано на рис.1.5. В нашем примере на рис. 1.1   Том - ближайший предок Лиз и отдаленный предок Пат.

Первое правило простое и его можно сформулировать так:

    Для всех 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).

        .  .  .

 

fig1_6.gif (3835 bytes)

Рис. 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).

fig1_7.gif (2136 bytes)

Рис 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 таким образом, чтобы она соответствовала новому определению?

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


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