Prolog

Неизвестно

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

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

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

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

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

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

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

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

знакомством с Микропленнером, языком, близким к логическому программированию, но реализованным не эффективно. Этот отрицательный опыт, относящийся к Микропленнеру, был неоправданно распространен и на Пролог, но позднее, после появления эффективной реализации, предложенной Дэвидом Уорреном, это предубеждение было убедительно снято. Определенная сдержанность по отношению к Прологу объяснялась также существованием "ортодоксальной школы" логического программирования, сторонники которой настаивали на использовании чистой логики, не запятнанной добавлением практически полезных внелогических средств. Практикам в области применения Пролога удалось изменить эту бескомпромиссную позицию и принять более прагматический подход, позволивший удачно сочетать декларативный принцип с традиционным - процедурным. И наконец, третьим фактором, приведшим к задержке признания Пролога, явилось то обстоятельство, что в США в течение долгого времени Лисп не имел серьезных конкурентов среди языков искусственного интеллекта. Понятно поэтому, что в исследовательских центрах с сильными лисповскими традициями возникало естественное противодействие Прологу. Но со временем соперничество между Прологом и Лиспом потеряло свою остроту, и в настоящее время многие считают, что оптимальный подход состоит в сочетании идей, лежащих в основе этих двух языков.

Благодарности

Интерес к Прологу впервые возник у меня под влиянием Дональда Мики. Я благодарен также Лоренсу Берду, Фернандо Перейра и Дэвиду Г. Уоррену, входившим в свое время в эдинбургскую группу разработчиков Пролога, за их советы по составлению программ и многочисленные дискуссии. Чрезвычайно полезными были замечания и предложения, высказанные Эндрью Макгеттриком и Патриком Уинстоном. Среди прочитавших рукопись книги и сделавших ценные замечания были также Игорь Кононенко, Таня Маярон, Игорь Мозетик, Тимоти Ниблетт и Фрэнк Зердин. Мне бы хотелось также поблагодарить Дебру Майсон-Этерингтон и Саймона Пламтри из издательства Эддисон-Уэсли за труд, вложенный в издание этой книги. И наконец, эта книга не могла бы появиться на свет без стимулирующего влияния творческой деятельности всего международного сообщества специалистов по логическому программированию.

Иван Братко

Институт Тьюринга, Глазго

Январь 1986

Назад | Содержание | Вперёд

Назад | Содержание | Вперёд

Часть 1

ЯЗЫК ПРОЛОГ

Глава 1

ОБЩИЙ ОБЗОР ЯЗЫКА ПРОЛОГ

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

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

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

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

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

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

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

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

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

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

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

Рис. 1. 1. Дерево родственных

отношений.