Главная

ПРОЕКТ "ЧЕЛОВЕК. ЗЕМЛЯ. ВСЕЛЕННАЯ"

Инструменты пользователя

Инструменты сайта


project:prolog:povtorenie_i_rekursija



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

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

Используются следующие методы повторения:

  • метод отката после неудачи;
  • метод отсечения и отката;
  • правило повтора, определяемое пользователем;
  • обобщенное рекурсивное правило.

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

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

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

  • повторение;
  • рекурсия.

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

Формат правила, выполняющего повторение:

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

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

Формат правила, выполняющего рекурсию:

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

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

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

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

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

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

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

Допустим есть простая база данных о спортивных увлечениях:

plays(tom,football) /* Том играет в американский футбол */
plays(john,soccer) /* Джон играет в европейский  футбол */
plays(john,volleyball) /* Джон играет в волейбол*/
plays(tom,basketball)/* Том играет в баскетбол*/
plays(tom,volleyball)/* Том играет в волейбол */
plays(john,baseball) /* Джон играет в бейсбол*/

Задача программы определить, в какую игру одновременно играют Джон и Том.

Утверждение цели следующее:

plays(john,G),plays(tom,G).

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

Чтобы вычислить первую подцель plays(john,G), Пролог ищет в базе данных сопоставимое утверждение. Первый объект утверждения plays(john,soccer) сопоставим с первым объектом первой подцели, так что подцель успешно вычисляется и переменная G получает значение soccer.

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

Далее Пролог пытается вычислить вторую подцель. Так как G имеет значение soccer, то эта подцель есть plays(tom,soccer). Пролог просматривает базу данных в поиске утверждения, сопоставимого с этой подцелью. Сопоставимых утверждений нет, поэтому подцель неуспешна.

Так как вторая подцель неуспешна, переменная G освобождается и Пролог снова начинает поиск утверждения для вычисления подцели plays(john,G).

Поиск начинается с указателя отката, отмеченного цифрой 1.

Следующее сопоставляемое утверждение – это plays(john,volleyball). Переменная G получает значение volleyball. Снова указатель отката помещается на следующее утверждение. Теперь Пролог пытается вычислить вторую подцель plays(tom,volleyball). Во время этой попытки удается найти сопоставимое утверждение. Присвоение переменной G значения volleyball приводит к успеху.

Обе подцели удовлетворены. Больше подцелей нет, поэтому вся исходная цель оказывается успешно вычисленной.

Если бы цель в этом примере была внутренней, то процесс вычисления остановился бы после первого ее успешного вычисления. Однако цель здесь внешняя, поэтому процесс повторяется до тех пор, пока не будут найдены все успешные способы вычисления цели. Но информация, содержащаяся в данных утверждениях, дает только одно допустимое значение для G, которое удовлетворяет обеим подцелям, т.е. результат вычисления подцели есть G=volleyball.

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

  • fail (неудача);
  • cut (отсечение).

Во время выполнения программы Пролог создает необходимые внутренние структуры данных (такие как списки и деревья) для выполнения обработки программы. Эта обработка включает такие процессы как:

  • поиск;
  • сопоставление с образцом;
  • создание экземпляра;
  • означивание;
  • освобождение переменных;
  • откаты.

Эти процессы выполняются внутренними подсистемами языка, которые называются внутренними унификационными подпрограммами. Во время выполнения программы эти подпрограммы всегда находятся в рабочем состоянии.

Программа

"Два игрока" - демонстрация автоматического отката для поиска игроков, играющих в одну игру.

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

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

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

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

Метод отката после неудачи

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

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

Например, утверждения программы о служащих содержат данные о служащих компании. Предикат базы данных имеет вид:

/* служащий(имя, пол, отдел, почасовая_оплата) */
employee(name,sex,department,pay_rate)

Следующее правило выдает содержимое всей базы данных:

/* выдать список служащих */
show_all_part_time_employees :- employee(Name,Sex,Dept,Pay_rate), write(Name, “ “, Sex, “ “, Dept, “ “, Pay_rate),nl, fail.

Переменные Name (имя), Sex (пол), Dept (отдел), Pay_rate (почасовая оплата) не означены, и следовательно, все они могут получить значения. Результат выполнения этой цели - список всех служащих.

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

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

show_male_part_time : employee(Name,”M”, Dept, Pay_rate),
write(Name,Dept, “$”,Pay_rate),
nl,
fail.

Альтернативной формой условия выборки по половому признаку является предикат равенства Sex=M. Используя этот предикат равенства, можно построить другое правило, имеющее тот же самый результат:

show_male_part_time : employee(Name, Sex, Dept, Pay_rate),
Sex=”M”,
write(Name,Dept, “$”, Pay_rate),
nl,
fail.

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

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

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

Метод ОПН удобен для программирования на Прологе прикладных задач по обработке служебных данных. Типичными примерами обработки служебных данных являются:

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

Программа

"Города" - демонстрация метода отката после неудачи с предикатом fail. Назначение программы о городах состоит в перечислении названий десяти городов США.

"Служащие" - демонстрация метода отката после неудачи с предикатом fail. Программа:

  • выводит полный список служащих;
  • выводит список мужчин;
  • расчитывает почасовую оплату.

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

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

Удобство этого метода становится более явным при большем числе условий для выборки. Например, метод ОО дает возможность выбрать все заявки, зафиксированные с 18 по 19 июня, имеющие литеру B в номере накладной, и полученные до того, как клерк Элайн Ларк заступил на дежурство.

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

Ппредикат fail может вызвать откат к другим возможным вариантам решения задачи или подцели. Однако, для того, чтобы из базы данных выбирать данные, удовлетворяющие некоторым условиям, необходимо иметь средства управления откатом. Для этих целей Пролог имеет встроенный предикат cut (отсечение). Предикат cut обозначается символом восклицательного знака (!). Этот предикат, вычисление которого всегда завершается успешно, заставляет внутренние унификационные подпрограммы «забыть» все указатели отката, установленные во время попыток вычислить текущую подцель.

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

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

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

Предикат cut выполнит отсечение в указанном месте. Предикат fail используется для продолжения откатов и доступа к последовательности имен базы данных до элемента с именем Diana. Таким образом, поставленную задачу выполняет соответствующая комбинация предикатов cut и fail. Эта комбинация называется методом отката и отсечения (ОО).

Правило, обеспечивающие генерацию всех имен (а не только некоторых) основано на методе ОПН и имеет вид:

show_them_all :- child(Name), write("Имя: ", Name), nl, fail.

Чтобы использовать предикат cut, необходимо определить некоторое условие Name=Diana. Правило, определяющее, это условие имеет вид:

make_cut(Name) :- Name="Diana".

Это правило с последующим предикатом cut (!) образует правило make_cut (сделать отсечение). Теперь выполнение программы будет неуспешным, а откаты будут повторяться до тех пор, пока Name не окажется равным Diana. В этот момент результат выполнения правила make_cut будет успешным, что в свою очередь, вызовет выполнение предиката cut.

Таким образом, комбинируя правила отсечения с методом ОПН, можно получить ОО-правило:

show_some_of_them :- child(Name), write("Имя: ", Name), nl, make_cut(Name),!.
make_cut(Name) :- Name="Diana".  

Этот способ использования ОО-метода называется методом ранжированного отсечения.

Метод ОО можно использовать для обработки выбираемых элементов. Например, если в базе данных есть несколько записей с одинаковым именем, то можно сделать выборку только первой записи с таким именем.

Например, в БД есть 7 записей, 3 из них содержат имя Alice.

Правило, которое выбирает и выдает имя Alice, имеет вид:

get_alice :- child(Name), Name=”Alice”, write("Имя: ", Name),nl, fail.

В базе данных имя Alice встречается трижды, поэтому, результатом работы приведенного правила будет список трех одинаковых имен.

Правило get_alice находит все (три) возможные означивания переменной Name, что является результатом применения метода ОПН.

Однако при желании можно выдать только первый экземпляр значения переменной Name. Это достигается введением в правило выборки отсечения:

get_first_alice :- child(Name), Name="Alice", write("Имя: ", Name), nl, !, fail.

В результате будет пулучен список, состоящий из единственного имени Alice.

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

Программа

  • "Дети" - демонстрация метода предиката cut (!) и метода отката и отсечения. Программа выводит список детей, до определённого имени ребёнка включительно.
  • "Дети-2" - демонстрация метода предиката cut (!) и метода отката и отсечения. Программа выводит только первое из найдённых в БД имен Alice.

Метод повтора (МП), определяемый пользователем

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

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

repeat. /* повторить */
repeat :- repeat.

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

Второй repeat - это правило, которое использует само себя как компоненту (третий repeat). Второй repeat вызывает третий repeat, и этот вызов вычисляется успешно, так как первый repeat удовлетворяет подцели repeat. Следовательно, правило repeat так же всегда успешно.

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

В МП-правиле можно использовать более одного правила повтора.

do_two_things : repeat1, <повторяемое тело>, <условие выхода>,!, repeat2, <повторяемое тело>, <условие выхода>,!.
repeat1.
repeat1 :- repeat1.
repeat2.
repeat2 :- repeat2.
<правило для условия выхода 1>.
<правило для условия выхода 2>.

Во время определения правил повтора можно вместо имени repeat использовать какое-нибудь другое. Ниже в качестве примеров приведены несколько альтернатив слову repeat:

loop. /* цикл */
loop :- loop.
loop1.
loop1 :- loop1.
loop2.
loop2 :- loop2.
iterate. /* итерация */
iterate :- iterate.
recurse. /* рекурсия */
recurse :- recurse.

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

Пример программы

  • "Ввод слова с клавиатуры" - демонстрация метода повтора с помощью простой рекурсии repeat. Программа считывает строку, введенную с клавиатуры, и дублирует ее на экран. Если пользователь введет stop, то программа завершается.
  • "Ввод символа с клавиатуры" - демонстрация метода повтора с помощью простой рекурсии repeat. Программа считывает символ, введенный с клавиатуры, и дублирует его на экран.

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

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

Простая рекурсия

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

Пример правила рекурсии:

write_srting :- /* выдать строку */
write(«Человек - это звучит гордо!»),
nl,
write_string.

Это правило состоит из трех компонент. Первые две выдают строку «Человек - это звучит гордо!» и переводят курсор на начало следующей строки экрана. Третья - это само правило. Так как оно содержит само себя, то чтобы быть успешным, правило write_string должно удовлетворять само себе. Это приводит снова к вызову операции выдачи на экран строки и смещение курсора на начало новой строки экрана. Процесс продолжается бесконечно и в результате строки выдается на экран бесконечное число раз.

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

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

Если рекурсивное правило не генерирует указателей отката и последняя подцель правила является рекурсивным вызовом самого правила, то Пролог устранит дополнительные расходы, вызываемые рекурсией. Этот процесс нызывается устранением хвостовой рекурсии.

Избежать возникновения бесконечной рекурсии можно. Для этого следует ввести предикат завершения, содержащий условие выхода. Формулировка условия выхода для правила write_string может иметь вид: «Продолжать печать строки до тех пор, пока счетчик печати не превысит число 7. После чего остановить процесс».

Определение условий выхода и включение их в правило рекурсии является очень важным элементом программирования на Прологе.

Пример программы

  • "Ввод символа с клавиатуры-2" - демонстрация простого правила рекурсии. Программа считывает символ, введенный с клавиатуры, и дублирует его на экран до тех пор, пока не будет введён символ #.

Метод обобщенного правила рекурсии (ОПР)

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

Общий вид правила рекурсии:

<имя правила рекурсии> : <список предикатов>, (1)
<предикат условия выхода>, (2)
<список предикатов>, (3)
<имя правила рекурсии>, (4)
<список предикатов>. (5)

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

Данное правило рекурсии имеет пять компонент. Первая - это группа предикатов. Успех или неудача любого из них на рекурсиию не влияет.

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

Третья компонента - список других предикатов. Аналогично, успех или неудача этих предикатов на рекурсию не оказывает влияния.

Четвертая группа - само рекурсивное правило. Успех этого правила вызывает рекурсию.

Пятая группа - список предикатов, успех или неудача которых не влияет на рекурсию. Пятая группа также получает значения (если они имеются), помещенные в стек во время выполнения рекурсии.

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

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

Пример обобщенного правила рекурсии:

write_number(Number) :- Number < 8, /* Голова правила и предикат выхода */
write(" ", Number), nl,
Next_number = Number + 1, /* увеличить счётчик */
write_number(Next_number). /* вызов самого правила рекурсии, но с другим значением Number */

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

Пример программы

  • "Генерация чисел от 1 до 7" - демонстрация обобщенного правила рекурсии. Программа генерирует числа от 1 до 7.
  • "Сумма ряда целых чисел от 1 до 7" - демонстрация обобщенного правила рекурсии. Программа суммирует числа от 1 до 7.
  • "Факториал" - демонстрация обобщенного правила рекурсии для вычисления факториала целого числа. Факториал числа N! есть произведение всех целых чисел от 1 до N: N! = N * (N-1) * (N-2) * … 2 * 1

!!Рекомендуем: Семейная Энциклопедия ЗдоровьяОбучениеКонсультация аналитикаОглавлениеГлавная сайта

Обсуждение

Ваш комментарий:
T F᠎ U C᠎ F
 
project/prolog/povtorenie_i_rekursija.txt · Последние изменения: 2012/11/18 21:32 (внешнее изменение)

Вы можете оставить свои комментарии в разделе "Обсуждение".
Рекомендуем оформить подписку на новости данного раздела. Для этого нажмите на кнопку "Подписаться", расположенную справа снизу каждой страницы (знак конверта).


www.work-zilla.com

Индекс цитирования