ПРЕДИКАТ ОТСЕЧЕНИЯ И УПРАВЛЕНИЕ ЛОГИЧЕСКИМ ВЫВОДОМ В ПРОГРАММАХ

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

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

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.

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