Повторения и рекурсия в языке Prolog (Л/Р)

Здесь рассмотрены методы построения правил поиска с повторением: метод отката после неудачи (ОПН), метод отсечения и отката (ОО), метод повтора (МП), определяемый пользователем и обобщенное правило рекурсии (ОПР). Введение ОО-метода продемонстрировано использованием отсечения (!), которое является встроенным средством VP. В методе повтора используется присущая VP возможность выполнять рекурсию, определяемой пользователем правилом. Изучается ОПР-метод построения рекурсивных правил  в типичных ситуациях.

Некоторые фрагменты из методички (полная версия методички  доступная по ссылке содержит гораздо больше материала с примерами и картинками):

Цель работы

Основы программирования на языке VISUAL PROLOG. Работа Пролог-программы в режиме поиска цели. В данной работе рассмотрены четыре метода построения правил: метод отката после неудачи (ОПН), метод отсечения и отката (ОО), метод повтора (МП), определяемый пользователем и обобщенное правило рекурсии (ОПР).

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

Теоретическая часть

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

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

1. Программирование повторяющихся ситуаций

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

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

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

repetitive_rule :-/* правило повторения */
<предикаты и правила>,
fail./* неудача*/

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

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

recursive_rule :-/* правило рекурсии */
<предикаты и правила>,
recursive_rule.

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

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

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

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

3. Методы повторения

Вспомните, что оператор внешней цели побуждает переменные получать все возможные значения одно вслед за другим. (Вы можете прочитать об этом в гл. 2 и 3). Если полученных значений не много (скажем меньше 10), то выдача их на экран компьютера дело несложное. Но если их число велико, то текст на экране будет быстро меняться. Поэтому прочитать его очень трудно или даже невозможно.

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

В лабораторной работе изучаются  два способа реализации повторов в VP. При программировании весьма удобны метод отката после неудачи и метод отсечения и отката.

3.1. Метод отката после неудачи
Рассмотрим метод отката после неудачи (ОПН) и его использование для управления вычислением внутренней цели при поиске всех возможных ее решений. Метод ОПН использует предикат fail. Программа о городах (листинг 1) демонстрирует использование этого предиката.

...............
...............

УПРАЖНЕНИЯ

1. Измените программу о городах таким образом, что бы результатом была выдача на экран целых чисел 66, 46, 32, 93, 44, 98, 37, 16, 12. Выдавайте только одно число на строке.
2. Какие необходимы модификации для выдачи целых чисел на одну строку так, что бы они были разделены двумя пробелами?

Программа о городах показывает, что использование метода ОПН позволяет извлекать данные из каждого утверждения базы данных. Если в программе содержатся утверждения для 10 вариантов, то результат так же содержит 10 строк. Данные извлекаются из каждого утверждения, так как каждый вариант удовлетворяет под¬цели cities(City). Но добавив дополнительные условия на значения объектов для одной или более переменных предиката, можно извлекать данные только из определенных утверждений. Программа о служащих (листинг 2) демонстрирует этот метод.

© Министерство образования Российской федерации, Волгоградский государственный архитектурно-строительный университет, Кафедра информационных систем и математического моделирования. Методические указания к лабораторному практикуму для "интеллектуальных информационных систем”.