 |
Предикат отсечения и управление логическим выводом в программах
|
|
|
|
Управление процессом просмотра предложений является важным аспектом программирования на Прологе. Это осуществляется с помощью специальной встроенной функции «резать», обозначаемой символом "!".
Данная встроенная функция может быть использована длядостижения следующих трех целей:
1) исключения бесконечной петли при выполнении программы;
2) программирования взаимоисключающих утверждений;
3) блокирования просмотра целей.
Продемонстрируем все три случая на примерах.
Пример 1. Устранение бесконечных циклов. Обратимся к утверждениям, определяющим последовательность Фибоначчи (числовая последовательность 1, 1, 2, 3, 5, 8,..., в которой каждое число, начиная с третьего есть сумма двух предыдущих).
Программа 118
fib (0,_,1).
fib (1,1,1).
fib (N,G,H): - fib (N-l,F,G), H is F+G.
На запрос
?- fib (0_,F).
получим F = 1, и Пролог сделает попытку сопоставить с запросом второй факт и потерпит неудачу. Однако сопоставление головы третьего утверждения с запросом происходит успешно и осуществляется попытка доказать цель fib(-l,FO,Fl), что, в свою очередь, приводит к цели fib(-2,..,..) и так далее, т.е. образуется бесконечный цикл.
Однако мы можем устранить такие ситуации, используя отсечение и тем самым указывая Прологу, что не существует других решении в случае успешного согласования граничного условия.
Программа 119
fib (0,_,1): -!.
fib (1,1,1): -!.
fib (N,G,H): - fib (N-l,F,G), H is F+G.
Учитывая данное определение fib и задавая вопрос
?- fib(0_,F).
получаем F=l. Других решений нет.
Пример 2. Программирование взаимоисключающих утверждений. Процедуру нахождения наибольшегоиз двух чисел можно записать в виде отношения
max(X, Y, М).
Здесь М=Х, если X>=Y, и M=Y, если X<Y. Соответствующие правила таковы:
|
|
|
max(X,Y,X):-X>=Y.
max(X, Y, Y): - X<Y.
Эти правила являются взаимоисключающими. Возможна более экономная формулировка, использующая понятие «иначе»:
если X>=Y то М=Х иначе M=Y.
На Прологе это записывается при помощи отсечения:
max(X,Y,X):-X>=Y,!
max(X, Y, Y).
Пример 3. Блокирование просмотра целей.
Программа 120
В.
D
А: - В, С. (1)
С: -D,!, Е. (2)
Е: -F, G, H. (З)
?А.
Говорят, что дизъюнкт (1) «порождает» дизъюнкт (2), так как в правой части (1) есть литера С и эта же литера - в левой части (2). Аналогично дизъюнкт (2) «порождает» дизъюнкт (3). Если (3) неудачен, то в (2) выполнится отсечение: дизъюнкт (2) также считается неудачным, восстанавливается «родительская среда» (1), делается попытка найти альтернативное решение для В. Если бы (2) имело вид С: -D, Е., то при неудаче в (3) была бы сделана попытка найти альтернативное решение для D.
В других случаях можетбыть необходимым продолжение поиска дополнительных решений, даже если целевое утверждение уже согласовано. В этих случаях можно использовать встроенный предикат fail.
Встроенный предикат fail не имеет аргументов. Он считается всегда ложным.
Пример: перебор всевозможных решений.
Программа 121
oc(cpm).
ос(msdos).
ос(unix).
печать-всех:-ос(X), write(X), fail.
?-печать-всех.
ОБРАБОТКА СПИСКОВ
На практике часто встречаются задачи, связанные с перечислением объектов. В некоторых случаях при решении задач важно сохранять информацию об уже сделанных шагах решения, чтобы их не повторять. Для решения таких задач в языке Пролог предусмотрены списки.
Список можно задать перечислением элементов. Например, имена учеников класса:
[саша,петя,дима,ксюша,лена].
Элементами списка могут быть не только атомы, но и функции, и вообще любые элементы, даже списки. Заранее длина списка не задается, и в ходе выполнения программы она может меняться.
Альтернативный способ задания списка использует понятия головы и хвоста списка.
|
|
|
Например, в списке [X | Y] Х - это голова списка. Y - его хвост.
Хвост списка по определению также является списком.
Теперь список может быть определен рекурсивно:
1) пустой список [] - список:
2) [X | Y] - список, если Y - список.
Определение списка через его голову и хвост в сочетании с рекурсией лежит в основе большого числа программ, оперирующих списками. Эти программы состоят
1) из факта, ограничивающего рекурсию и описывающего операцию для пустого списка;
2) из рекурсивного правила, определяющего операцию над списком, состоящим из головы и хвоста (в голове правила), через операцию над хвостом (в подцели).
Пример I: определение числа элементов в списке.
Программа 122
сколько ([], 0).
сколько ([А|В], N):- сколько (В, М), N is M+1.
?- сколько ([саша, игорь, лена]), X).
Ответ: Х=3.
Пример 2: принадлежность элемента списку.
Программа 123
принадлежит (X, [X | Y]).
принадлежит (X, [A |Y ]): - принадлежит (X,Y).
?-принадлежит (4,(1,3,4,9]).
Ответ:да.
Данная программа имеет очень простой декларативный смысл: элемент принадлежит списку, если он является его головой или принадлежит хвосту списка.
Пример 3: соединение двух списков.
Эту задачу можно описать с помощью следующих предикатов:
а) ограничение рекурсии состоит в том, что если к пустому списку [ ] добавить список Р, то в результате получится Р;
б) рекурсия состоит в том, что можно список Р добавить к концу списка [X|Y], если Р будет добавлен к хвосту Y и затем присоединен к голове Х (при этом получается список [Х|Т]).
Программа 124
присоединить([ ], Р, Р).
присоединить([XIY], Р, [X | Т]):-присоединить(Y, Р, Т).
? присоединить(L,[джим.R],(джек,бил,джим,тим,джим,боб]).
Ответ:
L=[джек,бил]. К=[тим джим,боб]. L=[джек,бил,джим,тим]. R=[бoб].
Существует традиция использовать для обозначения предикатаслияния двух списков предикативный символ append (по-английски -добавить).
В некоторых случаях постановки вопросов к такого рода программам приходится использовать отсечение (!).
Программа 125
append([ ], L, L).
append([A I 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):-!. и задать тот же вопрос, то получится правильный ответ:
|
|
|
Х=[]
Y=[l,2].
Пример 4. удаление элементов из списка.
Программа 126 аналогична проверке принадлежности элемента списку, но требует уже трехарного предиката, один аргумент которого указывает удаляемый элемент, второй аргумент-исходный список и третий - список-результат.
Программа 126
удал (X. [X I Y], Y): -!.
удал (X. [Z I Y], [Z I W]): - удал (X, Y, W).
Декларативный смысл: если удаляемый элемент совпадает с головой списка, то результатом программы является хвост списка, иначе удаления производятся из хвоста списка.
Данная программа удаляет первое вхождение в список элемента, связанного с переменной X. Знак отсечения "!"в конце правила предотвращает последующий поиск и вывод лишних вариантов ответов после выполнения ограничительного факта.
Для удаления всех вхождений элемента Х программу надо дополнить:
удал (Х,[ ],[]).
удал (X, [X | Y], W):- удал (X, Y, W).
удал (X, [Z I Y], W):- удал (X, Y, W).
Декларативный смысл программы таков: пока список не пуст, удалить элемент, если он совпадает с головой списка, значит, отбросить голову списка, а затем удалять его из оставшегося хвоста, иначе надо сразу удалять элемент из хвоста.
Пример 5: индексация элементов списка.
Смысл программы 127 состоит в том, чтобы получить элемент под номером N или узнать номер элемента X.
Программа 127
получить ([X | Y], 1, X).
получить ([W | Y], N, X):- N is M+l, получить (Y, M, X).
Пример 6: поиск максимального элемента.
Программа 128
max ([X], X).
max ([X | Y], X):- шах (Y, W), X>W,!.
max ([X | Y], W):-max (Y, W).
Декларативный смысл программы: если в списке один элемент - он и является максимальным, если более одного, то это голова списка, если она больше максимального элемента хвоста, или максимальный элемент хвоста.
Пример 7: обращение списка.
Данная задача - самая сложная из рассмотренных. Для ее решения важно сообразить, что обратить список из одного элемента - означает оставить список без изменения. Обратить более длинный список - обратить его хвост, а потом сзади приставить к нему голову исходного списка.
Программа 129
обр ([X], [X]).
обр ([X I Y], Z):- обр (Y, W), присоединить (W, [X], Z).
В этой программе используется процедура слияния списков, описанная выше.
Arity-Prolog располагает значительным числом встроенных предикатов для обработки списков, так что приведенные программы имеют, в основном, учебный характер.
|
|
|
