Лабораторная работа 5
Рекурсия и рекурсивные процедуры в Прологе

       Цель работы:
  1. Знакомство с рекурсией, как с алгоритмическим методом.
  2. Изучение способов построения рекурсивных процедур.
  3. Знакомство с особенностями рекурсии в Пролог-программах.
  4. Изучение способов обеспечения целостности отношений.

1. Определение понятия рекурсии

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

Для того, чтобы погрузить N контейнеров, нужно:
Если N=0, то остановиться.
Если N>0, то погрузить один контейнер, затем погрузить еще N-1 контейнер.
       Будем считать, что здесь дано определение процедуры "погрузка N контейнеров", где N - аргумент процедуры и обозначает некоторое целое число.

       Данная процедура рекурсивна, т.к. последняя строка - '"погрузить N-1 контейнер" - является вызовом процедурой самой себя. Заметим, что аргумент при рекурсивном вызове проще, чем исходный аргумент N, в том смысле, что N-1 - это число меньшее, чем число N. Поэтому ''погрузка N контейнеров" представляет собой более сложный случай, выраженный через менее сложный случай выполнения тех же самых действий, т.е. через "погрузит N-1 контейнер".

       Классическим примером рекурсивного определения в Прологе может служить процедура "предок", которая состоит из двух правил:
предок(А,Б):-родитель(А,Б).
предок(А,Б):-родитель(В,Б), предок(А.В).
       Совокупность этих правил определяет два способа, в соответствии с которыми одно лицо (А) может быть предком другого липа (Б).

       Согласно первому правилу, А является предком Б, если А - родитель Б, т.е. А является ближайшим предком Б (рис.3.а).

       Согласно второму. А будет предком Б, если есть некоторый В, который, являясь родителем Б, имеет своим предком А. Другими словами, А - предок Б, если А -предок родителя Б, т.е. А - отдаленным предок Б (рис.3.б). Таким образом второе правило зависит от более простой версии самого себя, т.е. от подцели "предок".


Рис.3. Примеры отношения "предок" н его связь с отношением "родитель"
а) А ближайший предок Б b) А отдаленный предок Б с) для программы


       Задание 1.
В программу 10 введите описание процедуры "предок". Выполните ряд произвольных запросов к программе. Используя режим трассировка, изучите последовательность обработки в Турбо-Прологе процедуры "предок". Сохраните программу в файле "lab5.pro"

2. Состав рекурсивной процедуры

       Любая рекурсивная процедура должна включать по крайней мере по одной из перечисленных ниже компонент:
      1.Нерекурсивное предложение (правило или факт), определяющее исходный вид процедуры, т.е. вид процедуры в момент, прекращения рекурсии. Это, так называемые, граничные условия.
      2.Рекурсивнос правило. Начальные подцели, располагающиеся в теле этого правила, вырабатывают новые значения аргументов. Далее размещается рекурсивная подцель, в которой используются новые значения аргументов.

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

       Второе предложение - это рекурсивное правило. При каждом вызове данное правило поднимается на одно поколение вверх. Подцель родитель(В,Б), входящая в тело правила, вырабатывает значение переменной В. Затем располагается рекурсивная подцель предок(А,В), где используется новый аргумент.

       Рассмотрим еще один пример построения рекурсивной процедуры для вычисления факториала любого целого числа.

       Из определения факториала известно, что О! = 1, а факториал любого числа N может быть вычислен как факториал N-1, умноженный на N. Это определение является рекурсивным, поскольку сводит задачу нахождения N! к более простой задаче нахождения (N-1)! и затем умножения полученного значения на N.
/* программа 11 */
predicates
f(integer,integer)
clauses
f(U) :- !.
f(N,R) :- M=N-1, f(M,V), R=V*N.
       Для обозначения факта, что факториал числа N равен R, используем предикат f(N,R). Рекурсивное его определение будет иметь вид, приведенный в программе 11.

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

       Реализация выполнения данной программы Пролог-системой для случая вычисления факториала числа 3 (т.е. З!) приведена на рис.4.


Рис.4. Схема выполнения рекурсивной процедуры f(N,R).


Из рис.4, видно, что при выполнении заданной цели f(3,X) Турбо-Пролог трижды обращается к процедуре. При этом первые два раза согласуется второе правило, а в третий раз - первое. Особенность согласования второго правила заключается в том, что оба раза выполнение третьей подцели откладывается (заносится в стек запросов) в виду рекурсии второй подцели. И только после согласования на третьем шаге первого правила Турбо-Пролог возвращается к выполнению третьих подцелей. Они последовательно, начиная с последней, извлекаются из стека запросов и выполняются.

       Задание 2.
Используя режим трассировки, изучите последовательность обработки рекурсивных процедур на примере вычисления факториала. Измените программу таким образом, чтобы она вычисляла сумму заданной последовательности целых чисел. Отладьте программу, а потом вычислите сумму первых тысячи чисел, сумму первых 10 тысяч чисел. Какой получился результат? Как его можно объяснить?

3. Особенности выполнения рекурсивных процедур Пролог-системой

       При использовании рекурсии и нсогра11ичешюм или очень большом количестве рекурсивных вызовов, количество отложенных на выполнение подцелей в стеке запросов постоянно растет и в некоторый момент стек переполнится. На экране появится сообщение об ошибке. Частично помочь в этой ситуации может увеличение размера стека, который может быть изменен с помощью опции меню системы Установки/Разные установки/Размер стека. Однако, если установлено предельное значение, то это уже не поможет. Недостатки, в этом случае, вызваны плохо продуманной организацией процедур. Для примера, вернемся к процедуре "предок" и определим ее несколько иначе:

       С декларативных позиций смысл процедуры "предок1" идентичен процедуре "предок", но процедурные трактовки существенно разнятся. В процедуре "предок1" переменная В не конкретизирована в момент обработки подцели предок1(А,В). На практике это означает то, что система, выполняя запрос к процедуре '"предок!", вначале отыщет правильные ответы, затем будет выполнять рекурсивные действия вплоть до исчерпания доступного объема памяти.
предок1(А,Б):-родитель(А,Б).
предок1(А,Б):-предок1(А.В),родитель(В,Б).
       Задание 3.
Загрузите программу "lab5.рго", замените в ней процедуру "предок" на "предок1". Выполните ряд запросов и исследуйте результат.

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

4. Пример рекурсивной процедуры поиска длины маршрута на графе

       Рассмотренная выше рекурсивная процедура "предок" строилась на основе бинарного отношение РОДИТЕЛЬ(ОТЕЦ, РЕБЕНОК), которое устанавливало логическую связь между этими двумя объектами. Вместе с тем в практике часто встречаются случаи, когда между объектами существует как качественная, так и количественная взаимосвязь.

       Примером такого отношения является, например,
ДОРОГА (ГОРОД1, ГОРОД2, РАССТОЯНИЕ).
которое характеризует не только наличие связи между какими-либо городами, но и расстояние между ними.

       Используя это отношение, можно сформировать базу данных по транспортным магистралям, на которой можно выполнять поиск маршрута между двумя заданными городами и определение расстояния между ними. Таким образом, встает задача разработки процедуры формирования нового отношения
ПУТЬ(ГОРОД1, ГОРОД2, ДЛИНА_ПУТИ).
на основе исходного отношения "дорога". Метод рекурсии, использованный при составлении процедуры "'предок" можно применить и в этом случае.
/* программа 12 */
domains
town = string
distance = integer
predicates
road(town,town,distance) route(town,town,distance)
clauses
road("C-П6" ,"Чудово", 110). road("Boлхов","C-П6" , 124). гоаd("Чудово" ,"Волхов", 102). road("Чудово","Тихвин", 165). гоаd("Волхов","Тихвин", 122).
route(Townl ,Town2,Distance):-road(Town 1 ,Town2,Distance).
route(Town1 ,Town2,Distance):-road(Town1,X,Dist1), route(X,Town2,Dist2), Distance=Dist l+Dist2,!.
       В процедуре route() отношение между двумя городами будет соблюдаться, если существует дорога, по которой можно добраться из одного города в другой через ряд населенных пунктов.

       Каждое предложение для предиката road() описывает дорогу из одного города в другой, имеющую определенное расстояние.

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

       Если маршрут содержит только один участок дороги, то в этом случае расстояние между городами равно длине этого участка.

       В случае, если маршрут из Города1 в Город2 является суммой маршрутов из Города1 в Х и из Х в Город2, то расстояние между Город1 и Город2 будет равно расстоянию между Город1 и Х плюс расстояние между Город2 и X, т.е. сумме двух расстояний.

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

       Задание 4.
Загрузите программу 12 и исследуйте путь от С-Пб до Волхова и до Тихвина. После чего попробуйте определить маршрут от Волхова до С-П6. Какой Вы получили результат?

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

5. Ограничения и свойства, обеспечивающие целостность отношения

       Для простоты рассмотрим только отношения между двумя объектами (бинарные отношения). Для любого бинарного отношения справедливо одно из ограничений: один-к-одному, один-ко-многим, многие-ко-многим. Кроме этого любое отношения можно характеризовать наличием или отсутствием таких свойств, как:
       - симметрия (асимметрия)
       - рефлексивность (нерефлексивность)
       - транзитивность (транзитивность)

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

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

       Отношение между двумя объектами будет симметричным, если роли, которые играют эти объекты, взаимозаменяемы.

       Отношение, которое соблюдается, когда оба объекта одинаковы, называется рефлексивным.

       Отношение между объектами называется транзитивным, если оно сохраняется при переходе от прямого отношения к косвенному. Транзитивные отношения обычно реализуются рекурсивными процедурами типа "предок" или "маршрут".

       На логических схемах симметричные отношения изображаются двунаправленной стрелкой, асимметричные - однонаправленной. Асимметричное транзитивное отношение с косвенными связями через несколько уровней будет выглядеть как дерево, "растущее" вниз (рис.3.с). Отношение, которое является одновременно и симметричным, и транзитивным (типа "маршрут"), можно изобразить так, как показано на рис.5.

       Самый простой способ изменить свойства отношений это ввести в программу дополнительные факты, обеспечивающие соблюдение этих свойств. Так, если в программе содержатся факты
супруги( "Иван", "Марья" )
супруги( tom ,betty ),

Рис.5. Симметричное транзитивное отношение


то отношение "супруги" можно сделать симметричным путем добавления дополнительных фактов с обратным следованием объектов:
супруги("Марья", 'Иван" )
супруги( belly , torn )
       Альтернативой применения данного подхода является использование процедуры, устанавливающей симметричность, нерефлексивность или транзитивность. Так, процедура
супруги_симетр(Супруг1,Супруг2):- супруги(Супруг1,Супруг2), !.
супруги_симетр(Супруг1,Супруг2):- супруги(Супруг2,Супруг1).
       устанавливает симметрию отношения "супруги", а рекурсивная процедура "предок" устанавливает транзитивность отношения предок. Отношение "сослуживцы" можно было превратить в нерефлексивное путем добавления последней подцели
colleague(Manl,Man2) :- work(Manl,X), work(Man2,X), Manl<>Man2.
       Таким образом, чтобы улучшить программу 12, можно базу данных "дороги" сделать симметричной путем введения дополнительной процедуры, а затем обратиться к этой базе данных из процедуры route(). Правило для route() при этом автоматически унаследует симметрию базы данных "дороги". Кроме этого, если еще добавить подцель, которая позволит сделать отношение нерефлексивным, то это позволит избавиться от некоторых неточных ответов системы.

       Задание 5.
Доработайте программу 12 так, чтобы используемые в ней отношения были бы симметричными и нерефлексивными и исследуйте се. Попробуйте теперь определить маршрут от Волхова до С-Пб. Какой Вы получили результат? Испытайте еще ряд целей. Попробуйте исключить предикат отсечения из второго правила.

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

6. Содержание отчета по лабораторной работе

       Отчет по лабораторной работе должен содержать:
  1. Текст программы по заданию 1, запросы к ней и результаты их обработки.
  2. Программу вычисления суммы заданной последовательности целых чисел.
  3. Результаты выполнения заданий 3 и 4. Текст программы по заданию 5.