У Клоксин - ПРОГРАММИРОВАНИЕ НА ЯЗЫКЕ ПРОЛОГ
Наш опыт показывает, что начинающим программы на Прологе представляются более понятными, чем соответствующие программы на традиционных языках программирования. Однако те же самые люди не склонны ценить те ограничения, которые накладывают традиционные языки на использование вычислительных ресурсов. С другой стороны, программист, имеющий опыт работы на традиционных языках программирования, лучше подготовлен к восприятию таких абстрактных понятий, как переменные и управление последовательностью действий. Но, несмотря на прежний опыт, приспособление к стилю программирования на Прологе может вызвать у него затруднения, и может потребоваться много убедительных примеров, прежде чем он начнет относиться к Прологу как к полезному средству программирования. Конечно, мы знаем много высококвалифицированных программистов, воспринявших Пролог с большим энтузиазмом. Тем не менее, цель этой книги не в том, чтобы «обратить в иную веру», а в том, чтобы научить программировать на Прологе.
Как и большинство других языков программирования, Пролог существует в множестве различных реализаций, каждая со своими семантическими и синтаксическими особенностями. Для описания в этой книге выбран «базовый» Пролог и все приводимые примеры написаны для стандартной версии, которая соответствует реализациям, разработанным главным образом в Эдинбурге для нескольких различных вычислительных систем: 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 ВВЕДЕНИЕ
Пролог – язык программирования, используемый для решения задач, сводимых к объектам и отношениям между объектами. В этой главе мы продемонстрируем основные элементы языка на примерах реальных программ, не вдаваясь особенно в детали, формальные правила и исключения. Исходя из этого, мы не старались, чтобы изложение было полным или достаточно точным. Мы хотим как можно быстрее подвести вас к тому моменту, когда вы сможете самостоятельно писать полезные программы, и чтобы добиться этого, мы должны сконцентрировать внимание на основных понятиях: фактах, запросах, переменных, конъюнкциях и правилах. Другие особенности языка Пролог, такие как списки и рекурсия, будут рассмотрены в последующих главах.
Пролог применяется в тех случаях, когда необходимо использовать ЭВМ для решения задачи, которая может быть выражена в терминах объектов и отношений между ними. Например, когда мы говорим: «Джон имеет книгу», мы объявляем, что между одним объектом «Джон» и другим объектом «книга» имеет место отношение обладания. Более того, это отношение имеет определенный порядок: Джон имеет книгу, но книга не имеет Джона! Когда мы задаем вопрос: «Имеет ли Джон книгу?», то нас интересует правильность именно отношения.
При констатации некоторых отношений не всегда упоминаются все объекты, включаемые в них. Например, когда мы говорим: «Драгоценные камни являются ценными», мы имеем в виду, что существует отношение, называемое «являться ценным», которое включает драгоценные камни. Для нас не имеет значения, кто считает, что драгоценные камни являются ценными, и почему он так считает. Это все зависит от того, что вы хотите сказать. При использовании Пролога, когда программируются отношения, подобные приведенным, уровень требуемой детализации также зависит от того, что вы хотите заставить делать ЭВМ.
Существует еще один вопрос идейного плана, который следует упомянуть, прежде чем приступать к программированию. Мы все знакомы с использованием правил для описания отношений между объектами. Например, правило «Два человека являются сестрами, если они оба женского пола и имеют одних и тех же родителей» объясняет нам, что значит быть сестрами. Оно также указывает, как определить, являются ли два человека сестрами: необходимо просто проверить, относятся ли они оба к женскому полу и имеют ли одних и тех же родителей. Важно отметить, что хотя правила обычно бывают упрощенными, тем не менее они приемлемы в качестве определений. В конце концов, не следует ожидать, что определение говорит нам все об определяемом объекте. Например, большинство людей согласится с тем, что в реальной жизни «быть сестрами» значит больше, чем это следует из приведенного правила. Однако, решая конкретную задачу, необходимо сосредоточить внимание именно на таких правилах, которые помогут ее решить. Таким образом, следует обратиться к схематичному и упрощенному определению, если его достаточно для достижения поставленной цели.
Программирование на языке Пролог состоит из следующих этапов:
• объявления некоторых фактов об объектах и отношениях между ними,
