Программирование на языке пролог

Клоксин У.

• Когда имеете дело с операциями над списками, проверяйте себя с помощью следующих вопросов и ответов:

• Как сопоставляются [а,b,с]и [X|Y]? ( X конкретизируется значением a, a Y– значением [b,с]).

• Сопоставимы ли [а]и [X|Y]? (Да, причем X конкретизируется значением a, a Y– значением []).

•

Сопоставимы ли []и [X|Y]? (Нет).

• Имеет ли смысл запись [X, Y|Z]? (Да).

• Имеет ли смысл запись [X|Y,Z]? (Нет).

• Имеет ли смысл запись [Х|[Y|Z]? (Да, это то же самое, что [X,Y|Z])

• Как сопоставляются [a, b]и [А |В]? ( А конкретизируется значением а, а В– значением [b] ).

• Существует ли более одного способа сопоставления приведенных выражений? (Нет, никогда).

Необходимо подчеркнуть, что когда приходится иметь дело со списками или другими структурами подобного рода, полезно прибегать к помощи «древовидных диаграмм», о которых говорилось в гл. 2.

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

• Циклические определения, о которых упоминалось в гл. 3.

• Недостаточность граничных условий или какая-либо другая недоопределенность задачи.

• Бесполезные процедуры, которые переопределяют встроенные предикаты.

• Задание неверного количества аргументов для функтора. Это не рассматривается как синтаксическая ошибка, поскольку количество аргументов функтора может быть разным.

• Неожиданный выход на конец файла при выполнении предиката чтения read.

Остерегайтесь следующих заблуждений относительно принципов работы механизма возврата:

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

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

• Заблуждение:Запись списка [X|Y]может быть сопоставлена с любым отрезком списка, и при этом разбиение списков на части может быть осуществлено несколькими разными способами. Именно этим объясняется действие предиката присоединить (X, Y, [a,b,c,d]).

На самом деле:В записи списка [X|Y] Xсопоставляется только с головой списка, a Yсопоставляется только с его хвостом. Цели с предикатом присоединитьспособны находить

разные разбиения списков благодаря возможностям возвратного хода, а не возможностям сопоставления.

8.3. Модель трассировки

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

При использовании трассировки Пролог-система выводит на печать информацию о последовательности отработки целей, чтобы показать, какой стадии выполнения достигла программа. При этом, для того чтобы разобраться в том, что происходит, важно понять, когда и почему определенные цели выводятся на печать. В обычных языках программирования особый интерес представляют моменты входа в подпрограммы и выхода из них. Однако Пролог допускает написание недетерминированных программ, а это вносит сложности, связанные с механизмом возврата. Дело не ограничивается последовательностью входов в утверждения и выходов из них. Механизм возврата может неожиданно вновь запустить выполнение каких-либо утверждений, чтобы построить альтернативное решение. Кроме того предикат отсечения 'Г указывает для каких целей нельзя искать другие решения. Наибольшие трудности, с которыми приходится сталкиваться начинающим программистам, связаны именно с пониманием принципов работы механизма возврата: что на самом деле происходит, когда попытка согласования цели завершается неудачей и система неожиданно начинает возвратный ход. Мы надеемся, что этот процесс достаточно подробно описан в предыдущих главах. Впрочем, в предыдущих главах рассматривалась не только последовательность обработки целей, но также и то, как происходит конкретизация переменных, как цели сопоставляются с заголовками утверждений из базы данных, и, наконец, как согласуются с базой данных подцели. В модели трассировки выполнение Пролог-программ описывается в терминах четырех видов происходящих событий: CALL(ВЫЗОВ), ЕХIT(ВЫХОД), REDО(ПЕРЕДЕЛКА), FAIL(HEУДАЧА).

CALL

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

EXIT

Событие EXIT фиксирует момент, когда некоторая цель только что согласована с базой данных. На наших диаграммах это обозначается стрелкой, выходящей снизу из прямоугольника.

REDO

Событие REDO фиксирует момент, когда система возвращается к цели, пытаясь повторно согласовать ее с базой данных. На наших диаграммах это обозначается стрелкой, которая возвращается в прямоугольник снизу.

FAIL

Событие FAIL фиксирует момент, когда попытка согласовать цель с базой данных заканчивается неудачно. На наших диаграммах это соответствует выходу стрелки вверх из прямоугольника.

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