Способность пролог-системы прорабатывать многие процедурные детали самостоятельно считается одним из специфических преимуществ Пролога. Это свойство побуждает программиста рассматривать декларативный смысл программы относительно независимо от ее процедурного смысла. Поскольку результаты работы программы в принципе определяются ее декларативным смыслом, последнего (Опять же в принципе) достаточно для написания программ. Этот факт имеет практическое значение, поскольку декларативные аспекты программы являются, обычно, более легкими для понимания, нежели процедурные детали. Чтобы извлечь из этого обстоятельства наибольшую пользу, программисту следует сосредоточиться главным образом на декларативном смысле и по возможности не отвлекаться на детали процесса вычислений. Последние следует в возможно большей мере предоставить самой пролог-системе.

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

Дерево родственных отношений.

Эта программа содержит шесть предложений. Каждое предложение объявляет об одном факте наличия отношения родитель.

После ввода такой программы в пролог-систему последней можно будет задавать вопросы, касающиеся отношения родитель. Например, является ли Боб родителем Пат? Этот вопрос можно передать пролог-системе, набрав на клавиатуре терминала:

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

Найдя этот факт в программе, система ответит

        yes            (да)

Другим вопросом мог бы быть такой:

        ?-  родитель( лиз, пат).

Система ответит

        no             (нет),

поскольку в программе ничего не говорится о том, является ли Лиз родителем Пат. Программа ответит "нет" и на вопрос

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

потому, что имя Бен в программе даже не упоминается.

Можно задавать и более интересные вопросы. Например:"Кто является родителем Лиз?"

       ?-  родитель( X, лиз).

На этот раз система ответит не просто "да" или "нет". Она скажет нам, каким должно быть значение X (ранее неизвестное), чтобы вышеприведенное утверждение было истинным. Поэтому мы получим ответ:

        X  =  том

Вопрос "Кто дети Боба?" можно передать пролог-системе в такой форме:

        ?-  родитель( боб, X).

В этом случае возможно несколько ответов. Сначала система сообщит первое решение:

        X  =  энн

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

        X  =  пат

Если мы потребуем дальнейших решений, система ответит "нет", поскольку все решения исчерпаны.

Нашей программе можно задавать и более общие вопросы: "Кто чей родитель?" Приведем другую формулировку этого вопроса:

        Найти X и Y такие, что X - родитель Y.

На Прологе это записывается так:

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

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

        X  =  пам
        Y  =  боб;

        X  =  том
        Y  =  боб;

        X  =  том
        Y  =  лиз;

        .  .  .

Мы можем остановить поток решений, набрав, например, точку вместо точки с запятой (выбор конкретного символа зависит от реализации).

Нашей программе можно задавать и еще более сложные вопросы, скажем, кто является родителем родителя Джима? Поскольку в нашей программе прямо не сказано, что представляет собой отношение родительродителя, такой вопрос следует задавать в два этапа, как это показано на рис. 1.2.

        (1)    Кто родитель Джима?   Предположим, что это некоторый Y.

        (2)    Кто родитель Y?   Предположим, что это некоторый X.

Такой составной вопрос на Прологе записывается в виде последовательности двух простых вопросов:

        ?-  родитель( Y, джим), родитель( X, Y).

Ответ будет:

        X  =  боб
        Y  =  пат

Графы отношений родительродителя, мать и отпрыск,

Такие отношения как родитель, отпрыск и мать можно изобразить в виде диаграмм, приведенных на рис. 1.3. Они нарисованы с учетом следующих соглашений. Вершины графа соответствуют объектам, т.е. аргументам отношений. Дуги между вершинами соответствуют бинарным (двуместным) отношениям. Дуги направлены от первого аргумента к второму. Унарные отношения на диаграмме изображаются просто пометкой соответствующих объектов именем отношения. Отношения, определяемые через другие отношения, представлены штриховыми дугами. Таким образом, любую диаграмму следует понимать так: если выполнены отношения, изображенные сплошными дугами, тогда и отношение, изображенное штриховой дугой, тоже выполнено. В соответствии с рис. 1.3, отношение родительродителя можно сразу записать на Прологе:

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

Здесь уместно сделать несколько замечаний о внешнем виде нашей программы. Пролог дает почти полную свободу расположения текста на листе. Так что можно вставлять пробелы и переходить к новой строке в любом месте текста по вкусу. Вообще мы хотим сделать так, чтобы наша программа имела красивый и аккуратный вид, а самое главное, легко читалась. Для этого мы часто будем помещать голову предложения и каждую цель на отдельной строке. При этом цели мы будем писать с отступом, чтобы сделать разницу между головой и целями более заметной. Например, правило родительродителя в соответствии с этими соглашениями запишется так:

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

На рис. 1.4 показано отношение сестра:

Как пролог-система отвечает на вопросы

В данном разделе приводится неформальное объяснение того, как пролог-система отвечает на вопросы.

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

Проиллюстрируем этот подход на классическом примере. Пусть имеются следующие аксиомы:

        Все люди смертны.
        Сократ - человек.

Теорема, логически вытекающая из этих двух аксиом:

        Сократ смертен.

Первую из вышеуказанных аксиом можно переписать так:

        Для всех X, если X - человек, то X смертен.

Соответственно наш пример можно перевести на Пролог следующим образом:

       смертен( X) :- человек( X).                    % Все люди смертны
       человек( сократ).                                     % Сократ - человек
       ?-  смертен( сократ).                                % Сократ смертен?
       yes                   (да)

Более сложный пример из программы о родственных отношениях, приведенной на рис. 1.8:

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

Мы знаем, что родитель( боб, пат) - это факт. Используя этот факт и правило пр1, мы можем сделать вывод, что утверждение предок( боб, пат) истинно. Этот факт получен в результате вывода - его нельзя найти непосредственно в программе, но можно вывести, пользуясь содержащимися в ней фактами и правилами. Подобный шаг вывода можно коротко записать

       родитель( боб, пат) ==> предок( боб, пат)

Эту запись можно прочитать так: из родитель( боб, пат) следует предок( боб, пат) на основании правила пр1. Далее, нам известен факт родитель( том, боб). На основании этого факта и выведенного факта предок( боб, пат) можно заключить, что, в силу правила пр2, наше целевое утверждение предок( том, пат) истинно. Весь процесс вывода, состоящий из двух шагов, можно записать так:

       родитель(боб, пат) ==> предок( боб, пат)

        родитель(том, боб)  и   предок( боб, пат)    ==>
               предок( том, пат)

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

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

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

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

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

Существует, однако, корректная и элегантная формулировка отношения предок - корректная в том смысле, что будет работать для предков произвольной отдаленности. Ключевая идея здесь - определить отношение предок через него самого. Рис 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 и пр2 описывают два варианта продолжения рассуждений для пролог-системы. Вначале система пробует предложение, стоящее в программе первым:

       предок( X, Z) :- родитель( X, Z).

Поскольку цель - предок( том, пат), значения переменным должны быть приписаны следующим образом:

       X  =  том,  Z  =   пат

Тогда исходная цель предок( том, пат) заменяется новой целью:

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

Такое действие по замене одной цели на другую на основании некоторого правила показано на рис. 1.9. В программе нет правила, голова которого была бы сопоставима с целью родитель(том, пат), поэтому такая цель оказывается неуспешной. Теперь система делает возврат к исходной цели, чтобы попробовать второй вариант вывода цели верхнего уровня предок( том, пат). То есть, пробуется правило пр2:

       предок( X, Z) :-
               родитель( X, Y),
               предок( Y, Z).

Как и раньше, переменным X и Z приписываются значения:

       X  =  том,   Z   =  пат

В этот момент переменной Y еще не приписано никакого значения. Верхняя цель предок( том, пат) заменяется двумя целями:

       родитель( том, Y),
        предок( Y, пат)

Этот шаг вычислений показан на рис. 1.10, который представляет развитие ситуации, изображенной на рис. 1.9.

Пример отношения предок: (а) 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).

        .  .  .

программы: родственные отношения

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

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

Здесь мы выбрали родитель в качестве имени отношения, том и боб - в качестве аргументов этого отношения. По причинам, которые станут понятны позднее, мы записываем такие имена, как том, начиная со строчной буквы. Все дерево родственных отношений рис. 1.1 описывается следующей пролог-программой:

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

Продолжение процесса вычислений, показанного на рис. 1.9.

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

называются правилами. Есть существенное различие между фактами и правилами. Факт, подобный факту

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

        отпрыск( Y, X) :- родитель( X, Y).
                голова                         тело

Если условие родитель( X, Y) выполняется (оно истинно), то логическим следствием из него является утверждение отпрыск( Y, X).

На приведенном ниже примере проследим, как в действительности правила используются Прологом. Спросим нашу программу, является ли Лиз отпрыском Тома:

       ?  -  отпрыск( лиз, том).

       X  =  том    и   Y  =  лиз

После конкретизации мы получаем частный случай нашего общего правила. Вот он:

       отпрыск( лиз, том) :- родитель( том, лиз).

Условная часть приняла вид:

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

Теперь пролог-система попытается выяснить, выполняется ли это условие (является ли оно истинным). Для этого исходная цель

        отпрыск( лиз, том)

заменяется подцелью

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

Эта (новая) цель достигается тривиально, поскольку такой факт можно найти в нашей программе. Это означает, что утверждение, содержащееся в выводе правила, также истинно, и система ответит на вопрос yes (да).

Добавим теперь в нашу программу-пример еще несколько родственных отношений. Определение отношения мать может быть основано на следующем логическом утверждении:

        Для всех X и Y
                X является матерью Y, если
                X является родителем Y и
                Х - женщина.

На Пролог это переводится в виде такого правила:

        мать( X, Y) :- родитель( X, Y), женщина( X).

Запятая между двумя условиями указывает ка конъюнкцию условий. Это означает, что они должны быть выполнены оба одновременно.

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

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

в постановке вопросов, касающихся этих

и такое определение? Сможете ли

используя программу, приведенную на рис.