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

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

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

Как и большинство других языков программирования, Пролог существует в множестве различных реализаций, каждая со своими семантическими и синтаксическими особенностями. Для описания в этой книге выбран «базовый» Пролог и все приводимые примеры написаны для стандартной версии, которая соответствует реализациям, разработанным главным образом в Эдинбурге для нескольких различных вычислительных систем: 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 представлен ряд проектов, на которых заинтересованные читатели могут поупражняться в развитии навыков программирования на Прологе.

Мы выражаем благодарность нашим учителям, сформировавшим наши взгляды на программирование: Роду Борстоллу, Питеру Скотту Лэнгстону и Робину Попплстоуну. Мы благодарны друзьям, участвовавшим вместе с нами в совершенствовании Пролога как практического и полезного средства программирования и поддерживавших нас в процессе подготовки этой книги: Алану Банди, Лоренсу Байрду, Роберту Ковальски, Фернандо Перейра и Дейвиду Уоррену. В частности, Лоуренс Байрд поддерживал работу по созданию книги с самого ее начала, предлагая программы,