Программа на Прологе - это конечное множество предложений.
Отсечение (Cut)
Отсечение (т.е. !) есть предикат, который отсекает (cuts) недетерминизм, то есть отсекает возможность выработки дальнейших решений (сообразно своему имени).
Отсекаемый недетерминизм можно разбить на два группы (хотя в ряде случаев отсечения могут принадлежать обеим):
§ Отсечения, которые отсекают возможность выполнения других (следующих по порядку) клауз текущего предиката.
§ Отсечения, которые ликвидируют возможность генерации новых решений у недетерминированных вызовов предикатов.
Других значимых причин для использования отсечений нет, кроме двух, упомянутых выше. Если эти цели понятны, то очень просто ставить отсечения в правильном месте:
§ либо отсечение ставится в месте, где перебор последовательных клауз больше не требуется и/или
§ оно ставится после вызова недетерминированного (то есть с квалификацией nondeterm или multi) предиката, для которого важно только одно решение.
Первая причина может быть проиллюстрирована следующим примером
clauses
p(17, X) :-
X > 13,
!,
q(X),
...
p(A, X) :-
...
В этом примере у нас есть отсечение после проверки X > 13. Это типичный случай использования первой причины: "Наши клаузы реагируют на значение входной переменной и сразу (где сразу означает немедленно после проверки X > 13) мы находим правильное решение".
Обычно такого рода отсечения помещаются сразу после головы клаузы или после проверки, ближайшей к голове клаузы.
Вторая причина может быть проиллюстрирована на следующем примере:
clauses
firstMember(X, L) :-
X = list::getMember_nd( L),
!.
В этом примере отсечение помещается немедленно после недетерминированного предиката, от которого мы ожидаем единственное решение.
Выше мы выделили слово немедленно дважды, поскольку ключевым словом в размещении отсечения является именно слово немедленно: они должны быть помещены настолько рано в клаузе, насколько это возможно.
Вы должны с подозрением относиться к клаузам, содержащим более одного отсечения. Наличие более одного отсечения в одном клаузе часто говорит о наличии ошибки в программе.
Красные и Зеленые отсечения
Вообще говоря, мы не поощряем зеленые отсечения, мы вполне уживаемся с красными отсечениями.
Сообщество традиционного Пролога дало определение красного и зеленого отсечений. Коротко это: зеленое отсечение - это отсечение, которое не меняет семантику предиката, в котором используется, а красное отсечение - меняет семантику.
Ясно, что все отсечения, которые отсекают все последующие решения недетерминированных предикатов являются красными по своей природе. Поэтому различия между красными и зелеными отсечениями имеют смысл только для тех отсечений, которые предотвращают откаты к следующим клаузам.
Рассмтрим клаузы:
clauses
p(X) :-
X > 0,
!,
...
p(X) :-
X <= 0,
...
В предикате выше отсечение является зеленым (green), поскольку, если мы его удалим, то предикат будет вести себя таким же образом. Когда отсечение имеется в первом клаузе, проверка X <= 0 во втором клаузе в действительности не нужна (второй клауз соответствует всем остальным случаям, кроме X<0 - прим. Переводчика):
clauses
p(X) :-
X > 0,
!,
...
p(X) :-
...
Но без этой проверки, однако, отсечение становится красным, поскольку теперь предикат будет вести себя по-другому, если мы удалим отсечение (предикат становится недетерминированным, поскольку, даже если X>0, появляется еще одно решение - хорошо, если безвредное - прим. Переводчика).
Зеленые отсечения могут показаться излишними, но в действительности они используются для исключения лишних вариантов отката (главным образом по соображениями скорости работы). В системе Visual Prolog они могут, однако, быть необходимыми для того, чтобы показать компилятору, что некоторые предикаты являются предикатами определенного типа, например, процедурами.
Рекурсия в прологе
Рекурсия - это второе средство для организации повторяющихся действий в Prolog'е. Рекурсивная процедура - это процедура, вызывающая сама себя до тех пор, пока не будет соблюдено некоторое условие, которое остановит рекурсию. Такое условие называют граничным. Рекурсия - хороший способ для решения задач, содержащих в себе подзадачу такого же типа.
Пример рекурсии: найти факториал n!.
Задача нахождения значения факториала n! очень хорошо решается с помощью рекурсии, поскольку может быть сведена к решению аналогичной подзадачи, которая, в свою очередь, сводится к решению аналогичной подподзадачи и т.д.
Действительно, чтобы найти значение факториала n!, можно найти значение факториала (n-1)! и умножить найденное значения на n. Для нахождения значения факториала (n-1)! можно пойти по уже известному пути - найти значение факториала (n-2)! и умножить найденное значения на n-1. Так можно действовать до тех пор, пока не доберемся до нахождения значения факториала (n-n)! или другими словами, факториала 0!. Значение факториала 0! известно - это 1. Вот это и будет граничное условие, которое позволит остановить рекурсию. Все, что теперь остается - это умножить полученную 1 на (n-(n-1)), затем на (n-(n-2)) и т.д. столько раз, сколько было рекурсивных вызовов. Результат n! получен.
Вот как выглядит программа, которая проделывает вычисление n! (нужно заметить, что предложения Prolog-программы достаточно точно повторяют формулировку задачи на естественном языке).
PREDICATES