Предикат отсечения и управление логическим выводом в программах

Управление процессом просмотра предложений является важным аспектом программирования на Прологе. Это осуществляется с помощью специальной встроен­ной функции “резать”, обозначаемой символом “!”.

Данная встроенная функция может быть использована для достижения следую­щих трех целей:

1) исключения бесконечной петли при выполнении программы;

2) программирования взаимоисключающих утверждений;

3) блокирования просмотра целей.

Продемонстрируем все три случая на примерах.

Пример 1. Устранение бесконечных циклов. Обратимся к утверждениям, опреде­ляющим последовательность Фибоначчи (числовая последовательность 1, 1, 2, 3, 5, 8,..., в которой каждое число, начиная с третьего есть сумма двух предыдущих).

 

fib (0, _, 1).

fib (1,1,1).

fib (N,G,H): - fib (N–1,F,G), H is F+G.

 

На запрос

 

?- fib (0, _,F).

 

получим F=1, и Пролог сделает попытку сопоставить с запросом второй факт и потерпит неудачу. Однако сопоставление головы третьего утверждения с запро­сом происходит успешно и осуществляется попытка доказать цель fib(–l,F0,F1), что, в свою очередь, приводит к цели
fib(–2,..,..) и т.д., т.е. образуется бесконечный цикл.

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

 

fib (0, _,1): -!.

fib (1,1,1): -!.

fib (N,G,H): - fib (N–1,F,G), H is F+G.

 

Учитывая данное определение fib и задавая вопрос

 

?- fib(0, _,F).

получаем F=1. Других решений нет.

Пример 2. Программирование взаимоисключающих утверждений. Процедуру нахождения наибольшего из двух чисел можно записать в виде отношения max(X, Y, М).

Здесь М=Х, если X>=Y, и M=Y, если X<Y. Соответствующие правила таковы:

 

max(Х, Y, X): - X>=Y.

max(Х, Y, Y): - X<Y.

 

Эти правила являются взаимоисключающими. Возможна более экономная фор­мулировка, использующая понятие “иначе”:

 

если X>=Y то М=Х иначе M=Y.

 

На Прологе это записывается при помощи отсечения:

 

max(Х, Y, X): - Х>=Y,!.

max(Х, Y, Y).

 

Пример 3. Блокирование просмотра целей.

 

B.

D.

А: - В, С. (1)

С: -D,!, Е. (2)

Е: -F, G, H. (3)

?А.

 

Говорят, что дизъюнкт (1) “порождает” дизъюнкт (2), так как в правой части (1) есть литера С и эта же литера – в левой части (2). Аналогично дизъюнкт (2) “порождает” дизъюнкт (3). Если (3) неудачен, то в (2) выполнится отсечение: дизъюнкт (2) также считается неудачным, восстанавливается “родительская среда” (1), делается попытка найти альтернативное решение для В. Если бы (2) имело вид С: -D, Е., то при неудаче в (3) была бы сделана попытка найти альтернативное решение для D.

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

Встроенный предикат fail не имеет аргументов. Он считается всегда ложным.

Пример 4: перебор всевозможных решений.

 

ос(cpm).

ос(msdos).

ос(unix).

печать-всех:-ос(X), write(X), fail.

?-печать-всех.

Обработка списков

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

Список можно задать перечислением элементов. Например, имена учеников класса:

 

[саша,петя,дима,ксюша,лена].

 

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

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

Например, в списке [X | Y] Х – это голова списка, Y – его хвост.

Хвост списка по определению также является списком.

Теперь список может быть определен рекурсивно:

1) пустой список [ ] – список;

2) [X | Y] – список, если Y – список.

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

1) из факта, ограничивающего рекурсию и описывающего операцию для пустого списка;

2) из рекурсивного правила, определяющего операцию над списком, состоящим из головы и хвоста (в голове правила), через операцию над хвостом (в подцели).

 

Пример 1. Определение числа элементов в списке.

 

сколько ([], 0). – для пустого списка

сколько ([А|В], N):- сколько (В, М), N is M+1. – для списка [А|В], где В – список

?- сколько ([саша, игорь, лена]), X).

 

Ответ: Х=3.

 

Пример 2. Принадлежность элемента списку:

 

принадлежит (X, [X | Y]). – для Х, если Х – голова списка

принадлежит (X, [А |Y ]): – принадлежит (X,Y). – для любого другого Х

?-принадлежит (4,[1,3,4,9]).

 

Ответ: да.

 

Данная программа имеет очень простой декларативный смысл: элемент принад­лежит списку, если он является его головой или принадлежит хвосту списка.

 

Пример 3. Соединение двух списков. Эту задачу можно описать с помощью следующих предикатов:

а) ограничение рекурсии состоит в том, что если к пустому
списку [] добавить список Р, то в результате получится Р;

б) рекурсия состоит в том, что можно список Р добавить к концу списка [X|Y], если Р будет добавлен к хвосту Y и затем присоединен к голове Х (при этом получа­ется список [X|T]).

 

присоединить ([ ], Р, Р). – присоединение списка Р к пустому списку

присоединить([X|Y], Р, [X | Т]):-присоединить(Y, Р, Т).

? присоединить(L, [джим..R],[джек,бил,джим,тим,джим,боб]).

 

Ответ:

L=[джек,бил]. – первый вариант

R=[тим,джим,боб].

L=[джек,бил,джим,тим]. – второй вариант

R=[боб].

 

Существует традиция использовать для обозначения предиката слияния двух списков предикативный символ append (по-английски – добавить).

В некоторых случаях постановки вопросов к такого рода программам прихо­дится использовать отсечение (!).

 

Append ([ ], L, L).

append([A | B], C, [A | D]):- append(B, C, D).

?-append(X,Y, [1,2]).

 

Ответ:

X=[ ] – первый вариант

Y=[l,2]

X=[l] – второй вариант

Y=[2]

X=[l,2] – третий вариант

Y=[ ].

 

Если же заменить первое предложение на append([ ], 1, 1):-!. и задать тот же во­прос, то получится правильный ответ:

 

X=[ ]

Y=[l,2].

 

Пример 4. Удаление элементов из списка. Следующая программа аналогична проверке принадлежности элемента списку, но тре­бует уже трехарного предиката, один аргумент которого указывает удаляемый элемент, второй аргумент – исходный список и третий – список-результат.

 

удал (X, [X | Y], Y): -!.

удал (X, [Z | Y], [Z | W]): - удал (X, Y, W).

 

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

Данная программа удаляет первое вхождение в список элемента, связанного с пе­ременной X. Знак отсечения “!” в конце правила предотвращает последующий поиск и вывод лишних вариантов ответов после выполнения ограничительного факта.

Для удаления всех вхождений элемента Х программу надо дополнить:

 

удал (X,[ ], [ ]).

удал (X, [X | Y], W):- удал (X, Y, W).

удал (X, [Z | Y], W):- удал (X, Y, W).

 

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

 

Пример 5. Индексация элементов списка. Смысл программы состоит в том, чтобы получить элемент под номером N или узнать номер элемента X.

 

получить ([X | Y], 1, X).

получить ([W | Y], N, X):- N is М+1, получить (Y, М, X).

Пример 6. Поиск максимального элемента.

 

max ([X], X).

max ([X | Y], X):- max (Y, W), Х>W,!.

max ([X | Y], W):- max (Y, W).

 

Декларативный смысл программы: если в списке один элемент – он и является максимальным, если более одного, то это голова списка, если она больше макси­мального элемента хвоста, или максимальный элемент хвоста.

 

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

 

обр ([X], [X]).

обр ([X | Y], Z):- обр (Y, W), присоединить (W, [X], Z).

 

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

Arity-Prolog располагает значительным числом встроенных предикатов для об­работки списков, так что приведенные программы имеют, в основном, учебный характер.