7.7. Повторение и рекурсия

При программировании могут быть встречаются правила, которые требуют, чтобы поиск элементов совершался несколько раз. Существуют два способа реализации правила, выполняющие одну и туже задачу многократно.

A) Повторение (итерация).

B) Рекурсия.

Правило, выполняющие повторение, использует откат, а правило, выполняющее рекурсию, использует самовызов.

Правило повторения:

repetitive_rule:– (предикаты и правила), fail.

Предикат fail искусственно вызывает откат, поэтому все, что стоит перед fail, повторяется много раз.

Вид правила, выполняющего рекурсию:

recursive_rule:– (предикаты и правила), recursive_rule.

Рекурсия требует много ресурсов памяти, так как новые копии используемых значений помещаются в СТЕК, который используется для передачи значений между правилами. Значения сохраняются до тех пор, пока правило не завершится успешно, либо неуспешно.

7.8. Повторение и откат

При поиске решений процедуры унификации используют откат как автоматический процесс, который используется, если не применяются специальные средства управления им. Как, например, для внутренней цели найти все решения? Для управления откатом используется два встроенных предиката:

1. fail – неудача,

2. cut – отсечение.

7.8.1. Метод отката после неудачи (опн).

Рассмотрим программу печати городов России. Поскольку все цели удовлетворяют условиям, то будет напечатан только первый город, а остальные не напечатаются. Чтобы заставить вывести программу все города, используют искусственное неуспешное завершение правила fail, при этом выполняется откат:

domain

name=symbol

preducates

cities(name)

showcities

goal

write(“There are the cities“), nl, showcities

clauses

cities(москва)

cities(томск)

cities(омск)

showcities:– cities (C),

write(“ “, C), nl, fail.

Если последнее правило будет иметь вид: write(“ “, C), nl, то будет напечатано название только одного города. Метод ОПН удобен для обработки служебных данных: создания платежной ведомости, начисления зарплаты, генерации отчета и т.д.

При добавлении дополнительных ограничений на значения объектов для одной или более переменных предиката можно извлекать данные только из определенных утверждений.

Например: cities(С), С=москва, выдаст только город Москву.

7.8.2. Метод отсечения и отката (оо).

Иногда необходимо иметь доступ только к определенной части данных. В этом случае используется метод ОО для фильтрации данных, извлеченных из базы. Отсечение применяется для устранения бесконечных циклов, при программировании взаимоисключающих утверждений и при необходимости неудачного завершения доказательства цели. Средство управления откатом – предикат cut (отсечение, !)

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

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

Пример. Напечатать список детей до Петра включительно

domain

person=symbol – дети

preducates

child(person) – список

show – показывает список

make_cut – отсекает на Петре

gool

write(“Дети”), nl, show.

clauses

child(“Маша”)

child(“Мила”)

child(“Миша”)

child(“Петр”)

child(“Катя”)

show:– child (Name), write (“имя”, Name), nl, make_cut (Name), !.

make_cut(Name):– Name=”Петр”.