Метод возврата после неудачи

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

Пример 32: распечатать все десятичные цифры.

domains

d=integer

predicates

decimal (d)

write_decimal

clauses

decimal (0)

decimal (1).

decimal (2).

decimal (3).

decimal (4).

decimal (5).

decimal (6).

decimal (7).

decimal (8).

decimal (9).

write_decimal:- decimal (C), write (C), nl, fail.

goal

write_decimal

В программе есть 10 предикатов, каждый из которых является альтернативным предложением для предиката decimal (d). Во время попытки вычислить цель внутренние подпрогрммы унификации связывают переменную C с термом первого предложения, то есть с цифрой 0. Так как существует следующее предложение, которое может обеспечить вычисление подцели decimal (C), то помещается указатель возврата, значение 0 выводится на экран. Предикат fail вызывает неуспешное завершение правила, внутренние подпрограммы унификации выполняют возврат и процесс повторяется до тех пор, пока не будет обработано последнее предложение.

Пример 34: необходимо выдать десятичные цифры до 5 включительно.

domains

d=integer

predicates

decimal (d)

write_decimal

make_cut (d)

clauses

decimal (0).

decimal (1).

decimal (2).

decimal (3).

decimal (4).

decimal (5).

decimal (6).

decimal (7).

decimal (8).

decimal (9).

write_decimal:- decimal (C), write (C), nl, make_cut (C),!.

make_cut (C):-C=5.

goal

write_decimal

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

Пример 35: необходимо выдать из БД первую цифру , равную 5.

domains

d=integer

predicates

decimal (d)

write_decimal

clauses

decimal (0).

decimal (5).

decimal (2).

decimal (3).

decimal (4).

decimal (5).

decimal (6).

decimal (5).

decimal (8).

decimal (9).

write_decimal:- decimal (C), С=5, write (C), nl, !.

goal

write_decimal

Если из тела правила убрать предикат !, то будут найдены все три цифры 5, что является результатом применения метода возврата после неудачи. При внесении отсечения будет выдана единственная цифра 5.

Метод повтора, использующий бесконечный цикл

Вид правила повторения, порождающего бесконечный цикл:

repeat.

repeat:- repeat.

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

Пример 36: ввести с клавиатуры целые числа и вывести их на экран. Программа завершается при вводе числа 0.

domains

d=integer

predicates

repeat

write_decimal

do_echo

check (d)

clauses

repeat.

repeat:- repeat.

write_decimal:-nl, write( «Введите, пожалуйста, цифры»), nl,

write(«Я повторю их»), nl,

write(«Чтобы завершить ввод, введите 0»), nl, nl.

do_echo:- repeat, readln (D), write(D), nl, check (D), !.

check (0):- nl, write («-OK!»).

check(_):- fail.

goal

write_decimal, do_echo.

Правило do_echo – это конечное правило повтора, благодаря тому, что предикат repeat является его компонентом и вызывает повторение предикатов readln, write, и check. Предикат check описывается двумя предложениями. Первое предложение будет успешным, если вводимая цифра 0, при этом курсор сдвигается на начало следующей строки и на экране появляется сообщение «OK!» и процесс повторения завершается, так как после предиката check в теле правила следует предикат отсечения. Если введенное значение отличается от 0, то результатом выполнения предиката check будет fail в соответствии со вторым предложением. В этом случае произойдет возврат к предикату repeat. Repeat повторяет посылки в правой части правила, находящиеся правее repeat и левее условия выхода из бесконечного цикла.

Методы организации рекурсии

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

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