Отладка ПРОЛОГ-программ.

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

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

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

! или cut.

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

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

человек(павел, 8).

человек(елена, 88).

человек(николай, 20).

После того, как первое решение будет найдено, дальнейшие вычисления являются напрасными и расположение отсечения является очевидным

возраст: - человек(_, Х): - Х< =8,!.

возраст: - человек(_, 8): -!.

В этом случае имеем “красное отсечение”, поскольку остальные решения не будут найдены.

Применение отсечения в случае правила для определения брата выглядит следующим образом

brother(X, Y): - parents (Y, M, F),!, parents (X, M, F), man (X), X< > Y.

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

В более общем случае для целевого утверждения

с базой знаний

получим следующие решения

;

;

Если теперь применить отсечение

,

это множество решений при той же базе знаний будет иметь вид

;

Действие механизма поиска с возвратом выполняется до встречи с предикатом!, т.е. для g(Y) будут пройдены все записи БЗ, а для p(X) – только первое, и отсечение в данном случае является “красным”.

Рассмотрим задачу сортировки списка методом пузырька. Для этого используем свойство предиката append возвращать составляющие списка по списку результата объединения

sort(X.Y): -append(W, [A, B|T], X), A> B,!, append(W, [B, A|T], Z), sort(Z, Y).

sort(L, L): -order(L).

order[_|[]]).

order([U, V|T]): -order([V|T]).

Решение задачи состоит из двух частей. Предикат sort(X.Y) по текущему значению составляющих в случае необходимости осуществляет инверсию двух соседних элементов Предикат order проверяет, является ли входной список упорядоченным, и в случае успешного решения возвращает исходному аргументу значение входного. Предикат sort построен на свойстве предиката append находить разные по содержанию решения в зависимости от конкретной формы его аргументов. Если место нарушения порядка элементов найдено, и перестановка выполнена, то не имеет никакого смысла рассматривать все возможные значения первых двух аргументов, объединение которых составляет список X.