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

РЕКУРСИИ. ЦИКЛЫ. СТРУКТУРЫ.

Рекурсии.

Общие положения.

Очень часто в программах необходимо выполнить одну и ту же задачу несколько раз. В программах на Турбо-Прологе повторяющиеся операции обычно выполняются при помощи правил, которые используют откат и рекурсию.

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

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

repetitive_rule :- /* правило повторения */

<предикаты и правила>,

fail. /* неудача */

Конструкция <предикаты и правила> в теле правила обозначает предикаты, содержащие несколько утверждений, а так же правила, определенные в программе. Встроенный предикат fail (неудача) вызывает откат, так что предикаты и правила выполняются еще раз.

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

recursive_rule :- /* правило рекурсии */

<предикаты и правила>,

recursive_rule.

Заметьте, что последним правилом в теле данного правила является само правило recursive_rule. Правила рекурсии содержат в теле правила сами себя.

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

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

Турбо-Пролог имеет средства для сокращения "потребления" стека, однако правила повтора, использующие откат, не увеличивают занятую часть стека.

Обычно цель программы на Турбо-Прологе содержит одну или несколько подцелей, которые могут быть либо фактами, либо правилами. Факт вычисляется немедленно. Результат будет либо успешным, либо неуспешным в зависимости от того, сопоставим ли факт в программе с фактом в правиле. Правило, являясь связкой подправил, вычисляется путем вычисления подправил. Если подправило не может быть успешно вычислено, то Турбо-Пролог выполняет откат, что бы найти другие возможные пути вычисления этого подправила.

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

При программировании различных задач удобно использовать метод отката после неудачи (МОПН) и метод отсечения и отката (ОО).

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

Откат является автоматическим инициируемым системой процессом, если не используются средства управления им. Для управления процессом отката предусмотрены два встроенных предиката: fail (неудача) - определяет, что текущий поиск решения для некоторой подцели неудачен и требуется начать новый поиск и предикат cut (или !)– принудительно завершает все поиски (отсечение).

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

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

Для этих целей Турбо-Пролог имеет встроенный предикат cut (отсечение). Предикат cut обозначается символом восклицательного знака (!).

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

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

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

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