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

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

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

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

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

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

Расширение программыпримера с помощью правил

1. 2.    Расширение программы-примера с помощью правил

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

        женщина( пам).
        мужчина( том).
        мужчина( боб).

        женщина( лиз).
        женщина( пат).
        женщина( энн).
        мужчина( джим).

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

        пол( пам, женский).
        пол( том, мужской).
        пол( боб, мужской).
        .  .  .

В качестве дальнейшего расширения нашей программы-примера давайте введем отношение отпрыск, которое обратно отношению родитель. Можно было бы определить отпрыск тем же способом, что и родитель, т.е. представив список простых фактов наличия этого отношения для конкретных пар объектов, таких, что один является отпрыском другого. Например:

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

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

        Для всех X и Y
                Y является отпрыском X, если
                X является родителем Y.

Эта формулировка уже близка к формализму, принятому в Прологе. Вот соответствующее прологовское предложение, имеющее тот же смысл:

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

Это предложение можно прочитать еще и так:

        Для всех X и Y,
                если X - родитель Y, то
                Y - отпрыск X.

Такие предложения Пролога, как

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

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

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

это нечто такое, что всегда, безусловно истинно. Напротив, правила описывают утверждения, которые могут быть истинными, только если выполнено некоторое условие. Поэтому можно сказать, что правила имеют условную часть (правая половина правила) и часть вывода (левая половина правила).

Вывод называют также головой предложения, а условную часть - его телом. Например:

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

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

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

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

В программе нет фактов об отпрысках, поэтому единственный способ ответить на такой вопрос - это применить правило о них. Правило универсально в том смысле, что оно применимо к любым объектам X и Y, следовательно, его можно применить и к таким конкретным объектам, как лиз и том. Чтобы это сделать, нужно вместо Y подставить в него лиз, а вместо X - том. В этом случае мы будем говорить, что переменные X и Y конкретизируются:

       X  =  том    и   Y  =  лиз

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Декларативный и процедурный смысл программ

1. 5.    Декларативный и процедурный смысл программ

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

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

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

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

Литература

Литература

Различные реализации Пролога используют разные синтаксические соглашения. В данной книге мы применяем так называемый Эдинбургский синтаксис (его называют также синтаксисом DEC-10, поскольку он принят в известной реализации Пролога для машины DEC-10; см. Pereira и др. 1978), он используется во многих популярных пролог-системах, таких как Quintus Prolog, Poplog, CProlog, Arity/ Prolog, Prolog-2 и т.д.

Bowen D. L. (1981). DECsystem-10 Prolog User's Manual. University of Edinburgh: Department of Artificial Intelligence.

Mellish С. and Hardy S. (1984). Integrating Prolog in the POPLOG environment. Implementations of Prolog (J. A. Campbell, ed.). Ellis Horwood.

Pereira F. (1982). C-Prolog User's Manual. University of Edinburgh: Department of Computer-Aided Architectural Design.

Pereira L. M., Pereira F., Warren D. H. D. (1978). User's Guide to DECsystem-10 Prolog. University of Edinburgh: Department of Artificial Intelligence.

Quintus Prolog User's Guide and Reference Manual. Palo Alto: Quintus Computer System Inc. (1985).

The Arity/Prolog Programming Language. Concord, Massachusetts: Arity Corporation (1986).

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

Резюме

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

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

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

Рисунок 1. 1.  Дерево родственных отношений.

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

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

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

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

        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. 2.   Отношение родительродителя, выраженное через композицию двух отношений родитель.

Наш составной вопрос можно интерпретировать и так: "Найти X и Y, удовлетворяющие следующим двум требованиям":

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

Если мы поменяем порядок этих двух требований, то логический смысл останется прежним:

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

Этот вопрос можно задать нашей пролог-системе и в такой форме:

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

При этом результат будет тем же. Таким же образом можно спросить: "Кто внуки Тома?"

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

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

        X  =  боб
        Y  =  энн;

        X  =  боб
        Y  =  пат

Следующим вопросом мог бы быть такой: "Есть ли у Энн и Пат общий родитель?" Его тоже можно выразить в два этапа:

        (1)    Какой X является родителем Энн?
        (2)    Является ли (тот же) X родителем Пат?

Соответствующий запрос к пролог-системе будет тогда выглядеть так:

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

Ответ:

        X  =  боб

Наша программа-пример помогла проиллюстрировать некоторые важные моменты: На Прологе легко определить отношение, подобное отношению родитель, указав n-ку объектов, для которых это отношение выполняется. Пользователь может легко задавать пролог-системе вопросы, касающиеся отношений, определенных в программе. Пролог-программа состоит из предложений. Каждое предложение заканчивается точкой. Аргументы отношения могут быть (среди прочего): конкретными объектами, или константами (такими, как том и энн), или абстрактными объектами, такими, как X и Y. Объекты первого типа называются атомами. Объекты второго типа - переменными. Вопросы к системе состоят из одного или более целевых утверждений (или кратко целей). Последовательность целей, такая как

        родитель( X, энн), родитель( X, пат)

означает конъюнкцию этих целевых утверждений:

        X  -  родитель Энн   и
        X  -  родитель Пат.

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

Графы отношений родительродителя мать и отпрыск определенных через другие отношения

Рисунок 1. 3.  Графы отношений родительродителя, мать и отпрыск,
определенных через другие отношения.

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

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

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

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

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

    Для любых X и Y
         X является сестрой Y, если
         (1)        у X и Y есть общий родитель, и
         (2)        X - женщина.

Определение отношения сестра

Рисунок 1. 4.  Определение отношения сестра.

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

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

Обратите внимание на способ, с помощью которого выражается требование "у X и Y есть общий родитель". Была использована следующая логическая формулировка: "некоторый Z должен быть родителем X и этот же самый Z должен быть родителем Y". По-другому, менее красиво, можно было бы сказать так: "Z1 - родитель X, Z2 - родитель Y и Z1 равен Z2".

Теперь можно спросить:

       ?-  сестра( энн, пат).

Как и ожидается, ответ будет "yes" (да) (см. Рисунок 1.1). Мы могли бы заключить отсюда, что определенное нами отношение сестра работает правильно. Тем не менее в нашей программе есть маленькое упущение, которое обнаружится, если задать вопрос: "Кто является сестрой Пат?"

       ?-  сестра( X, пат).

Система найдет два ответа, один из которых может показаться неожиданным:

        X  =  энн;
        X  =  пат

Получается, что Пат - сестра себе самой?! Наверное, когда мы определяли отношение сестра, мы не имели этого ввиду. Однако ответ Пролога совершенно логичен, поскольку он руководствовался нашим правилом, а это правило ничего не говорит о том, что, если X - сестра Y, то X и Y не должны совпадать. Пролог (с полным правом) считает, что X и Y могут быть одним и тем же объектом и в качестве следствия из этого делает вывод, что любая женщина, имеющая родителя, является сестрой самой себе.

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

       различны( X, Y)

достигается тогда и только тогда, когда X и Y не равны. Усовершенствованное правило для отношения сестра примет тогда следующий вид:

       сестра( X, Y) :-
                родитель( Z, X),
                родители( Z, Y),
                женщина( X),
                различны( X, Y).

Некоторые важные моменты этого раздела: Пролог-программы можно расширять, добавляя в них новые предложения. Прологовские предложения бывают трех типов: факты, правила и вопросы. Факты содержат утверждения, которые являются всегда, безусловно верными. Правила содержат утверждения, истинность которых зависит от некоторых условий. С помощью вопросов пользователь может спрашивать систему о том, какие утверждения являются истинными. Предложения Пролога состоят из головы и тела. Тело - это список целей, разделенных запятыми. Запятая понимается как конъюнкция. Факты - это предложения, имеющие пустое тело. Вопросы имеют только тело. Правила имеют голову и (непустое) тело. По ходу вычислений вместо переменной может быть подставлен другой объект. Мы говорим в этом случае, что переменная конкретизирована. Предполагается, что на переменные действует квантор всеобщности, читаемый как "для всех...". Однако для переменных, появляющихся только в теле, возможны и другие формулировки. Например,

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

можно прочитать двумя способами:

(а)        Для всех X и Y,
            если X - отец Y, то
            X имеет ребенка.

(б)        Для всех X,
            X имеет ребенка, если
            существует некоторый Y, такой, что
            X - родитель Y.

Пример отношения предок (а) X ближайший предок Z; (b) X отдаленный предок Z

Рисунок 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).

        .  .  .

Пары предокпотомок разделенных разным числом поколений

Рисунок 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. 8.   Программа о родственных отношениях.

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

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

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

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

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

Первый шаг вычислений Верхняя цель истинна если истинна нижняя

Рисунок 1. 9.  Первый шаг вычислений. Верхняя цель истинна, если истинна нижняя.

Это правила, входящие в отношение предок. Будем говорить, что головы этих правил сопоставимы с целью.

Два предложения пр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.

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

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


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

       предок( боб, пат)

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

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

Голова этого правила должна соответствовать нашей текущей цели предок( боб, пат). Поэтому

       X '  =  боб,   Z '   =  пат

Текущая цель заменяется на

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

Такая цель немедленно достигается, поскольку встречается в программе в качестве факта. Этот шаг завершает вычисление, что графически показано на Рисунок 1.11.

Все шаги достижения цели предок( том пат) Правая ветвь демонстрирует что цель достижима

Рисунок 1. 11.  Все шаги достижения цели предок( том, пат). Правая
ветвь демонстрирует, что цель достижима.

Графическое представление шагов вычисления на Рисунок 1.11 имеет форму дерева. Вершины дерева соответствуют целям или спискам целей, которые требуется достичь. Дуги между вершинами соответствуют применению (альтернативных) предложений программы, которые преобразуют цель, соответствующую одной вершине, в цель, соответствующую другой вершине. Корневая (верхняя) цель достигается тогда, когда находится путь от корня дерева (верхней вершины) к его листу, помеченному меткой "да". Лист помечается меткой "да", если он представляет собой простой факт. Выполнение пролог-программы состоит в поиске таких путей. В процессе такого поиска система может входить и в ветви, приводящие к неуспеху. В тот момент, когда она обнаруживает, что ветвь не приводит к успеху, происходит автоматический возврат к предыдущей вершине, и далее следует попытка применить к ней альтернативное предложение.

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

Упражнение

1. 6.    Рассмотрим другой вариант отношения предок:
    предок( X, Z) :-
           родитель( X, Z).
    предок( X, Z) :-
           родитель( Y, Z).
           предок( X, Y).
Верно ли и такое определение? Сможете ли Вы изменить диаграмму на Рисунок 1.7 таким образом, чтобы она соответствовала новому определению?
Посмотреть ответ

Упражнение

1. 7.    Постарайтесь понять, как пролог-система, используя программу, приведенную на Рисунок 1.8, выводит ответы на указанные ниже вопросы. Попытайтесь нарисовать соответствующие диаграммы вывода по типу тех, что изображены на Рисунок 1.9 -1.11. Будут ли встречаться возвраты при выводе ответов на какие-либо из этих вопросов?
    (a)        ?-   родитель( пам, боб).
    (b)        ?-  мать( пам, боб).
    (с)        ?-   родительродителя( пам, энн).
    (d)        ?-   родительродителя( боб, джим).
Посмотреть ответ

Сформулируйте на Прологе следующие вопросы

Упражнения

1. 1.    Считая, что отношение родитель определено так же, как и раньше в данном разделе (см. Рисунок 1.1), найдите, какими будут ответы пролог-системы на следующие вопросы:
        (a)        ?   -  родитель ( джим, X).
        (b)        ?   -  родитель( X, джим).
        (c)        ?   -  родитель( пам,Х), родитель( Х, пат).
        (d)        ?   -  родитель( пам, X), родитель( Х, Y),
                        родитель( Y, джим).
Посмотреть ответ
1. 2.    Сформулируйте на Прологе следующие вопросы об отношении родитель:
        (a)        Кто родитель Пат?
        (b)        Есть ли у Лиз ребенок?
        (c)        Кто является родителем родителя Пат?
Посмотреть ответ

Упражнения

1. 3.    Оттранслируйте следующие утверждения в правила на Прологе:
(a)    Всякий, кто имеет ребенка, - счастлив (введите одноаргументное отношение счастлив).
(b)    Всякий X, имеющий ребенка, у которого есть сестра, имеет двух детей (введите новое отношение иметьдвухдетей).
Посмотреть ответ
1. 4.    Определите отношение внук, используя отношение родитель. Указание: оно будет похоже на отношение родительродителя (см. Рисунок 1.3).
Посмотреть ответ
1. 5.    Определите отношение тетя( X, Y) через отношение родитель и сестра. Для облегчения работы можно сначала изобразить отношение тетя в виде диаграммы по типу тех, что изображены на Рисунок 1.3.
Посмотреть ответ

Атомы и числа

2. 1. 1.    Атомы и числа

В гл. 1 мы уже видели несколько простых примеров атомов и переменных. Вообще же они могут принимать более сложные формы, а именно представлять собой цепочки следующих символов: прописные буквы А, В, ..., Z строчные буквы а, b, ..., z цифры 0, 1, 2, ..., 9 специальные символы, такие как
        +  -  *  /   =  :  .  &  _  ~

Атомы можно создавать тремя способами:

(1)    из цепочки букв, цифр и символа подчеркивания _, начиная такую цепочку со строчной буквы:

       анна
        nil
        х25
        х_25
        х_25AB
        х_
        х__у
        альфа_бета_процедура
        мисс_Джонс
        сара_джонс

(2)    из специальных символов:

       <--->
        ======>
        ...
         .
        ...
        : : =

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

(3)    из цепочки символов, заключенной в одинарные кавычки. Это удобно, если мы хотим, например, иметь атом, начинающийся с прописной буквы. Заключая его в кавычки, мы делаем его отличным от переменной:

        'Том'
        ' Южная_Америка'
        'Сара Джонс'

Числа в Прологе бывают целыми и вещественными. Синтаксис целых чисел прост, как это видно из следующих примеров: 1, 1313, 0, -97. Не все целые числа могут быть представлены в машине, поэтому диапазон целых чисел ограничен интервалом между некоторыми минимальным и максимальным числами, определяемыми конкретной реализацией Пролога. Обычно реализация допускает диапазон хотя бы от -16 383 до 16 383, а часто, и значительно более широкий.

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

Кроме отсутствия необходимости в использовании вещественных чисел в обычных применениях Пролога, существует и другая причина избегать их. Мы всегда стремимся поддерживать наши программы в таком виде, чтобы их смысл был предельно ясен. Введение вещественных чисел в некоторой степени нарушает эту ясность из-за ошибок вычислений, связанных с округлением во время выполнения арифметических действий. Например, результатом вычисления выражения 10000 + 0.0001 - 10000 может оказаться 0 вместо правильного значения 0.0001.

Переменные

2. 1. 2.    Переменные

Переменные - это цепочки, состоящие из букв, цифр и символов подчеркивания. Они начинаются с прописной буквы или с символа подчеркивания:

        Х
        Результат
        Объект2
        Список_участников
        СписокПокупок
        _х23
        _23

Если переменная встречается в предложения только один раз, то нет необходимости изобретать ей имя. Можно использовать так называемую "анонимную" переменную, которая записывается в виде одного символа подчеркивания. Рассмотрим, например, следующее правило:

Структуры

2. 1. 3.    Структуры

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

       дата( 1, май, 1983)

(см. Рисунок 2.2).

Все компоненты в данном примере являются константами (две компоненты - целые числа и одна - атом). Компоненты могут быть также переменными или структурами. Произвольный день в мае можно представить структурой:

       дата( День, май, 1983)

Заметим, что День является переменной и ей можно приписать произвольное значение на некотором более позднем этапе вычислений.

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

Синтаксически все объекты данных в Прологе представляют собой термы. Например,

       май

и

       дата( 1, май, 1983)

суть термы.

Все структурные объекты можно изображать в виде деревьев (пример см. на Рисунок 2.2). Корнем дерева служит функтор, ветвями, выходящими из него, - компоненты. Если некоторая компонента тоже является структурой, тогда ей соответствует поддерево в дереве, изображающем весь структурный объект.

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

       точка                            для точек
       отрезок                         для отрезков и
       треугольник                для треугольников.

Объекты данных

2. 1.    Объекты данных

На Рисунок 2.1 приведена классификация объектов данных Пролога. Пролог-система распознает тип объекта по его синтаксической форме в тексте программы. Это возможно благодаря тому, что синтаксис Пролога

Сопоставление

2. 2.    Сопоставление

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

Пусть даны два терма. Будем говорить, что они сопоставимы, если:

(1)    они идентичны или

(2)    переменным в обоих термах можно приписать в качестве значений объекты (т.е. конкретизировать их) таким образом, чтобы после подстановки этих объектов в термы вместо переменных, последние стали идентичными.

Например, термы дата( Д, М, 1983) и дата( Д1, май, Y1) сопоставимы. Одной из конкретизации, которая делает эти термы идентичными, является следующая: Д   заменяется на   Д1 М   заменяется на   май Y1   заменяется на   1983

Более компактно такая подстановка записывается в привычной форме, т. е. в той, в которой пролог-система выводит результаты:

       Д  =  Д1
       М  =  май
       Y1  =  1983

С другой стороны, дата( Д, М, 1983) и дата( Д1, Ml, 1944) не сопоставимы, как и термы дата( X, Y, Z) и точка( X, Y, Z).

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

Рассмотрим еще раз сопоставление двух дат. Запрос на проведение такой операции можно передать системе, использовав оператор '=':

       ?-  дата( Д, М, 1983)  =   дата( Д1, май, Y1).

Мы уже упоминали конкретизацию Д = Д1, М = май, Y1 = 1983, на которой достигается сопоставление. Существуют, однако, и другие конкретизации, делающие оба терма идентичными. Вот две из них:

       Д  =  1
       Д1  =  1
       М  =  май
       Y1  =  1983

       Д  =  третий
       Д1  =  третий
       М  =  май
       Y1  =  1983

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

       ?-  дата( Д, М, 1983)  =   дата( Д1, май, Y1),
             дата( Д, М, 1983)  =  дата( 15, М, Y).

Для достижения первой цели система припишет переменным такие значения:

        Д  = Д1
        М  =  май
        Y1  =  1983

После достижения второй цели, значения переменных станут более конкретными, а именно:

        Д  =  15
        Д1  =  15
        М  =  май
        Y1  =  1983
        Y  =  1983

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

Общие правила выяснения, сопоставимы ли два терма S и Т, таковы:

line();

(1)    Если S и Т - константы, то S и Т сопоставимы, только если они являются одним и тем же объектом.

(2)    Если S - переменная, а Т - произвольный объект, то они сопоставимы, и S приписывается значение Т. Наоборот, если Т -переменная, а S -произвольный объект, то Т приписывается значение S.

(3)    Если S и Т - структуры, то они сопоставимы, только если

(а)    S и Т имеют одинаковый главный функтор
        и
(б)    все их соответствующие компоненты сопоставимы.

        Результирующая конкретизация определяется сопоставлением компонент.

line();

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

        треугольник  =   треугольник,
        точка( 1, 1)  =  X,
        А  =  точка( 4, Y),
        точка( 2, 3)  =  точка( 2, Z).

Весь процесс сопоставления успешен, поскольку все сопоставления в этой последовательности успешны. Результирующая конкретизация такова:

        Х  =  точка( 1, 1)
        А  =  точка( 4, Y)
        Z  =  3

В приведенном ниже примере показано, как сопоставление само по себе можно использовать для содержательных вычислений. Давайте вернемся к простым геометрическим объектам с Рисунок 2.4 и напишем фрагмент программы для распознавания горизонтальных и вертикальных отрезков. "Вертикальность" - это свойство отрезка, поэтому его можно формализовать в Прологе в виде унарного отношения.

Декларативный смысл прологпрограмм

2. 3.    Декларативный смысл пролог-программ

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

Рассмотрим предложение

        Р :- Q,  R.

где Р, Q и R имеют синтаксис термов. Приведем некоторые способы декларативной интерпретации этого предложения:

        Р  -  истинно, если  Q  и  R   истинны.
        Из  Q  и  R  следует  Р.

А вот два варианта его "процедурного" прочтения:

        Чтобы решить задачу  Р,  сначала реши подзадачу
        Q,  а затем - подзадачу  R.
        Чтобы достичь  Р,  сначала достигни  Q,  а затем  R.

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

Формализуем теперь декларативный смысл.

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

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

Приведем два варианта этого предложения:

        имеетребенка( А) :- родитель( А, В).
        имеетребенка( X1) :- родитель( X1, Х2).

Примеры конкретизаций этого же предложения:

        имеетребенка( питер) :- родитель( питер, Z).
        имеетребенка( барри) :- родитель( барри,
                                                      маленькая( каролина) ).

Пусть дана некоторая программа и цель G, тогда, в соответствии с декларативной семантикой, можно утверждать, что

line();

Цель  G  истинна (т.е. достижима или логически следует из программы) тогда и только тогда, когда

(1)    в программе существует предложение  С, такое, что

(2)    существует такая его  (С)   конкретизация  I,  что

        (a)    голова   I  совпадает с  G  и
        (б)    все цели в теле  I  истинны.

line();

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

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

        Р   :-   Q;  R.

читается так:  Р  -  истинно, если истинно   Q   или истинно  R.  То есть смысл такого предложения тот же, что и смысл следующей пары предложений:

        Р   :-   Q.
        Р   :-   R.

Запятая связывает (цели) сильнее, чем точка с запятой. Таким образом, предложение

        Р   :-   Q,  R;  S,  Т,   U.

понимается как:

        Р   :-   ( Q,  R);  (S,   Т,  U).

и имеет тот же смысл, что и два предложения

        Р   :-   Q,  R.
        Р   :-   S,  T,  U.

Процедурная семантика

2. 4.    Процедурная семантика

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

Назовем эту процедуру вычислить. Как показано на Рисунок 2.9, входом и выходом этой процедуры являются:

    входом - программа и список целей,
    выходом - признак успех/неуспех и подстановка переменных.

Пример обезьяна и банан

2. 5.    Пример: обезьяна и банан

Задача об обезьяне и банане часто используется в качестве простого примера задачи из области искуственного интеллекта. Наша пролог-программа, способная ее решить, показывает, как механизмы сопоставления и автоматических возвратов могут применяться для подобных целей. Мы сначала составим программу, не принимая во внимание процедурную семантику, а затем детально изучим ее процедурное поведение. Программа будет компактной и наглядной.

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

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

(1)        Обезьяна у двери.
(2)        Обезьяна на полу.
(3)        Ящик у окна.
(4)        Обезьяна не имеет банана.

Удобно объединить все эти четыре информационных фрагмента в один структурный объект. Давайте в качестве такого объединяющего функтора выберем слово "состояние". На Рисунок 2.12 в виде структурного объекта изображено исходное состояние.

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

        состояние( -, -, -, имеет)

Второе, каковы разрешенные ходы, переводящие мир из одного состояния в другое? Существуют четыре типа ходов:

(1)        схватить банан,
(2)        залезть на ящик,
(3)        подвинуть ящик,
(4)        перейти в другое место.

Опасность бесконечного цикла

2. 6. 1.    Опасность бесконечного цикла

Рассмотрим следующее предложение:

        р   :-   р.

В нем говорится: "р истинно, если р истинно". С точки зрения декларативного смысла это совершенно корректно, однако в процедурном смысле оно бесполезно. Более того, для пролог-системы такое предложение может породить серьезную проблему. Рассмотрим вопрос:

        ?-  р.

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

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

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

        ?- можетзавладеть( состояние( удвери, наполу, уокна, неимеет) ).

протекал бы на этот раз так. Первые четыре списка целей (с соответствующим образом переименованными переменными) остались бы такими же, как и раньше:

(1)    можетзавладеть( состояние( удвери, наполу, уокна, неимеет) ).

Применение второго предложения из можетзавладеть ("может2") породило бы

(2)    ход( состояние( удвери, наполу, уокна, неимеет), М', S2'),
                можетзавладеть( S2')

С помощью хода перейти( уокна, Р2') получилось бы

(3)    можетзавладеть( состояние( Р2', наполу, уокна, неимеет) )

Повторное использование предложения "может2" превратило бы список целей в

(4)    ход( состояние(Р2', наполу, уокна, неимеет), М'', S2''),
                можетзавладеть( S2")

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

        S2" = состояние( Р2", наполу, уокна, неимеет).

Поэтому список целей стал бы таким:

(5)    можетзавладеть( состояние( Р2'', наполу, уокна, неимеет) )

Применение предложения "может2" дало бы

(6)    ход( cocтояниe( P2", наполу, yoкнa, неимeeт), M" ', S2'' '),
                можетзавладеть( S2" ')

Снова первый было бы попробовано "перейти" и получилось бы

(7)    можетзавладеть( состояние( Р2" ', наполу, уокна, неимеет) )

Сравним теперь цели  (3),  (5)  и  (7).   Они похожи и отличаются лишь одной переменной, которая по очереди имела имена  Р',   Р''  и  P" '.  Как мы знаем, успешность цели не зависит от конкретных имен переменных в ней. Это означает, что, начиная со списка целей (3), процесс вычислений никуда не продвинулся. Фактически мы замечаем, что по очереди многократно используются одни и те же два предложения: "может2" и "перейти". Обезьяна перемещается, даже не пытаясь воспользоваться ящиком. Поскольку продвижения нет, такая ситуация продолжалась бы (теоретически) бесконечно: пролог-система не сумела бы осознать, что работать в этой направлении нет смысла.

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

Теперь уместно спросить: "Не можем ли мы внести какое-либо более существенное изменение в нашу программу, так чтобы полностью исключить опасность зацикливания? Или же нам всегда придется рассчитывать на удачный порядок предложений и целей?" Как оказывается, программы, в особенности большие, были бы чересчур ненадежными, если бы можно было рассчитывать лишь на некоторый удачный порядок. Существует несколько других методов, позволяющих избежать зацикливания и являющихся более общими и надежными, чем сам по себе метод упорядочивания. Такие методы будут систематически использоваться дальше в книге, в особенности в тех главах, в которых пойдет речь о нахождении путей (в графах), о решения интеллектуальных задач и о переборе.

Варианты программы полученые путем переупорядочивания предложений и целей

2. 6. 2.    Варианты программы, полученые путем переупорядочивания предложений и целей

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

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

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

Проанализируем некоторые варианты этой программы. Ясно, что все варианты будут иметь одинаковую декларативную семантику, но разные процедурные семантики.

В соответствии с декларативной семантикой Пролога мы можем, не меняя декларативного смысла, изменить

(1)        порядок предложений в программе и

(2)        порядок целей в телах предложений.

Процедура предок состоит из двух предложений, и одно из них содержит в своем теле две цели. Возможны, поэтому, четыре варианта данной программы, все с одинаковым декларативным смыслом. Эти четыре варианта можно получить, если

(1)        поменять местами оба предложения и
(2)        поменять местами цели в каждом из этих двух последовательностей предложений.

Соответствующие процедуры, названные пред1, пред2, пред3 и пред4, показаны на Рисунок 2.16.

Есть существенная разница в поведении этих четырех декларативно эквивалентных процедур. Чтобы это продемонстрировать, будем считать, отношение родитель определенным так, как показано на Рисунок 1.1 гл. 1. и посмотрим, что произойдет, если мы спросим, является ли Том предком Пат, используя все четыре варианта отношения предок:

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

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

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

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

line();

%  Четыре версии программы предок
%  Исходная версия

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

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

%  Вариант  а:  изменение порядка предложений в исходной версии

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

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

%  Вариант  b:  изменение порядка целей во втором предложении
%  исходной версии

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

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

%  Вариант  с:  изменение порядка предложений и целей в исходной
%  версии

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

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

line();

Сочетание декларативного и процедурного подходов

2. 6. 3.    Сочетание декларативного и процедурного подходов

В предыдущем разделе было показано, что порядок целей и предложений имеет существенное значение. Более того, существуют программы, которые верны в декларативном смысле, но на практике не работают. Такое противоречие между декларативным и процедурным смыслами может вызвать недовольство. Кто-нибудь спросит: "А почему вообще не забыть о декларативном смысле?" Такое пожелание становится особенно сильным, когда рассматриваются предложения типа:

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

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

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

Порядок предложений и целей

2. 6.    Порядок предложений и целей

Замечания о взаимосвязи между Прологом и логикой

2. 7.    Замечания о взаимосвязи между Прологом и логикой

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

Синтаксис Пролога - это синтаксис предложений логики предикатов первого порядка, записанных в так называемой форме предложений (форме, при которой кванторы не выписываются явно), а точнее, в виде частного случая таких предложений - в виде формул Хорна (предложений, имеющих самое большее один положительный литерал). Клоксин и Меллиш (1981 г.) приводят пролог-программу, которая преобразует предложения исчисления предикатов первого порядка в форму предложений. Процедурный смысл Пролога основывается на принципе резолюций, применяющемся для автоматического доказательства теорем, который был предложен Робинсоном в его классической статье (1965 г.). В Прологе используется особая стратегия доказательства теоремы методом резолюций, носящая название SLD. Введение в исчисление предикатов первого порядка и доказательство теорем, основанное на методе резолюций, можно найти у Нильсона (1981 г.). Математические вопросы, касающиеся свойств процедурной семантики Пролога в их связи с логикой, проанализированы Ллойдом (1984 г.).

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

Имеетребенка( X) родитель( X _ )

        имеетребенка( X) :- родитель( X, _ ).

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

Имеетребенка( X) родитель( X Y)

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

Это правило гласит: "Для всех X,  Х имеет ребенка, если X является родителем некоторого Y". Здесь мы определяем свойство имеетребенка таким образом, что оно не зависит от имени ребенка. Следовательно, это как раз тот случай, когда уместно использовать анонимную переменную. Поэтому вышеприведенное правило можно переписать так:

Литература

Литература

Clocksin W. F. and Mellish С. S. (1981). Programming in Prolog. Springer-Verlag. [Имеется перевод: Клоксин У., Меллиш К. Программирование на языке Пролог. - М.: Мир, 1987.]

Lloyd J. W. (1984). Foundations of Logic Programming. Springer-Verlag.

Nilsson N. J. (1981). Principies of Artificial Intelligence. Tioga; Springer-Verlag.

Robinson A. J. (1965). A machine-oriented logic based on the resolution principle. JACM 12: 23-41. [Имеется перевод: Робинсон Дж. Машинно-ориентированная логика, основанная на принципе резолюции.- В кн. Кибернетический сборник, вып. 7, 1970, с. 194-218.]

Некто_имеет_ребенка родитель( _ _ )

        некто_имеет_ребенка :- родитель( _, _ ).

Это предложение эквивалентно следующему:

Некто_имеет_ребенка родитель( X Y)

        некто_имеет_ребенка :- родитель( X, Y).

Однако оно имеет совершенно другой смысл, нежели

       некто_имеет_ребенка :- родитель( X, X).

Если анонимная переменная встречается в вопросе, то ее значение не выводится при ответе системы на этот вопрос. Если нас интересуют люди, имеющие детей, но не имена этих детей, мы можем просто спросить:

Помогает сформулировать это отношение Отрезок

Рисунок 2.8 помогает сформулировать это отношение. Отрезок

К настоящему моменту мы изучили

Резюме

К настоящему моменту мы изучили нечто вроде базового Пролога, который называют еще "чистый Пролог". Он "чист", потому что довольно точно соответствует формальной логике. Расширения, преследующие цель приспособить язык к некоторым практическим нуждам, будут изучены дальше (гл. 3, 5, 6. 7). Важными моментами данной главы являются следующие: Простые объекты в Прологе - это атомы, переменные и числа. Структурные объекты, или структуры, используются для представления объектов, которые состоят из нескольких компонент. Структуры строятся посредством функторов. Каждый функтор определяется своими именем и арностью. Тип объекта распознается исключительно по его синтаксической форме. Область известности (лексический диапазон) переменных - одно предложение. Поэтому одно и то же имя в двух предложениях обозначает две разные переменные. Структуры могут быть естественным образом изображены в виде деревьев. Пролог можно рассматривать как язык обработки деревьев. Операция сопоставление берет два терма и пытается сделать их идентичными, подбирая соответствующую конкретизацию переменных в обоих термах. Сопоставление, если оно завершается успешно, в качестве результата выдает наиболее общую конкретизацию переменных. Декларативная семантика Пролога определяет, является ли целевое утверждение истинным, исходя из данной программы, и если оно истинно, то для какой конкретизации переменных. Запятая между целями означает их конъюнкцию. Точка с запятой между целями означает их дизъюнкцию. Процедурная семантика Пролога - это процедура достижения списка целей в контексте данной программы. Процедура выдает истинность или ложность списка целей и соответствующую конкретизацию переменных. Процедура осуществляет автоматический возврат для перебора различных вариантов. Декларативный смысл программ на "чистом Прологе" не зависит от порядка предложений и от порядка целей в предложениях. Процедурный смысл существенно зависит от порядка целей и предложений. Поэтому порядок может повлиять на эффективность программы; неудачный порядок может даже привести к бесконечным рекурсивным вызовам. Имея декларативно правильную программу, можно улучшить ее эффективность путем изменения порядка предложений и целей при сохранении ее декларативной правильности. Переупорядочивание - один из методов предотвращения зацикливания. Кроме переупорядочивания существуют и другие, более общие методы предотвращения зацикливания, способствующие получению процедурно правильных программ. В данной главе обсуждались следующие понятия:

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

Обьекты данных Пролога

Рисунок 2. 1.  Обьекты данных Пролога.

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

Дата пример структурного

Рисунок 2. 2.  Дата - пример структурного объекта:
(а)    его представление в виде дерева;     (б)    запись на Прологе.

Тогда объекты, приведенные на Рисунок 2.3, можно представить следующими прологовскими термами:

       Р1 = точка( 1, 1)
            P2 = точка( 2, 3)

            S = отрезок( P1, P2) =
                    отрезок( точка( 1, 1), точка( 2, 3) )

            Т = треугольник( точка( 4, 2), точка( 6, 4),
                                             точка( 7, 1) )

Простые геометрические объекты

Рисунок 2. 3.  Простые геометрические объекты.

Соответствующее представление этих объектов в виде деревьев приводится на Рисунок 2.4. Функтор, служащий

Представление объектов с Рисунок 2 3 в виде деревьев

Рисунок 2. 4.  Представление объектов с Рисунок 2.3  в виде деревьев.

корнем дерева, называется главным функтором терма.

Если бы в такой же программе фигурировали точки трехмерного пространства, то можно было бы для их представления использовать другой функтор, скажем точка3:

       точка3( X, Y, Z)

Можно, однако, воспользоваться одним и тем же именем точка одновременно и для точек двумерного и трехмерного пространств и написать, например, так:

       точка( XI, Y1)  и   точка ( X, Y, Z)

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

(1)    именем, синтаксис которого совпадает с синтаксисом атомов;

(2)    арностью - т. е. числом аргументов.

Как уже объяснялось, все структурные объекты в Прологе - это деревья, представленные в программе термами. Рассмотрим еще два примера, чтобы показать, насколько удобно сложные объекты данных представляются с помощью прологовских термов. На Рисунок 2.5 показана древовидная структура, соответствующая арифметическому выражению

       (а + в)*(с - 5)

В соответствии с введенным к настоящему моменту синтаксисом, такое выражение, используя символы *,  +  и  -  в качестве функторов, можно записать следующим образом:

       *( +( а, в), -( с, 5) )

Древовидная структура соответствующая арифметическому выражению (а + w)*(s 5)

Рисунок 2. 5.  Древовидная структура, соответствующая арифметическому
выражению (а + w)*(s - 5).

Это, конечно, совершенно правильный прологовский терм, однако это не та форма, которую нам хотелось бы иметь, при записи арифметических выражений. Хотелось бы применять обычную инфиксную запись, принятую в математике. На самом деле Пролог допускает использование инфиксной нотации, при которой символы *,  +   и  -  записываются как инфиксные операторы. Детали того, как программист может определять свои собственные операторы, мы приведем в гл. 3.

В качестве последнего примера рассмотрим некоторые простые электрические цепи, изображенные на Рисунок 2.6. В правой части рисунка помещены древовидные представления этих цепей. Атомы r1, r2, r3 и r4 - имена резисторов. Функторы пар и посл обозначают соответственно параллельное и последовательное соединение резисторов. Вот соответствующие прологовские термы:

       посл( r1, r2)
        пар( r1, r2)
        паp( rl, пap( r2, r3) )
        пар( r1, посл( пар( r2, r3), r4) )

 

Некоторые простые

Рисунок 2. 6.  Некоторые простые электрические цепи и их представление: (а) последовательное соединение резисторов rl и r2; (b) параллельное соединение двух резисторов; (с) параллельное соединение трех резисторов; (d) параллельное соединение r1 и еще одной цепи.

Сопоставление треугольник((

Рисунок   2. 7.    Сопоставление треугольник(( точка( 1, 1), А, точка( 2, 3)) = треугольник( Х, точка( 4, Y),
точка( 2, Z))

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

        верт( отр( точка( Х, Y), точка( Х, Y1) ) ).
        гор( отр( точка( Х, Y), точка( Х1, Y) ) ).

С этой программой возможен такой диалог:

        ?-  верт( отр( точка( 1, 1), точка( 1, 2) ) ).
        да

        ?-  верт( отр( точка( 1, 1), точка( 2, Y) ) ).
        нет

        ?-  гор( отр( точка( 1, 1), точка( 2, Y) ) ).
        Y  =  1

На первый вопрос система ответила "да", потому. что цель, поставленная в вопросе, сопоставима с одним из фактов программы. Для второго вопроса сопоставимых фактов не нашлось. Во время ответа на третий вопрос при сопоставлении с фактом о горизонтальных отрезках Y получил значение 1.

Пример вертикальных и горизонтальных отрезков прямых

Рисунок 2. 8.  Пример вертикальных и горизонтальных отрезков прямых.

Сформулируем более общий вопрос к программе: "Существуют ли какие-либо вертикальные отрезки, начало которых лежит в точке (2,3)?"

        ?-  верт( отр( точка( 2, 3), Р) ).
        Р  =  точка( 2, Y)

Такой ответ означает: "Да, это любой отрезок, с концом в точке (2,Y), т. е. в произвольной точке вертикальной прямой х = 2". Следует заметить, что ответ пролог-системы возможно будет выглядеть не так красиво, как только что описано, а (в зависимости от реализации) приблизительно следующим образом:

        Р  =  точка( 2, _136)

Впрочем, разница здесь чисто внешняя. В данном случае _136 - это неинициализированная переменная. Имя _136 - законное имя прологовской переменной, которое система построила сама во время вычислений. Ей приходится генерировать новые имена, для того чтобы переименовывать введенные пользователем переменные в программе. Это необходимо по двум причинам: первая - одинаковые имена обозначают в разных предложениях разные переменные; и вторая - при последовательном применении одного и того же предложения используется каждый раз его "копия" с новым набором переменных.

Другим содержательным вопросом к нашей программe является следующий: "Существует ли отрезок, который одновременно и горизонтален в вертикален?"

        ?-  верт( S), гор( S).
        S  =  отр( точка( Х, Y), точка( Х, Y) )

Такой ответ пролог-системы следует, понимать так: "да, любой отрезок, выродившийся в точку, обладает как свойством вертикальности, так и свойством горизонтальности одновременно". Этот ответ снова получен лишь из сопоставления. Как и раньше, в ответе вместо Х и Y могут появиться некоторые имена, сгенерированные системой.

Входы и выходы процедуры вычисления списка целей

Рисунок 2. 9.  Входы и выходы процедуры вычисления списка целей.

Смысл двух составляющих выхода такой:

(1)    Признак успех/неуспех принимает значение "да", если цели достижимы, и "нет" - в противном случае. Будем говорить, что "да" сигнализирует об успешном завершении и "нет" - о неуспехе.

(2)    Подстановка переменных порождается только в случае успешного завершения; в случае неуспеха подстановка отсутствует.

line();

ПРОГРАММА

большой( медведь).                % Предложение 1
большой( слон).                       % Предложение 2
маленький( кот).                    % Предложение 3
коричневый ( медведь).        % Предложение 4
черный ( кот).                         % Предложение 5
серый( слон).                           % Предложение 6

темный( Z) :-                           % Предложение 7:
           черный( Z).                   % любой черный
                                                   % объект является темным
темный( Z) :-                           % Предложение 8:
           коричневый( Z).           % Любой коричневый
                                                    % объект является темным

ВОПРОС

?-  темный( X), большой( X)    % Кто одновременно темный
                                                     % и большой?

ШАГИ  ВЫЧИСЛЕНИЯ

(1)    Исходный список целевых утверждений:

            темный( X),  большой( X).

(2)    Просмотр всей программы от начала к концу и поиск предложения, у которого голова сопоставима с первым целевым утверждением

            темный( X).

        Найдена формула 7:

            темный( Z) :- черный( Z).

Замена первого целевого утверждения конкретизированным телом предложения 7 - порождение нового списка целевых утверждений.

            черный( X),  большой( X)

(3)    Просмотр программы для нахождения предложения, сопоставимого с черный( X). Найдено предложение 5: черный ( кот). У этого предложения нет тела, поэтому список целей при соответствующей конкретизации сокращается до

            большой( кот)

(4)    Просмотр программы в поисках цели большой( кот). Ни одно предложение не найдено. Поэтому происходит возврат к шагу (3) и отмена конкретизации Х = кот. Список целей теперь снова

            черный( X),  большой( X)

Продолжение просмотра программы ниже предложения 5. Ни одно предложение не найдено. Поэтому возврат к шагу (2) и продолжение просмотра ниже предложения 7. Найдено предложение (8):

           темный( Z) :- коричневый( Z).

Замена первой цели в списке на коричневый( Х), что дает

           коричневый( X), большой( X)

(5)    Просмотр программы для обнаружения предложения, сопоставимого коричневый( X). Найдено предложение коричневый( медведь). У этого предложения нет тела, поэтому список целей уменьшается до

            большой( медведь)

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

line();

Пример иллюстрирующий

Рисунок 2. 10.  Пример, иллюстрирующий процедурную семантику
      Пролога: шаги вычислений, выполняемых процедурой вычислить.

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

Конкретные операции, выполняемые в процессе вычисления целевых утверждений, показаны на Рисунок 2.10. Возможно, следует изучить этот рисунок прежде, чем знакомиться с последующим общим описанием.

Чтобы вычислить список целевых утверждений

        G1, G2, ..., Gm

процедура вычислить делает следующее:

line(); Если список целей пуст - завершает работу успешно. Если список целей не пуст, продолжает работу, выполняя (описанную далее) операцию 'ПРОСМОТР'. ПРОСМОТР: Просматривает предложения программы от начала к концу до обнаружения первого предложения С, такого, что голова С сопоставима с первой целью G1. Если такого предложения обнаружить не удается, то работа заканчивается неуспехом.

Если С найдено и имеет вид

        Н   :-   B1,  ...,   Вn.

то переменные в С переименовываются, чтобы получить такой вариант С' предложения С, в котором нет общих переменных со списком  G1,   ...,  Gm. Пусть С' - это

        Н'   :-   B1',  ...,   Вn'.

Сопоставляется  G1  с  H';  пусть  S  - результирующая конкретизация переменных.  В списке целей  G1,  G2,  ....  Gm, цель  G1   заменяется на список  В1',  ..,  Вn',   что порождает новый список целей:

        В1',  ...,  Вn', G2,  ...,   Gm

(Заметим, что, если  С  - факт, тогда  n=0,   и в этом случае новый список целей оказывается короче, нежели исходный; такое уменьшение списка целей может в определенных случаях превратить его в пустой, а следовательно, - привести к успешному завершению.)

Переменные в новом списке целей заменяются новыми значениями, как это предписывает конкретизация  S,  что порождает еще один список целей

        В1'',  ....  Вn", G2',   ...,  Gm'
Вычисляет (используя рекурсивно ту же самую процедуру) этот новый список целей. Если его вычисление завершается успешно, то и вычисление исходного списка целей тоже завершается успешно. Если же его вычисление порождает неуспех, тогда новый список целей отбрасывается и происходит возврат к просмотру программы. Этот просмотр продолжается, начиная с предложения, непосредственно следующего за предложением  С   (С  -  предложение, использовавшееся последним) и делается попытка достичь успешного завершения с помощью другого предложения. line();

Более компактная запись этой процедуры в обозначениях, близких к Паскалю, приведена на Рисунок 2.11.

Здесь следует сделать несколько дополнительных замечаний, касающихся процедуры вычислить в том виде, в котором она приводится. Во-первых, в ней явно не указано, как порождается окончательная результирующая конкретизация переменных. Речь идет о конкретизации S, которая приводит к успешному завершению и которая, возможно, уточнялась последующими конкретизациями во время вложенных рекурсивных вызовов вычислить.

line();

procedure вычислить (Прогр, СписокЦелей, Успех)

Входные параметры:

        Прогр:   список предложений
        СписокЦелей:   список целей

Выходной параметр:

        Успех:          истинностное значение; Успех принимает значение
                               истина, если список целевых утверждений
                               (их конъюнкция) истиннен с точки зрения Прогр

Локальные переменные:

        Цель:  цель
        ДругиеЦели:  список целей
        Достигнуты:   истинностное значение
        Сопоставились:   истинностное значение
        Конкрет:   конкретизация переменных
                Н,   Н',  B1,  B1',  ...,  Вn ,  Вn':   цели

Вспомогательные функции:

        пycтой( L):   возвращает истину, если L - пустой список

        голoвa( L):   возвращает первый элемент списка L

        хвост( L):   возвращает остальную часть списка L

        конкат( L1, L2):   создает конкатенацию списков - присоединяет
                список L2 к концу списка L1

        сопоставление( T1, T2, Сопоставились, Конкрет): пытается
                сопоставить термы Т1 и T2; если они сопоставимы, то
                Сопоставились - истина, а Конкрет представляет
                собой конкретизацию переменных

        подставить( Конкрет, Цели): производит подстановку переменных
                в Цели согласно Конкрет

begin
    if пустой( СписокЦелей) then Успех : = истина
    else
        begin
            Цель : = голова( СписокЦелей);
            ДругиеЦели : = хвост( СписокЦелей);
            Достигнута : = ложь;
            while not Достигнута and
                "в программе есть еще предложения" do
                begin
                    Пусть следующее предложение в Прогр есть
                            Н    :-   B1,  ....  Вn.
                    Создать вариант этого предложения
                            Н'    :-   В1',  ....  Вn'.
                    сопоставление( Цель, Н',
                                                    Сопоставились, Конкрет)
                    if Сопоставились then
                        begin
                            НовыеЦели : =
                                конкат( [В1', ..., Вn' ], Другие Цели);
                            НовыеЦели : =
                                подставить( Конкрет, НовыеЦели);
                            вычислить( Прогр, НовыеЦели, Достигнуты)
                        end
                    end;
            Успех : = Достигнуты
        end
end;

line();

Вычисление целевых утверждений Пролога

Рисунок 2. 11.  Вычисление целевых утверждений Пролога.

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

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

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

Исходное состояние

Рисунок 2. 12.  Исходное состояние обезьяньего мира, представленное в виде структурного объекта. Его четыре компоненты суть горизонтальная позиция обезьяны, вертикальная позиция обезьяны, позиция ящика, наличие или отсутствие у обезьяны банана.

Не всякий ход допустим при всех возможных состояниях мира. Например, ход "схватить" допустим, только если обезьяна стоит на ящике прямо под бананом (т.е. в середине комнаты) и еще не имеет банана. Эти правила можно формализовать в Прологе в виде трехместного отношения ход:

        ход( Состояние1, М, Состояние2)

Три аргумента этого отношения определяют ход, следующим образом:

        Состояние1 --------> Состояние2
                                    М

Состояние1 это состояние до хода, М - выполняемый ход, и Состояние2 - состояние после хода.

Ход "схватить", вместе с необходимыми ограничениями на состояние перед этим ходом, можно выразить такой формулой:

ход( состояние( середина, наящике, середина, неимеет),
                                                           % Перед ходом
        схватить,                                 % Ход
        состояние( середина, наящике, середина, имеет) ).
                                                         % После хода

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

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

        ход( состояние( Р1, наполу, В, Н),
                перейти( Р1, Р2),             % Перейти из Р1 в Р2
                состояние( Р2, наполу, В, Н) ).

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

Рекурсивная формулировка отношения можетзавладетъ

Рисунок 2. 13.  Рекурсивная формулировка отношения можетзавладетъ.

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

Два других типа ходов: "подвинуть" и "залезть" - легко определить аналогичным способом.

Главный вопрос, на который должна ответить наша программа, это вопрос: "Может ли обезьяна, находясь в некотором начальном состоянии  S,   завладеть бананом?" Его можно сформулировать в виде предиката

        можетзавладеть( S)

где аргумент  S  -  состояние обезьяньего мира. Программа для можетзавладеть может основываться на двух наблюдениях:

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

        можетзавладеть( состояние( -, -, -, имеет) ).

(2)    В остальных случаях требуется один или более ходов. Обезьяна может завладеть бананом в любом состоянии S1, если для него существует ход из состояния Р1 в некоторое состояние S2, такое, что, попав в него, обезьяна уже сможет завладеть бананом (за нуль или более ходов). Этот принцип показан на Рисунок 2.13. Прологовская формула, соответствующая этому правилу, такова:

        можетзавладеть( S1) :-
                ход( S1, М, S2),
                можетзавладеть( S2).

Теперь мы полностью завершили нашу программу, показанную на Рисунок 2.14.

Формулировка можетзавладеть рекурсивна и совершенно аналогична формулировке отношения предок из гл. 1 (ср. Рисунок 2.13 и 1.7). Этот принцип используется в Прологе повсеместно.

Мы создали нашу программу "непроцедурным" способом. Давайте теперь изучим ее процедурное поведение, рассмотрев следующий вопрос к программе:

        ?-   можетзавладеть( состояние( удвери, наполу, уокна, неимеет) ).

Ответом пролог-системы будет "да". Процесс, выполняемый ею при этом, обрабатывает, в соответствии с процедурной семантикой Пролога, последовательность списков целей. Для этого требуется некоторый перебор ходов, для отыскания верного из нескольких альтернативных. В некоторых точках при таком переборе будет сделан неверный ход, ведущий в тупиковую ветвь процесса вычислений. На этом этапе автоматический возврат позволит исправить положение. На Рисунок 2.15 изображен процесс перебора.

line();

% Разрешенные ходы

ход( состояние( середина, на ящике, середина, неимеет),
        схватить,                                 % Схватить банан
        состояние( середина, наящике, середина, имеет)).

ход( состояние( Р, наполу, Р, Н),
        залезть,                                     % Залезть на ящик
        состояние( Р, наящике, Р, Н) ).

ход( состояние( Р1, наполу, Р1, Н),
        подвинуть( Р1, Р2),             % Подвинуть ящик с Р1 на Р2
        состояние( Р2, наполу, Р2, Н) ).

ход( состояние( Р1, наполу, В, Н),
        перейти( Р1, Р2),                     % Перейти с Р1 на Р2
        состояние( Р2, наполу, В, Н) ).

    % можетзавладеть(Состояние): обезьяна может завладеть
    % бананом, находясь в состоянии Состояние

можетзавладеть( состояние( -, -, -, имеет) ).

    % может 1:  обезьяна уже его имеет

можетзавладеть( Состояние1) :-

    % может 2:  Сделать что-нибудь, чтобы завладеть им

        ход( Состояние1, Ход, Состояние2),

    % сделать что-нибудь

        можетзавладеть( Состояние2).

    % теперь может завладеть

line();

Программа для задачи об обезьяне и банане

Рисунок 2. 14.  Программа для задачи об обезьяне и банане.

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

Поиск банана обезьяной

Рисунок 2. 15.  Поиск банана обезьяной. Перебор начинается в верхнем узле и распространяется вниз, как показано. Альтернативные ходы перебираются слева направо. Возврат произошел только один раз.

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

Четыре версии программы предок

Рисунок 2. 16.  Четыре версии программы предок.

В последнем случае пролог-система не сможет найти ответа. И выведет на терминал сообщение: "Не хватает памяти".

На Рисунок 1.11 гл. 1 были показаны все шаги вычислений по пред1 (в главе 1 она называлась предок), предпринятые для ответа на этот вопрос. На рис 2.17 показаны соответствующие вычисления по пред2, пред3 и пред4. На Рисунок 2.17 (с) ясно видно, что работа пред4 - бесперспективна, а Рисунок 2.17(а) показывает, что пред2 довольно неэффективна по сравнению с пред1: пред2 производит значительно больший перебор и делает больше возвратов по фамильному дереву.

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

Из всех четырех вариантов отношения предок, пред1 использует наиболее простое соображение в первую очередь. В противоположность этому пред4 всегда сначала пробует использовать самое сложное. Пред2 и пред3 находятся между этими двумя крайностями. Даже без детального изучения процессов вычислений ясно, что пред1 следует предпочесть просто на основании правила "самое простое пробуй в первую очередь".

Наши четыре варианта процедуры предок можно далее сравнить, рассмотрев вопрос: "На какие типы вопросов может отвечать тот или иной конкретный вариант и на какие не может?" Оказывается, пред1 и пред2 оба способны найти ответ на любой вид вопроса относительно предков; пред4 никогда не находит ответа, а пред3 иногда может найти, иногда нет. Вот пример вопроса, на который пред4 ответить не может:

        ?-  пред3( лиз, джим).

Такой вопрос тоже вводит систему в бесконечную рекурсию. Следовательно и пред3 нельзя признать верным с точки зрения процедурного смысла.

Поведение трех вариантов

Рисунок 2. 17.  Поведение трех вариантов формулировки отношения
предок при ответе на вопрос, является ли Том предком Пат?

? Родитель( X _ )

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

Лексический диапазон имени - одно предложение. Это значит, что если, например, имя Х15 встречается в двух предложениях, то оно обозначает две разные переменные. Однако внутри одного предложения каждое его появлений обозначает одну и ту же переменную. Для констант ситуация другая: один и тот же атом обозначает один и тот же объект в любом предложении, иначе говоря, - во всей программе.

и по типу того, как

Упражнение

2. 9.    Рассмотрите программу на Рисунок 2.10 и по типу того, как это сделано на Рисунок 2.10, проследите процесс вычисления пролог-системой вопроса
        ?-  большой( X),   темный( X).
Сравните свое описание шагов вычисления с описанием на Рисунок 2.10, где вычислялся, по существу, тот же вопрос, но с другой последовательностью целей:
        ?-  темный( X),   большой( X).
В каком из этих двух случаев системе приходится производить большую работу для нахождения ответа?
Посмотреть ответ

hl();


Упражнение

2. 10. Что будет, если пролог-системе задать такой вопрос:
        ?-   Х  =  f( X).
Успешным или неуспешным будет здесь сопоставление? По определению унификации в логике, сопоставление должно быть неуспешным, а что будет в соответствии с нашим определением сопоставления из раздела 2.2? Попробуйте объяснить, почему многие реализации Пролога отвечают на вышеприведенный вопрос так:
        X  =   f(f(f(f(f(f(f(f(f(f(f(f(f(f(f( ...
Посмотреть ответ

Какие из следующих выражений представляют

Упражнения

2. 1.    Какие из следующих выражений представляют собой правильные объекты в смысле Пролога? Что это за объекты (атомы, числа, переменные, структуры)?
    (а)        Диана
    (b)        диана
    (с)        'Диана'
    (d)        _диана
    (e)        'Диана едет на юг'
    (f)        едет( диана, юг)
    (g)        45
    (h)        5( X, Y)
    (i)        +( север, запад)
    (j)        три( Черные( Кошки) )
Посмотреть ответ
2. 2.    Предложите представление для прямоугольников, квадратов и окружностей в виде структурных объектов Пролога. Используйте подход, аналогичный приведенному на Рисунок 2.4. Например, прямоугольник можно представить четырьмя точками (а может быть, только тремя точками). Напишите несколько термов конкретных объектов такого типа с использованием предложенного вами представления.

Упражнения

2. 3.    Будут ли следующие операции сопоставления успешными или неуспешными? Если они будут успешными, то какова будет результирующая конкретизация переменных?
    (а)        точка( А, В) = точка( 1, 2)
    (b)        точка( А, В) = точка( X, Y, Z)
    (c)        плюс( 2, 2) = 4
    (d)        +( 2, D)= +( Е, 2)
    (е)        треугольник( точка( -1, 0), Р2, Р3) =
                 треугольник( Р1, точка( 1, 0), точка( 0, Y)
Результирующая конкретизация определяет семейство треугольников. Как бы Вы описали это семейство?
Посмотреть ответ
2. 4    Используя представление отрезков, применявшееся в данной разделе, напишите терм, соответствующий любому отрезку на вертикальной прямой x = 5.
Посмотреть ответ
2. 5.    Предположим, что прямоугольник представлен термом прямоугольник( P1, P2, P3, Р4), где Р - вершины прямоугольника, положительно упорядоченные. Определите отношение
        регулярный( R)
которое имеет место, если R - прямоугольник с вертикальными и горизонтальными сторонами.
Посмотреть ответ

Упражнения

2. 6.    Рассмотрим следующую программу:
    f( 1, один).
    f( s(1), два).
    f(    s(s(1)),    три).
    f( s(s(s(X))),  N) :-
               f(X,   N).
Как пролог- система ответит на следующие вопросы? Там, где возможны несколько ответов, приведите по крайней мере два.
    (a)        ?- f( s( 1), A).
    (b)        ?- f( s(s(1)), два).
    (c)        ?- f(   s(s(s(s(s(s(1)))))), С).
    (d)        ?- f( D, три).
Посмотреть ответ
2. 7.    В следующей программе говорится, что два человека являются родственниками, если
    (a)        один является предком другого, или
    (b)        у них есть общий предок, или
    (c)        у них есть общий потомок.
    родственники( X, Y) :-
          предок( X, Y).
    родственники( X, Y) :-
          предок( Y, X).
    родственники( X, Y) :-
                      % X и Y имеют общего предка
          предок( Z, X),
          предок( Z, Y).
    родственники( X, Y) :-
                      % X и Y имеют общего потомка
          предок( X, Z),
          предок( Y, Z).
Сможете ли вы сократить эту программу, используя запись с точками с запятой?
Посмотреть ответ
2. 8.    Перепишите следующую программу, не пользуясь точками с запятой.
    преобразовать( Число, Слово) :-
          Число = 1,  Слово = один;
          Число = 2,  Слово = два;
          Число = 3,  Слово = три.
Посмотреть ответ

---

---