- •Предисловие
- •Глава 1 Введение в Пролог
- •Глава 2 Синтаксис и унификация
- •2.1. Синтаксис термы
- •Константы
- •Переменные
- •Область действия переменных
- •Сложные термы, или структуры
- •Синтаксис операторов
- •Синтаксис списков
- •Синтаксис строк
- •Утверждения
- •Запросы
- •Ввод программ
- •2.2 Унификация
- •Глава 3 Арифметические выражения
- •3.1. Введение
- •3.2. Арифметические выражения
- •3.3. Арифметические операторы
- •3.4. Вычисление арифметических выражений
- •3.5. Сравнение результатов арифметических выражений
- •Глава 4 Рекурсия
- •4.1. Стратегия «разделяй и властвуй»
- •Пример 4.1.1
- •Фаза разбиения
- •Фаза решения задачи
- •4.2. Восходящая стратегия
- •4.3. Рекурсия и эффективность
- •Пример 4.3.2
- •Глава 5 Структуры данных
- •5.1. Списки списковая форма записи
- •А на запрос
- •Некоторые стандартные целевые утверждения для обработки списков
- •5.2. Бинарные деревья представление бинарных деревьев
- •Бинарное дерево на рис.5.2.1 имеет левое поддерево
- •Представление множеств с помощью бинарных деревьев
- •Будем называть линейным представление такого вида, как на рис.5.2.3, и сбалансированным - такое, как на рис.5.2.2.
- •Левому поддереву соответствует отсортированный список
- •Глава 6 Операторы
- •6.1. Операторы и структуры синтаксис операторов
- •Свойства операторов
- •6.2. Позиция операторов
- •6.3. Приоритет операторов
- •6.4. Ассоциативность операторов
- •6.5. Спецификаторы
- •6.6. Операторы объявления
- •6.7. Пример: вычисление многочленов
- •6.8. Системные операторы
- •Глава 7 Механизм возврата и процедурная семантика
- •7.1. Механизм возврата
- •7.2. Пример: задача поиска пути в лабиринте
- •Целевое утверждение не удается согласовать с первым утверждением
- •Если мы введем
- •Если затем мы введем
- •7.3. Обработка фактов с помощью механизма возврата
- •7.4. Предикат repeat
- •7.5. Декларативная и процедурная семантики
- •Характеристики процедуры
- •7.6. Вопросы эффективности
- •Глава 8 Отсечение
- •8.1. Почему используют отсечение?
- •8.2. Использование отсечения
- •Выдав запрос
- •Обратившись к системе с запросом
- •8.3. Ловушки отсечения
- •Глава 9 Встроенные предикаты
- •9.1. Встроенные предикаты
- •9.2. Обновление базы данных Пролога
- •Добавление и удаление утверждений
- •Считывание утверждений в базу данных
- •Предикаты сохранения и восстановления
- •9.3. Особенности ввода и вывода чтение символов
- •Запись символов
- •Считывание термов Предикаты
- •Запись термов
- •9.4. Обработка файлов
- •Редактирование программ на прологе
- •Распечатка предикатов
- •Глава 10 Модули. Пример разработки системы
- •10.1. Модули
- •Пример 10.1.1
- •10.2. Пример разработки системы: деревья решений
- •Описание дерева решений
- •Разработка системы
- •Целевое утверждение
- •Глава 11 Отладка
- •11.1. Трассировка
- •Включение и выключение механизма трассировки
- •Необязательные параметры трассировки
- •Предикаты трассировки
- •Режимы трассировки
- •11.2. Установка контрольных точек
- •Возможные действия в контрольной точке
- •Включение и выключение режима контрольных точек
- •Необязательные параметры режима контрольных точек
- •Предикаты для работы с контрольными точками
- •Режимы, связанные с контрольными точками
- •Основные отладочные предикаты
- •Статистическая информация
Предисловие
Предлагаемая книга поможет вам научиться использовать язык программирования Пролог. В ней рассматриваются структура и методы Пролога, необходимые для разработки эффективных и понятных программ. Книга не дает строгого определения языка Пролог. Такое определение и описание связи Пролога с логикой изложено в учебниках, написанных более квалифицированными специалистами, чем авторы этой книги.
Язык Пролог возвестил о начале новой эры в программировании. Он ориентирован не на разработку решений, а на систематическое и формализованное описание задачи с тем, чтобы решение следовало из составленного описания. В настоящее время в программировании наметился переход от поиска решения задачи к определению того, какое решение требуется. Пролог является существенным шагом в этом направлении. Мы надеемся, что читатели разделят наши взгляды в данной области науки о программировании. Надеемся, что чтение этой книги доставит вам удовольствие.
Глава 1 Введение в Пролог
Пролог существенно отличается от языков, традиционно используемых в программировании. В языках Бейсик, Алгол и Паскаль основным методом программирования является разбиение задачи на дискретные шаги и их последовательное описание. Последовательность шагов отображается в машинные команды, выполняемые компьютером. Отменить ранее выполненные команды невозможно, поскольку содержимое памяти постоянно обновляется. Языки программирования такого вида называются алгоритмическими. Алгоритм - математическая процедура, которая позволяет решить задачу за конечное число шагов. Пролог не относится к алгоритмическим языкам.
Свое название Пролог получил от слов «ПРОграммирование на языке ЛОГики». На самом деле Пролог не считается чистым языком логического программирования, но его создание - важный этап в этом направлении.
Большой интерес к Прологу проявляют специалисты в области инженерии знаний и искусственного интеллекта. Растет его популярность в академическом мире.
Пролог был принят в качестве базового языка в японской программе создания ЭВМ пятого поколения, ориентированной на исследование методов логического программирования и искусственного интеллекта, а также на разработку нового поколения компьютеров, специально предназначенных для реализации данных методов.
При программировании на Прологе значительно упрощается описание решения, и программист имеет возможность заниматься непосредственно задачей, а не поиском способа разбиения ее решения на небольшие шаги, которые можно запрограммировать, как при программировании на алгоритмических языках.
Теоретической основой Пролога является раздел символьной логики, называемый исчислением предикатов. Прологу присущ ряд свойств, которыми не обладают традиционные языки программирования, что делает его мощным средством в области логического программирования. К таким свойствам относятся механизм вывода с поиском и возвратом, встроенный механизм сопоставления с образцом, и простая, но выразительная структура данных с возможностью ее изменения. Пролог отличает единообразие программ и данных. Данные и программы - лишь две различные точки зрения на объекты Пролога. В единой базе данных можно свободно создавать и уничтожать отдельные элементы. Поскольку не существует различия между программами и данными, можно менять программу во время ее работы. В Прологе отсутствуют указатели, операторы присваивания и GO_TO. Естественным методом программирования является рекурсия.
Многие интересные и полезные свойства Пролога непосредственно вытекают из его декларативности. Декларативность позволяет понимать программу, не отслеживая динамику ее выполнения, и является уникальной особенностью Пролога. Однако истинная мощь Пролога базируется не на одном каком-либо свойстве, а на сочетании всех его свойств. Мы приведем их подробное описание в последующих главах, а сейчас дадим общее представление о языке Пролог.
Мы не ставим перед собой цель описать исчисление предикатов, приведем лишь основные принципы, необходимые для изучения Пролога.
В сущности, после завершения работы программы на Прологе (доказательства цели) могут возникнуть только два состояния: «доказано» и «не доказано». Иногда они называются соответственно «истинно» и «ложно». Мы не будем употреблять термины «истинно» и «ложно», поскольку они определяют смысл результата. Доказанное утверждение обычно является истинным, но не обязательно, так как доказательство зависит от известных фактов и сделанных на их основе выводов. Итак, мы ввели два новых термина. Факт есть некоторое утверждение; все факты определяются как доказанные. В частности, факт «рекс - это собака» считается доказанным по определению. Но такой запрос к факту, как «Является ли феликс собакой ?», не будет доказан с помощью известных фактов. Отрицательный ответ системы Пролог означает вовсе не то, что утверждение «феликс - собака» ложно, а лишь то, что у нас нет фактов о «феликсе» и о том, является ли он собакой. Другим термином, который мы использовали, был вывод. Имея множество фактов, мы можем определять новые свойства описанных в них объектов. Иными словами, допускается вывод свойств из фактов. Вернемся к факту «рекс - это собака». Предположим, мы хотим на основе известных фактов выявить все объекты, обладающие свойством «быть собакой». Задав вопрос «Какие существа являются собаками?», получим ответ: «Рекс - это собака». Мы привели тривиальный пример вывода. Введем некоторую дополнительную информацию.
«рекс - это собака» : факт
«голди является родителем рекса» : факт
«джок является родителем рекса» : факт
«объект является собакой при условии, что он является родителем собаки»
Первые три элемента данных представляют собой факты, четвертый элемент - формализованный вывод, называемый правилом. Теперь, если мы спросим: «Какие объекты являются собаками ?», то получим ответ, что «рекс», «голди» и «джок» - собаки, причем «рекс» является собакой по определению, а «голди» и «джок» - вследствие вывода. Они должны быть собаками как родители собаки. В этом и заключается основное различие между алгоритмическим и логическим мышлением. Если сформулировать приведенный выше запрос в алгоритмических терминах, то получится весьма сложное определение:
Объект является собакой в том случае,
если он имеет свойство «быть собакой» или же имеет
свойство «быть родителем» и существует объект,
связанный с родителем и обладающий свойством
«быть собакой».
Для того чтобы продемонстрировать алгоритмический подход к рассматриваемой задаче, приведем соответствующую программу на Паскале. Паскаль был выбран нами н случайно: во-первых, он очень популярен, и мы считаем, что программу на Паскале легко поймут читатели, имеющие некоторый опыт программирования. Во-вторых, в Паскале есть средства, позволяющие выразить задачу в символической форме, а не в терминах чисел, представляющих объекты, как требовалось бы сделать в Бейсике. В своей книге мы надеемся показать хороший стиль программирования на Прологе и поэтому должны сравнить его с хорошим стилем алгоритмического программирования.
В приводимой ниже программе прежде всего описывается информация, относящаяся к «рексу», «голди» и «джоку», а затем перечисляются объекты, являющиеся собаками по определению и вследствие вывода.
program являтьсяСобакой(Іприt, output);
type
строка = packed array [1..6] of char;
{Определить символы}
символ = (рекс.голди.джок);
{Определить виды информации}
информация = (собакаИнф,родительИнф);
объект = record
case инф: информация of
родительИнф: (родительЧей-либо: символ);
собакаИнф: (являтьсяСобакой: логический);
end {record};
var
дачные : array [символ] of объект;
имя : array [символ] of строка;
Х : символ;
{Эта функция будет возвращать значение «истина»,
если объект является собакой}
function собака (X: объект) : логический;
begin
if Х.инф = собакаИнф
then собака := Х.являтьсяСобакой
else
собака := собака (данные [Х.родительЧей-либо];
end;
begin
{Установить имена объектов}
имя [рекс] := рекс;
имя [голди] := голди;
имя [джок] := джок;
{Установить информацию для рекса}
with данные [рекс] do
begin
инф := собакаИнф;
являтьсяСобакой := истина; {рекс - это собака}
end;
{Установить информацию для голди}
with данные [голди] do
begin
инф := родительИнф;
родитель := рекс;
{голди является родителем рекса}
end;
{джок имеет те же свойства, что и голди}
данные [джок] := данные [голди];
{Теперь напечатаем имена объектов, обладающих
свойством быть собакой по определению или
вследствие вывода}
for Х := рекс to джок do
if собака (данные [X]) then
печататьСтроку (имя [X]);
end;
При написании программы пришлось много заниматься вопросами, не связанными непосредственно с решением задачи «Какие объекты являются собаками ?». Надо было определить типы данных, создать данные, в которых должна храниться информация, и установить их значения. Имея факты и выводы, мы должны были запрограммировать, как отвечать на вопрос «Какие объекты являются собаками ?». Только тогда программа давала ответ.
Ничего больше мы не могли получить от программы при известных условиях задачи и требуемых ответах. В этом состоит основной недостаток обычных языков программирования. Мы должны заранее в точности знать, какие могут быть заданы вопросы, и запрограммировать процедуры, которые будут давать на них ответы. В приведенной выше программе потребуется произвести немало изменений, чтобы обращаться к ней со следующими вопросами:
Какие собаки имеют родителей ?
Кто является родителем рекса ?
Кто является родителем ?
Для того чтобы представить, как решается на Прологе задача «Какие объекты являются собаками?», приведем фрагмент программы. Он позволит понять различие между программированием на Прологе и алгоритмическим программированием.
На Прологе задача описывается следующим образом:
/* факт «рекс - это собака»:
собака (рекс).
/* вывод «объект является собакой, если он
/* является родителем объекта Y, являющегося
/* собакой
собака(Х) :- родитель (Х,У),собака(У).
/* факт «голди является родителем рекса»
родитель(голди.рекс).
/* факт «джок является родителем рекса»
родитель(джок,рекс).
Данная программа на Прологе определяет свойства «быть собакой» и «быть родителем». (После знака /* записаны комментарии.)
Теперь, если мы хотим узнать, какие объекты являются собаками, то должны спросить:
?- собака (Кто).
Используемый нами синтаксис Пролога подробно будет определен позже. Пока примем, что каждый элемент, записанный строчными буквами, есть литерал. Он представляет объект и не может быть изменен. Каждое слово, начинающееся с прописной буквы (например, X, Y, Кто), является переменной. Во время выполнения программы переменным присваиваются значения. Символ ?- означает попытку согласовать, т.е. доказать следующую за ним цель (собака(Кто) является целью).
Мы определили, что рекс - это собака. Некоторый Х является собакой (X называется именованной переменной) при условии, что Х является родителем Y (другой свободной именованной переменной) и Y является собакой. Мы задали также условия, что голди - это родитель рекса и джок - это родитель рекса.
Запрос
?-собака (Кто). /*Кто - именованная свободная
/*переменная
выполняется следующим образом: Пролог-система просматривает программу с начала и ищет ответ на вопрос: «Какое значение должна принять свободная переменная Кто, если мы хотим доказать цель
собака (Кто) ?-".
Прослеживая программу с начала, мы видим, что если переменная Кто получит значение рекс, то целевое утверждение будет согласовано. Итак, переменная Кто принимает значение рекс, и цель становится доказанной. В ответ на наш вопрос будет напечатано:
Кто = рекс
Затем Пролог-система спросит, хотим ли мы получить другие ответы. Допустим, мы отвечаем «да»
другие решения (да/нет)? да
Для того чтобы найти следующий ответ, Пролог - система запоминает, где был получен последний результат, и продолжает работу с этого места в поисках другого варианта. После вопроса системы переменная Кто теряет значение рекс. Теперь предстоит сопоставление с утверждением, содержащим правило вывода.
При каком же значении переменной Кто цель будет согласована? Заметим, что переменная Кто сцеплена со свободной переменной X, стоящей в голове второго утверждения собака - собака (X). Особенность работы Пролога проявляется при сопоставлении объектов собака(Кто) и собака(Х): свободные переменные Х и Кто занимают один и тот же участок памяти. Поэтому, когда Х принимает некоторое значение, одновременно и Кто принимает то же самое значение. Подробнее данный вопрос будет раскрыт позже. Пока будем просто считать, что Х и Кто - лишь различные имена для одного и того же объекта.
Теперь мы подошли к утверждению «при условии, что». «Объект является собакой при условии, что он является родителем кого-то и этот кто-то является собакой.» На Прологе утверждение записывается следующим образом: за головной целью собака (X) следует символ «:-», означающий «при условии, что», а за ним конъюнкция целей. Конъюнкция в Прологе обозначается символом «,». Так, родитель(Х,У),собака(У) есть конъюнкция (логическое И) цели родитель(Х,У) и цели собака(У). Конъюнкция - важное понятие в Прологе, и мы не случайно обращаем на нее внимание. В Прологе существует также дизъюнкция, обозначаемая символом «;» и означающая «цель1 или цель2». Ниже мы детально разберем введенные понятия, а сейчас рассмотрим программы на Прологе. Чтобы согласовать цель собака (X), нужно согласовать цели родитель(X, Y) и собака (Y).
При доказательстве цели родитель(X,Y) Пролог сопоставляет цель с первым фактом, относящимся к родителям, а именно, с родитель(голди,рекс). Переменные получают значения Х=голди и Y=peкc. Поскольку Х сцеплена с переменной Кто и Х получает значение голди, переменная Кто тоже становится равной голди.
Присваивания значения переменным еще недостаточно; мы должны также согласовать цель собака(Y), которая теперь эквивалентна собака(реке). Такое утверждение найдено, и цель родитель(Х,У) согласуется при Х=голди и У=рекс. Таким образом, цель собака(Кто) повторно согласована при
Кто=голди.
Как и раньше, Пролог спрашивает, хотим ли мы получить другие решения. Ответим «да».
Пролог ищет альтернативу, пытаясь по-новому согласовать самую последнюю цель - собака(рекс). Однако такой возможности нет. Тогда Пролог пытается вновь согласовать предыдущую цель, родитель(Х,У). Так как Пролог запомнил, что цель родитель(Х,У) была согласована фактом родитель(голди,рекс), он находит альтернативный факт родитель(джок.рекс). Затем Пролог успешно производит согласование цели собака(рекс). Следовательно, найден альтернативный способ доказательства цели собака(Кто):
Кто=джок
И вновь на вопрос системы: «Хотите ли вы получить другие решения ?», ответим «да». На этот раз все возможные варианты исчерпаны, и Пролог посылает сообщение:
Других решении нет.
Ответ означает не то, что не существует других вариантов, а то, что Пролог не может их получить исходя из введенной информации.
Напомним, что после разбора программы на Паскале были приведены дополнительные вопросы:
Какие собаки имеют родителей ?
Кто является родителем рекса ?
Кто является родителем ?
Для их обработки в Прологе нет необходимости вносить изменения в программу. Мы просто вводим запросы:
?- родитель(_, Потомок).
?- родитель(Родитель,ре噫с).
?- родитель(Родитель,_).
Пролог просматривает базу данных и ищет решения описанным выше способом.
Теперь, когда мы рассмотрели пример программы на Прологе и соответствующую программу на Паскале, надеемся, вы убедились, что для задач данного класса программирование на Прологе значительно легче. Мы дали только предварительные сведения о Прологе; в последующих главах будут описаны его синтаксис и семантика.
Мы показали, что программа на Прологе состоит из фактов и правил для получения других фактов и ответов на вопросы. Использование фактов и правил является основой для языка экспертных систем. Экспертная система состоит из базы данных, содержащей факты и называемой иногда базой знаний, и машины вывода, которая обращается к базе данных, чтобы получить ответы на любые запросы. Даже при беглом взгляде на Пролог видно, что обе части оболочки экспертной системы могут быть реализованы на Прологе.
Пролог предоставляет средства для добавления и изменения информации в базе данных во время выполнения программы или запроса. Модификация базы данных, а следовательно, и программы позволяет повышать их информационное содержание. Программа может взаимодействовать с внешним источником информации, а затем использовать полученную информацию для изменения своей базы данных. Этот аспект является очень существенным в области искусственного интеллекта. Мы рассмотрим его в одной из последующих глав после того, как более подробно опишем работу Пролога.