ПРОГРАММИРОВАНИЕ НА ЯЗЫКЕ ПРОЛОГ

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


---------------------------------------------


 У.Клоксин, К.Меллиш
 ПРОГРАММИРОВАНИЕ НА ЯЗЫКЕ ПРОЛОГ
 Для программистов и пользователей ЭВМ.



 ПРЕДИСЛОВИЕ РЕДАКТОРОВ ПЕРЕВОДА


 Язык программирования Пролог появился в 1970 г. одновременно с такими сейчас широко распространенными языками, как Паскаль и Си. Его ориентация – «нетрадиционные» применения вычислительной техники: понимание естественного языка, базы знаний, экспертные системы и другие задачи, которые принято относить к проблематике искусственного интеллекта. Сила этого языка – в принципиально отличном от традиционных языков программирования подходе к описанию способа решения задачи: программа на Прологе описывает не процедуру решения задачи, а логическую модель предметной области – некоторые факты относительно свойств предметной области и отношений между этими свойствами, а также правила вывода новых свойств и отношений из уже заданных. Таким образом, Пролог – описательный язык. Как отмечено в авторском предисловии, такой логический подход к программированию создает и некоторые проблемы в распространении языка: основные понятия языка опытными программистами понимаются без труда, однако практическое претворение этого понимания в полезные программы вызывает затруднения.
 Несмотря на очевидные и яркие достоинства, Пролог, в отличие от своих «сверстников» (Паскаля и Си), продолжительное время развивался, применялся и обсуждался в сравнительно узком кругу исследователей, работающих в области искусственного интеллекта. И лишь в последние годы Пролог попал в поле зрения широких кругов специалистов по информатике. Резкий рост его популярности объясняется, по-видимому, выходом теории искусственного интеллекта в область практического, «коммерческого» программирования.
 В настоящее время растет круг практических систем, использующих достижения искусственного интеллекта на современных ЭВМ, появились престижные национальные проекты создания ЭВМ новых поколений, в которых интеллектуальный интерфейс с конечным пользователем (непрофессионалом в информатике) является центральным элементом. В японском проекте создания ЭВМ пятого поколения Пролог прямо называется базовым языком программирования. По-видимому, Пролог реально претендует на роль одного из основных инструментальных языков для «нетрадиционных» применений вычислительной техники, поэтому своевременное знакомство с ним отечественных специалистов, работающих в данной области, будет несомненно полезным.
 В социалистических странах активное участие в разработках, связанных с Прологом, принимают ученые ВНР. В Институте по координации вычислительной техники (г. Будапешт) создана версия Пролога – МПролог, получившая международное признание. Не исключено, что МПролог будет широко доступен и пользователям нашей страны. Этим объясняется включение в русское издание специального приложения (F) посвященного МПрологу.
 При переводе книги встретились значительные терминологические проблемы, поскольку установившаяся русская терминология в данной области практически отсутствует, а станет ли таковой англоязычный жаргон специалистов – покажет время. Для удобства читателей в предметном указателе приведены английские эквиваленты терминов, употребляемых в переводе.
 Предисловие, главы 1,3-6, 9, 10 и Приложение В перевел М. М. Комаров, главы 7, 8, 11, Приложения А,С, D, E, F- А. В. Горбунов, главу 2 – Ю. М. Лазутин.




 ПРЕДИСЛОВИЕ КО ВТОРОМУ ИЗДАНИЮ


 После выхода в 1981 г. первого издания книги «Программирование на языке Пролог» этот язык вызвал неожиданно большой интерес у специалистов по информатике, и в настоящее время он рассматривается как возможная основа для принципиально нового поколения языков и систем программирования.
 Мы надеемся, что данная книга частично удовлетворила возрастающую потребность в простом и в то же время исчерпывающем введении в язык практического программирования, каким является Пролог. При подготовке второго издания книги мы воспользовались случаем, чтобы улучшить изложение материала и исправить различные незначительные ошибки. Мы благодарны многим читателям, высказавшим предложения по исправлению и улучшению книги.
 У.  Клоксин К .  Меллиш
  Кембридж, Англия, август  1984




 ПРЕДИСЛОВИЕ К ПЕРВОМУ ИЗДАНИЮ


 Язык программирования Пролог быстро завоевывает популярность во всем мире. С момента его создания, приблизительно в 1970 г., большое число программистов выбрали Пролог  для  использования при решении задач в различных областях символьных вычислений, включающих:
 • реляционные базы данных,
 • математическую логику,
 • решение абстрактных задач,
 • понимание естественного языка,
 • автоматизацию проектирования,
 • символьное решение уравнений,
 • анализ биохимических структур,
 • различные области искусственного интеллекта.
 До настоящего времени не было книг, ставивших своей целью обучить Прологу как языку практического программирования. Видимо, Пролог оказался настолько привлекательным для многих людей, что они стали его изучать, используя неизбежно краткие справочные руководства, небольшое число опубликованных статей и передаваемый устно среди пользователей языка «фольклор». Однако с внедрением Пролога в учебные программы для студентов и аспирантов многим из наших коллег понадобилось учебное руководство по Прологу. Мы надеемся, что наша небольшая книга до некоторой степени удовлетворит эту потребность.
 Многие новички обнаруживали, что задача написания программы на Прологе не похожа на спецификацию алгоритма при программировании на традиционном языке программирования. Программист, использующий Пролог, больше интересуется тем, какие формальные отношения и объекты имеют место в решаемой задаче и какие отношения справедливы для разыскиваемого решения. Таким образом, Пролог можно рассматривать как язык  описаний,  а не как язык  предписаний.  Используемый в Прологе подход состоит главным образом в описании известных фактов и отношений, касающихся решаемой задачи, а не в предписании последовательности шагов, выполняя которые ЭВМ решит задачу. При реализации программы на Прологе фактическая последовательность вычислений, выполняемая ЭВМ, определяется частично логической декларативной семантикой Пролога, частично новыми фактами, которые Пролог может «вывести» из заданных ему фактов, и лишь отчасти управляющей информацией, явно заданной программистом.
 Пролог является  практической  и  эффективной  реализацией многих принципов, относящихся к «интеллектуальному» выполнению программы, таких, как недетерминизм, параллельность, вызов процедур по образцу. Пролог имеет единообразную структуру данных, называемую  термом,  на основе которой конструируются все данные и в том числе программы на Прологе. Программа на Прологе состоит из множества утверждений, каждое из которых является либо фактом о заданной информации, либо правилом, указывающим, как решение связано с заданными фактами или каким образом его можно из них вывести. Таким образом, Пролог можно считать первым шагом на пути к конечной цели –  программированию на языке логики.  В этой книге мы не будем подробно рассматривать ни более широкие следствия, вытекающие из идеи логического программирования, ни вопрос о том, почему Пролог нельзя рассматривать как окончательный язык логического программирования. Вместо этого мы покажем, как, используя существующие сегодня системы программирования на Прологе, можно создавать  полезные  программы.
 Эта книга может служить нескольким целям. Мы не собираемся учить искусству программирования как таковому. Нам кажется, что нельзя научиться программированию, просто читая книги или слушая лекции. Вы должны  программировать,  чтобы научиться делать это. Мы надеемся, что начинающие программисты, не имеющие математической подготовки, смогут освоить Пролог по этой книге, хотя в этом случае мы советовали бы, чтобы начинающий программист осваивал язык под руководством программиста, знающего Пролог, в рамках вводного курса по программированию как таковому. Предполагается, что начинающий программист может получить доступ к ЭВМ, на которой имеется Пролог-система, и что он прошел необходимый инструктаж по работе с терминалом. Опытному программисту не потребуется дополнительная помощь, но он также не должен впадать в уныние от наших усилий ограничить математические излишества. Мы использовали предварительный вариант этой книги при обучении выпускников университета, имевших математическую подготовку на уровне школьной программы и специализировавшихся в университете по философии и психологии.
 Наш опыт показывает, что начинающим программы на Прологе представляются более понятными, чем соответствующие программы на традиционных языках программирования. Однако те же самые люди не склонны ценить те ограничения, которые накладывают традиционные языки на использование вычислительных ресурсов. С другой стороны, программист, имеющий опыт работы на традиционных языках программирования, лучше подготовлен к восприятию таких абстрактных понятий, как переменные и управление последовательностью действий. Но, несмотря на прежний опыт, приспособление к стилю программирования на Прологе может вызвать у него затруднения, и может потребоваться много убедительных примеров, прежде чем он начнет относиться к Прологу как к полезному средству программирования. Конечно, мы знаем много высококвалифицированных программистов, воспринявших Пролог с большим энтузиазмом. Тем не менее, цель этой книги не в том, чтобы «обратить в иную веру», а в том, чтобы научить программировать на Прологе.
 Как и большинство других языков программирования, Пролог существует в множестве различных реализаций, каждая со своими семантическими и синтаксическими особенностями. Для описания в этой книге выбран «базовый» Пролог и все приводимые примеры написаны для стандартной версии, которая соответствует реализациям, разработанным главным образом в Эдинбурге для нескольких различных вычислительных систем: DEC-10 с операционной системой TOPS-10, DEC VAX и PDP-11 с операционной системой Unix, DEC LSI-11 с операционной системой RT-11 и ICL2980 с операционной системой ЕМА. Реализации для ЭВМ фирмы DEC являются, вероятно, наиболее распространенными. Все примеры, приведенные в этой книге, подходят для всех указанных реализаций. В приложениях приведены описания некоторых из существующих реализаций Пролога с указанием их отличий от стандарта. Читатель сможет убедиться, что большинство отличий имеет чисто «косметическую» природу.
 Книга построена таким образом, что читать ее надо последовательно. Тем не менее, будет полезно прочитать гл. 8 в тот момент, когда читатель начнет писать программы на Прологе, состоящие более чем из десяти утверждений. Кроме того, разумно прочитать соответствующее приложение, содержащее описание используемой реализации Пролога. В приложениях говорится, как вводить утверждения, какие средства отладки имеются в системе, и рассматриваются другие практические вопросы. Не будет особого вреда, если вы лишь просмотрите книгу, но старайтесь при этом не пропускать главы.
 Каждая глава книги делится на несколько разделов, и мы советуем читателю выполнять упражнения, приводимые в конце многих разделов. Решения к некоторым из этих упражнений даны в конце книги. Глава 1 представляет собой введение, цель которого – дать читателю почувствовать характер программирования на Прологе. Здесь вводятся основные идеи языка Пролог и читателю рекомендуется тщательно изучить их. В гл. 2 содержится более полное обсуждение идей и понятий, введенных в гл. 1. В гл. 3 рассматриваются структуры данных и приводятся в качестве примеров несколько небольших программ. В гл. 4 более подробно обсуждается механизм возврата, вводится символ «отсечения», используемый для управления механизмом возврата. В  гл.  5 вводятся имеющиеся в языке средства ввода-вывода. В гл. 6 описывается каждый встроенный предикат базовой версии языка Пролог. Глава 7 представляет собой «попурри» из примеров программ, взятых из многих источников и снабженных комментариями, поясняющими их работу. В гл. 8 даются некоторые советы по отладке программ на Прологе. В гл. 9 вводится синтаксис грамматических правил и изучаются предположения, лежащие в основе программ для анализа естественного языка с использованием грамматических правил. В гл. 10 описывается связь Пролога с идеями математического доказательства теорем и логического программирования, лежащими в основе языка. В гл. 11 представлен ряд проектов, на которых заинтересованные читатели могут поупражняться в развитии навыков программирования на Прологе.
 Мы выражаем благодарность нашим учителям, сформировавшим наши взгляды на программирование: Роду Борстоллу, Питеру Скотту Лэнгстону и Робину Попплстоуну. Мы благодарны друзьям, участвовавшим вместе с нами в совершенствовании Пролога как практического и полезного средства программирования и поддерживавших нас в процессе подготовки этой книги: Алану Банди, Лоренсу Байрду, Роберту Ковальски, Фернандо Перейра и Дейвиду Уоррену. В частности, Лоуренс Байрд поддерживал работу по созданию книги с самого ее начала, предлагая программы, упражнения, некоторые проекты, приведенные в гл. 11, и много идей по организации книги. Мы также благодарны нашим друзьям, внесшим свой вклад в создание книги полезными замечаниями и советами по улучшению предварительного ее варианта: Джону Каннингаму, Ричарду О'Кифу, Элен Пейн, Фернандо Перейра, Гордону Плоткину, Роберту Реи, Питеру Россу, Максвеллу Шортеру, Арону Сломену и Дейвиду Уоррену. В этом отношении У. Клоксин особенно благодарен своим аспирантам из School of Epistemics и Department of Artificial Intelligence, которые помимо их воли стали объектом многочисленных экспериментов в области обучения программированию. При выборе примеров мы свободно пользовались распространенным программистским фольклором и в связи с этим приносим наши извинения всем, кто чувствует себя обойденным вниманием.
 Эта книга была подготовлена в период работы авторов на факультете искусственного интеллекта Эдинбургского университета. Мы благодарны Джиму Хоу, возглавлявшему факультет, за создание благоприятных условий при работе над книгой.
 У.  Клоксин К. Меллиш
  Эдинбург, Шотландия, июнь  1981




 ГЛАВА 1 ВВЕДЕНИЕ


 Пролог – язык программирования, используемый для решения задач, сводимых к объектам и отношениям между объектами. В этой главе мы продемонстрируем основные элементы языка на примерах реальных программ, не вдаваясь особенно в детали, формальные правила и исключения. Исходя из этого, мы не старались, чтобы изложение было полным или достаточно точным. Мы хотим как можно быстрее подвести вас к тому моменту, когда вы сможете самостоятельно писать полезные программы, и чтобы добиться этого, мы должны сконцентрировать внимание на основных понятиях: фактах, запросах, переменных, конъюнкциях и правилах. Другие особенности языка Пролог, такие как списки и рекурсия, будут рассмотрены в последующих главах.
 Пролог применяется в тех случаях, когда необходимо использовать ЭВМ для решения задачи, которая может быть выражена в терминах объектов и отношений между ними. Например, когда мы говорим: «Джон имеет книгу», мы объявляем, что между одним объектом «Джон» и другим объектом «книга» имеет место отношение обладания. Более того, это отношение имеет определенный порядок: Джон имеет книгу, но книга не имеет Джона! Когда мы задаем вопрос: «Имеет ли Джон книгу?», то нас интересует правильность именно отношения.
 При констатации некоторых отношений не всегда упоминаются все объекты, включаемые в них. Например, когда мы говорим: «Драгоценные камни являются ценными», мы имеем в виду, что существует отношение, называемое «являться ценным», которое включает драгоценные камни. Для нас не имеет значения, кто считает, что драгоценные камни являются ценными, и почему он так считает. Это все зависит от того, что вы хотите сказать. При использовании Пролога, когда программируются отношения, подобные приведенным, уровень требуемой детализации также зависит от того, что вы хотите заставить делать ЭВМ .
 Существует еще один вопрос идейного плана, который следует упомянуть ,  прежде чем приступать к программированию. Мы все знакомы с использованием правил для описания отношений между объектами. Например, правило «Два человека являются сестрами, если они оба женского пола и имеют одних и тех же родителей» объясняет нам, что значит быть сестрами. Оно также указывает, как определить, являются ли два человека сестрами: необходимо просто проверить, относятся ли они оба к женскому полу и имеют ли одних и тех же родителей. Важно отметить, что хотя правила обычно бывают упрощенными, тем не менее они приемлемы в качестве определений. В конце концов, не следует ожидать, что определение говорит нам все об определяемом объекте. Например, большинство людей согласится с тем, что в реальной жизни «быть сестрами» значит больше, чем это следует из приведенного правила. Однако, решая конкретную задачу, необходимо сосредоточить внимание именно на таких правилах, которые помогут ее решить. Таким образом, следует обратиться к схематичному и упрощенному определению, если его достаточно для достижения поставленной цели.
 Программирование на языке Пролог состоит из следующих этапов:
 • объявления некоторых  фактов  об объектах и отношениях между ними,
 • определения некоторых  правил  об объектах и отношениях между ними и
 • формулировки  вопросов  об объектах и отношениях между ними.
 Например, предположим, что мы записали на Прологе наше правило о сестрах. Мы могли бы сделать запрос о том, являются ли Мэри и Джейн сестрами. Пролог просмотрел бы все, что ему известно о Мэри и Джейн, и выдал бы ответ да или нет в зависимости от того, что ему известно. Таким образом, можно рассматривать Пролог как некоторое хранилище фактов и правил, используемых для поиска ответов на вопросы. Программирование на Прологе заключается в том, чтобы описать все эти факты и правила. Пролог-система позволяет использовать ЭВМ как хранилище фактов и правил и предоставляет механизм, позволяющий делать выводы, переходя от одних фактов к другим.
 Пролог является диалоговым языком. Это следует понимать так, что пользователь и ЭВМ осуществляют некоторое подобие диалога. Предположим, что вам предложили поработать за терминалом ЭВМ и воспользоваться Прологом. Ваш терминал состоит из  клавиатуры  и  дисплея.  Вы используете  клавиатуру  для ввода информации в ЭВМ, а ЭВМ использует  дисплей  (может быть, экран либо бумажную ленту) для вывода полученных результатов. Пролог будет ждать, пока вы введете факты и правила, относящиеся к задаче, которую вы хотите решить. Затем, если вы сможете задать вопросы и если вы делаете это правильно, Пролог будет искать соответствующие ответы и выводить их на дисплей.
 Теперь мы последовательно введем каждое из основных понятий языка Пролог. Не беспокойтесь о том, что вы не получите сразу полного представления о всех особенностях языка Пролог. В последующих главах будет дано их исчерпывающее описание и будет приведено и разобрано много примеров решения задач на языке Пролог.

  1.1. Факты

 Начнем обсуждение с  фактов  об объектах. Предположим, мы хотим сообщить Прологу [1] факт: «Джону нравится Мэри». Этот факт включает в себя два объекта, обозначенных именами «Мэри» и «Джон», и отношение, обозначенное словом «нравится». В языке Пролог используется стандартная форма записи фактов:
 нравится (джон, мэри).
 Важно соблюдать следующие правила:
 • Имена всех отношений и объектов должны начинаться со строчной буквы. Например,  нравится, джон, мэри.
 • Сначала записывается имя отношения. Затем через запятую записываются имена объектов, а весь список имен объектов заключается в круглые скобки.
 • Каждый факт должен заканчиваться точкой.
 Определяя с помощью фактов отношения между объектами, необходимо учитывать, в каком порядке перечисляются имена объектов внутри круглых скобок. Этот порядок может быть произвольным, но, выбрав один раз какой-то определенный порядок, мы должны везде следовать ему и далее. Например, в приведенном выше факте мы поставили на первое место в списке объектов «того, кому нравится», а объект «который нравится» стоит во второй позиции. Таким образом, факт  нравится(джон,мэри) не одно и тоже, что  нравится(мэри,джон) . В соответствии с принятой нами (хотя и произвольным образом) договоренностью первый факт говорит о том, что Джону нравится Мэри, в то время как второй факт говорит, что Мэри нравится Джон. Если мы хотим сказать, что Мэри нравится Джон, то мы должны сформулировать это утверждение явно, в виде факта
 нравится(мэри,джон).
 Взгляните на следующие примеры фактов, приведенные вместе с возможной их интерпретацией на естественном языке:
  ценный(золото).  Золото является ценным,
  женщина(джейн).  Джейн — женщина.
  владеет(джон,золото).  Джон владеет золотом.
  отец(джон,мэри).  Джон является отцом Мэри.
  дает(джон,книга,мэри).  Джон дает Мэри книгу.
 Всякий раз когда используется некоторое имя, оно указывает на определенный индивидуальный объект. В силу жизненного опыта нам совершенно ясно, что имена  джон и  джейн относятся к индивидуальным объектам. Но в некоторых других фактах мы использовали имена  золото и  ценный , и совсем не очевидно, что они значат. Логики называют имена такого сорта «словами, не имеющими определенного значения вне контекста». Используя такие имена, мы должны решить, как  интерпретировать  эти имена. Например, имя золото могло бы относиться к некоторому объекту. В этом случае мысленный образ объекта имеет вид конкретного куска золота, который мы обозначаем именем  золото . И когда мы записываем на Прологе  ценный(золото) , мы должны понимать это в том смысле, что этот конкретный кусок золота, для обозначения которого мы использовали имя  золото , является ценным. С другой стороны, мы могли бы интерпретировать имя  золото как  слово, обозначающее химический элемент золото с атомным весом 79,  и, когда мы записываем  ценный(золото) , мы должны понимать это так, что химический элемент золото является ценным. Таким образом, имеется несколько способов интерпретировать имя и именно автор программы определяет конкретную интерпретацию. До тех пор пока последовательно используется одна и та же интерпретация имен, никаких проблем не возникает. Выявлять отличия между различными интерпретациями необходимо с самого начала, с тем чтобы быть совершенно уверенным в том, что обозначают,имена.
 Теперь пришла пора сказать несколько слов о терминологии. Имена объектов, список которых в каждом факте заключен в круглые скобки, называются аргументами. Заметим, что в программировании значение слова «аргумент» не имеет ничего общего с его общеупотребительным значением, используемым в контексте слов «диспут», «дебаты», «дискуссия», «спор» и т. п. Имя отношения, которое записывается непосредственно перед круглыми скобками, называется  предикат. [2]  Таким образом,  ценный – это предикат, имеющий один аргумент, а  нравится – предикат с двумя аргументами.
 Имена объектов и отношений являются полностью произвольными. Например, вместо терма  нравится(джон,мэри) мы могли бы с таким же успехом представить это как  a(b,c) , помня при этом, что а значит  нравится,   b означает  Джон,  а  с –  Мэри.  Однако обычно мы выбираем имена таким образом, чтобы они сами напоминали нам, что они значат. Следовательно, мы заранее должны решить, что значат наши имена и каким должен быть порядок аргументов. С этого момента необходимо последовательно придерживаться принятых соглашений.
 Отношения могут иметь произвольное число аргументов. Если мы хотим определить предикат  играть , в котором упоминаются два игрока и игра, в которую они играют между собой, то необходимы три аргумента. Здесь приведены два примера, показывающие, как это можно сделать:
 играть(джон,мэри,футбол).
 играть(джейн, джим,бадминтон).
 Как мы увидим далее, такой способ обеспечивает возможность представления сложных взаимодействий между отношениями.
 В Прологе можно объявить факты, которые не являются истинными в реальном мире. Например, можно было бы написать  король(джон, франция) , чтобы объявить, что  Джон является королем Франции.  В реальном мире этот факт со всей очевидностью является ложным, в частности, потому, что монархия во Франции уничтожена приблизительно в 1792 г. Но Пролог не знает этого и не заботится об этом. Факты в Прологе просто позволяют выражать произвольные отношения между объектами.
 Совокупность фактов в Прологе называется  базой данных.  Мы будем пользоваться термином  база данных  всякий раз при объединении вместе некоторых фактов (а в дальнейшем и правил) для совместного их использования при решении некоторой конкретной задачи.

 1.2. Вопросы

 Имея некоторую совокупность фактов, мы можем обращаться к Прологу с вопросами о них. В Прологе вопрос записывается почти так же, как и факт, за исключением того, что перед ним ставится специальный символ. Специальный символ состоит из вопросительного знака и следующего за ним тире. Рассмотрим вопрос:
 ?- имеет(мэри, книга).
 Если мы интерпретируем  мэри  как  человека по имени Мэри,  а  книга  - это какая-то конкретная книга, то смысл вопроса в следующем:  «Имеет ли Мэри (данную конкретную) книгу?»  или  «Имеет ли место факт, что Мэри имеет данную книгу?».  Мы не спрашиваем, имеет ли она все книги или книги вообще.
 Обращение к Прологу с вопросом инициирует процедуру поиска в базе данных, ранее введенной в систему. Пролог ищет факты,  сопоставимые  с фактом о вопросе. Два факта  сопоставимы  (или соответствуют один другому), если их предикаты одинаковы (побуквенное совпадение) и их соответствующие аргументы попарно совпадают. Если Пролог находит факт, сопоставимый с вопросом, то он отвечает  да   [3]  . Если в базе данных такого факта не существует, то Пролог отвечает  нет . Ответ, выдаваемый Прологом, выводится на дисплей терминала непосредственно под запросом. Пусть имеется следующая база данных:
 нравится(джо,рыба).
 нравится(джо,мэри).
 нравится(мэри,книга).
 нравится(джо,книга).
 Если все эти факты введены в Пролог-систему, то можно было бы делать следующие вопросы, ответы на которые Пролог написал бы непосредственно под текстом вопроса:
 ?- нравится(джо,деньги).
 нет
 ?- нравится(мэри,джо).
 нет
 ?- нравится(мэри,книга).
 да
 ?- король(джон,франция).
 нет
 Ответы на три первых вопроса должны быть понятны. Кроме этого, Пролог отвечает  нет на вопрос о том, является ли Джон королем Франции. Система выдает такой ответ, так как среди фактов в базе данных, представленной приведенными выше четырьмя отношениями  нравится , нет отношений, указывающих на королевские звания. В Прологе ответ  нет используется в смысле  ничто в базе данных не согласуется с вопросом.  Важно помнить, что ответ нет вовсе не эквивалентен ответу  является ложным.  Предположим, например, что база данных содержит три факта об известных мыслителях Греции:
 человек(сократ).
 человек(аристотель).
 афинянин(сократ).
 Можно было бы сделать несколько вопросов:
 ?- афинянин(сократ).
 да
 ?- афинянин(аристотель).
 нет
 ?- грек(сократ).
 нет
 Хотя тот факт, что Аристотель жил когда-то в Афинах, может быть исторически верным, мы просто не можем  доказать  его на основе фактов, представленных в базе данных. Более того, хотя в базе данных содержится факт о том, что Сократ жил в Афинах, это не  доказывает  того, что он был греком, если только в базе данных нет дополнительной информации. Таким образом, когда Пролог на вопрос отвечает  нет , это значит  не доказуемо, не согласуется с базой данных.
 В приведенном ранее примере Джону и Мэри нравится один и тот же объект. Мы знаем, что им нравится один и тот же объект, так как одно и то же имя  книга появляется в обоих фактах.
 Обсуждавшиеся до сих пор факты и вопросы не представляют большого интереса. Все что мы можем сделать – это получить обратно ту же самую информацию, которую мы ввели в систему. Более полезны были бы вопросы вида:  «Какие объекты нравятся Мэри?».  Именно для реализации такой возможности предназначены  переменные.

 1.3. Переменные

 Если вы хотите узнать, что нравится Джону, то было бы утомительно спрашивать  «Нравятся ли Джону книги?», «Нравится ли Джону Мэри?»  и так далее, получая каждый раз ответ  да или  нет . Более разумно обратиться к Пролог-системе с просьбой назвать что-нибудь, что нравится Джону. Такой вопрос можно сформулировать следующим образом« «Нравится ли Джону X?».  Задавая вопрос, мы не знаем, для обозначения какого объекта использована литера  X . Нам хотелось бы, чтобы Пролог перечислил все имеющиеся возможности  для обозначения какого объекта использована литера   X . В Прологе можно не только присваивать имена конкретным объектам, но и использовать имена, подобные  X , для обозначения объектов, которые должны быть определены Пролог-системой. Имена такого типа называются  переменными.  Переменная в Прологе может иметь либо не иметь конкретное значение. Переменная конкретизирована, если имеется объект, который обозначает эта переменная. Переменная не конкретизирована, если еще не известно, что именно она обозначает. В Прологе используется соглашение, позволяющее отличать переменные от имен конкретных объектов –  каждое имя, начинающееся с прописной буквы, рассматривается как переменная.
 При поиске ответа на вопрос Пролог организует просмотр всех фактов в базе данных, чтобы обнаружить объект, который эта переменная могла бы обозначать. Так, когда мы спрашиваем  «Нравится ли Джону X?»,  Пролог просматривает все известные ему факты для обнаружения тех вещей, которые нравятся Джону.
 Такая переменная, как  X , сама по себе не является именем какого-то конкретного объекта, но она может быть использована для обозначения объектов, которым мы не можем дать имя. Например, мы не можем  чему-то, что нравится Джону,  дать имя как объекту, поэтому для выражения подобных вопросов вместо вопросов вида
 ?- нравится(джон,  Что-то, что любит Джон).
 Пролог позволяет использовать переменные и задавать вопросы в виде
 ?- нравится(джон,Х).
 При желании можно давать переменным более длинные имена. Следующий вопрос вполне приемлем в Прологе:
 ?- нравится(джон, Что-точтонравитсяджону).
 Почему? Потому что переменной может быть любое имя, начинающееся с прописной буквы. Рассмотрим следующую базу данных и запрос к Прологу:
 нравится (джон,цветы).
 нравится (джон,мэри).
 нравится(поль,мэри).
 ?- нравится(джон,Х).
 В вопросе спрашивается:  Существует ли что-нибудь, что нравится Джону?  В ответ Пролог напечатает:
 Х=цветы
 а затем будет ждать дальнейших приказов; это мы вкратце обсудим далее. Как это произойдет? При поступлении такого вопроса в Пролог-систему переменная, входящая в вопрос, изначально является неконкретизированной. Пролог просматривает базу данных в поисках факта,  сопоставимого  с вопросом. Если неконкретизированная переменная появляется в качестве аргумента, то Пролог считает, что такой аргумент сопоставим с  любым  другим аргументом, находящимся в той же самой позиции факта. В нашем примере Пролог ищет любой факт с предикатом  нравится и первым аргументом  джон .  Второй  аргумент в этом случае может быть каким угодно, так как в вопросе вторым аргументом является неконкретизированная переменная. При обнаружении такого факта переменная  X становится конкретизированной, обозначая объект, являющийся вторым аргументом найденного факта, каким бы этот аргумент ни был. Пролог просматривает факты базы данных в том порядке, в каком они вводились (на печатной странице это соответствует просмотру сверху вниз), поэтому факт  нравится(джон, цветы) найден первым. С этого момента переменная  X обозначает объект  цветы или, говоря другими словами, переменная  X конкретизируется значением  цветы . Пролог с помощью специального  маркера  отмечает место в базе данных, в котором произошло сопоставление. Обсудим кратко причины, по которым оказалось необходимым использование такого маркера.
 Обнаружив факт, соответствующий вопросу, Пролог печатает имена объектов, которые теперь обозначают переменные. В нашем примере есть только одна переменная  X , которой соответствует объект  цветы . Затем Пролог ждет дальнейших указаний, как об этом говорилось выше. Если в этой ситуации нажать на терминале клавишу  RETURN , указывая тем самым, что вы удовлетворены полученным ответом, то Пролог прекратит дальнейший поиск в базе данных. Если вместо этого нажать клавишу  ;  (и вслед за ней клавишу  RETURN ), то Пролог продолжит поиск в базе данных,  начиная с места, отмеченного маркером.  В такой ситуации, когда Пролог начинает поиск не с начала базы данных, а с места, отмеченного маркером, мы говорим, что Пролог пытается заново согласовать вопрос.
 Предположим, что в ответ на первое найденное Прологом соответствие ( Х=цветы ) мы предлагаем системе продолжить поиск (введя  ; ). Это значит, что мы хотим согласовать вопрос иначе; мы хотим найти другой объект, который могла бы обозначать переменная  X . Это также значит, что Пролог должен «забыть» о том, что переменная  X обозначает  цветы , и снова продолжить поиск с неконкретизированной переменной  X . Так как мы ищем альтернативное решение, то поиск продолжается с места, отмеченного маркером. Следующий найденный системой факт, соответствующий вопросу, есть  нравится(джон,мэри).  Переменная  X вновь становится конкретизированной, обозначая  мэри,  а Пролог отмечает маркером факт  нравится(джон,мэри).  Пролог напечатает  Х=мэри  и будет ожидать дальнейших команд. Если мы вновь введем точку с запятой, то Пролог продолжит поиск. В нашем примере нет больше ничего, что нравится Джону. Поэтому Пролог завершит поиск и предоставит нам возможность сделать новые запросы или ввести новые факты.
 Что произойдет, если, имея те же факты, что и ранее, мы зададим вопрос:
 ?- нравится(Х,мэри).
 В этом вопросе спрашивается:  «Существует ли объект, которому нравится Мэри?».  Теперь вы сами можете понять, что в примере объектами, которые нравятся Мэри, являются  джон  и  поль . Опять, если бы мы хотели увидеть все варианты, мы должны были бы вводить; после каждого ответа, выдаваемого Прологом:
 ?-  нравится(Х, мэри).   наш вопрос
  Х=джон;  первый ответ. Мы вводим   ;
  Х=поль;  второй ответ. Вновь вводим   ; .
  нет  больше ответов нет.

  1.4. Конъюнкции

 Предположим, что мы хотим получать ответы на вопросы о более сложных отношениях, таких как:  «Нравятся ли Джон и Мэри друг другу?».  Один из способов сделать это – узнать сначала, нравится ли Джону Мэри, и если Пролог ответит да, то спросить, нравится ли Мэри Джон. Таким образом, эта задача состоит из двух «целевых утверждений» (или целей), которые Пролог должен согласовать. Ввиду того что подобная комбинация часто используется при программировании на Прологе, для нее имеется специальное обозначение. Предположим, мы имеем следующую базу данных:
 нравится(мэри,пища).
 нравится(мэри,вино).
 нравится(джон,вино).
 нравится(джон,мэри).
 Мы хотим узнать, нравятся ли Джон и Мэри друг другу. Для этого мы спрашиваем:  «Нравится ли Джон Мэри  и  нравится ли Мэри Джон?».  Связка  и  выражает тот факт, что нас интересует конъюнкция двух указанных целей – мы хотим последовательно согласовать с базой данных обе цели. Мы выражаем это в вопросе, записывая обе цели через запятую:
 ?- нравится(джон,мэри),нравится(мэри,джон).
 Запятая читается как «и» и используется для разделения произвольного числа различных целей, которые должны быть согласованы с базой данных для того, чтобы ответить положительно на вопрос. Если задана последовательность целей (разделенных запятыми), то Пролог пытается согласовать каждую цель по очереди, просматривая базу данных в поисках сопоставимых фактов. Чтобы согласовать с базой данных последовательность целей, необходимо согласовать все отдельные цели. Что должен напечатать Пролог в ответ на приведенный выше вопрос? Ответ будет  нет . Действительно, так как имеет место факт, что Джону нравится Мэри, то первая цель согласуется с базой данных. Однако вторая цель не согласуется с базой данных, так как в ней отсутствует факт  нравится(мэри,джон) . Учитывая, что мы хотели знать, нравятся ли они  оба  друг другу, окончательным ответом на вопрос является  нет .
 Сочетая возможности конъюнкции и использования переменных, можно строить достаточно содержательные вопросы. Теперь, когда мы знаем, что нельзя выяснить, нравятся ли Джон и Мэри друг другу, мы спрашиваем:  «Существует ли что-нибудь такое, что нравится обоим  -  Джону и Мэри?».  Этот вопрос также содержит две цели:
 • Существует ли такой объект  X , который нравится Мэри.
 • Нравится ли Джону найденное значение  X .
 В Прологе два указанных целевых утверждения следует объединить, используя конъюнкцию, как показано ниже:
 ?- нравится(мэри,Х), нравится(джон,X).
 Пролог отвечает на вопрос, пытаясь подобрать соответствие для первой цели. Если в базе данных есть факт, соответствующий целевому высказыванию, то Пролог отметит найденное место и попытается согласовать вторую цель. Если и она достигнута, то Пролог также отмечает в базе данных соответствующее ей место, и таким образом находится решение, удовлетворяющее обеим целям.
 Важно помнить, что каждая цель имеет свой собственный маркер для указания места в базе данных,  где  найдены соответствующие им факты. Если, однако, вторая цель не согласуется с базой данных, то Пролог попытается найти новое соответствие для предыдущей цели (в данном случае для первой цели). Помните, что Пролог полностью просматривает базу данных для каждой из целей. Если случится так, что некоторый факт в базе данных можно сопоставить с заданной целью, то Пролог отметит это место в базе данных на случай, если впоследствии он будет вынужден снова искать для этой цели другое соответствие. И когда возникнет необходимость найти для цели другое соответствие, Пролог начнет поиск не с начала базы данных, а с места, отмеченного маркером, соответствующим этой цели. Наш предыдущий вопрос:  «Существует ли что-нибудь, что нравится и Мэри и Джону?»  иллюстрирует пример такого поиска с возвратом («бектрекинга»). Пролог выполняет следующую последовательность действий:
 1. База данных просматривается в попытке согласовать первую цель. Так как второй аргумент  (X) неконкретизирован, то ему может соответствовать все что угодно. Первый факт, сопоставимый с целью, в приведенной выше базе данных есть  нравится(мэри, пища).  С этого момента  каждому  появлению переменной  X в вопросе соответствует значение  пища.  Пролог отмечает в базе данных то место, где был обнаружен соответствующий факт, так что при необходимости найти другой способ согласования цели с фактами он может вернуться в эту точку и продолжить поиск. Более того, следует помнить, что переменная  X была конкретизирована в этой точке и Пролог может «забыть» найденное для  X значение в случае необходимости найти новое соответствие в фактах для рассматриваемой цели.
 2. Теперь в базе данных ищется факт  нравится(джон,пища),  так как следующая цель – это  нравится (джон,X) , а переменная  X теперь имеет значение  пища.  Как можно видеть, база данных такого факта не содержит, так что эта цель с базой данных не согласуется. В этой ситуации мы должны попытаться найти новое соответствие в фактах для предыдущей цели. Поэтому Пролог предпринимает попытку найти новое соответствие для  нравится(мэри,X) , при этом поиск в базе данных начинается с отмеченного маркером места. Но сначала необходимо «расконкретизировать» переменную  X так, чтобы  X опять могла быть сопоставлена с любым объектом.
 3. Отмеченным маркером местом является факт  нравится(мэри, пища).  Поэтому Пролог начинает поиск со следующего непосредственно за ним факта. Так как мы еще не достигли конца базы данных, то мы не исчерпали всех объектов, которые нравятся Мэри. Следующим сопоставимым фактом является  нравится(мэри, вино).  Теперь переменная  X принимает значение  вино,  и Пролог отмечает это место на случай, если потребуется найти новое соответствие для того, что нравится Мэри.
 4. Как и ранее, Пролог пытается теперь согласовать с фактами вторую цель в вопросе, осуществляя поиск в базе данных факта  нравится(джон,вино).  Пролог не пытается при этом использовать механизм поиска нового соответствия для этой цели. Это новая цель, которую он выбирает, продвигаясь, как и раньше, слева направо по списку целей в исходном вопросе, поэтому он должен начать поиск с начала базы данных. Когда после недолгого поиска будет найден сопоставимый факт, Пролог выдает надлежащее сообщение. Как только вторая цель согласована, Пролог отмечает соответствующий ей факт в базе данных на случай, если вдруг потребуется найти для нее новое соответствие. Для каждой цели, которую Пролог пытается согласовать, в базе данных имеется свой маркер, указывающий факт, поставленный в соответствие этой цели.
 5. Теперь обе цели согласованы. Переменная  X обозначает имя  вино.  Маркер первого целевого утверждения отмечает в базе данных факт  нравится(мэри,вино),  а маркер второго целевого утверждения отмечает факт  нравится(джон,вино).
 Как и в случае других запросов, как только Пролог находит ответ, он прекращает поиск и ожидает дальнейших указаний.
 Если ввести  ; , то Пролог продолжит поиск объектов, которые нравятся одновременно Джону и Мэри. Теперь мы знаем, что все последующие попытки поиска новых ответов на вопрос с двумя целями начинаются с мест, отмеченных маркерами, которые оставили эти цели на предыдущем этапе.
 Подводя итог, можно представить конъюнкцию целей в вопросе как список целей, упорядоченных слева направо и разделенных запятыми. Каждая цель может иметь соседа слева и соседа справа. Ясно, что цели, занимающие в списке крайнее левое и крайнее правое положения, не будут иметь соседей соответственно слева и справа. Обрабатывая конъюнкцию целей, Пролог пытается по очереди согласовать с базой данных каждую цель, просматривая вопрос слева направо. Если обнаруживается факт, сопоставимый с целью, то Пролог оставляет в этом месте базы данных маркер, связанный  с  целью. Это можно наглядно представить с помощью стрелки, ведущей от цели к некоторому месту в базе данных, где находится соответствующий факт. Кроме того, некоторые ранее неконкретизированные переменные могут при этом быть конкретизированы, как это имело место выше на шаге 1. Если некоторая переменная конкретизируется, то конкретизируются и все вхождения этой переменной в вопрос. Далее Пролог пытается удовлетворить правого соседа этой цели, начиная поиск с вершины базы данных (наполнение базы данных в Прологе осуществляется сверху вниз, так что вершина – это факт, внесенный в базу данных первым). Как и любая другая цель, для которой найдено соответствие, она оставляет после себя в базе данных маркер (проводит еще одну стрелку от этой новой цели к соответствующему ей факту), на случай если впоследствии возникнет необходимость найти для цели другое соответствие. Каждый раз, когда целевое утверждение не выполняется (нельзя найти сопоставимого факта), Пролог возвращается и пытается найти новое соответствие для соседа  слева  данной цели, начиная поиск с места, отмеченного соответствующим ему маркером. Кроме того, Пролог должен сначала расконкретизировать все переменные, которые были конкретизированы при достижении этой цели. Другими словами, когда Пролог ищет новое соответствие для цели, он должен «уничтожить» старое значение этих переменных. Если для цели, к рассмотрению которой был возврат справа, нельзя найти новое соответствие, то Пролог перейдет еще левее, постепенно приближаясь к левой границе конъюнкции. Если не удается найти новое соответствие для крайней слева цели, которая уже не имеет соседа слева, то в этом случае считается несогласуемой с базой данных вся конъюнкция целей в вопросе к Прологу. Такое поведение, когда Пролог неоднократно пытается согласовать (и вновь согласовать) цели, входящие в вопрос-конъюнкцию, называется поиском с возвратом (бектрекингом). В следующей главе дается краткое описание механизма возврата, а в гл. 4 проводится более полное и детальное рассмотрение этого процесса.
 Разбирая примеры, полезно записывать под каждой переменной, входящей в целевое утверждение, значение (имя объекта), которое было присвоено этой переменной при установлении согласованности цели с базой данных. Следует также изображать стрелки, идущие от цели к соответствующему ей маркеру в базе данных. На рис. 1.1 приведен пример такой иллюстрации на бумаге работы Пролога, состоящий из четырех «мгновенных снимков» процесса поиска в приведенном выше примере. На каждом снимке показаны полная база данных и вопрос, а также пронумерованная последовательность комментариев. На рисунке цели, для которых найдены соответствия, заключены в прямоугольник.
 На протяжении всей книги мы постараемся показать, где в рассматриваемых примерах имеет место возврат и какую роль он играет в решении задачи. Значение механизма возврата при поиске настолько велико, что ему полностью посвящена гл. 4.
  Упражнение 1.1. Продолжить разбор рассмотренного выше примера с помощью карандаша и бумаги, предположив, что вы ввели точку с запятой;, инициируя возврат для того, чтобы определить, существует ли еще что-нибудь, что нравится одновременно Джону и Мэри.
  Рис. 1.1.

  1.5. Правила

 Предположим, мы хотим сформулировать утверждение, что Джону нравятся все люди. Один из способов сделать это заключается в записи для каждого человека, упоминаемого в базе данных, отдельного факта:
 нравится(джон,альфред).
 нравится(джон,бертран).
 нравится(джон,чарлз).
 нравится(джон,дейвид).
 * * *
 Это было бы очень утомительным, особенно если в нашей программе на Прологе упоминается несколько сот человек. Другой способ выразить факт, что Джону нравятся все люди, - это сказать  Джону нравится любой объект при условии, что этот объект является человеком.  Здесь этот факт представлен в форме  правила  для определения того, что нравится Джону, а не прямого перечисления всех людей, которые ему нравятся. В ситуации, когда Джону мог бы нравиться любой человек, представление утверждения в виде правила является значительно более компактным, чем список фактов.
 В Прологе правила используются в том случае, когда необходимо сказать, что некоторый факт  зависит  от группы других фактов. В естественном языке для выражения правила мы можем использовать слово  если.  Например:
 •  Я пользуюсь зонтом, если идет дождь.
 •  Джон покупает вино, если оно дешевле, чем пиво.
 Правила используются также для выражения определений, например:
   X является птицей, если:
    X является живым существом и  X имеет перья.
 или
   X является сестрой  Y , если:
    X является женщино и  X и  Y имеют одних и тех же родителей.
 В последних примерах мы использовали переменные  X и  Y . Важно помнить, что каждое вхождение переменной в правило обозначает один и тот же объект. Иначе мы разрушили бы саму суть определения. Например, используя приведенное выше определение птицы, мы не смогли бы показать, что Фред является птицей на основании того, что Фидо – это живое существо, а Мэри имеет перья. Этот принцип согласованной интерпретации переменных справедлив также и для правил в Прологе.
 Правило – это некоторое  общее утверждение об объектах и об отношениях между ними.  Например, мы можем сказать, что Фред является птицей, если Фред является живым существом и Фред имеет перья, мы можем также сказать, что Бертрам является птицей, если Бертрам является живым существом и Бертрам имеет перья. Таким образом, мы допускаем, что при каждом новом  использовании  правила переменная обозначает новый, отличный от прежнего объект. Конечно, в рамках конкретного использования правила переменные интерпретируются согласованно, как на это указывалось выше.
 Рассмотрим несколько примеров, начав с правила, содержащего одну переменную и конъюнкцию:
  Джону нравится любой, кому нравится вино,  или,
 другими словами,
  Джону нравится что-то, если чему-то нравится вино,
 или, используя переменные,
  Джону нравится  X , если  X нравится вино.
 В Прологе правило состоит из  заголовка  и  тела  правила. Заголовок и тело соединяются с помощью символа :-, который состоит из двоеточия  : и тире  - . Символ ':-' читается  если.
 Предыдущий пример записывается на Прологе следующим образом:
 нравится(джон,X):- нравится(Х,вино).
 Отметим, что правила также заканчиваются точкой. Заголовком этого правила является нравится(джон,Х). Заголовок правила описывает факт, для определения которого предназначено это правило. Тело правила, в данном случае нравится(Х,вино), описывает конъюнкцию целей, которые должны быть последовательно согласованы с базой данных, для того чтобы заголовок правила был истинным. Например, мы можем сделать Джона более разборчивым в выборе тех, кто ему нравится, просто добавив к телу правила еще несколько целевых утверждений, разделив их запятыми:
 нравится(джон,X):- нравится(Х,вино), нравится(X,пища).
 или, другими словами,  Джону нравится любой, кому нравятся вино и пища.  Или, предположим, что Джону нравится любая женщина, которой нравится вино:
 нравится(джон,Х):- женщина(Х), нравится(Х,вино).
 Всякий раз, когда мы имеем дело с правилом в Прологе, необходимо отмечать все вхождения переменных. В последнем примере переменная  X использована три раза. Всякий раз, как переменная X конкретизируется некоторым объектом (ей присваивается значение), все вхождения  X в пределах  области действия этой переменной  становятся конкретизированными. При каждом употреблении правила  область действия  переменной  X – это все правило, начиная с заголовка и до точки '.' в конце этого правила. Так, если в приведенном выше правиле переменная X оказалась конкретизированной, принимая значение  мэри,  то Пролог попытается согласовать с базой данных целевые утверждения  женщина(мэри)  и  нравится(мэри,вино).
 Теперь, чтобы продемонстрировать правило, использующее более одной переменной, рассмотрим базу данных, содержащую факты о семействе королевы Виктории. Мы будем использовать предикат  родители,  имеющий три аргумента.  родители(Х, Y, Z)  означает:  Родителями   X  являются   Y  и   Z . Переменная  Y обозначает мать, а переменная  Z обозначает отца. Кроме того, мы будем использовать предикаты  женщина  и  мужчина  в их очевидном значении. Некоторая часть этой базы данных могла бы выглядеть следующим образом:
 мужчина(альберт).
 мужчина(эдуард).
 женщина(алиса).
 женщина(виктория).
 родители(эдуард,виктория,альберт).
 родители(алиса,виктория,альберт).
 Здесь мы воспользуемся описанным ранее правилом  является_сестрой.  Правило определяет предикат  является_сестрой , имеющий два аргумента, таким образом, что  является_сестрой(X, Y)  истинно, если  X является сестрой  Y . Обратим внимание на использование в имени предиката символа подчеркивания '_'. Хотя до сих пор не было дано полных правил конструирования имен, отметим, что допускается использование подчеркивания в именах, а более подробно об этом будет сказано в следующей главе. Тогда  X является сестрой  Y , если:
 •  X является женщиной,
 •  X имеет мать  М и отца  F и
 •  Y имеет тех же мать и отца, что и  X .
 Это можно записать в виде следующего правила Пролога:
 является_сестрой(X,Y):- женщина(X), родители(X,M,P), родители(Y,M,P).
 Мы используем переменные  M и  F для обозначения  матери  и  отца,  хотя при желании мы могли бы использовать имена  Мать и  Отец . Отметим, что мы употребляем переменные, которые не появляются в заголовке правила. Эти переменные,  M и  F , обрабатываются таким же образом, как и любая другая переменная. Когда Пролог использует это правило, переменные  M и  F изначально будут неконкретизированными. Этим переменным будет присвоено некоторое значение в момент установления соответствия для предиката  родители(X,M,F) . Однако, как только они конкретизируются, становятся конкретизированными и  все  вхождения переменных  M и  F , соответствующие текущему использованию правила. Следующий пример должен помочь объяснить, как используются эти переменные. Давайте зададим вопрос:
 ?- является_сестрой(алиса,эдуард).
 Имея описанные выше базу данных и правила  является_сестрой и получив такой вопрос, Пролог выполняет следующие действия:
 1. Сначала вопрос сопоставляется с единственным правилом для предиката  является_сестрой , приведенным выше. При этом переменная  X конкретизируется, принимая значение  алиса , и переменная  Y конкретизируется значением  эдуард . Правило, с которым произошло сопоставление, отмечается маркером. Теперь Пролог пытается последовательно согласовать с базой данных три предиката, входящие в тело правила.
  2.  Так как на предыдущем шаге переменной  X присвоено значение  алиса , то первой целью является  женщина(алиса) . Истинность этого предиката следует из списка фактов, так что цель достигнута. Поскольку данная цель согласована, то Пролог отмечает соответствующее ей место в базе данных (третье утверждение в  базе данных).  При этом не  произошло  никаких присвоений значений переменным. Далее Пролог пытается согласовать следующую цель.
 3. Теперь Пролог ищет соответствие для предиката  родители(алиса,M,F) , где переменные  M и  F сопоставимы с любыми аргументами, так как первоначально они неконкретизированы. Факт, с которым происходит сопоставление, есть  родители(алиса, виктория,альберт) , и тем самым вторая цель достигнута. Пролог отмечает маркером соответствующее место в базе данных (шестое утверждение сверху) и записывает, что  M присвоено значение  виктория , a  F – значение  альберт . (Если хотите, вы можете делать соответствующую запись над целевым утверждением в правиле.) Затем Пролог пытается найти соответствие для следующего предиката в правиле.
 4. Теперь Пролог ищет в базе данных факт  родители(эдуард,виктория,альберт),  так как из запроса нам известно, что  Y – это  эдуард,  а из предыдущего шага мы знаем, что  M и  F обозначают  виктория  и  альберт.  Эта цель достигается, поскольку найден подходящий факт (пятое утверждение сверху). Так как это последняя цель в конъюнкции, то и полное целевое утверждение является согласованным с базой данных, и тем самым доказано, что факт  является_сестрой(алиса, эдуард)  является истинным, Пролог отвечает  да.
 Предположим, мы хотим знать, является ли Алиса чьей-либо сестрой. Соответствующий вопрос на Прологе имеет вид
 ?- является_сестрой(алиса,X).
 В ответ на вопрос Пролог выполняет следующие действия:
 1. Вопрос сопоставляется с заголовком единственного правила для предиката  является_сестрой.  Переменная  X , входящая в это правило, конкретизируется значением  алиса.  Так как переменная  X в запросе неконкретизирована, то и переменная  Y в правиле также будет неконкретизированной. Однако эти две переменные теперь становятся  сцепленными.  Как только одной из переменных присваивается некоторое значение, другая переменная становится конкретизированной тем же самым значением. Конечно, в данный момент они неконкретизированы.
 2. Первая цель –  женщина(алиса),  которая достигается так же, как и в предыдущем примере.
 3. Вторая цель –  родители(алиса,М,F).  Эта цель сопоставляется с  родители(алиса,виктория,альберт).  Переменные  M и  F становятся конкретизированными.
 4. Так как переменная  Y пока неизвестна, то третьей целью будет  родители(Y,виктория,альберт),  и она сопоставляется с  родители(эдуард, виктория,альберт).  Переменная  Y конкретизируется значением  эдуард.
 5. Так как все целевые утверждения согласованы с базой данных, то тем самым согласовано и правило в целом, при этом переменная  X  (как известно из вопроса) равна  алиса и  Y равна  эдуард.  Учитывая, что  Y  (в правиле) является  сцепленной  с  X  (в вопросе), то  X также конкретизирована значением  эдуард.  Пролог печатает  Х=эдуард .
 Как обычно, Пролог ожидает, пока вы сообщите ему, хотите ли вы найти все ответы на вопрос. Оказывается, что на данный вопрос имеется более одного ответа. Как Пролог находит оставшиеся ответы (ответ), является содержанием упражнения, приведенного в конце главы.
 Как мы видели до сих пор, существуют два способа предоставить Прологу информацию относительно предиката, подобного предикату  нравится.  Мы можем сделать это, используя как факты, так и правила. В общем случае предикат будет определен смесью фактов и правил. Эти факты и правила, определяющие предикат, называются  утверждениями  [4]  .  Мы будем использовать слово  утверждение  в случаях, когда мы ссылаемся либо на факт, либо на правило.
 В качестве следующего примера, на этот раз не имеющего отношения к монархам, рассмотрим правило:  Человек может украсть что-либо, если этот человек вор и ему нравится вещь и эта вещь является ценной.  На Прологе это записывается следующим образом:
 может_украсть(P,T:- вор(P), нравится(P,T), ценный(T).
 Предикат  может_украсть,  который имеет две переменные  P и  T , представляет отношение:  некоторый человек   P  может украсть вещь   T . Это правило зависит от утверждений, определяющих предикаты  вор, нравится  и  ценный.  Они могут быть представлены либо как факты, либо как правила в зависимости от того, что является более подходящим. Например, рассмотрим следующую базу данных, составленную в том числе из утверждений, обсуждавшихся ранее. Мы добавим к ним номера утверждений, заключенные между специальными скобками /*… */. Именно таким образом в Пролог-системе записывается  комментарий.  Комментарии игнорируются Пролог-системой, но мы можем добавить их в программу для удобства. В последующем обсуждении мы будем ссылаться на номера предложений, представленные в виде комментариев.
 /*1*/ вор(джон).
 /*2*/ нравится(мэри, пища).
 /*3*/ нравится(мэри,вино).
 /*4*/ нравится(джон,X):- нравится(X,вино).
 /*5*/ может_украсть(X,Y):- вор(X), нравится(X,Y).
 Отметим, что определение предиката  нравится  содержит три отдельных утверждения: два факта и правило. Для Пролога это не имеет значения. Единственное различие состоит в том, что когда осуществляется поиск в базе данных, чтобы согласовать с ней некоторую цель, то правило вызывает дальнейший поиск, чтобы согласовать его собственные предикаты-подцели. Факт не имеет подцелей, так что при сопоставлении  с  фактом поиск либо сразу завершается, либо сразу происходит переход к следующему утверждению. Например, давайте проследим за тем, что получится, если обратиться к Прологу с вопросом:  Что Джон может украсть?  Прежде всего этот вопрос транслируется на Прологе:
 ?- может_украсть(джон,Х).
 Чтобы ответить на этот вопрос, Пролог осуществляет поиск следующим образом:
 1. Прежде всего Пролог ищет в базе данных утверждение, описывающее предикат  может_украсть,  и находит такое утверждение. Оно представлено в виде правила и имеет номер 5. Пролог отмечает это место в базе данных. Так как это утверждение является правилом, то, чтобы установить, согласуется ли заголовок правила с базой данных, необходимо попытаться согласовать с ней тело правила. Тогда переменной  X в правиле 5 присваивается значение  джон,  которое берется из вопроса. Как и в предыдущих примерах, мы должны сопоставить неконкретизированные переменные ( X в вопросе и  Y в правиле), так что теперь они будут  сцеплены.  Если вы не уверены, что до конца понимаете, что это значит, то необходимо вернуться назад к примерам с предикатом я вляется_сестрой(X, Y) . Для того чтобы правило выполнилось, необходимо согласовать цели с базой данных. Таким образом, теперь проверяется на согласованность с базой данных первое утверждение  вор(джон).
 2. Эта цель достигается, так как факт  вор(джон)  содержится в базе данных (утверждение 1). Пролог отмечает это место в базе данных, и при этом присвоения значений переменным не происходит. Далее Пролог пытается достигнуть вторую цель, применяя утверждение 5. Так как  X , как и ранее, обозначает  джон,  то теперь Пролог ищет  нравится (джон, Y).  Заметим, что к этому моменту  Y остается неконкретизированной.
 3. Цель  нравится(джон, Y)  сопоставляется с заголовком правила (утверждение 4). Переменная  Y , входящая в цель,  сцепляется  с  X в заголовке правила, и обе эти переменные остаются неконкретизированными. Чтобы доказать это правило, теперь ищется  нравится(Х, вино).
 4. Эта цель достигается, так как она сопоставляется с  нравится (мэри,вино)  - фактом, являющимся утверждением с номером 3. Так что теперь  X становится  мэри.
 5. Так как цель в утверждении 4 достигнута, то согласовано и правило в целом. Факт  нравится(джон, мэри)  следует из утверждения 4, так как переменная  Y в утверждении 5 сцеплена с  X , и ей тоже присваивается значение  мэри.
 6. Утверждение 5 теперь согласуется с базой данных при  Y , имеющем значение  мэри.  Так как переменная  Y была сцеплена со вторым аргументом исходного вопроса, то переменная  X в вопросе конкретизируется, принимая значение  мэри.  Приведем рассуждение, обосновывающее факт  Джон может украсть Мэри:
  Для того чтобы украсть что-либо, прежде всего Джон должен быть вором. Из утверждения 1 следует, что это имеет место. Далее, Джону должен нравиться похищаемый предмет. Из утверждения 4 мы видим, что Джону нравится любой, кому нравится вино. Из утверждения 3 мы видим, что Мэри нравится вино. Следовательно, Джону нравится Мэри. Поэтому оба условия для похищения некоторого объекта имеют место, а значит, Джон может украсть Мэри.
 Заметим, что факт (утверждение 2) о том, что Мэри нравится пища, не имеет никакого отношения к данному конкретному запросу, так как он нигде не понадобился.
 В приведенном примере мы повторно использовали переменные  X и  Y в различных утверждениях. Например, в правиле  может_ украсть X  обозначает объект, который может что-нибудь украсть. Но в правиле  нравится X  обозначает объект, которому что-то нравится. Для того чтобы приведенная программа имела смысл, в Прологе должна иметься возможность указывать, что X может обозначать различные вещи в различных употреблениях утверждений. Помните, что знание  области действия  переменной может разрешить любые неясности. Мы могли бы использовать более мнемоничные имена, чтобы попытаться предотвратить любые неясности, но мы используем простые имена, такие как X, чтобы продемонстрировать работу принципа области действия переменной.

  1.6. Заключение и упражнения

 К этому моменту мы уже обсудили большинство основных черт языка Пролог. В частности, мы рассмотрели:
 • объявление фактов об объектах;
 • задание вопросов относительно известных фактов;
 • роль переменных и их области действия;
 • конъюнкцию как способ описания  и -условий;
 • представление отношений в виде правил;
 • общую схему поиска с механизмом возврата.
 С этим небольшим набором элементарных конструкций можно уже писать полезные программы для работы с простыми базами данных. Скорее всего, наиболее правильно так и поступить, работая над упражнениями, приведенными ниже.
 Чтобы понять, как пользоваться этой книгой, вам следует прочитать предисловие, если вы не сделали это до сих пор. Кроме того, когда вы начнете писать программы для имеющейся в вашем распоряжении системы программирования на Прологе, вам следует обратиться к соответствующему приложению, чтобы узнать, как организуется взаимодействие с системой. Вы также найдете несколько практических советов в гл. 8.
 Теперь, когда вы имеете в своем распоряжении достаточно большой арсенал средств Пролога, вам следует перейти к следующей главе, в которой обсуждаются некоторые вопросы, не рассматривавшиеся в этой главе. Кроме того, мы покажем, какие средства для работы с числами имеются в Прологе. Черты языка, рассматриваемые в нескольких последующих главах, делают очевидными выразительные возможности и удобство Пролога.
  Упражнение 1.2.  При применении правила  является_сестрой  к обсуждавшейся ранее базе данных, содержащей информацию о семействе королевы Виктории, может быть получено несколько ответов. Объясните, как могут быть получены все ответы и каковы они.
  Упражнение 1.3.  В основу этого упражнения положено одно из упражнений из книги Kowalski R.  Logic for Problem Solving,  North Holland, 1979. Предположим, что кем-то уже написаны на Прологе утверждения, определяющие следующие отношения:
 отец(Х,Y) /* X является отцом Y */
 мать(Х, Y) /* X является матерью Y */
 мужчина(Х) /* X – мужчина */
 женщина(Х) /* X - женщина */
 родитель(Х,Y) /* X является родителем Y */
 различны(Х,Y) /* X и Y различны */
 Задача состоит в том, чтобы написать правила для следующих отношений:
 является_матерью(Х) /* X является матерью */
 является_отцом(Х) /* X является отцом */
 является_сыном(Х) /* X является сыном */
 является_сестрой(Х,Y) /* X является сестрой Y */
 дедушка(Х, Y) /* X является дедушкой Y */
 общие_родители(Х,Y) /* X и Y имеют общих родителей*/
 Например, мы могли бы написать правило для предиката  тетя,  при условии что у нас уже имеются правила для  женщина, общие_родители  и  родитель.
 тетя(Х,Y):- женщина(Х), общие_родители(X, Z), родитель(Z,Y).
 Это можно также записать следующим образом:
 тетя(Х,Y):- является_сестрой(Х,Z), родитель(Z, Y).
 при условии что мы имеем правило для отношения  является_сестрой.
  Упражнение 1.4.  Используя правило для отношения  является_сестрой,  определенное в тексте, объясните, каким образом становится возможным, что некто может быть своей собственной сестрой. Как можно было бы изменить это правило, если такое свойство нежелательно? Считайте, что предикат  различны  из упр. 1.3 уже определен.




 ГЛАВА 2 БОЛЕЕ ДЕТАЛЬНОЕ ОПИСАНИЕ


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

 2.1. Синтаксические правила

 Синтаксические правила языка описывают допустимые способы соединения слов. В соответствии с нормами английского языка предложение «I see a zebra» («я вижу зебру») является синтаксически правильным в отличие от предложения «zebra see I а» («зебра видит я»). В первой главе синтаксис Пролога явно не обсуждался, просто показывалось на примерах, как выглядят некоторые элементы Пролога. В данном разделе приводится краткое описание синтаксических правил для уже знакомых нам элементов Пролога.
 Пролог-программы состоят из  термов.  Терм – это либо  константа,  либо  переменная,  либо  структура.  Каждый из этих термов фигурировал в предыдущей главе, но не назывался там таким именем. Терм записывается как последовательность  литер.  Литеры делятся на четыре категории:
 ABCDEFGHIJKLMNOPQRSTUVWXYZ
 abсdefghijklmnopqrstuvwxyz
 0123456789
 +-*/\^<>~:.?@#$&
 Первая строка состоит из  прописных букв.  Вторая строка – из  строчных букв.  В третьей строке –  цифры.  В четвертой строке перечислены  специальные литеры (спецзнаки).  В действительности спецзнаков больше, чем показано в четвертой строке, но остальные используются только в особых случаях, обсуждаемых ниже  [5]  . Для термов каждого типа, таких как константа, переменная, структура, имеются свои правила образования имен термов из литер. Ниже вкратце обсуждаются каждый из типов термов.

  2.1.1. Константы

 Константами являются поименованные  конкретные объекты  или  конкретные отношения.  Существует два вида констант:  атомы  и  целые числа.  Примерами атомов являются имена, приводившиеся в предыдущей главе:
  нравится мэри джон книга вино имеет драгоценности может_украсть
 Специальные символы, используемые Прологом для обозначения вопросов '?-' и правил ':-', также являются атомами. Есть два вида атомов: составленные из букв и цифр и составленные из спецзнаков. Первые, как мы видели в предыдущей главе, должны обычно начинаться со строчной буквы. Атомы, составленные из спецзнаков, как правило, состоят только  из спецзнаков. Иногда возникает необходимость иметь атом, начинающийся с прописной буквы или цифры. Если атом заключается в одиночные кавычки, то его имя может содержать  любые  литеры. И наконец, для простоты чтения внутрь атома можно включать специальную литеру – подчеркивание '_'. Ниже приведено несколько атомов:
 а
 свободный
 =
 'джордж-смит'
 --›
 джордж_смит
 ieh2304
 Следующие объекты не являются атомами:
 2304ieh
 джордж-смит
 Пустой
 _ альфа
 Другой вид констант, целые числа, используется для представления числовых данных, что позволяет выполнять над ними арифметические операции. В предыдущей главе не обсуждались способы выполнения арифметических операций в Прологе, такие средства будут определены ниже. Целые числа состоят только из цифр и не могут содержать десятичной запятой. В этой книге будут использоваться сравнительно небольшие положительные числа, такие как
 0 1 999 512 8192 14765 6224
 Пролог реализован на различных ЭВМ и в зависимости от того, на какой именно ЭВМ работает программист, ему может быть разрешено или не разрешено использовать большие или отрицательные числа. Однако в данной книге приводятся только примеры, допустимые для любой из существующих версий Пролога. Можно утверждать, что всегда разрешается использовать числа из диапазона от 0 до 16 383. Возможно, что на доступной читателю ЭВМ допустимы и другие числа (превышающие 16 383 или отрицательные), однако дальнейшее изложение этого не учитывает. Может быть, это покажется удивительным, однако в задачах, в которых оказался полезным Пролог, как правило, не нужны средства для работы с очень большими, дробными или отрицательными числами. Тем не менее, поскольку Пролог является расширяемым языком, программист, обладающий соответствующими ресурсами, может без особого труда добавить к системе предикаты, определяющие такие возможности. Например, некоторые Пролог-системы предоставляют пользователям библиотечные программы, определяющие операции над рациональными числами и числами произвольной точности.

  2.1.2. Переменные

 Второй разновидностью термов в Прологе являются переменные. Переменные внешне похожи на атомы, за исключением того, что они начинаются с прописной буквы или знака подчеркивания '_'. Переменная служит для представления объекта, на который нельзя сослаться по имени. Здесь можно провести аналогию с использованием местоимений в естественном языке. В приведенных выше примерах фигурировали переменные с такими именами как  X ,  Y и  Z . Однако имена могут быть сколь угодно длинными, например:
 Ответ
 Ввод
 Большая_Выплата
 _3_слепые_мыши
 Иногда возникает необходимость в использовании переменной, имя которой не будет нигде употребляться. Например, если необходимо определить, нравится ли кому-нибудь Джон, и при этом не важно, кому именно он нравится, можно использовать  анонимную переменную.
 Анонимная переменная – это одиночный знак подчеркивания '_'. Наш пример с Джоном записывается на Прологе следующим образом:
 ?- нравится(_,джон).
 Если в одно утверждение входят несколько анонимных переменных, их можно интерпретировать неоднозначно. Это характерная особенность, присущая только анонимной переменной. Она позволяет избавить программиста от необходимости придумывать разные имена переменным в тех случаях, когда эти имена в утверждении нигде больше не употребляются.

  2.1.3. Структуры

 Третьим видом терма, присутствующим в Пролог-программах, является структура. Структура – это единый объект, состоящий из совокупности других объектов, называемых компонентами. Компоненты группируются в структуру для удобства их использования.
 В реальной жизни одним из примеров структур является карточка-указатель для библиотечной книги. Карточка-указатель содержит несколько компонент: сведения об авторе, название книги, дату издания, место, где книга хранится в библиотеке, и т. д. Некоторые из компонент в свою очередь тоже можно разбить на компоненты. Например, сведения об авторе состоят из фамилии и инициалов.
 Структуры служат средством организации данных в программе, поскольку они позволяют рассматривать как единый объект (карточку-указатель) группу отдельных элементов данных. Способ, которым осуществляется разложение данных на компоненты, зависит от решаемой задачи, В книге будут приведены некоторые рекомендации на этот счет.
 Структуры полезны также в тех случаях, когда имеется общий тип и может существовать много конкретных экземпляров объектов этого типа. Например, книги. В главе 1 приводился факт
 имеет(джон, книга).
 обозначающий, что у Джона есть некоторая конкретная книга. Если затем будет сформулирован факт
 имеет(мэри, книга).
 то это означает, что у Мэри есть тот же самый объект, что и у Джона, поскольку в обоих фактах фигурирует одно и то же имя. Не существует другого способа указания факта, что объекты различны, кроме присвоения им различных имен. Можно было бы уточнить приведенные факты:
 имеет(джон,грозовой_перевал).
 имеет(мэри,моби_дик).
 явно указав, какие именно книги есть у Джона и Мэри. Однако в больших программах обилие различных констант, смысл которых из контекста не очевиден, может вызвать затруднения. Человек, читающий данную Пролог-программу, может не знать, что константа  грозовой_перевал  представляет собой название книги Эмили Бронте, жившей в Йоркшире (Англия) в 19-м веке. Можно было бы, скажем, предположить, что Джон назвал так своего любимого кролика. С помощью структур можно предоставить читателю необходимый контекст.
 Структура записывается на Прологе с помощью указания ее  функтора  и  компонент.  Компоненты заключаются в круглые скобки и разделяются запятыми. Функтор записывается перед открывающей круглой скобкой. Рассмотрим факт, заключающийся в том, что у Джона есть книга с названием «Грозовой перевал», написанная Эмили Бронте:
 имеет(джон,книга(грозовой_перевал, бронте)).
 Внутри факта  имеет находится структура с именем  книга,  имеющая две компоненты: название и автор. Поскольку структура  книга  появляется внутри факта как один из его аргументов, она действует как объект, принимая участие в отношении. При желании можно было бы создать еще одну структуру – для идентификации автора, поскольку существовали три писательницы с фамилией Бронте:
 имеет(джон,книга(грозовой_перевал, автор(эмили, бронте))).
 Структуры с переменными в качестве компонент могут появляться в вопросах. Например, можно было бы спросить, есть ли у Джона какая-либо книга сестер Бронте:
 ?- имеет(джон,книга(Х,автор(Y, бронте))).
 Если будет доказано, что это утверждение согласовано с базой данных, то значением  X будет название книги, а значением  Y – имя автора. В тех случаях, когда переменные в дальнейшем не используются, можно употребить анонимную переменную:
 ?- имеет(джон, книга(_, автор(_,бронте))).
 Напомним, что анонимные переменные не «сцепляются» друг с другом.
 Структуру  книга  можно было бы еще улучшить, добавив аргумент, указывающий экземпляр книги. Например, третий аргумент, на место которого следует ставить целое число, дал бы нам возможность однозначно идентифицировать книгу:
 имеет(джон, книга (улисc, автор(джеймс,джойс), 3129)).
 что соответствует следующей фразе на естественном языке:  Джон имеет 3129-й экземпляр книги Джеймса Джойса «Улисс».  Если у читателя сложилось впечатление, что синтаксис структур совпадает с синтаксисом фактов, то нам остается только подтвердить его правоту. Предикат (используемый в фактах и правилах) является на самом деле функтором некоторой структуры. Аргументы факта или правила – это компоненты структуры. Представление самих Пролог-программ в виде структур обладает многими достоинствами. Сейчас преждевременно обсуждать эти достоинства, однако читателю все же следует помнить, что все части Пролога, даже сами Пролог-программы, состоят из констант, переменных и структур.

 2.2.  Литеры

 Имена констант и переменных образованы цепочками литер. Хотя для каждого вида имени (атом, целое число, переменная) имеются специальные правила, указывающие, из каких литер оно может составляться, полезно знать, что представляет собой весь набор литер, распознаваемых Прологом. Это связано с тем, что литера сама может рассматриваться как самостоятельный элемент данных. Поскольку мы уже знакомы с целыми числами, можно теперь описать, как литеры представляются небольшими целыми числами. Над литерами чаще всего выполняются операции «ввод» и «вывод». Эти операции будут обсуждаться в  гл.  5.
 В Прологе имеются два типа литер:  печатаемые  литеры и  непечатаемые  литеры. Печатаемые литеры обладают визуальным образом, появляющимся на терминале при выводе. Непечатаемые литеры такого образа не имеют, но при выводе они вызывают выполнение некоторых действий. Этими действиями могут быть пропуск пустого места («печать» пробела), переход на новую строку, подача звукового сигнала. Ниже приведены все печатаемые литеры, которые можно использовать в Пролог-программах.
 ABCDEFGHIJKLMNOPQRSTUVWXYZ
 abedefghijklmnopqrstuvwxyz
 0123456789
 !"#$%&'()=–~^|\{}[] _`@ +;*:‹›,.?/
 Читатель должен заметить, что данный набор более полон, чем приводившийся в начале главы. Некоторые из этих литер имеют специальное значение. Например, круглые скобки используются для выделения компонент структур. Однако, как мы увидим в последующих главах, любая литера может рассматриваться в Пролог-программе как и информационный элемент данных. Литеры могут печататься, вводиться с клавиатуры, сравниваться и принимать участие в арифметических операциях.
 Литеры на самом деле интерпретируются как небольшие целые числа – из диапазона от 0 до 127. Каждой литере поставлено в соответствие некоторое целое число, называемое ее ASCII-кодом. Аббревиатура ASCII расшифровывается следующим образом: American Standard Code for Information Interchange (Американский стандартный код для обмена информацией) [6] . Этот код широко используется на вычислительных машинах и в языках программирования во всем мире. Таблицу кодов ASCII можно найти почти в любом руководстве по работе на ЭВМ. Коды букв упорядочены в алфавитном порядке, так что выяснение порядка следования литер в алфавите сводится к сравнению их кодов с помощью операторов отношений, описываемых ниже в данной главе. Коды всех печатаемых литер больше 32.
 Хотя польза кода ASCII в данный момент может быть для читателя и не очевидной, мы вновь вернемся к этому вопросу в разд. 3.2. и 3.5.

  2.3. Операторы

 Иногда удобно записывать некоторые функторы как  операторы.  Это особая форма синтаксиса, облегчающая чтение соответствующих структур. Например, арифметические операции обычно записываются как операторы. В арифметическом выражении  x+y*z  знаки сложения и умножения являются операторами. Если же данное арифметическое выражение записать в обычном для структур виде, то оно будет выглядеть следующим образом:  +(x,*(y,z)) . Однако в некоторых случаях операторная форма записи удобнее потому, что мы со школьных лет привыкли использовать ее в арифметических выражениях. Кроме того, структурная форма требует заключения аргументов функтора в круглые скобки, что иногда обременительно.
 Важно отметить, что операторы не вызывают выполнения каких-либо арифметических операций. Так, в Прологе  3+4 и  7 означают разные объекты. Терм  3+4  - другой способ записи терма  +(3,4) , который является структурой. Позже будет описан способ интерпретации структур как арифметических выражений и вычисления их в соответствии с правилами арифметики.
 Для начала необходимо знать, как читать арифметические выражения, содержащие операторы. Это требует знания трех свойств каждого оператора: его  позиции,  его  приоритета  и его  ассоциативности.  В данном разделе будут описаны правила использования операторов Пролога с учетом этих свойств, но пока без излишних подробностей. В Пролог-программе можно определить много различных видов операторов, но мы будем иметь дело только с хорошо знакомыми атомами +, -, * и /.
 Синтаксис терма, содержащего операторы, частично зависит от их  позиций.  Операторы, подобные знакам сложения (+), вычитания (-), умножения (*) и деления (/), записываются между своими аргументами и называются поэтому  инфиксными  операторами. Можно также помещать операторы перед их аргументами. Так, в выражении - х+у  минус перед  х  обозначает арифметическую операцию изменения знака. Операторы, записываемые перед своими аргументами, называются  префиксными  операторами. Наконец, некоторые операторы могут помещаться после своего аргумента. Например, оператор вычисления факториала, употребляемый математиками, помещается после числа, для которого необходимо вычислить факториал. В математических обозначениях факториал  х  записывается как  x !  t  где восклицательный знак обозначает операцию вычисления факториала. Операторы, записанные после своих аргументов, называются  постфиксными  операторами. Таким образом, позиция оператора указывает его место по отношению к своим аргументам. Все операторы, рассматриваемые в следующем разделе, являются  инфиксными.
 Теперь рассмотрим приоритет операторов. Когда нам необходимо проинтерпретировать терм  х+y*z как арифметическое выражение, мы знаем, что для того, чтобы получить правильное значение, нужно сначала перемножить  у  и  z,  а затем прибавить  х.  Этими знаниями мы обязаны школе, где нас научили, что умножения и деления выполняются до сложений и вычитаний; исключениями являются случаи, когда порядок операций задается скобками. С другой стороны, структурная форма  +(x,*(y,z))  явно показывает порядок выполнения операций, поскольку структура с функтором * является аргументом структуры с функтором +. Для того чтобы ЭВМ правильно произвела соответствующие вычисления, необходимо сначала выполнить умножение – тогда в структуре с + будут известны значения аргументов. Таким образом, для использования операторов необходимы правила, указывающие порядок выполнения операций. Именно этой цели служит  приоритет.
 Приоритет оператора определяет, какая операция выполняется первой. В Прологе каждый оператор связан со своим  классом приоритета.  Класс приоритета представляет собой целое число, величина которого зависит от конкретной версии Пролога. Однако в любой версии оператор с большим приоритетом имеет класс приоритета, более близкий к 1. Если классы приоритетов принимают значения из диапазона от 1 до 255, то оператор с первым классом приоритета выполняется первым, до выполнения операторов, принадлежащих (например) к классу 129. В Прологе операторы умножения и деления принадлежат к более высокому классу приоритетов, чем сложение и вычитание, поэтому терм  а-b/с эквивалентен терму  -(a,/(b,c)) . Точное соответствие между операторами и классами приоритетов в данный момент не существенно, однако желательно запомнить относительный порядок выполнения операций.
 Наконец, рассмотрим свойство  ассоциативности  операторов. Необходимость знания этого свойства становится очевидной, когда нам требуется определить порядок выполнения операторов с одинаковым приоритетом. Например, какому выражению эквивалентно выражение «8/2/2» – «(8/2)/2» или «8/(2/2)»? В первом случае при интерпретации выражения было бы получено значение 2, во втором 8. Для того чтобы иметь возможность разделить эти два случая, необходимо знать, является ли данный оператор  левоассоциативным  или  правоассоциативным. Левоассоциативный  оператор должен иметь слева операции  одинакового  или  низшего  приоритета, а справа – операции  низшего  приоритета. Например, все арифметические операции (сложить, вычесть, умножить и поделить) являются левоассоциативными. Это означает, что выражения, подобные «8/4/4», интерпретируются как «(8/4)/4», а выражение «5+8/2/2» эквивалентно «5+((8/2)/2)».
 На практике в выражениях, понимание которых затрудняется правилами приоритета и ассоциативности, люди стремятся использовать круглые скобки. В нашей книге этот прием тоже будет использоваться, однако для полного понимания операторов надо знать синтаксические правила.
 Напомним, что структура, образованная арифметическими операторами, подобна любой другой структуре. На самом деле никакие арифметические действия не выполняются до тех пор, пока не встретится предикат  'is'  (есть), описанный в разд. 2.5.

 2.4. Равенство и установление соответствия

 В Прологе существует особый предикат  равенство,  являющийся инфиксным оператором, обозначаемым литерой '='. Когда делается попытка доказать согласованность с базой данных целевого утверждения
 ?- X = Y.
 (произносится  X равно Y),  Пролог пытается  установить соответствие  между  X и  Y ; целевое утверждение «доказуемо», если такое соответствие имеется. Это действие можно представить себе как  попытку сделать   X  и   Y  равными.  Предикат равенства является  встроенным,  т. е. он уже определен в Пролог-системе. Предикат равенства работает так, словно определен следующий факт: X = X.
 Внутри всякого утверждения  X всегда равно  X , и это свойство использовано нами при определении предиката равенства.
 При согласовании с базой данных цели вида  X = Y , где  X и  Y – любые термы, в которых могут содержаться неконкретизированные переменные, действуют следующие правила:
 • если  X представляет собой неконкретизированную переменную, а переменная  Y конкретизирована (какое именно значение ей дано, неважно), то  X и  Y равны. Кроме того,  X станет конкретизированной – ей будет дано то же значение, что и  Y . Например, следующий вопрос приведет к тому, что  X будет присвоено значение в виде структуры:  ехать(клерк, велосипед) :
 ?- ехать(клерк, велосипед) = X.
 • целые числа и атомы всегда равны самим себе. Например, попытки согласовать следующие целевые утверждения дадут результаты, показанные справа:
 полицейский = полицейский /* верно */
 бумага = карандаш /* ложно */
 1066=1066 /* верно */
 1206=1583 /* ложно */
 • Две структуры равны, если они имеют один и тот же функтор и одинаковое число аргументов, причем все соответствующие аргументы равны. Например, при согласовании следующего целевого утверждения  X будет присвоено конкретное значение  велосипед :
 ехать(клерк,велосипед) = ехать(клерк,Х).
 Структуры могут быть вложены одна в другую на любую глубину. Если такие вложенные структуры проверяются на равенство, проверка займет больше времени, поскольку необходимо проверить все структуры. Попытка согласовать следующую цель:
 a(b,C,d(e,F,g(h,i,J)))=a(B,c,d(E,f,g(H,i,j))).
 будет успешной,  а  переменные  В ,  С ,  F ,  Е ,  J будут конкретизированы, им будут присвоены соответственно значения  b ,  с ,  f ,  e ,  j . Что произойдет, если мы попытаемся приравнять две неконкретизированные переменные? Это специальный случай первого из вышеприведенных правил. Так, цель будет согласована и две переменные станут  сцепленными.  Если две переменные сцеплены, то при конкретизации одной из них второй переменной будет автоматически присвоено то же самое конкретное значение, что и первой. Таким образом, в следующем правиле второй аргумент будет конкретизирован так же, как первый:
 ничего_не_делать(Х,Y):- Х = Y.
 Целевое утверждение X=Y всегда верно (т. е. согласуется с базой данных), если один из аргументов неконкретизирован. Более простой способ записи такого правила заключается в использовании того факта, что переменная равна самой себе:
 ничего_не_делать(Х,Х).
 Пролог предоставляет также предикат '\=' соответствующий  не равно.  Целевое утверждение  Х\=Y верно в тех случаях, когда не доказуемо утверждение  X=Y , и наоборот. Таким образом,  Х\=Y означает, что  X  не может быть сделано равным   Y .
  Упражнение 2.1.  Скажите, верны ли следующие целевые утверждения, какие переменные будут конкретизированы и какие им будут даны значения:
 пилоты(А, Лондон) = пилоты(лондон, париж)
 точка(Х,Y,Z) = точка(Х1,Y1,Z1) = слово(буква)
 существительное(альфа) = альфа
 'викарий' = викарий
 f(X,X) = f(a,b)
 f(X,a(b,c)) = f(Z,a(Z,c)

  2.5. Арифметика

 ЭВМ часто используют для выполнения действий над числами. С помощью арифметических операций можно сравнивать числа и проводить вычисления. В данном разделе будут приведены примеры такого использования арифметических операций.
 Рассмотрим сначала сравнение чисел. Для двух заданных чисел всегда можно сказать,  равно ли  одно число другому,  меньше ли  одно число другого,  больше ли  одно число другого. Пролог предоставляет некоторые «встроенные» предикаты, позволяющие
 сравнивать числа. Для этого могут использоваться обсуждавшиеся в разд. 2.4 предикаты '='и '\='. Их аргументами могут быть конкретизированные переменные, значениями которых являются целые числа, а также целые числа, записанные в виде констант. Существует еще несколько предикатов, позволяющих сравнивать числа. Перечислим здесь все эти предикаты, отметив предварительно, что каждый из них можно использовать в форме инфиксного оператора.
  X = Y  X и Y представляют одно и то же число
  X \= Y  X и Y представляют разные числа
  X ‹ Y  X меньше Y
  X › Y  X больше Y
  X =‹ Y  X меньше или равно Y
  X ›= Y  X больше или равно Y
 Отметим, что символ «меньше или равно» записывается не так, как во многих других языках программирования (обычно ‹=). Это сделано в Прологе для того, чтобы программист мог использовать похожий на стрелку атом ‹= для своих собственных нужд.
 Поскольку операторы сравнения являются предикатами, можно было бы предположить, что в Прологе допустим следующий факт:
 2›3.
 утверждающий, что 2 на самом деле больше 3. Факты, подобные этому, с формальной стороны полностью соответствует правилам Пролога. Однако Пролог не разрешает добавлять факты к «встроенным» предикатам. Такая особенность предотвращает непредсказуемые изменения смысла встроенных предикатов. В главе 6 будут описаны все встроенные предикаты, в том числе и те, с которыми мы уже познакомились.
 В качестве первого примера использования чисел предположим, что у нас есть база данных, содержащая сведения о принцах, правивших Уэльсом в 9-м и 10-м веках. Предикат  правил(Х,Y,Z)  истинен, если принц с именем  X находился у власти с года  Y по год  Z . Список фактов базы данных выглядит следующим образом:
 правил(родри,844,878).
 правил(анаравд,878,916).
 правил(хивел_дда,916,950).
 правил(лаго_ад_идвал,950,979).
 правил(хивел_аб_иеуаф,979,985).
 правил(кадваллон,985,986).
 правил(маредудд, 986,999).
 Теперь предположим, что мы хотим узнать, кто был на троне Уэльса в каком-то конкретном году. Можно было бы определить правило, аргументами которого являлись бы имя и дата и которое просматривало бы базу данных и сравнивало заданную дату с теми, что указаны в фактах. Давайте определим предикат  принц(X, Y),  который истинен, если принц по имени  X был на троне в год  Y :
 X был
   принцем в год Y, если:
   X правил с года А по год В и  
   Y находится между А и В или совпадает с А или В.
 Первое целевое утверждение будет согласовываться с базой данных путем поиска подходящего факта. Второе целевое утверждение верно, если  Y равно  А , или  Y равно  В , или  Y лежит между  А и  В . Для проверки можно использовать утверждения  Y›=А и  Y=‹В . Переписав это на Прологе, получаем следующее правило:
 принц (X,Y):-правил(Х,А,В),Y ›= А,Y =‹ В.
 Ниже приведено несколько возможных запросов и ответов, даваемых Пролог-системой.
 ?- принц(кадваллон,986).
 да
 ?- принц(родри,1979).
 нет
 ?- принц(Х,900).
 Х = анаравд
 да
 ?- принц(X,979).
 X = лаго_ад_идвал ;
 X = хивел_аб_иеуаф да
 Заметьте использование переменных в последних примерах. Убедитесь, что вы понимаете, как работает механизм поиска Пролога при ответе на подобные вопросы.
 Арифметические операции могут также использоваться для вычислений. Например, если имеются сведения о населении и площади некоторой страны, то можно вычислить среднюю плотность населения для этой страны. Средняя плотность населения показывает, сколь тесно было бы в данной стране, если бы ее население было равномерно распределено по всей ее территории.
 Рассмотрим следующую базу данных, содержащую сведения о населении и площади некоторых стран в 1976 г. Для представления связи между страной и ее населением будет использоваться предикат  нас.  В наши дни население обычно характеризуется довольно большими числами. Не все версии Пролога позволяют работать с такими числами. Поэтому будем исчислять население в миллионах:  нас(Х, Y)  означает, что население страны  X составляет примерно « Y миллионов» людей. Предикат  площадь  будет обозначать связь между страной и ее площадью (в миллионах квадратных километров):
 нас(сша,203).
 нас(индия, 548).
 нас(китай,800).
 нас(бразилия,108).
 площадь(сша,8).
 площадь(индия,3).
 площадь(китай,9).
 площадь(бразилия,8).
 Теперь для того, чтобы найти среднюю плотность населения некоторой страны, мы должны использовать правило, гласящее, что значение плотности получается делением числа, представляющего население, на число, представляющее площадь.
 Введем предикат  плотность(Х,  Y), где X – это страна, a Y – плотность населения в данной стране, и запишем соответствующее правило на Прологе:
 плотность(X,Y):-нас(Х,Р), площадь(Х,А), Y is Р/А.
 Данное правило читается следующим образом:
  Плотность населения страны X представляется числом Y, если:
   Население X  -  это Р, и Площадь X  -  это A, и Y вычисляется делением Р на A.
 В правиле используется оператор деления '/' введенный в предыдущем разделе. Операция деления выполняется на самом деле как целочисленное деление, сохраняющее только целую часть результата.
 Новым здесь является инфиксный оператор  'is' . Его правый аргумент – терм, интерпретируемый как арифметическое выражение. Для того чтобы выполнить  'is' , Пролог сначала вычисляет его правый аргумент в соответствии с правилами арифметики. Результат вычислений проверяется на соответствие с левыми аргументами, чтобы определить, доказуемо ли целевое утверждение. В вышеприведенном примере переменная  Y до исполнения  is не конкретизирована, и она остается в таком состоянии до вычисления выражения. Когда выражение вычислено,  Y принимает значение, равное полученной величине. Это означает, что должны быть известны значения всех переменных, находящихся справа от  is .
 Предикат  is нужно использовать каждый раз, когда требуется вычислить арифметическое выражение. Напомним, что конструкции вида  Р/А являются такими же обычными структурами Пролога, как и  автор(эмили,бронте).  Но если некоторая структура интерпретируется как арифметическое выражение, то к ней применяется специальная операция, заключающаяся в фактическом выполнении арифметических действий над двоичными представлениями элементов структуры и получении соответствующего результата. Эта операция называется  вычислением  арифметического выражения. Не любую структуру можно вычислить как арифметическое выражение. Например, очевидно, что нельзя вычислить структуру  автор,  поскольку функтор  автор  не определен как арифметическая операция.
 Вернемся к примеру со средней плотностью населения. Нетрудно видеть, что типичные вопросы и ответы на них выглядят следующим образом:
 ?- плотность(китай,X).
 X=89
 ?= плотность(турция,X).
 нет
  Х=89  в первом вопросе представляет собой ответ Пролог-системы, означающий 89 человек на квадратный километр. Второй запрос не выполним, поскольку в базе данных нашего примера невозможно найти сведения о населении Турции.
 Набор допустимых арифметических операций зависит от используемой ЭВМ. Однако все Пролог-системы обеспечивают выполнение следующих операций:
  X+Y  сумма X и Y
  X–Y  разность X и Y
  X*Y  произведение X и Y
  X/Y  частное от деления X на Y
  X mod Y  остаток от деления X на Y
 Этот список вместе со списком операторов сравнения, приведенным выше, содержит все, что необходимо для решения простых арифметических задач. Поскольку Пролог в основном ориентирован на нечисловые задачи, арифметические возможности не так важны, как в других языках программирования.

 2.6. Общая схема согласования целевых утверждений

 Для ответа на вопрос, поступивший от программиста, Пролог выполняет решение некоторой задачи. Вопрос содержит  конъюнкцию  целевых утверждений, которые необходимо попытаться доказать, т. е. проверить на согласованность с базой данных. Для доказательства целевых утверждений Пролог использует известные  утверждения.  Факт может привести к немедленному доказательству (согласованию) целевого утверждения, в то время как правило может только свести данную задачу к конъюнкции предикатов-подцелей. Однако использование некоторого утверждения возможно только, когда оно «подходит» к рассматриваемому целевому утверждению, т. е. соответствует ему (сопоставимо с ним). Если целевое утверждение не доказано, возбуждается  процесс возврата.  Процесс возврата заключается в пересмотре проделанной работы и попытках передоказать (вновь согласовать) целевые утверждения путем поиска альтернативных путей доказательства. Более того, если программист неудовлетворен ответом на свой вопрос, он может сам инициировать процесс возврата, нажав на клавиатуре клавишу ';', после того как Пролог информирует его о найденном решении. В данном разделе будут представлены диаграммы, показывающие, как Пролог пытается доказать и передоказать целевые утверждения.

 2.6.1. Успешное доказательство конъюнкции целевых утверждений

 Пролог пытается согласовать с базой данных входящие в конъюнкцию целевые утверждения в том порядке, в каком они написаны (слева направо), где бы они ни появились – в теле правила или в вопросе. Это означает, что Пролог не будет проверять некоторое утверждение, пока не будет доказан его сосед слева. А сосед справа будет рассматриваться только после доказательства данного целевого утверждения. Рассмотрим следующую простую программу о семейных связях:
 родители (С,M,F):- мать(С,М), отец(C,F).
 мать(джон,анна).
 мать(мэри,анна).
 отец(мэри,фред). отец(джон,фред).
 Давайте рассмотрим последовательность событий, позволяющую дать ответ на вопрос:
 ?-женщина(мэри), родители(мэри,М,Р), родители(джон,М,Р).
 Данный вопрос позволяет определить, является ли  мэри сестрой  джона . Для того чтобы дать ответ Прологу, необходимо согласовать с базой данных последовательность подцелей, приведенных на рис. 2.1.
 Представим целевые утверждения в виде прямоугольников, распределенных по странице. Стрелка, начинающаяся в верхней части страницы, указывает, какие целевые утверждения уже согласованы. Прямоугольники, через которые стрелка уже прошла, соответствуют согласованным целевым утверждениям. Прямоугольники, лежащие ниже острия стрелки, соответствуют целевым утверждениям, которые Пролог еще не рассматривал. При выполнении программы стрелка движется вверх и вниз по странице в соответствии с переходом Пролога от одного целевого утверждения к другому. Будем называть ее  цепочкой доказательств.  В данном примере стрелка начинается в верхней части страницы, как показано выше. По мере согласования трех целевых утверждений она будет удлиняться вниз, проходя через соответствующие прямоугольники. Конечная ситуация представлена на рис. 2.2. Отметим, что в ходе доказательства согласованности целевых утверждений с базой данных были найдены значения для переменных  М и  F .
 Такая диаграмма иллюстрирует общую структуру происходящего, но она не показывает,  как  доказывались эти три целевых утверждения. Для того чтобы показать это, поместим внутрь прямоугольников больше информации. Давайте посмотрим, как доказывалось второе целевое утверждение. Доказательство согласованности целевого утверждения с базой данных включает в себя поиск в базе данных  соответствующих  (сопоставимых) утверждений, пометку этого места базы данных и затем доказательств возникших подцелей. Этот процесс для второго целевого утверждения можно проиллюстрировать, включив в прямоугольник  родители  индикацию выбранного утверждения и возникшие подцели. Выбранное утверждение обозначается числом в скобках, в данном случае  (1) . Это число указывает  номер выбранного утверждения в наборе утверждений с соответствующим предикатом.  Таким образом, число  1 означает, что было выбрано первое утверждение с данным предикатом. Эта информация достаточна для отметки места в базе данных. Подцели заключены в маленькие прямоугольники, помещенные в прямоугольник данного целевого утверждения. В момент, когда выбрано утверждение  родители,  ситуация выглядит так, как показано на рис. 2.3.
 Рис. 2.3.
 Стрелка вошла в прямоугольник  родители  и прошла через скобки, указывая, что выбрано некоторое утверждение. Данное утверждение создало две подцели –  мать  и  отец. В  данный момент для получения ответа на вопрос необходимо, чтобы стрелка прошла через два маленьких прямоугольника, вышла из прямоугольника  родители  и затем прошла через второй прямоугольник  родители.  Когда стрелка проходит через маленькие прямоугольники, необходимо выполнить те же самые шаги: выбор соответствующего утверждения и доказательство порождаемых им подцелей. В данном примере для каждого из этих двух целевых утверждений в базе данных находится соответствующий факт, и их согласованность с базой данных доказывается. На рис. 2.4 приведено более детальное изображение ситуации в момент получения ответа на вопрос.
 Рис. 2.4.
 Отметим, что для полноты картины нам необходимо было бы показать, как доказываются целевые утверждения  женщина(мэри)  и  родители(джон,анна,фред).  Однако столь подробная диаграмма не поместилась бы на одной странице.
 Данный пример иллюстрирует общую схему рассмотрения целевых утверждений, объединенных в конъюнкцию, для случая, когда все цели согласуются с базой данных. Стрелка перемещается вниз по странице, по очереди проходя через прямоугольники. Когда стрелка входит в какой-либо прямоугольник, выбирается некоторое утверждение и отмечается его позиция. Если данное утверждение сопоставимо с целью и является фактом, стрелка может покинуть прямоугольник (такая ситуация имела место для целевых утверждений  мать  и  отец).  Если же утверждение сопоставимо с целью, но является правилом, создаются прямоугольники для подцелей, и стрелка должна пройти через них, прежде чем она сможет покинуть первоначальный прямоугольник.

  2.6.2. Рассмотрение целевых утверждений при использовании механизма возврата

 Когда целевое утверждение недоказуемо (проверены все возможные утверждения или пользователь нажал клавишу ';'), «цепочка доказательств» проходит назад тот путь, по которому она пришла в данную точку. Она возвращается в покинутые перед этим прямоугольники для того, чтобы попытаться  передоказать  (вновь согласовать) соответствующие целевые утверждения. Когда стрелка возвращается в то место, где было выбрано какое-то утверждение (это событие изображается числом в скобках), Пролог пытается найти альтернативное утверждение, соответствующее данной цели. Сначала делаются неопределенными все переменные, которые были конкретизированы в ходе доказательства данного целевого утверждения. Затем возобновляется поиск в базе данных, начиная с того места, где был оставлен маркер. Если будет найдено другое утверждение, соответствующее целевому, Пролог помечает это место, и дальше события развиваются, как было описано выше в разд. 2.6.1. Отметим, что рассмотрение любых целевых утверждений, находящихся «ниже» данного (даже если они были пройдены в ходе рассмотрения предыдущей альтернативы), всегда начинается с самого начала. Пролог пытается доказать их без учета положения маркера (т. е. это не передоказательство). Если не удается найти другое подходящее утверждение, данное целевое утверждение считается недоказуемым и стрелка продолжает возвращаться назад до следующего маркера. В нашем примере, если целевое утверждение  родители(джон,анна,фред)  недоказуемо, стрелка уйдет назад из прямоугольника  родители(джон,анна,фред)  и войдет в прямоугольник  родители (мэри,анна,фред)  снизу для того, чтобы попытаться передоказать данное целевое утверждение (см. рис. 2.5).
 Рис. 2.5.
 Отступая дальше, стрелка достигнет места, где было выбрано утверждение, соответствующее целевому утверждению отец. В первую очередь освобождаются все переменные, которые были конкретизированы в результате использования данного утверждения. Это означает, что переменная  F вновь становится неконкретизированной. Затем Пролог просматривает базу данных, начиная с утверждения, следующего за первым утверждением с предикатом  отец  (здесь находится маркер), пытаясь найти альтернативное утверждение. Если предположить, что  мэри  имеет только одного отца, то этот процесс успехом не завершится. Поэтому стрелка продолжит отступление. Она покинет прямоугольник  отец(мэри, F)  (это целевое утверждение недоказуемо) и вернется в прямоугольник  мать(мэри,анна)  (для того, чтобы попытаться передоказать данное целевое утверждение) (см. рис. 2.6).
 Рис. 2.6.
 Отступление стрелки будет продолжаться до успешного доказательства соответствующего целевого утверждения.
 Эти примеры иллюстрируют общую схему повторного рассмотрения целевых утверждений в процессе возврата. Когда некоторое целевое утверждение недоказуемо, стрелка возвращается из соответствующего прямоугольника в прямоугольник с предшествующим целевым утверждением. Стрелка отступает до тех пор, пока не встретится маркер. Все переменные, которые были конкретизированы в результате предыдущего выбора сопоставимого утверждения, становятся неконкретизированными. Затем Пролог возобновляет поиск в базе данных сопоставимого утверждения, начиная с маркера. Если сопоставимое утверждение будет найдено, новое место помечается маркером, создаются прямоугольники для целевых подутверждений и стрелка опять начинает движение вниз. В противном случае стрелка продолжает отступать вверх в поисках другого маркера.

  2.6.3. Установление соответствия

 Правила, определяющие, подходит ли некоторое утверждение для согласования с целевым утверждением, выглядят следующим образом. Отметим, что при выборе утверждения все переменные сначала неконкретизированы.
 • Неконкретизированная переменная соответствует любому объекту. Этот объект становится значением переменной.
 • Целое число или атом соответствуют только самим себе.
 • Между структурами можно установить соответствие, только если они имеют одинаковый функтор, одинаковое число параметров и соответствующие параметры соответствуют друг другу.
 Особым случаем является установление соответствия между двумя неконкретизированными переменными. В этом случае мы говорим, что переменные  сцеплены.  Две сцепленные переменные обладают следующим свойством: как только одна из них принимает конкретное значение, то же самое конкретное значение принимает и другая.
 Если читатель заметил сходство между установлением соответствия и приравниванием аргументов (разд. 2.4), то он совершенно прав. Дело в том, что предикат '=' пытается сделать свои аргументы равными путем установления соответствия между ними.
 Попытаемся применить на практике наши знания об операторах, арифметических действиях и установлении соответствия. Предположим, что в базе данных находятся следующие факты:
 сумма(5).
 сумма(З).
 сумма(X+Y).
 Рассмотрим вопрос:
 ?- сумма(2+3).
 Какой из вышеприведенных фактов будет соответствовать данному запросу? Если вы думаете, что таковым будет первый факт, вам следует вернуться назад и еще раз прочесть разделы о структурах и операторах. В вопросе аргументом структуры  сумма является  структура  с функтором + и компонентами 2 и 3. На самом деле указанной цели соответствует третий факт, при этом переменные  X и  Y принимают конкретные значения 2 и 3.
 С другой стороны, если программист действительно хочет вычислить сумму, ему следовало бы воспользоваться предикатом is. Он должен был бы написать
 ?- X is 2+3.
 или (в качестве развлечения) он мог бы определить предикат сложить, связывающий два целых числа и их сумму:
 сложить (X, Y, Z):- Z is X+Y.
 В этом определении  X и  Y должны быть конкретизированы, а  Z неконкретизирована.




 ГЛАВА 3.  ИСПОЛЬЗОВАНИЕ СТРУКТУР ДАННЫХ


 Оксфордский толковый словарь английского языка определяет слово «рекурсия» следующим образом:
 РЕКУРСИЯ. [Теперь употребляется редко, устаревшее.] Обратное движение, возвращение.
 Это определение загадочно и, по-видимому, устаревшее. В настоящее время рекурсия является очень популярным и мощным средством в области нечислового программирования. Она используется в двух случаях: для описания структур, имеющих другие структуры в качестве компонент, и для описания программ, выполнению которых предшествует выполнение их собственной копии. Иногда начинающие программисты относятся к рекурсии с подозрением, не понимая, как это можно определить некоторое отношение через само себя? В Прологе рекурсия – это нормальный и естественный способ представления структур данных и программ. Мы надеемся, что тема этой главы – рекурсия – обретает ясность удобным и ненавязчивым образом.

 3.1. Структуры и деревья

 Чтобы легче было понять сложную структуру, ее обычно представляют в виде  дерева,  в котором каждому функтору соответствует вершина, а компонентам соответствуют ветви дерева. Каждая ветвь может указывать на другую структуру, так что мы можем иметь структуры внутри структур. Обычно принято изображать дерево таким образом, чтобы корень дерева находился вверху, а ветви были направлены вниз, как это показано на рис. 3.1. Заметим, что два последних дерева имеют одинаковую форму, хотя корни и листья деревьев различны. Прежде чем читать дальше, вы должны быть уверены в том, что можете представить в виде дерева каждую из структур, с которыми вы уже сталкивались в предыдущих главах.
 Предположим, у нас есть предложение «Джону нравится Мэри», и необходимо представить синтаксическую структуру этого предложения. В английском языке имеется очень простое синтаксическое правило построения предложений: предложение состоит из существительного, за которым следует глагольная группа. В свою очередь глагольная группа состоит из глагола и другого существительного. Это отношение между частями предложения может быть описано следующей структурой (которая представлена в виде дерева, приведенного на рис. 3.2):  предложение(существительное, глагольная_группа(глагол, существительное)).
 Рис. 3.1.
 Если мы возьмем наше предложение («Джону нравится Мэри») и вставим слова из этого предложения в качестве аргументов функторов  существительное  и  глагол  в структуру предложения, то мы получим (см. рис. 3.3):
 предложение(существительное(джон), глагольная_группа(глагол(нравится), существительное(мэри)))
 Этот пример показывает, как можно использовать структуры в языке Пролог для представления синтаксиса очень простых предложений. В общем случае если мы знаем, какой частью речи является каждое слово в предложении, то можно записать структуру на Прологе, которая в явном виде описывает отношения между различными словами в предложении. Эта задача сама по себе представляет интересную тему исследования, и далее мы еще вернемся к вопросу о том, как, используя Пролог, заставить ЭВМ «понимать» некоторые простые предложения.
 Деревья могут также применяться для графического описания переменных внутри структуры, в частности показывая, как сцеплены переменные, имеющие одинаковые имена (см. рис. 3.4).
  Рис. 3.2.
 Рис. 3.3.
 Рис. 3.4.

 3.2. Списки

  Список  - довольно широко используемая структура данных в области числового программирования. Список -это  упорядоченная последовательность элементов,  которая может иметь произвольную длину. Признак  упорядоченный  указывает на то, что порядок элементов в последовательности является существенным.  Элементами  списка могут быть любые термы – константы, переменные, структуры, которые включают, конечно, и другие списки. Указанные свойства очень полезны в ситуации, когда мы не в состоянии заранее предсказать, насколько большим должен быть список и какую информацию он будет содержать. Более того, списки позволяют представить практически любой тип структуры, который может потребоваться при символьных вычислениях. Списки широко используются для представления деревьев синтаксического разбора, грамматик, карт городов, программ для ЭВМ и математических объектов, таких как графы, формулы и функции. Существует язык программирования – Лисп, в котором единственными доступными структурами данных являются константа и список. Однако в Прологе список – это просто один из частных видов структуры.
 Списки могут быть представлены как специального вида дерево. Список – это любой  пустой список,  не содержащий ни одного элемента, либо структура, имеющая две компоненты: голову и хвост списка. Конец списка обычно представляют как хвост, который является пустым списком. Пустой список записывают как [] – открывающая квадратная скобка, за которой следует закрывающая квадратная скобка. Голова и хвост списка являются компонентами функтора, обозначаемого точкой '.'. Так, список, состоящий из одного элемента ' а ' есть  .(а, []) , а его представление в виде дерева имеет вид
 Аналогично список, состоящий из атомов  a ,  b и  с , мог бы быть записан как  .(а,.(b,.(с,[]))) , что изображается следующим образом:
 Иногда функтор точка ('.') определяется как оператор, так что допустимо для Пролога два последних списка записать как  а.[] и  а.(b.(с.[]))) . Второй список можно было бы записать просто как  а.b.с.[] , так как функтор точка – правоассоциативный оператор. Списки являются упорядоченными последовательностями элементов, так что список  а.b отличается от списка  b.а .
 Некоторые любят записывать древовидные диаграммы списков в виде дерева, «растущего» слева направо, ветви которого направлены вниз. Приведенный выше список, представленный диаграммой в виде такой «виноградной лозы» выглядит так:
 В этой диаграмме компонента функтора '.', соответствующая голове списка, «свисает» вниз, а компонента, соответствующая хвосту списка, «растет» вправо. Конец списка четко выделен тем, что последняя компонента – хвост списка – является пустым списком. Главное преимущество использования диаграммы для представления списка заключается в том, что она может быть записана справа налево на листе бумаги.
 «Виноградная» диаграмма может оказаться удобной для записи списков на бумаге, когда нам необходимо видеть структуру списка, но в программах на Прологе для записи списков такие диаграммы не используются. Так как запись сложных списков с помощью функтора '.' часто оказывается неудобной, то в Прологе предусмотрена другая синтаксическая форма, которая может быть использована для записи списков в программе. Это так называемая  скобочная форма записи списка.  Она представляет собой заключенную в квадратные скобки последовательность элементов списка, разделенных запятыми. Например, упоминавшиеся выше списки могут быть записаны в скобочной форме в виде  [а] и  [а, b, с] . Списки могут содержать другие списки или переменные. Например, в Прологе допустимы следующие списки:
 []
 [конкретный, человек, [любит, ловить, рыбу]]
 [а, V1, b, [X, Y]]
 Переменные, входящие в списки, ничем не отличаются от переменных в любой другой структуре. Они в любой момент могут быть конкретизированы, так что умелое использование переменных может обеспечить образование «пустых мест» в списке, которые впоследствии могут быть заполнены данными.
 Чтобы продемонстрировать структуру списков, содержащих в качестве элементов другие списки, приведем «виноградную» диаграмму для последнего из рассмотренных списков:
 Из приведенной диаграммы ясно видно, что каждый ее горизонтальный уровень является списком, состоящим из некоторого числа элементов. Верхний уровень на приведенной диаграмме представляет список, содержащий четыре элемента, один из которых сам является списком. Второй уровень, содержащий два элемента, представляет четвертый элемент списка верхнего уровня. Работа со списками основана на расщеплении их  наголову  и  хвост  списка. Голова списка – это первый аргумент функтора '.', который используется для конструирования списка. Хвост списка – это второй аргумент функтора '.'. В случае когда для записи списка используется скобочная форма записи, головой списка является первый его элемент. Хвост списка представляет  список,  состоящий из всех элементов исходного списка, за исключением первого его элемента. Следующие примеры демонстрируют расщепление списков на голову и хвост:

 Список      Голова      Хвост     
 [а, b, с]      а      [b, с]     
 [а,]      а      []     
 []         
 [[эта, кошка], сидела]      [эта, кошка]      [сидела]     
 [эта, [кошка, сидела]]      эта      [кошка, сидела]]     
 [эта, [кошка, села], на пол]      эта      [кошка, села], на пол]     
 [X+Y, х + y]      X + Y      [x + y]     

 Заметим, что пустой список не имеет ни головы, ни хвоста. В последнем примере оператор ± используется как функтор для структур  +(Х, Y) и  +(х,у) .
 Так как операция расщепления списка на голову и хвост очень широко используется, то в Прологе введена специальная форма для представления списка с головой  X и хвостом  Y . Это записывается как  [X|Y] , где для разделения  X и  Y используется вертикальная черта. При конкретизации структуры подобного вида  X сопоставляется с головой списка, a  Y – с хвостом списка, как это показано в следующем примере:
 p([1, 2, 3]).
 p([эта, кошка, сидела, [на, этой, подстилке]]).
 ?- p([X|Y]).
 X = 1 Y=[2,3]  ;
 X=эта Y=[кошка, сидела, [на, этой, подстилке]]
 ?- p([_,_,_,[_|X]]).
 X=[этой, подстилке]
 Ниже приведено еще несколько примеров с использованием различных синтаксических возможностей записи списков, показывающих, каким образом производится сопоставление списков. В этих примерах делается попытка сопоставить два заданных списка, конкретизируя переменные, если это возможно.

 Список 1      Список 2      Конкретизация     
 [X, Y, Z]       [джону,нравится,рыба]       X=джону Y= нравится Z = рыба      
 [кошка]       [X| Y]       X= кошка     
 [X, Y | Z]       [мэри,нравится,вино]       X = мэри  Y = нравится Z = [вино]     
 [[этот, Y]|Z]       [[X, заяц], [находится, здесь]]         X = этот Y = заяц Z = находится_ здесь      
 [X, Y|Z, W]      (синтаксически некорректная конструкция списка)         
 [золотистый | T]       [золотистый, норфолк]       T= [норфолк]     
 [лошадь, X]       [белая, лошадь]     (сопоставление невозможно)     
 [белая | Q]       [P | лошадь]      P  =  белая Q  =  лошадь     

 Как видно из последнего примера, используя скобочную форму записи списков, можно создавать структуры, похожие на списки, но не заканчивающиеся пустым списком. Одна из таких структур,  [белая|лошадь],  обозначает структуру, головой которой является  белая,  а хвостом –  лошадь.  Константа  лошадь  не является ни списком, ни пустым списком, и, как мы увидим далее, обработка таких структур требует большой осторожности, когда они используются в качестве хвоста списка.
 Существует еще одна область применения списков – это представление строк литер. Иногда возникает необходимость в использовании строк литер для печати или ввода текста. Если строка литер заключена в двойные кавычки, то эта строка представляется как список кодов, соответствующих литерам строки. Для кодировки литер используется код ASCII, который обсуждался в разд. 2.2. Например, строка  "system"  преобразуется в Прологе в следующий список:  [115, 121, 115 ,  116, 101, 109].

 3.3. Принадлежность элементов списку

 Предположим, что имеется некоторый список, в котором  X обозначает его голову, a  Y – хвост списка. Напомним, что такой список мы можем записать так:  [X|Y] . Этот список мог бы содержать, например, клички тех лошадей потомков жеребца  Coriander,  которые все выиграли скачки в Великобритании в 1927 году:
 [curragh_tip, music_star, park_mill, portland]
 Теперь предположим, что мы хотим определить, содержится ли некоторая кличка в указанном списке. В Прологе это можно сделать, определив, совпадает ли данная кличка с головой списка.
 Если совпадает, то наш список завершается успехом. Если нет, то мы проверяем, есть ли кличка в хвосте исходного списка. Это значит, что снова проверяется голова, но уже  хвоста  списка. Затем проверяется голова  очередного  хвоста списка. Если мы доходим до конца списка, который будет пустым списком, то наш поиск завершается неудачей: указанной клички в исходном списке нет.
 Для того чтобы записать все это на Прологе, сначала надо установить, что между объектом и списком, в который этот объект может входить, существует отношение. Это отношение, называемое отношением принадлежности, представляет достаточно распространенное в повседневной жизни понятие. Так, мы говорим о людях, являющихся членами клубов, и о других тому подобных вещах. Для записи этого отношения мы будем использовать предикат  принадлежит:  целевое утверждение  принадлежит(X, Y) является истинным («выполняется»), если терм, связанный с  X , является элементом списка, связанного с  Y . Имеются два условия, которые надо проверить для определения истинности предиката. Первое условие говорит, что  X будет элементом списка  Y , если X совпадает с головой списка  Y . На Прологе этот факт записывается следующим образом:
 принадлежит(X,[X |_]).
 Эта запись констатирует, что  X  является элементом списка, который имеет   X  в качестве головы.  Заметим, что мы использовали анонимную переменную '_' для обозначения хвоста списка. Это сделано потому, что мы никак не используем хвост списка в этом частном факте. Заметим, что данное правило могло бы быть записано и по-другому:
 принадлежит(X,[Y|_]:- X = Y.
 К этому моменту вы должны уже понимать, почему можно использовать  X сразу в двух местах в первой, более короткой, версии этого правила.
 Второе, и последнее, правило говорит о том, что  X принадлежит списку при условии, что он входит в хвост этого списка, обозначаемый через  Y . И нет лучшего пути, чем использовать тот же самый предикат  принадлежит  для того, чтобы определить, принадлежит ли  X хвосту списка! В этом и состоит суть рекурсии. На Прологе это выглядит так:
 принадлежит(X,[_ |Y]):- принадлежит(X,Y).
 и констатирует, что X  является элементом списка, если  X  является элементом хвоста этого списка.  Заметим, что мы использовали анонимную переменную '_', так как нас не интересует имя переменной, обозначающей голову списка. Два этих правила в совокупности определяют предикат для отношения принадлежности и указывают Прологу, каким образом просматривать список от начала до конца при поиске некоторого элемента в списке. Наиболее важный момент, о котором следует помнить, встретившись с рекурсивно определенным предикатом, заключается в том, что прежде всего надо найти  граничные условия  и способ  использования рекурсии.
 Для предиката  принадлежит в действительности имеются два типа граничных условий. Либо объект, который мы ищем, содержится в списке, либо он не содержится в нем. Первое граничное условие для предиката  принадлежит распознается первым утверждением, которое приведет к прекращению поиска в списке, если первый аргумент предиката  принадлежит совпадает с головой списка, соответствующего второму аргументу. Второе граничное условие встречается, когда второй аргумент предиката  принадлежит является пустым списком.
 Как мы можем убедиться в том, что граничные условия будут когда-либо удовлетворены? Для этого необходимо обратить внимание на то, как используется рекурсия во втором правиле для предиката  принадлежит . Заметим, что каждый раз, когда при поиске соответствия для целевого предиката  принадлежит происходит рекурсивное обращение к тому же предикату, новая цель формируется для  более короткого  списка. Хвост списка всегда является более коротким списком, чем исходный список. Очевидно, что рано или поздно произойдет одно из двух событий: либо произойдет сопоставление с первым правилом для  принадлежит , либо в качестве второго аргумента  принадлежит будет задан список длины 0, т. е. пустой список. Как только возникнет одна из этих ситуаций, прекратится рекуррентное порождение целей для предиката  принадлежит . Первое граничное условие распознается фактом, который не вызывает порождения новых подцелей. Второе граничное условие не распознается ни одним из утверждений для принадлежит , так что процесс поиска сопоставимого элемента списка для целевого утверждения принадлежит закончится неудачей. Это демонстрирует следующий пример на Прологе:
 принадлежит(Х, [X | _]).
 принадлежит(Х,[_|Y]):- принадлежит (X,Y).
 ?- принадлежит(d,[a,b,с,d,e,f,g]).
 да
 ?- принадлежит(2,[3,a,4,f]).
 нет
 Предположим, мы введем вопрос
 ?- принадлежит(clugatе,[curraugh_tiр,music_star,раrk_mill, ortland]).
 Так как  clygate  не сопоставимо с  curragh_tip,  то происходит сопоставление со вторым правилом для  принадлежит.  Переменная Y получает значение  [music_star, park_mill, portland],  и порождается следующая цель: определить, принадлежит ли  clygate  этому списку. Опять происходит сопоставление со вторым правилом, и снова выделяется хвост списка. Текущей целью становится  принадлежит (clugate,[park_mill,portland])  Этот процесс рекурсивно повторяется до тех пор, пока мы не доберемся до цели, у которой  X есть  clygate,  a  Y есть  [portland].  Происходит еще одно сопоставление со вторым правилом, и теперь  Y конкретизируется хвостом списка  [portland],  который является пустым списком. Следующей целью становится  принадлежит(clygate,[]).  Ни одно из правил в базе данных не сопоставимо с этой целью, так что цель оказывается ложной и ответ на вопрос будет отрицательным.
 Важно помнить, что каждый раз, когда при согласовании  принадлежит  с базой данных выбирается второе утверждение этого предиката, Пролог рассматривает рекурсивное обращение к предикату  принадлежит  как попытку найти соответствие для некоторой новой его «копии». Это предотвращает путаницу переменных, соответствующих одному употреблению утверждения, с переменными, соответствующими другому употреблению этого же утверждения.
 Предикат отношения принадлежности настолько полезен, что мы еще неоднократно будем использовать его в оставшейся части этой книги. Предикат  принадлежит важен еще и потому, что он представляет практически наименьший полезный пример рекурсивного предиката – определение предиката  принадлежит  содержит утверждения, которые могут быть проверены с помощью только того же самого предиката  принадлежит.  Рекурсивные определения часто встречаются в программах на Прологе, и они полностью равноправны с другими определениями. Однако надо быть осторожным, чтобы не допускать «закольцованные» определения, как, например, следующее:
 родитель(X,Y):- ребенок(Y,X).
 ребенок(A,B):- родитель(B,A).
 В этом примере, чтобы согласовать с базой данных целевое утверждение  родитель,  необходимо согласовать подцель  ребенок . Однако определение для ребенок приведет к появлению единственной подцели –  родитель.  Вы должны понимать, почему вопрос, содержащий в качестве целей  родитель  или  ребенок,  приводит к циклу, находясь в котором Пролог не сможет найти какие-либо новые факты, и этот цикл никогда не завершится.
 Одна важная проблема, на которую следует обращать внимание в рекурсивных определениях, - это  левосторонняя рекурсия.  Она возникает в случае, когда правило порождает подцель, по существу эквивалентную исходной цели, которая явилась причиной использования этого правила. Так, если бы мы определили предикат
 человек(X):- человек(Y), мать(Х,Y).
 человек(адам).
 и ввели вопрос
 ?- человек(X).
 то Пролог сначала использовал бы правило и рекурсивно породил подцель  человек (Y).  Попытка найти соответствие этой цели вновь привела бы к выбору первого правила и породила бы еще одну новую эквивалентную подцель. И так далее, до тех пор, пока не исчерпались бы вычислительные ресурсы. Конечно, если бы была возможность использовать механизм возврата, то был бы найден сообщенный в определении факт об Адаме и началось бы порождение решений  [7]  . Ошибка заключается в том, что для того, чтобы начался возврат, Пролог должен потерпеть неудачу при проверке первого утверждения. В данном же случае поиск решения оказывается неопределенно длинным, и нет никакой возможности завершить этот поиск с успехом либо с неудачей. Из всего сказанного выше можно извлечь следующую мораль:
 Не следует предполагать, что только потому, что вы предоставили все относящиеся к делу факты и правила, Пролог всегда найдет их. Создавая программу на Прологе, вы все время должны представлять, каким образом Пролог осуществляет поиск в базе данных и какие переменные будут конкретизированы, когда будет использовано одно из ваших правил.
 Для приведенного примера имеется простой способ устранения ошибки – поместить факт перед правилом, а не после него. В действительности существует хороший эвристический принцип: помещать, где это возможно, факты перед правилами. Иногда при размещении правил в некотором конкретном порядке может возникнуть ситуация, когда они будут правильно работать для целей одного вида и не будут работать для целей другого вида. Рассмотрим следующее определение предиката  список (X),  при котором предикат  список  является истинным, если  X – список, последний элемент которого имеет в качестве хвоста пустой список:
 список([A|B]):- список(B).
 список([]).
 Если мы используем эти правила для получения ответов на вопросы, подобные следующим:
 ?- список ([a,b,c,d]).
 ?- список([]).
 ?- список(f(1,2,3))
 то данное определение будет работать хорошо. Но если мы сделаем запрос
 ?- список(X).
 то программа зациклится. Предикат, аналогичный предикату  список,  но неподверженный зацикливанию, задается следующими двумя фактами:
 обобщенный_список([]).
 обобщенный_список([_ |_]).
 В этом варианте просто проверяется начало списка, а не тот факт, что последний хвост списка является пустым списком ([]). Последнее определение не является таким же строгим тестом правильности списка, как определение предиката  список,  но оно не приведет к зацикливанию, если аргументом является переменная.

 3.4. Пример: преобразование предложений

 Рассмотрим программу на Прологе, которая в ответ на введенное с терминала предложение (на английском языке) печатает другое предложение, представляющее преобразованное исходное предложение. Эта программа для «ответов» программисту могла бы поддерживать следующий диалог:
 Вы: you are a computer (Вы - ЭВМ)
 Пролог: i am not a computer (Я – не ЭВМ)
 Вы: do you speak french (Вы говорите по-французски?)
 Пролог: no i speak german (Нет, я говорю по-немецки)
 Хотя этот диалог может показаться натянутой, но все же осмысленной беседой, очень легко написать программу, выполняющую свою «часть» диалога. Для этого достаточно просто последовательно выполнять следующие действия:
 1. Ввести предложение, набранное пользователем на терминале.
 2. Заменить каждое вхождение слова  you  на слово  i .
 3. Аналогичным образом заменить  are  на  am not.
 4. Заменить  french  на  german.
 5. Заменить  do на  nо.
 Если применить данную схему преобразования  к  надлежащим образом подобранным предложениям, подобным использованным в приведенном выше диалоге, то получим осмысленные преобразованные предложения. Однако эта схема применима не ко всем предложениям. Например;
 Вы: i do like you (я действительно люблю вас)
 Пролог: i no like i (я не люблю себя)
 Но если простая программа уже написана, то впоследствии ее можно модифицировать так, чтобы она справлялась и с предложениями, подобными приведенному.
 Программа на Прологе, преобразующая одно предложение английского языка в другое, может быть реализована следующим образом. Прежде всего необходимо осознать, что имеется отношение между исходным предложением и преобразованным. В связи с этим нам следует определить предикат, называемый  преобразовать. Преобразовать(Х, Y)  означает, что предложение  X может быть преобразовано в предложение  Y . Предложения  X и  Y удобно представлять в виде списков атомов, обозначающих слова, так что предложения могут быть записаны следующим образом:  [this,is,a , sentence]  (это некоторое предложение). Определив предикат  преобразовать,  мы могли бы обращаться к Прологу с вопросами вида
 ?- преобразовать([dо,you,know,french],X). (Знаете ли вы французский)
 на что Пролог отвечал бы
 X=[no,i,know,german] (нет, я знаю немецкий).
 Не следует обращать внимание на то, что вводимое и печатаемое в ответ предложения представлены в такой неестественной форме и не похожи на обычные предложения. В последующих главах мы обсудим способы ввода и вывода структур в виде, удобном для чтения. В данный момент нас интересуют лишь способы преобразования одного списка в другой.
 Так как аргументами предиката  преобразовать являются списки, то прежде всего следует рассмотреть, что произойдет, если исходный список пустой. В этом случае мы скажем, что пустой список преобразуется в пустой список:
 преобразовать([], [])
 Или, иначе:  это факт, что преобразование пустого списка дает пустой список.  Если причины для того, чтобы рассматривать пустой список, здесь не очевидны, то последующее изложение прояснит их. Далее нам следует разобраться в том, что основные действия предиката  преобразовать заключаются в следующем:
 1. Заменить голову входного списка соответствующим словом и поместить это слово в выходной список в качестве головы.
 2. Преобразовать хвост входного списка и сделать его хвостом выходного списка.
 3. Если мы достигли конца входного списка, то к выходному списку больше ничего добавлять не надо, и мы можем завершить выходной список пустым списком [].
 Переводя это на язык, более близкий к Прологу, можно сказать:
  Преобразование списка с головой   H  и хвостом   T  дает список с головой   X  и хвостом   Y ,  если замена слова   H  дает слово   X ,  а преобразование списка   T  дает список   Y .
 Теперь следует сказать, что значит «заменить» одно слово на другое. Это может быть сделано при наличии в базе данных фактов вида  заменить(Х, Y) , означающих, что слово  X может быть заменено словом  Y . В конце базы данных следует поместить факт-«ловушку», так как если слово не заменяется другим словом, то его следует заменить самим собой. Если сейчас не совсем понятно назначение «ловушки», то позднее, когда мы объясним, как работает программа, это должно стать ясным.
 Роль такого факта-ловушки выполняет факт  заменить(Х,Х),  который обозначает, что слово  X заменяется самим собой. Ниже приведена база данных, обеспечивающая указанные выше замены слов:
 заменить(уоu,i).
 заменить(аrе, [am,not]).
 заменить(french,german).
 заменить(dо,nо)
 заменить(Х,Х). /* это факт-ловушка */
 Заметим, что фраза  «am not»  представлена как список, так что она входит в факт как один аргумент.
 Теперь можно перевести приведенный выше текст на псевдо-Прологе в настоящую программу на Прологе, помня, что запись  [А|В]  обозначает список, имеющий голову А и хвост В. Мы получаем нечто подобное следующему:
 преобразовать([],[]).
 преобразовать([Н|T],[X|Y]):-заменить(Н, X), преобразовать(Т,Y).
 Первое утверждение в приведенной процедуре проверяет, является ли аргумент пустым списком. Оно же проверяет окончание списка. Как? Рассмотрим это на примере:
 ?- преобразовать([уоu,are,a,computer],Z).
 Этот вопрос был бы сопоставлен с основным правилом для  преобразовать,  при этом переменная  Н получила бы значение  you , а переменная  Т – значение  [are,a,computer] . Затем была бы рассмотрена подцель заменить  (you,Х) , найден подходящий факт и переменная  X стала бы равной  i . Так как  X является головой выходного списка (в целевом утверждении преобразовать), то первое слово в выходном списке есть  i . Далее, поиск соответствия для подцели преобразовать  ([are, a, computer], Y) привел бы к использованию того же правила. Слово are в соответствии с имеющейся базой данных заменяется на список  [am,not] , и генерируется другая подцель с предикатом  преобразовать –  преобразовать([а,computer], Y) . Ищется факт  заменить(а,X) , но так как в базе данных нет факта заменить, первый аргумент которого равен а, то будет найден факт-ловушка, расположенный в конце базы данных, заменяющий ' а ' на ' а '. Правило преобразовать вызывается еще раз с  computer в качестве головы входного списка и  пустым списком  [] в качестве хвоста входного списка. Как и ранее,  заменить(computer, X) сопоставляется с фактом-ловушкой. Наконец, преобразовать вызывается с пустым списком на месте первого аргумента, и происходит сопоставление с первым утверждением предиката преобразовать. Результатом является пустой список, который заканчивает преобразованное предложение (напомним, что список заканчивается пустым хвостом). В заключение Пролог отвечает на вопрос, печатая
 Z = [i,[am,not], a, computer]
 Отметим, что фраза  [am,not] появляется в списке точно в таком же виде, как она была в него вставлена.
 Теперь должны быть ясны причины появления в базе данных факта  преобразовать ([],[]) и факта-ловушки заменить (Х,Х) . Факты, подобные этим, часто включаются в программу, когда требуется проверить выполнение граничных условий. Из приведенного выше объяснения должно быть ясно, что выход на граничные условия происходит в случае, когда входной список становится пустым и когда оказываются просмотренными все факты для предиката  заменить . В обоих случаях выхода на граничные условия необходимо выполнить определенные действия. В случае когда входной список становится пустым, необходимо завершить выходной список (вставив пустой список в его конец). Если просмотрены все факты для предиката  заменить , но при этом не обнаружен факт, содержащий данное слово, то это слово должно остаться неизменным (путем замены его самим собой).

  3.5. Пример: упорядочение по алфавиту

 Как мы видели в гл. 2, в Прологе существуют предикаты для сравнения целых чисел. В приложениях, имеющих дело со словами, например работа со словарями, полезно иметь предикат для сравнения  слов  в соответствии с алфавитным порядком.
 Рассмотрим предикат, который мы назовем  меньше.  Если предикат  меньше(Х, Y)  используется в качестве целевого утверждения, то он истинен (т. е. согласуется с базой данных), если X и Y обозначают атомы и X по алфавиту предшествует Y. Так, предикат  меньше(арбуз, букварь)  истинен, а  меньше(ветер,автомобиль)  ложен. Точно так же должен быть ложен и предикат  меньше(картина,картина).  Сравнивая два слова, мы сравниваем их последовательно, буква за буквой и при сравнении каждой буквы определяем, какое из следующих условий имеет место:
 1. Достигнут конец первого слова, но не достигнут конец второго слова. Это имеет место, например, в случае  меньше(пар, паровоз).  При возникновении такой ситуации предикат  меньше  должен считаться истинным (т. е. согласованным с базой данных).
 2. Очередная литера в первом слове предшествует в алфавите соответствующей литере во втором слове. Например,  меньше (слово,слон).  Буква ' в ' в слове  слово  предшествует в алфавите букве ' н ' в слове  слон.  В этом случае предикат  меньше  истинен.
 3. Литера в первом слове совпадает с соответствующей литерой во втором слове. В этом случае следует использовать предикат  меньше  для сравнения  оставшихся литер  в обоих словах. Например, если дано  меньше(облако,одеяло),  то, так как оба аргумента начинаются с буквы ' о ', необходимо взять в качестве следующей цели  меньше(блако,деяло).
 4. Одновременно достигнут конец первого и второго слов, как, например, в случае  меньше(яблоко,яблоко).  При возникновении такого условия предикат  меньше  должен быть ложным, так как оба слова являются одинаковыми.
 5. Обработаны все литеры второго слова, но еще остались литеры в первом слове, как, например, в случае  меньше(алфавитный,алфавит).  В такой ситуации предикат  меньше  должен быть ложным.
 После того как сформулированы перечисленные выше условия, задача перевода их на Пролог является довольно простой. Будем представлять слова в виде списков литер (целых чисел из некоторого диапазона). Для этого необходим способ преобразования атома в список литер. Эту функцию выполняет встроенный предикат Пролога  name(имя) . Целевое утверждение  name(X, Y) согласуется с базой данных, когда атом, являющийся значением  X , состоит из литер, коды которых образуют список, являющийся значением  Y  (используются коды ASCII). Отсылаем читателя к гл. 2, если он забыл, что такое коды ASCII. Если один из аргументов не определен, то Пролог предпримет попытку конкретизировать его, создавая соответствующую структуру. Поэтому можно использовать предикат  name  для преобразования слова в список литер. Например, зная, что код ASCII для  'а' есть 97, код для  'l' – 108 и код для  'p' – 112, можно задавать следующие вопросы:
 ?- name (Х,[97,108,112])
 Х=аlр
 ?- name (alp,X)
 X=[97,108,112]
 Первым утверждением в определении предиката  меньше  является следующее правило:
 меньше(Х, Y):- name(X,L),name(Y,M), меньше_l(L,M)
 Это правило сначала преобразует слова в списки, используя предикат  name,  и затем с помощью предиката  меньше_1  (будет определен ниже) сравнивает списки на соответствие алфавиту. Определение предиката  меньше_1  состоит из утверждений, реализующих приведенный выше набор условий. Первое условие является истинным, когда первый аргумент есть пустой список, а второй аргумент – это произвольный непустой список:
 меньше_1([], [_|_]).
 Второе условие записывается следующим образом:
 меньше_1([X|_],[Y|_]):- X‹Y
 Напомним, что аргументами предиката  меньше_1  являются списки чисел, так что разрешается сравнивать элементы этих списков, используя предикат '‹'. Третье условие записывается следующим образом:
 меньше_1([А|Х],[В|Y]:- А=В, меньше_1(Х,Y).
 Наконец, два последних условия описывают ситуации, когда предикат ложен, т. е. не согласуется с базой данных, так что если мы не предусмотрим никаких соответствующих им фактов или правил, то при используемом механизме поиска в базе данных доказательство согласованности любого целевого утверждения, для которого эти условия справедливы, закончится неудачей. Собирая все правила вместе, получим
 меньше(Х,Y):- name(X,L), name(Y,M), меньше _1(L,M).
 меньше_1([], [_|_]).
 меньше_1([X|_],[Y|_]):- Х‹Y.
 меньше_1([P|Q], [R|S]):- P = R, меньше_1(Q,S).
 Заметим, что третье правило для  меньше_1 можно было бы записать более естественно так:
 меньше_1([H|Q], [H|S]):- меньше_l(Q,S).
  Упражнение 3.1. Подумайте, какое еще утверждение необходимо добавить к этому определению так, чтобы предикат был истинен и в том случае, когда два слова совпадают. В результате получится предикат, проверяющий, меньше или равен первый аргумент второму по алфавиту. Указание: обратите внимание на условие (4), приведенное выше, и вставьте утверждение, обрабатывающее это условие.
  Упражнение 3.2. Почему в первом утверждении для предиката  меньше_1 в качестве второго аргумента использован список [_|_]? Почему недостаточно использовать список [.]?

 3.6. Использование предиката присоединить и спецификация деталей

 Предикат  присоединить , обрабатывающий списки, используется для создания нового списка, являющегося результатом соединения двух других списков. Например, верен следующей факт:
 присоединить([а,b,с], [3,2,1], [а,b,с,3,2,1]).
 Предикат  присоединить наиболее часто используется для создания нового списка в результате конкатенации двух других списков, как в следующем примере:
 ?- присоединить ([alpha,beta],[gamma,delta],X).
 X=[alpha, beta, gamma, delta]
 Но он может также использоваться и другим способом;
 ?- присоединить(Х,[b,c,d],[a,b,c,d]). Х=[а]
 Предикат  присоединить имеет следующее определение;
 присоединить([],L,L).
 присоединить([Х|L1],L2,[Х|L3]):- присоединить (L1,L2,L3).
 Выход на граничное условие происходит, когда первый аргумент является пустым списком. Любой список, присоединенный к пустому списку, дает тот же самый список. Во всех других случаях будет выполняться второе правило, смысл которого можно описать словами следующим образом:
 1. Первый элемент первого списка  (X) всегда будет и первым элементом третьего списка.
 2. Хвост третьего аргумента  (L3) всегда будет представлять результат присоединения второго аргумента  (L2) к хвосту первого списка  (L1) .
 3. Для присоединения одного списка к другому, о чем шла речь в пункте 2, необходимо использовать предикат  присоединить.
 4. Так как при каждом обращении к правилу удаляется голова списка, являющегося первым аргументом, то постепенно этот список будет исчерпан и станет пустым, так что произойдет выход на граничное условие.
 В дальнейших примерах будут встречаться ссылки на предикат  присоединить с необходимыми дополнительными пояснениями. В последующих главах мы обсудим различные свойства и применения этого предиката. Но сначала давайте применим его в другом простом примере рекурсии.
 Предположим, что мы работаем на заводе, выпускающем велосипеды, и нам необходимо хранить спецификацию деталей велосипеда. Для того чтобы собрать велосипед, надо знать, какие детали заказать поставщикам. Каждая деталь велосипеда может состоять из более мелких элементов – поддеталей, например каждое колесо имеет спицы, обод и ступицу. Более того, ступица может состоять из оси и шестеренок. Давайте рассмотрим базу данных, организованную в виде дерева, которая позволит нам делать запросы о деталях, необходимых для изготовления некоторой части велосипеда. В одной из следующих глав предложенная здесь программа будет улучшена, с тем чтобы позволить вычислять, сколько экземпляров каждой детали нам потребуется.
 Имеются два типа объектов, которые используются для изготовления велосипеда. Это  узлы  и  детали.  Каждый узел состоит из некоторого числа деталей, подобно тому как колесо состоит из спиц, обода и ступицы. Детали не имеют еще более мелких частей – они просто соединяются друг с другом, образуя узлы.
 Можно представить детали как факты следующим образом:
 деталь(обод). деталь(спица).
 деталь(задняя_рама). деталь(руль).
 деталь(шестерни). деталь(болт).
 деталь(гайка). деталь(вилка).
 Естественно, что это далеко не полный список деталей, необходимых для сборки велосипеда, но приведенные факты показывают основную идею. Узел может быть представлен именем узла, за которым следует список входящих в него деталей с указанием их количества. Например, следующий факт означает, что  велосипед  - это узел, состоящий из двух колес и рамы:
 узел(велосипед, [колесо, колесо, рама]).
 Ниже представлена база данных узлов, необходимых для нашего упрощенного велосипеда:
 узел(велосипед, [колесо,колесо,рама]).
 узел(колесо, [спица,обод,ступица]).
 узел(рама, [задняя_рама, передняя_рама]).
 узел(передняя_рама, [вилка,руль]).
 узел(ступица, [шестерни,ось]).
 узел(ось, [болт,гайка]).
 Заметим, что это частное множество утверждений неполностью описывает велосипед. Мы не делаем различия между передней и задней ступицами – обе имеют шестерни! Цепь и педали отсутствуют, и негде сидеть велосипедисту. Не указано также, как соединять детали друг с другом. Это просто перечисление некоторого числа требуемых деталей.
 Теперь мы готовы написать программу, которая для заданной части перечислит все детали, необходимые для ее сборки. Если часть, которую мы хотим собрать, является деталью, то для нее ничего больше не требуется. Однако если мы хотим собрать некоторый узел, то необходимо применить этот процесс к каждой составной части узла. Определим предикат  часть (X, Y),  где  X  - имя части, a  Y – список деталей, необходимых для ее сборки. В первой версии программы мы не будем рассматривать вопрос о количестве деталей каждого типа, необходимых для сборки. Более полная программа будет представлена в гл. 7.
 Выход на граничное условие происходит, когда  X является деталью. В этом случае  X просто возвращается в качестве элементарного списка:
 часть(Х, [X]):- деталь(Х).
 Следующее условие связано со случаем, когда  X является узлом. Здесь необходимо определить, имеется ли в базе данных соответствующий факт узел, и если такой имеется, то применить предикат  часть  к каждому элементу списка подчастей. Для выполнения второй из указанных задач используется предикат, названный  список_частей.
 часть(Х,Р):- узел(Х,Подчасти),
 список_чаcтей(Подчасти, Р).
 Предикат  список_частей  берет список частей (из второго аргумента факта узел, представленного выше) и применяет предикат  часть  к каждой части в списке. После вызова самого себя, необходимого для обработки хвоста списка, предикат  список_частей  должен склеить полученные списки вместе, используя предикат  присоединить:
 список_частей([Р|Хвост], Полный_список):- часть(Р,Части_головы)
 список_частей(Хвост,Части_хвоста)
 присоединить(Части_головы, Части_хвоста, Полный_список)
 Список, созданный предикатом  часть , не будет содержать информации о требуемом количестве деталей, при этом элементы списка могут дублироваться. В гл. 7 будет представлена улучшенная версия программы, в которой эти недостатки отсутствуют.
 Существуют две идеи, указывающие, как использовать предикат  часть для генерации предложений на английском языке. Во-первых, предложения могут быть представлены в виде иерархических структур: предложение имеет части  группа_существительного и  группа_глагола ;  группа_существительного состоит из  определения и  существительного и т. д. Так что любая простая грамматика может быть выражена на языке «частей». Во-вторых, предикат  список_частей всегда обрабатывает элементы списка, представленного его первым аргументом, в порядке слева направо, и его результат (второй аргумент) накапливается в том же порядке. Два указанных свойства предиката  часть показывают, что можно использовать тот же метод для генерации предложений по некоторой грамматике. Типичный «узел» в этой грамматике мог бы выглядеть так:
 узел(предложение,[группа_существительного,группа_глагола]).
 узел(группа_существительного,[определение,существительное]).
 узел(определение,[thе]).
 узел(существительное, [clergyman]).
 узел(существительное,[motorcar]).
 А слова используемой лексики были бы определены как «детали»:
 деталь(сlеrgуmаn).
 деталь(motorcar)
 Теперь у вас может возникнуть желание поэкспериментировать с таким подходом к генерации предложений. Для этого необходимо составить разумную грамматику и словарь. Убедитесь сами, что измененная таким образом программа будет выдавать все допускаемые грамматикой предложения, которые можно построить по заданным грамматике и словарю. Всякий раз, выдав очередное предложение, Пролог будет ожидать, когда вы введете точку с запятой, указывающую ему, что необходимо выполнить возврат для получения следующего предложения.
 На приведенном здесь примере не заканчивается обсуждение проблемы обработки текстов на естественном языке в этой книге. Глава 9 полностью посвящена более детальному рассмотрению такого применения Пролога.




 ГЛАВА 4. ВОЗВРАТ И ОТСЕЧЕНИЕ


 Давайте подытожим всю информацию, которую мы почерпнули в гл. 1 и 2 о том, что может произойти с целевым утверждением (целью).
 1. Может иметь место попытка  доказать согласованность  целевого утверждения с базой данных. В процессе доказательства база данных просматривается, начиная с ее вершины. При этом возможны две ситуации:
 (а) Может быть найден факт (или заголовок правила), сопоставимый с целевым утверждением. В этом случае мы говорим, что произошло  сопоставление  цели с утверждением (фактом или правилом) в базе данных. Это место отличается в базе данных маркером и конкретизируются (присваиваются значения) соответствующие переменные, если они не были конкретизированы ранее. Если произошло сопоставление с правилом, то прежде всего необходимо попытаться доказать согласованность подцелей, вводимых этим правилом. Если цель согласуется с базой данных, то предпринимается попытка согласовать следующее целевое утверждение. В используемых нами диаграммах это будет цель, указанная в следующем, нижнем прямоугольнике, на который указывает стрелка. Если исходная цель входит в конъюнкцию, то это будет цель, расположенная в программе  непосредственно справа  от исходной цели.
 (б) В базе данных нет факта (или заголовка правила), сопоставимого с целевым утверждением. В этом случае мы говорим, что попытка доказать согласованность целевого утверждения потерпела  неудачу  (цель не согласуется с базой данных). Тогда будет предпринята попытка (см. п.2)  вновь доказать согласованность  целевого утверждения, указанного в прямоугольнике, расположенном выше стрелки. Если исходное целевое утверждение входит в конъюнкцию, то это будет целевое утверждение, расположенное в программе непосредственно слева от рассматривавшегося целевого утверждения.
 2. Мы можем сделать попытку  вновь доказать согласованность  целевого утверждения с базой данных. Для этого прежде всего необходимо попытаться вновь согласовать каждую из его подцелей, при этом стрелка возвращается в некоторую исходную позицию, поднимаясь вверх по странице. Если ни одна из подцелей вновь не может быть согласована каким-либо подходящим образом, делается попытка найти альтернативное утверждение для самой исходной цели. В этом случае необходимо вернуть в исходное (неопределенное) состояние каждую переменную, конкретизированную при выборе предыдущего утверждения. Эти действия мы называем «уничтожением» результатов, полученных ранее при доказательстве согласованности целевого утверждения. Затем возобновляется просмотр базы данных, но начинается этот просмотр с места, отмеченного маркером данной цели. Как и ранее, эта новая цель, выбранная при возврате, может оказаться либо согласованной, либо несогласованной с базой данных. При этом будет иметь место либо шаг (а), либо шаг (б).
 В этой главе процесс возврата будет рассмотрен более подробно. Кроме того, будет рассмотрен специальный механизм – «отсечение», который может быть использован в программах на Прологе. Отсечение позволяет указывать, какие из ранее сделанных выборов альтернатив не следует более пересматривать.

  4.1. Порождение множественных решений

 Простейшая ситуация, в которой некоторое множество фактов допускает несколько ответов на вопрос, возникает, когда в этом множестве имеется несколько фактов, сопоставимых с вопросом. Например, имеются следующие факты:
 отец(мэри, джордж).
 отец(джон, джордж).
 отец(сью,гарри).
 отец(джордж,эдуард).
 в которых  отец(X, Y)  обозначает, что  Y является отцом  X . Вопрос
 ?- отец(X,Y).
 имеет несколько возможных ответов. Если мы будем вводить после каждого ответа точку с запятой, то Пролог выдаст следующие ответы:
 X = мэри, Y = джордж;
 X = джон, Y = джордж;
 X = сью, Y = гарри;
 X = джордж, Y = эдуард.
 Пролог найдет эти ответы, просматривая базу данных в поисках фактов и правил с предикатом  отец  и печатая их в том порядке, в каком они представлены в базе данных. При этом Пролог не проявляет особого «интеллекта» – он ничего не помнит о предыдущих ответах. Так, если мы обратимся с вопросом
 ?- отец(_,X).
  (для каких   X  верно то, что   X  является отцом),  то мы получим
 Х=джордж;
 Х=джордж;
 Х=гарри;
 Х=эдуард.
 при этом ответ  джордж повторен дважды, так как Джордж является отцом как Мэри, так и Джона. Если Пролог может сделать одно и то же двумя различными способами, то он рассматривает это как два различных решения.
 Повторный просмотр выполняется точно таким же способом, если выбор среди альтернатив происходит на более глубоком уровне обработки. Например, для определения отношения «одним из детей  X является  Y » могло бы быть использовано правило
 ребенок(Х,Y):- отец(Y,X).
 Тогда вопрос
 ?- ребенок(Х,Y).
 дал бы
 X = джордж, Y = мэри;
 X = джордж, Y=джон;
 X = гарри, Y = сью;
 X = эдуард, Y = джордж.
 Так как  отец(Y, X) имеет четыре решения, то столько же решений имеет и  ребенок(Х, Y).  Более того, решения порождаются в том же самом порядке. Единственное, что отличает эти решения, - это различный порядок аргументов в соответствии с определением для предиката  ребенок.  Аналогично, если мы определили
 отец(X):- отец(_,X).
 (отец (X) обозначает, что X является чьим-либо отцом), то на вопрос
 ?- отец(X).
 были бы получены ответы:
 X = джордж;
 X = джордж;
 X  =  гарри;
 X = эдуард.
 Если мы перемешаем факты и правила, то выбор альтернатив вновь будет производиться в соответствии с порядком, в котором представлены факты и правила. Так, мы могли бы определить:
 человек(адам).
 человек(X):- мать(X,Y).
 человек(ева).
 мать(каин,ева).
 мать(авель,ева).
 мать(иавал,ада).
 мать(тувалкаин,цилла).
 ( адам  - человек; объект является человеком, если он имеет мать;  ева – человек. Перечисленные люди имеют указанных матерей). В этом случае если бы мы сделали запрос
 ?- человек (X).
 то ответом было бы:
 X = адам;
 X = каин;
 X = авель;
 X = иавал;
 X = тувалкаин;
 X = ева.
 Давайте рассмотрим более интересный случай, когда имеются два целевых утверждения, для каждого из которых есть несколько решений. Предположим, что мы планируем провести вечеринку и хотим порассуждать о том, кто с кем мог бы танцевать. Мы можем начать писать программу следующим образом:
 возможная_пара(X, Y):- парень(Х), девушка(Y).
 парень(джон).
 парень(мармадук).
 парень(бертрам).
 парень(чарлз).
 девушка(гризелда).
 девушка(эрминтруда).
 девушка(брунхильда).
 В программе определено, что  X и  Y образуют возможную пару, если  X является парнем, a  Y — девушкой. Теперь давайте посмотрим, какие возможные пары имеются:
 ?- возможная_пара(X, Y).
 X = джон, Y = гризелда;
 X = джон, Y = эрминтруда;
 X = джон, Y = брунхильда;
 X = мармадук, Y = гризелда;
 X = мармадук, Y = эрминтруда;
 X = мармадук, Y = брунхильда;
 X = бертрам, Y = гризелда;
 X = бертрам, Y = эрминтруда;
 X = бертрам, Y = брунхильда;
 X = чарлз, Y = гризелда;
 X = чарлз, Y = эрминтруда;
 X = чарлз, Y = брунхильда.
 Вы должны быть уверены, что понимаете, почему Пролог породил решения в таком порядке. Прежде всего он ищет сопоставление для цели  парень(X)  и находит, что первым парнем является  джон.  Затем он находит сопоставление для цели  девушка(Y) , выбирая  гризелда  в качестве первой девушки. В этом месте мы запрашиваем новое решение, вводя ';'. Пролог поэтому считает, что последнее доказательство согласованности цели потерпело неудачу, и делает попытку вновь доказать согласованность последней из рассматривавшихся целей. Этой целью является утверждение девушка, встретившееся при доказательстве согласованности целевого утверждения  возможная_пара.  Обнаруживается альтернативный вариант  эрминтруда,  и, следовательно, следующим решением является пара  джон  и  эрминтруда.  Аналогично порождается пара  джон  и  брунхильда  в качестве третьего решения. При следующей попытке доказать согласованность целевого утверждения  девушка(Y)  Пролог обнаружит, что маркер, соответствующий этому целевому утверждению, находится в конце базы данных и, следовательно, попытка найти новое сопоставление для этого целевого утверждения терпит неудачу. Тогда делается попытка вновь доказать согласованность целевого утверждения  парень(Х),  маркер которого был установлен на первый факт предиката  парень,  и, следовательно, следующим найденным решением, соответствующим второму парню, является  мармадук.  Теперь, когда для этого целевого утверждения найдено новое решение, Пролог определяет, что следует делать далее – он должен найти сопоставление для цели  девушка(Y),  осуществляя поиск решения с самого начала базы данных. Так что он выбирает гризелда в качестве первой девушки. Следующие три решения содержат  мармадук  и имена трех девушек. Очередная попытка найти альтернативное решение для цели  девушка  заканчивается неудачей. Поэтому ищется другой парень, а поиск среди девушек производится с начала базы данных. Аналогичным образом происходит выполнение программы и далее.
 В конце концов сложится ситуация, когда доказательство согласованности целевого утверждения  девушка  закончится неудачей и при этом будут также исчерпаны все решения для целевого утверждения  парень.  Программа не может более найти ни одной пары.
 Все приведенные примеры являются очень простыми. Они содержат лишь определения большого числа фактов или используют правила для доступа к этим фактам. По этой причине они могут порождать только конечное число возможных решений. В некоторых случаях нам может потребоваться порождать бесконечное число возможных вариантов – не потому, что мы хотим рассмотреть их все, а потому, что мы не знаем заранее, сколько их понадобится. В этом случае необходимо рекурсивное определение (обсуждавшееся в предыдущей главе).
 Рассмотрим следующее определение целого числа (здесь под «целым» числом понимается целое положительное число). Целевое утверждение  целое _ число(N)  согласуется с базой данных, если переменная  N конкретизирована и ее значением является целое число. Если переменная  N неконкретизирована в момент рассмотрения целевого утверждения, то попытка найти соответствие для утверждения  целое_число (N) приведет к тому, что будет выбрано целое число, которое будет присвоено N в качестве значения.
 /* 1 */ целое_число(0).
 /* 2 */ целое_число (X):- целое_число (Y),X is Y+1)
 Если мы зададим вопрос
 ?- целое_число (X).
 то получим в качестве возможных ответов все целые числа в порядке возрастания (0, 1, 2, 3,…), по одному числу каждый раз. Всякий раз, когда инициируется возврат (возможно, в результате ввода точки с запятой ';'), для предиката  целое_число  находится новое сопоставление, в результате чего его аргументу присваивается очередное целое число. Таким образом, это короткое определение порождает бесконечное число решений. Почему? На рис. 4.1, 4.2, 4.3 показана последовательность событий, приводящая к порождению трех первых решений. На каждом этапе самый нижний указатель (1) на рисунке указывает место, где впоследствии будет выбрано  иное решение.  Первоначально для ответа на вопрос имеется выбор между фактом  1 и правилом  2 . Если выбирается факт  1 , то ничего более выбирать не придется, и мы получаем X = 0. В противном случае выбирается правило  2 и ищется соответствие для цели, порождаемой этим правилом. Если выбирается факт  1 , то завершается доказательство целевого утверждения с ответом  X=1 ; в противном случае используется правило  2 и снова ищется соответствие для появившейся подцели. И так далее. На каждом этапе первое что делает Пролог – это выбирает факт  1 . Только при выполнении возврата он изменяет последний сделанный им выбор. Каждый раз, когда он это делает, он возвращается к тому месту, где в последний раз выбирал факт  1 , и выбирает вместо него правило  2 . При этом выборе появляется новая подцель. Факт  1 представляет первую возможность для сопоставления с этой подцелью.
 Рис. 4.1.
 Рис. 4.2.
 Рис. 4.3.
 Большинство правил на Прологе будут порождать альтернативные решения, если они сопоставляются с целями, содержащими большое число неконкретизированных переменных. Например, отношение принадлежности элемента списку:
 принадлежит(X,[X |_] ).
 принадлежит(X,[_ |Y]):- принадлежит(X,Y).
 порождает альтернативные решения. Если мы задаем вопрос
 ?- принадлежит(а,X).
 (обратите внимание, что  X в вопросе является неконкретизированной переменной), то последовательные значения переменной  X будут представлять частично конкретизированные списки, в которых  а является первым, вторым, третьим и так далее элементом списка. Убедитесь, что вы понимаете, почему так получается. Другим следствием возврата, допускаемого при выполнении предиката принадлежит, является то, что вопрос
 ?- принадлежит(а,[а,b,r,а,с,а,d,а,b,r,а]).
 фактически может быть согласован  пятью способами.  Очевидно, что имеются приложения предиката  принадлежит , в которых требуется найти лишь одно решение, если оно вообще существует, и затем отбросить (обойти) остальные возможные решения. Такое отбрасывание оставшихся решений может быть реализовано с помощью «отсечения».

 4.2. Отсечение

 Этот раздел посвящен специальному механизму, используемому в программах на Прологе и называемому «отсечением» [8] . Отсечение позволяет указать, какие из сделанных ранее выборов не следует пересматривать при возврате по цепочке согласованных целевых утверждений. Существуют две причины, побуждающие включать в программу такие указания:
 • Программа будет выполняться быстрее, так как не будет тратиться время на попытки найти новые сопоставления для целей, о которых заранее известно, что они не внесут более ничего нового в решение.
 • Программа может занимать меньше места в памяти ЭВМ, так как отсутствие необходимости запоминать точки возврата для последующего анализа позволяет более экономно использовать память.
 В некоторых случаях включение отсечения в программу может означать переход от программы, которая не будет работать, к программе, которая будет работать.
 Синтаксически использование в правиле отсечения выглядит как вхождение целевого утверждения с предикатом '!', не имеющим аргументов. Как целевое утверждение этот предикат всегда согласуется с базой данных и не может быть вновь согласован. Однако он имеет побочный эффект, который изменяет процесс последующего возврата. Эффект заключается в том, что маркеры некоторых целей становятся недоступными, так что для этих целей нельзя найти новые сопоставления. Рассмотрим, как это происходит на примере. Предположим, что вы заведуете библиотекой и имеете базу данных на Прологе, содержащую информацию о наличии книг, о том, кто и какие книги взял и когда книги должны быть возвращены. Один из вопросов, который мог бы вас интересовать,- это какие виды услуг, предоставляемых библиотекой, доступны каждому из читателей. Некоторые услуги, которые мы могли бы назвать основными, должны быть доступны любому читателю. Они включают пользование каталогом и справочным бюро. С другой стороны, дополнительные услуги, такие как пользование абонементом или получение книг из других библиотек, хотелось бы предоставлять читателю выборочно. Одно из правил могло бы состоять в том, что если читатель не возвратил в указанный срок книгу, то дополнительные виды услуг ему недоступны до тех пор, пока он не вернет книгу. Здесь приведена часть программы, которая использует это правило:
 услуги(Читатель,Вид_услуг):-
  книга_не_возвращена(Читатель,Книга),!,основные_услуги (Вид_услуг).
 услуги(Читатель,Вид_услуг):-общие_услуги(Вид_услуг).
 основные_услуги(пользование_каталогом).
 основные_услуги(получение_справок).
 дополнительные_услуги (абонемент).
 дополнительные_услуги(межбиблиотечный_абонемент).
 общие_услуги(X):-основные_услуги(X).
 общие_услуги(X):-дополнительные_услуги(X).
 книга_не_возвращена('С. Уотзер',книга10089),
 книга_не_возвращена('А. Джонс', книга29907).
 . . .
 читатель('А.Джонс'). читатель('В.Метеск').
 Зачем понадобилось использовать отсечение в этой программе и какой эффект оно оказывает? Предположим, что вы хотите просмотреть список всех читателей и определить, какие услуги им доступны. В этом случае вам надо обратиться к Прологу со следующим вопросом:
 ?- читатель(X), услуги(X,Y).
 Начав поиск ответа, Пролог выберет первого читателя:  А.Джонс.  Предположим, что этот читатель имеет на руках несколько не возвращенных в указанный срок книг. Для того чтобы определить, какие услуги доступны ему, Пролог воспользуется первым утверждением для предиката  услуги.  Это приводит к появлению нового целевого утверждения –  книга_не_возвращена.  После небольшого поиска среди фактов  книга_не_возвращена  обнаружен факт о первой не возвращенной А. Джонсом в срок книги (второй факт для этого предиката). Следующее целевое утверждение – это отсечение. Эта цель автоматически согласуется с базой данных, и в результате этого в системе закрепляются все решения, принятые с момента выбора первого утверждения  услуги.
 Мы можем представить ситуацию, возникшую непосредственно перед выполнением отсечения, в виде диаграммы, приведенной на рис. 4.4. Когда в программе встречается отсечение, то оно «отсекает» путь, представляющий цепочку выполненных доказательств таким образом, что следующая цель соединяется непосредственно с исходной (см. рис. 4.5). Результат действия отсечения в правиле для предиката  услуги  (утверждение 1) заключается в том, что все цели, выбранные с момента, когда было выбрано это правило, запоминаются в системе как неизменяемые при обратном просмотре.
 Путь, представляющий цепочку найденных доказательств, при этом изменяется так, что исключаются все маркеры, соответствующие целям, расположенным между  услуги  и отсечением включительно. Таким образом, если впоследствии произойдет возврат на точку! (отсечение), то попытка согласовать цель  услуги  немедленно потерпит неудачу. Система не будет рассматривать альтернативные решения для целевого утверждения  книга_не_возвращена ('А. Джонс', Книга),  и это совершенно разумно, так как мы интересуемся лишь тем, числится ли за читателем  хотя бы одна  не возвращенная в срок книга, а не тем, каковы  все  книги, числящиеся за ним. Утверждение 2 в предикате  услуги  тоже рассматриваться системой не будет, так как при возврате обходится и выбор правила, в котором встречается отсечение. Такое поведение системы в рассматриваемой ситуации тоже является разумным, так как мы не хотим порождать решения, указывающие на то, что  А. Джонсу  доступны все услуги.
 Рис. 4.4.
 Рис. 4.5.
 Действие отсечения в этом примере можно резюмировать следующим образом:
 Если оказывается, что читатель имеет не возвращенную в срок книгу, то ему разрешается пользоваться лишь основными видами услуг, предоставляемыми библиотекой. Нет необходимости выявлять все книги, не возвращенные читателем в срок, равно как нет необходимости рассматривать какие-либо другие правила относительно услуг, предоставляемых читателю.
 В этом примере использование отсечения привело к «сокращению» всех решений, принятых после выбора целевого утверждения  услуги.  Оно называется  родительским  целевым утверждением для отсечения, так как именно это целевое утверждение привело к использованию правила, содержащего отсечение. На наших диаграммах родительским целевым утверждением всегда является целевое утверждение, соответствующее наименьшему прямоугольнику, содержащему прямоугольник с '!'. Формальное определение эффекта, производимого отсечением, формулируется следующим образом:
 Если отсечение встречается в качестве целевого утверждения, то после этого система лишается возможности изменять решения, принятые ею с момента вызова родительского целевого утверждения. Все альтернативы принятым решениям отбрасываются. Следовательно, попытка вновь доказать согласованность с базой данных любого целевого утверждения между родительским целевым утверждением и ! (отсечением) закончится неудачей.
 Существуют различные способы описания того, что произошло с решениями, попавшими в область действия отсечения. Можно сказать, что эти решения отсекаются или замораживаются, что система лишается возможности изменять эти решения или что оставшиеся альтернативы отбрасываются. Можно также смотреть на символ отсечения как на некий разделитель (забор), отделяющий целевые утверждения. Так, при обработке конъюнкции целей
 foo:- а, b, с,!, d, e, f
 Пролог без каких-либо ограничений может выполнять возврат среди целей  a ,  b и  с   до тех пор,  пока доказательство согласованности целевого утверждения  с  с базой данных не приведет к тому, что Пролог «перешагнет» через «забор»! и приступит к доказательству согласованности целевого утверждения  d . Далее возврат может осуществляться между целевыми утверждениями  d ,  e и  f , при этом, возможно, неоднократно будет достигаться согласованность всей конъюнкции целиком. Однако если произойдет неудача при доказательстве согласованности целевого утверждения  d , что вызовет «перешагивание через забор» справа налево, то никаких попыток вновь доказать согласованность целевого утверждения  с  делаться не будет; доказательство согласованности конъюнкции целей в целом, а следовательно, и цели  foo потерпит неудачу.
 Прежде чем перейти к рассмотрению других примеров с использованием отсечения, сделаем еще одно замечание. Мы сказали, что если отсечение появляется в некотором правиле и выбирается в качестве целевого утверждения, то Пролог-система лишается возможности  изменять все решения, принятые с момента вызова родительского целевого утверждения.  Это значит, что выбор этого правила и всех решений, принятых после него, становится зафиксированным. Далее мы увидим, что есть возможность указывать альтернативы в  рамках одного правила,  используя встроенный предикат ';' (обозначающий « или »). На выбор альтернатив, сделанный с использованием этой возможности, эффект отсечения действует точно так же, т. е. при отсечении фиксируются все « или »-выборы, сделанные с момента выбора правила, содержащего отсечение.

  4.3. Общие случаи использования отсечения

 Мы можем выделить три основных случая использования отсечения.
 Первый связан с ситуациями, когда мы хотим указать Пролог-системе, что она нашла нужное правило для заданного целевого утверждения. В этом случае отсечение означает: «если вы дошли до этого места, то вы выбрали именно то правило, которое нужно для данного целевого утверждения».
 Второй случай относится к ситуации, когда мы хотим указать Пролог-системе, что необходимо немедленно прекратить доказательство согласованности конкретного целевого утверждения, не пытаясь найти для него альтернативные решения. В этом случае используется конъюнкция отсечения с предикатом  fail,  что означает; «если вы дошли до этого места, то вам следует прекратить попытки доказать согласованность данного целевого утверждения».
 К третьему случаю относятся ситуации, когда мы хотим закончить порождение альтернативных решений механизмом возврата. В этом случае отсечение означает: «если вы дошли до этого места, то вы нашли единственное решение задачи и никакой возможности найти другие альтернативные решения нет».
 Теперь мы рассмотрим несколько примеров использования отсечения в перечисленных выше ситуациях. Однако необходимо помнить, что во всех этих случаях отсечение имеет один и тот же смысл. Выделение трех случаев использования отсечения обусловлено чисто методическими соображениями, чтобы показать, по каким причинам в программах могут использоваться отсечения.

 4.3.1. Подтверждение правильности выбора правила

 При программировании на Прологе очень часто возникает желание использовать для описания одного предиката несколько утверждений. Одно утверждение будет использоваться, если аргументы имеют один вид, другое будет использоваться для аргументов иного вида и так далее. Часто мы можем указать, какое правило следует использовать для данного целевого утверждения, указав в качестве аргументов в заголовке правила необходимые образцы структур так, чтобы это правило могло быть сопоставлено лишь с соответствующими целевыми утверждениями. Однако это не всегда возможно. Если мы не можем сказать заранее, какого вида аргументы будут использоваться, или если мы не можем перечислить все множество возможных образцов аргументов, то мы можем принять компромиссное решение. Это значит, что задаются правила для аргументов определенных типов, а в конце задается правило-«ловушка» для всех остальных правил. В качестве примера такого способа рассмотрим следующую программу. Определим предикат сумма таким образом, что при выборе в качестве целевого утверждения  сумма(N, X) , где  N – некоторое целое число, переменной  X присваивается значение, равное сумме всех целых чисел от  1 до  N . Так, например, возможен следующий диалог:
 ?- сумма(5,X).
 X = 15;
 нет
 Полученный ответ объясняется тем, что 1+2+3+4+5 равно 15. Здесь приведена соответствующая программа.
 сумма(1,1):-!.
 сумма(N,Результат):- N1 is N-1, сумма(N1,Результат),Результат is Результат+N.
 Приведенное определение является рекурсивным. Идея состоит в том, что выход на граничное условие происходит в случае, когда первый аргумент равен 1. В этом случае ответ тоже равен  1 . Второе утверждение вводит рекурсивное целевое утверждение  сумма . Однако первый аргумент нового целевого утверждения на единицу меньше, чем первый аргумент в исходном целевом утверждении. Следующее целевое утверждение, которое будет порождено этим целевым утверждением, снова будет иметь первый аргумент на единицу меньше. И так далее до тех пор, пока не будет достигнуто граничное условие. Так как первый аргумент всегда на единицу меньше, то в конце концов произойдет выход на граничное условие (в предположении, что исходное целевое утверждение имеет первый аргумент не меньше 1) и выполнение программы закончится.
 Представляет интерес то, как в этой программе организована обработка двух случаев: когда число, соответствующее первому аргументу, равно  1 и когда оно отлично от  1 . Когда мы определяли предикаты для обработки списков, то было легко указать два типичных случая: когда список был пустым ([]) и когда он имел вид  [A|B].  Для чисел это не так просто сделать, потому что мы не можем задать такой аргумент, который был бы сопоставим только с целым числом, не равным 1. Приемлемое решение в данном примере состоит в том, чтобы выделить случай, когда первый аргумент равен 1, и обеспечить сопоставление для всех остальных случаев с помощью переменной. Мы знаем, что в соответствии со стратегией, используемой при поиске в базе данных, Пролог сначала будет пытаться произвести сопоставление с правилом для  1 , и только в случае неудачи он попытается использовать второе правило. Таким образом, второе правило используется только для чисел, не равных  1 . Но этим дело не кончается. Если когда-либо Пролог будет выполнять возврат и попытается пересмотреть выбор правила с первым аргументом, равным  1 , то он обнаружит, что второе правило тоже применимо. Как можно видеть, оба правила являются альтернативными для целевого утверждения  сумма(1,X).  Мы должны указать Прологу, что ни в коем случае не следует использовать второе правило, если число, соответствующее первому аргументу, равно 1. Один из способов сделать это – вставить отсечение в первое правило (как это и показано в записи этого правила). Это отсечение указывает Прологу, что если выбрано первое правило, то больше не следует принимать нового решения относительно того, какое правило использовать для целевого утверждения  сумма. В  случае если число, соответствующее первому аргументу, действительно равно  1 , может произойти только выбор первого правила.
 Давайте посмотрим, как все это выглядит на языке диаграмм. Если мы обратимся к предикату  сумма(1,X)  в следующем контексте:
 выполнить:- сумма(1,X), foo(apples)
 ?-выполнить.
 и для цели  foo(apples)  нет сопоставления, то к моменту, когда обнаружится несогласованность  foo(apples)  с базой данных, результат работы Пролога будет иметь вид, как показано на рис. 4.6. Если Пролог попытается найти новые сопоставления для целевых утверждений, просматривая их в обратном порядке, то обнаружится, что рассмотренные выше два альтернативных целевых утверждения не могут быть пересмотрены, так как они исключены из цепочки доказательства. Следовательно, наиболее верный путь – не пытаться найти другое сопоставление для предиката  сумма(1,X).
 Рис. 4.6.
  Упражнение 4.1.  Что произойдет в процессе возврата при попытке найти новое сопоставление для целевогоутверждения  сумма,  если из первого правила для предиката  сумма  удалить отсечение? Какие альтернативные результаты будут получены (если вообще они будут возможны) и почему?
 Последний пример показал, как можно использовать отсечение для того, чтобы сделать поведение Пролога чувствительным к случаю, когда мы не можем выделить все возможные случаи путем перечисления образцов в заголовках правил. Более типичная ситуация, в которой мы не можем указать структуру заголовков правил для выполнения сопоставления, возникает, если мы хотим ввести дополнительные условия в виде целевых утверждений Пролога, позволяющих в процессе согласования с базой данных выбрать соответствующие правила. Рассмотрим следующий альтернативный вариант решения последнего примера:
 сумма(N,1):- N =‹ 1,!.
 cyммa(N,R):- N1 is N-1, сумма(N1,R1), R is Rl+N
 В этом случае указывается, что первое правило следует выбрать, когда заданное количество суммируемых чисел меньше или равно единице. Такое определение правила немного лучше, чем предыдущее, потому что соответствующая ему программа даст ответ (вместо того чтобы выполняться бесконечно), если в качестве первого аргумента будет задан  0 или отрицательное число. Если условие первого правила выполняется, то сразу же выдается результат  1 и не требуется прибегать к рекурсивному порождению целевых утверждений. Второе правило следует попытаться использовать лишь в случае, когда это условие не выполняется. Мы должны указать Прологу, что если уже обнаружено, что N  = ‹  1, то не следует возвращаться к пересмотру выбора правила. Это как раз и достигается с помощью отсечения.
 Общий принцип заключается в том, что использование механизма отсечения для указания Прологу на ситуации, когда он выбрал единственно правильное правило, может быть заменено использованием предиката  not.  Это встроенный предикат Пролога, т. е. определение этого предиката заранее известно Пролог-системе. Поэтому его можно использовать, не выписывая каждый раз его определение (более полно встроенные предикаты описываются в гл. 6). Предикат  not  определен таким образом, что целевое утверждение  not(X)  истинно, только если X, рассматриваемое как целевое утверждение, не согласуется с базой данных. Таким образом,  not(X)  означает, что  X  недоказуемо как целевое утверждение Пролога,  т. е. не согласовано с базой данных. В качестве примера использования  not  вместо отсечения перепишем два варианта определения предиката  сумма  следующим образом:
 сумма(1,1).
 cyммa(N,R):- not(N = 1), N1 is N-1, cyммa(N1,R1),R is N1 + R1.
 или
 сумма(N,1):- N =‹1.
 сумма(N,R):- not(N=‹l), N1 is N-1, сумма(N1,R1 ), R is N1 + R1.
 В действительности в Прологе имеются другие удобные встроенные предикаты, которые могут заменить оба из приведенных вхождений предиката  not.  Например, можно заменить  not(N=1)  на  N\=1,  a  not(N  =‹  1)  на  N›1.  В общем случае это можно сделать не со всеми возможными условиями.
 Использование предиката  not  вместо отсечения свойственно для хорошего стиля программирования. Это связано с тем, что программы, содержащие отсечения, как правило, более трудны для чтения, чем программы, не содержащие их. Если удается локализовать все вхождения отсечения и заменить их с помощью предиката  not , то программа станет более понятной. Однако определение not предполагает попытку доказать, что заданное целевое утверждение согласуется с базой данных. Поэтому если мы имеем программу, в общем виде представимую как
  A:-B, C
  A:-not(B),D
 то Прологу для успешного завершения программы может потребоваться две попытки согласовать  B.  Он должен попытаться согласовать  B при просмотре первого правила. Но если затем будет выполнен возврат и рассмотрено второе правило, то он будет вынужден попытаться согласовать  B вновь, чтобы убедиться, может ли быть согласовано  not(B).  Такое дублирование приводит к потере эффективности программы, когда условие  B  достаточно сложно. Этого бы не произошло, если бы вместо приведенной программы мы имели:
  A:-B,!,C
  A:-D
 Таким образом, иногда нужно взвесить преимущества ясной программы по сравнению с преимуществами ее быстрого выполнения. Обсуждение вопроса эффективности приводит нас к последнему примеру, в котором отсечение используется для фиксирования выбора правила. Рассмотрим определение предиката  присоединить :
 присоединить([],X,X).
 присоединить([А|В],С,[А|D]) – присоединить(В,С,D).
 Если предикат  присоединить  используется лишь в случаях, когда, имея два списка, мы хотим найти список, получающийся в результате добавления элементов второго списка в конец первого, то такая программа неэффективна, поскольку, если выполняется возврат при обработке целевого утверждения вида  присоединить([],[a,b,c,d],X) , Пролог обязан сделать попытку использовать второе правило, несмотря на то что эта попытка заранее обречена на неудачу. В таком контексте пустота первого списка указывает на то, что первое правило является единственным возможным для использования и эта информация может быть сообщена Прологу с помощью отсечения. В общем случае при применениях Пролог-системы смогут лучше использовать имеющуюся память, если сообщать системе такие сведения, по сравнению с тем, когда она должна хранить информацию о выборе правил, которая в действительности использована не будет. Можно с этой целью переписать наше определение следующим образом:
 присоединить([],X,X):-!.
 присоединить([А|В],С,[А|D]:- присоединить(В,С,D).
 При сделанных предположениях относительно применения предиката  присоединить это никак не повлияет на то, какие решения найдет программа, но несколько повысит ее эффективность по времени выполнения и объему занятой памяти. В качестве платы за это мы потеряли возможность использования предиката  присоединить в других ситуациях – он больше не будет работать ожидаемым образом, что будет показано в разд. 4.4.

  4.3.2. Комбинация «отсечение-fail»

 Во втором из перечисленных выше случаев применения отсечение используется в конъюнкции с встроенным предикатом  fail – еще одним встроенным предикатом, подобным  not . Предикат  fail не имеет аргументов, это означает, что выполнение целевого утверждения  fail не зависит от того, какие значения имеют переменные. Действительно, предикат  fail определен таким образом, что доказательство его согласованности как целевого утверждения всегда заканчивается неудачей и приводит к включению механизма возврата. Это в точности совпадает с тем, что происходит, когда мы пытаемся найти сопоставление для целевого утверждения, для которого в базе данных нет ни фактов, ни правил. Если  fail встречается после отсечения, то нормальное выполнение возврата изменится в результате действия механизма отсечения. Данная комбинация «отсечение- fail » оказывается очень полезной на практике.
 Давайте обсудим, как можно было бы использовать эту комбинацию в программе вычисления размера налога, который следует уплатить тому или иному человеку. Один из вопросов, на который мы хотели бы получить ответ – это является ли человек «средним налогоплательщиком». В этом случае вычисления были бы очень простыми и не требовали бы рассмотрения множества особых случаев. Давайте определим предикат  средний_налогоплательщик , где  средний_налогоплательщик(X) означает, что  X является средним налогоплательщиком. Например, Френд Влоггс, который женат, имеет двух детей и работает на велосипедном заводе, мог бы рассматриваться как действительно средний налогоплательщик. Однако директор-распорядитель нефтяной компании получает, по-видимому, достаточно много, а пенсионер – слишком мало, чтобы в обоих случаях был приемлем один и тот же способ вычисления налога. Нам следовало бы начать с особого случая. Возможно, что на иностранного гражданина распространяются особые налоговые законы, так как он может иметь налоговые обязательства также и в своей стране. Поэтому, каким бы средним он ни являлся в других отношениях, иностранец не будет классифицирован как средний налогоплательщик. Мы можем начать запись правил об этом следующим образом:
 средний_ налогоплательщик(X):- иностранец(X), fail .  
 средний_налогоплательщик(X):-…
 В этой выдержке из программы  (которая является неверной)  в первом правиле делается попытка сказать: «если X – иностранец, то доказательство согласованности целевого утверждения  средний_налогоплательщик(X) должно закончиться неудачей». Второе правило должно использовать общий критерий того, что значит быть средним налогоплательщиком в тех случаях, когда  X – не иностранец. Ошибка заключается в том, что если бы мы обратились с вопросом
 ?- средний_налогоплательщик(видслевип).
 об иностранце по фамилии  видслевип,  то произошло бы сопоставление с первым правилом и согласованность целевого утверждения  иностранец  была бы доказана. Далее, целевое утверждение  fail  инициировало бы возврат. При попытке найти новое сопоставление для цели  средний_налогоплательщик  Пролог нашел бы второе правило, определяющее общие критерии вычисления налога, и начал бы применять это правило к  видслевип.  Вполне вероятно, что этот иностранец удовлетворил бы общим критериям, что привело бы к неверному ответу «да».
 Таким образом, первое правило оказалось абсолютно неэффективно при «отбраковке» нашего приятеля как среднего налогоплательщика. Почему так получается? Ответ кроется в том, что при возврате Пролог пытается найти новое сопоставление для  каждого  целевого утверждения, рассматривавшегося ранее. Поэтому, в частности, будут исследованы альтернативные способы сопоставления для  средний_налогоплательщик(видслевип) . Для того чтобы остановить поиск альтернатив в данном случае, необходимо отсечь сделанный выбор правила (заморозить решение), прежде чем будет выполнен предикат  fail.  Мы можем сделать это, вставив отсечение перед  fail.  Несколько более обстоятельное определение предиката  средний_налогоплательщик,  включающее эти изменения, приведено ниже:
 средний_налогоплателыцик(Х):- иностранец(Х),!,fail.
 средний_налогоплательщика(X):-супруга(Х,Y), доход(Y,Доход), Доход › 3000,!, fail.
 средний_налогоплателыцик(Х):- доход(X,Доход),2000 ‹ Доход, 20000 › Доход.
 доход(Х,Y):- получаемое_пособие(Х,Р),Р‹5000,!, fail .
 доход(Х,Y):-жалованье(Х,Z),доход_от_капиталовложений(X,W),Y is Z + W.
 доход_от_капиталовложений(Х,Y):-…
 Обратите внимание на использование в этой программе других комбинаций «отсечение- fail ». Во втором правиле  средний_налогоплательщик говорится, что попытка показать, что некоторый человек является средним налогоплательщиком, может быть прервана, если можно показать, что заработок его супруги превышает некоторый порог. Точно так же в определении предиката  доход  указано (в первом правиле), что если человек получает пособие, сумма которого меньше некоторого порога, то независимо от других обстоятельств мы будем рассматривать его как вовсе не имеющего дохода.
 Интересный пример использования комбинации «отсечение- fail»  представляет предикат  not.  Большинство реализаций имеют этот предикат как встроенный, но интересно рассмотреть, как можно описать его с помощью правил. Мы требуем, чтобы целевое утверждение  not(P),  где  P  обозначает некоторое другое целевое утверждение, было истинным тогда и только тогда, когда доказательство согласованности целевого утверждения  P терпит неудачу. Это не совсем точно соответствует нашему интуитивному пониманию «не является истинным» – далеко не всегда мы можем без опасения считать, что что-то не является истинным, если мы не в состоянии доказать это. Но как бы то ни было, здесь приводится соответствующее определение:
 not(P):- call(P),!, fail.
 not(P)
 Определение предиката  not  содержит обращение к аргументу  P как к целевому утверждению с использованием встроенного предиката  call.  Предикат  call  просто интерпретирует свой аргумент как целевое утверждение и пытается доказать его согласованность. Мы хотим, чтобы первое правило применялось в тех случаях, когда согласуется  P с базой данных, а в противном случае должно применяться второе правило. Таким образом, мы говорим, что если Пролог может согласовать  call(P),  то он должен прекратить на этом правиле доказательство целевого утверждения  not.  Другая возможность имеет место, если Пролог не может согласовать  call(P).  В этом случае он никогда не дойдет до отсечения. Так как доказательство согласованности  call(P)  потерпело неудачу, то происходит возврат, и Пролог обнаруживает второе правило. Следовательно, доказательство согласованности целевого утверждения  not(P)  закончится успешно в случае, когда  P недоказуемо.
 Как и в первом случае применения отсечения, мы можем заменить любое употребление комбинации «отсечение- fail»  использованием предиката  not.  Такая замена требует несколько большей реорганизации программы, чем ранее, но при этом не приводит к потере эффективности. Если бы мы стали с этой целью переписывать нашу программу для предиката  средний _ налогоплательщик,  то следовало бы начать ее примерно так:
 средний_налогоплателыцик(X):-
  nоt(иностранец(X)),not((супруга(X,Y),доход(Y,Доход), Доход›3000)), доход(Х, Доход1),…
 Обратите внимание на то, что в этом примере конъюнкция целей, являющаяся аргументом  not,  заключена в скобки. Для того чтобы однозначно показать, что запятые разделяют цели в конъюнкции (а не аргументы предиката  not),  мы заключили аргумент предиката  not  в дополнительные круглые скобки.
 Теперь мы можем рассмотреть последнюю основную область применения отсечения в программах на Прологе – завершение последовательности порождения и проверки вариантов. Очень часто программа состоит из частей, соответствующих следующей общей модели. Имеется последовательность целей, которые могут быть согласованы множеством различных способов и которые порождают много возможных решений при возврате. Кроме того, имеются цели, проверяющие приемлемость порожденных решений для последующего использования. Если поиск сопоставлений для этих целевых утверждений закончится неудачей, то возврат приведет к тому, что будет предложено новое решение. Новое решение будет подвергнуто проверке на пригодность и так далее. Процесс завершится, либо когда будет порождено приемлемое решение (успех), либо когда нельзя больше найти решений (неудача). Мы можем назвать «генератором» целевые утверждения, которые порождают все возможные альтернативы, а целевые утверждения, которые проверяют пригодность решения, - «контролером». Давайте рассмотрим пример такой программы. Приводимый ниже фрагмент мог бы быть частью программы, играющей в крестики-нолики. Эта программа использует встроенные предикаты  var  и  arg,  которые подробно рассмотрены в гл. 6.
 вынужденный ход(Доска,K):- линия(Клетки), угроза(Клетки,Доска,K),!.
 линия([1,2,3]).
 линия([4,5,6]).
 линия([7,8,9]).
 линия([1,4,7]).
 линия([2,5,81).
 линия([3,6,9]).
 линия ([1,5,9]).
 линия([3,5,7]).
 угроза([X,Y,Z],B,X):- пусто(Х,В), крестик (Х,В), крестик(Z,B).
 угроза([X,Y,Z],B,Y):- пусто(Y,B), крестик (Х,В), крестик(Z,B). 
 угроза([X,Y,Z],B,Z):- пусто(Z,B), крестик(Х,В), крестик(Y,B).
 пусто(К,Доска):- arg(K,Дocкa,C), var(C).
 крестик(К,Доска):- arg(K,Дocкa,C), nonvar(C), C=X.
 нолик(К,Доска):- arg(К,Доска,С), nonvar(C), С=0.
 Для тех, кто не знаком с этой игрой, вкратце объясним ее правила. Два игрока по очереди заполняют клетки на доске размером 3x3. Один игрок использует для этого символ 0, а другой игрок — символ X. Цель игры — расположить три своих символа подряд по одной линии (вертикальной, горизонтальной или диагональной). Мы можем перенумеровать девять клеток на доске следующим образом:
 Предполагается, что программа действует за игрока, делающего свои ходы ноликами. Предикат  вынужденный_ход  используется для ответа на вопрос: «Нужно ли делать вынужденный ход в конкретной позиции?» Такая ситуация имеет место, если игрок 0 (игрок, делающий ходы ноликами, т. е. программа) не может выиграть немедленно (мы не будем рассматривать этот слу- случай), но есть угроза того, что игрок  X может выиграть следую- следующим ходом. Например, в позиции
 Игрок  0 вынужден поставить  0 в 4-й квадрат, так как если он не сделает этого, то его противник будет иметь возможность на следующем ходу заполнить линию 1-4-7. Программа работает, пытаясь найти линию, две клетки которой заполнены крестиками, а третья – пустая. Если такая линия имеется, то игрок 0 вынужден сделать ход, поставив нолик в пустую клетку. В утверждении для предиката  вынужденный_ход цель
 линия(Клетки)
 служит «генератором» возможных линий. Эта цель может быть согласована с базой данных несколькими способами, в частности, присваиванием в качестве значения переменной Клетки одного из возможных списков номеров клеток, находящихся на одной линии. Выбрав линию, необходимо проверить, существует ли угроза со стороны противника на этой линии. Это составляет задачу целевого утверждения, выполняющего функции «контролера»:
 угроза(Клетки,Доска,К)
 В этом целевом утверждении переменная  Доска  используется для представления текущей позиции на доске (т. е. какие клетки заняты и какими символами), а переменная К получает в качестве значения номер клетки, в которой игрок 0 должен поставить нолик (при условии что доказательство этой цели завершается успешно).
 Основная идея программы очень проста – предикат  линия  выдает линию, а затем предикат  угроза проверяет, имеется ли на этой линии угроза. Если это так, то доказательство согласованности исходного целевого утверждения  вынужденный_ход  заканчивается успешно. Иначе инициируется возврат, и предикат  линия  предполагает другую возможную линию. Эта линия также подвергается проверке, и, возможно, снова произойдет возврат. Если мы окажемся в ситуации, когда предикат  линия  не может более порождать линии, то доказательство согласованности целевого утверждения  вынужденный_ход  закончится неудачей (вынужденных ходов нет).
 Теперь рассмотрим, что происходит, если эта программа, являясь частью некоторой большей системы, успешно находит вынужденный ход. Переменная К получит в качестве значения номер клетки, в которой должен быть сделан ход, и эта информация будет использована где нибудь в другом месте в программе. Предположим, что в дальнейшем где-то в программе имеет место неудача при доказательстве согласованности некоторого утверждения и что Пролог в конце концов пытается вновь согласовать целевое утверждение  вынужденный_ход.  Тогда предикат  линия  начнет порождение новых возможных линий, которые должны быть проверены. Это бессмысленно, так как нет никакой пользы в том, чтобы искать альтернативный вынужденный ход. Если найден один из таких ходов, то мы не можем сделать ничего лучше, чем сделать этот ход – неудача при его осуществлении гарантировала бы проигрыш игры. В большинстве случаев, однако, альтернативных вынужденных ходов не будет, и при поиске сопоставления для цели  вынужденный_ход  будут бесполезно просматриваться все неопробованные линии, прежде чем попытка доказать согласованность цели не закончится неудачей. Однако в случае альтернативных ходов известно, что даже если имеется другое решение, оно не может быть использовано без возникновения проблем с использованием первого решения Мы можем предотвратить потерю времени Прологом на поиск различных вынужденных ходов, поместив отсечение в конце соответствующего утверждения. Это приведет к замораживанию последнего успешного решения для предиката  линия.  Введение отсечения равносильно следующему заявлению: «если ищутся вынужденные ходы, то важно найти только первое решение».
 Чтобы понять такое использование отсечения, необходимо лишь рассмотреть общую структуру этой программы. Однако некоторые из деталей также представляют интерес. В программе предполагается, что игровую доску можно описать с помощью структуры, состоящей из девяти компонент. Каждая компонента представляет содержимое клетки с соответствующим номером. Таким образом, в любой момент времени содержимое четвертой клетки доски может быть получено путем выборки четвертого аргумента структуры, представляющей текущую позицию на доске (для этого мы используем встроенный предикат  arg ). Если клетка ничем не заполнена, то переменная будет неконкретизи-рованной; иначе ее значение равно одному из атомов  О или  X . Мы используем предикаты  var  и  nonvar  для того, чтобы определить, занята клетка или нет.
 Давайте рассмотрим другой пример программы, работающей по методу «порождения и проверки». Вернемся к вопросу о делении целых чисел, рассмотренному в разд. 2.5. Большинство Пролог-систем обеспечивают эту возможность автоматически, но здесь представлена программа для целочисленного деления, которая использует лишь операции сложения и умножения.
 разделить(N1,N2,Результат):-
  целое_число(Результат), Произведение_1 is Результат*N2, Произведение_2 is (Результат + 1)*N2, Произведение_1 =‹ N1, Произведение_2›N1,!.
 Это правило использует предикат  целое_число  (как он определен ранее) для порождения числа  Результат,  которое является результатом «деления»  N1 на  N2 . Так, например, результат деления  27 на  6 равен  4 , так как  4

Метки: программирование, языке, язык, пролог
Комментарии: 0 Просмотров: 24 [История изменений] Размер:377464 байт
Последние изменения сделаны: ninpoja Александр Дерксен 415 дней назад

Отправить комментарий

Зарегистрированный Анонимно Имя . Пароль расширенный... ( Вход / Регистрация ) Введите код на картинке  Ваше имя  E-mail  (видим лишь владельцу сайта) WWW  Тема Текст страницы Визуальный редакторПростой редакторПродолжить редактирование В таком виде текст будет выглядеть после сохранения. Ты можешь сохранить его сейчас или продолжить редактирование В тексте можно использовать Wiki или HTML теги Вы не ввели текст записи Я хочу получать уведомления о комментариях по почте