Министерство образования и науки российской федерации федеральное агентство по образованию санктпетербургский государственный университет
 Скачать 1.41 Mb.
|
|
1.6. Рекурсии и итерации Напишем на Прологе простую программу, которая имитирует на компьютере пишущую машинку: type :- readchar(X), write (X), type. Стандартный предикат readchar выполняет чтение символа с клавиатуры. Это бесконечная рекурсия – из нее нет выхода. Модифицируем программу таким образом, чтобы она обеспечивала ввод только одного предложения (до первой точки): type :- readchar(X), write(X), X <> ’.’, type. type. Первый предикат type читает символ, выводит его на экран, после чего сравнивает его с точкой. Если введенный символ не точка, то происходит рекурсивный вызов type, в противном случае – откат на следующий, пустой предикат type. Второй предикат type нужен лишь для того, чтобы вся программа завершилась успехом, а не неудачей. Заметим, что рекурсия в этой программе совершенно не нужна, так как вызов предиката из самого себя не имеет никакого смысла для логики программы. По программистской привычке нам было бы предпочтительней зациклить данное правило. Но в Прологе GOTO нет в принципе. Вместо этого есть возможность вызывать откат. Напишем следующую конструкцию: type :- readchar(X), write(X), X = ’.’. При первом выполнении данного правила (введенный символ не равен точке) предикат завершится неудачей. Отката же не будет по той причине, что все предикаты в теле правила являются однозначными. Кстати, все стандартные предикаты являются однозначными. Таким образом, для того, чтобы откатиться на начало правила, необходимо, чтобы там был неоднозначный предикат. Создадим такую конструкцию: repeat. repeat :- repeat Предикат repeat ничего не делает кроме того, что является неоднозначным. Можно даже сказать, очень неоднозначным, поскольку перебрать все его варианты невозможно. Это бесконечная рекурсия. Программа, имитирующая пишущую машинку, без рекурсивного вызова type будет выглядеть следующим образом: repeat. repeat :- repeat type :- repeat, readchar(X), write(X), X = ’.’. Здесь рекурсия заменена итерацией, хотя рекурсивный вызов в виде предиката repeat все же присутствует. 18 1.7. Отсечения в Прологе Из всего вышесказанного можно сделать справедливый вывод о том, что интерпретатор Пролога, выполняя резолюцию цели, всегда делает полный обход дерева решений. Спуск по дереву вниз соответствует углублению в тело правила, возврат наверх и переход на соседнюю ветвь – откату после неудачи. Рассмотрим концепцию отсечения на конкретном примере. Пусть нас пригласили на дачу. При этом обычно дают подробную инструкцию, как проехать и найти конкретный дом. Например, полученная нами инструкция выглядит следующим образом: 1. Въехать в деревню Васино (а может быть и Ванино. Написано неразборчиво). 2. Повернуть направо. 3. Доехать до колодца. 4. Искомый дом из красного кирпича – первый от колодца по правой стороне. Запишем правило поиска дачи предикатами Пролога: dacha1(X) :- enter_village(Х), find_a_house. find_a_house :- turn_right, meet_mine, see_a_red_brick_house. enter_village(vasino). enter_village(vanino). Начинаем поиск (рис.1.1)... Рис.1.1. Иллюстрация отсечения в Прологе Въезжаем в деревню и поворачиваем направо (стрелка 1). Проезжаем до конца деревни и не находим колодца. Выполняем откат, то есть возвращаемся на шоссе и едем до следующего поворота направо (стрелка 2), доезжаем до колодца и видим, что ближайший к нему дом из белого кирпича. Едем до конца улицы и видим, что колодцев больше нет (стрелка 3). Откатываемся на шоссе и едем до следующего поворота (стрелка 4), проезжаем всю улицу и 5 4 3 2 1 19 откатываемся, поскольку колодцев здесь нет (стрелка 5). Из этого делаем вывод, что название деревни мы прочитали неверно, и дачу следует искать в следующей деревне. В деревне Ванино повторяем все сначала. Отсечение позволяет сократить количество пробегаемых ветвей дерева решений. Если хозяин дачи даст нам важную дополнительную информацию о том, что в каждой деревне есть только один колодец (а если в качестве ориентира заданы почта или милиция, то можем догадаться сами, что они могут быть в деревне только в одном экземпляре), мы не будем выполнять действия, обозначенные стрелками 3 и 4, а сразу поймем, что попали не в ту деревню. Отсечение – это предикат, который обозначается восклицательным знаком и вставляется в правило. Срабатывает отсечение после того, как Пролог пройдет через него. Отсечение уничтожает указатели отката, установленные в ходе унификации данного правила, т. е. делает предыдущие предикаты данного правила однозначными. Если мы хотим указать в программе поиска дачи, что колодец в деревне единственный, мы должны поставить отсечение после найденного колодца: dacha2(X) :- enter_village(Х), find_house. find_a_house :- turn_right, meet_mine, !, see_a_red_brick_house. enter_village(vasino). enter_village(vanino). Как только Пролог достигнет отсечения, весь предикат find_house станет однозначным, следовательно, дальнейшая неудача в предикате see_a_red_brick_houseприведет к тому, что предикат find_house также завер- шится неудачей. Если при этом предикат enter_village является неоднозначным (как показано в программе), то мы имеем шанс найти дачу в другой деревне, поскольку отсечение в правиле find_house не затрагивает свойства предиката dachaи установленные в нем указатели отката. Если предикат enter_villageявляется однозначным, то нам придется возвращаться домой. Дачи мы не нашли. Если дом возле колодца окажется все- таки из красного кирпича, то наличие отсечения никак не скажется на результате поиска. Таким образом, отсечение следует включать в программу на Прологе всегда, когда нам точно известно, что решение либо единственное, либо его нет вовсе. Примечание. Если программа поиска дачи будет выглядеть следующим образом: dacha3(X) :- enter_village(X), turn_right, meet_mine, !, 20 see_a_red_brick_house. enter_village(vasino). enter_village(vanino). то отсечение, вставленное в указанном месте, приведет к тому, что все предыдущие предикаты в правиле dacha станут однозначными, в том числе и enter_village. Иными словами, нам будет запрещено искать дачу в следующей деревне. 1.8. Красное и зеленое отсечения Если отсечение не влияет на логику работы программы, а только сокращает возможные спуски по ложным ветвям дерева решений, то такое отсечение называется зеленым. Если отсечение влияет на логику программы (без него программа работает иначе), такое отсечение называется красным. В приведенном выше правиле dacha2 отсечение зеленое, поскольку не влияет на логику программы, а только избавляет нас от бесполезного блуждания по деревне. В правиле dacha3 отсечение меняет логику программы, т.к. поиск ограничивается первым найденным колодцем на всем пути следования к цели, а не в каждой деревне. Следует заметить, что и зеленое отсечение в правиле dacha2 все же меняет логику программы. Правда, это отсечение отсекает лишь возможность поехать на две дачи сразу. Использование отсечений позволяет существенно сокращать как время работы программы на Прологе, так и объем требуемой оперативной памяти. Кроме того, вдумчивая расстановка отсечений сокращает отладку программ, поскольку устраняет коллизии, подобные той, что приведена в следующем примере. Пусть человек считается уважаемым в обществе, если он/она состоит в браке и имеет свой дом. Правило для этого выглядит следующим образом: respectable(X) :- spouse (X,_), has_home(X). Пусть в базе знаний имеются следующие факты и правила: spouse(alla, filipp). spouse (X,Y) :- spouse (Y, X). has_home(alla). Зададим следующую цель: respectable(filipp). Для резолюции данной цели Пролог войдет в тело правила respectableи поставит себе подцель: spouse (filipp,_). Поскольку такого факта в базе нет, Пролог выполнит откат на правило spouse (X,Y) :- spouse (Y, X). из которого создаст себе подцель: spouse (_, filipp). В ходе резолюции данной подцели будет получено успешное решение, поскольку такой факт в базе есть. Далее Пролог ставит себе следующую 21 подцель из правила respectable: has_home(filipp). Такого факта в базе нет, и, поскольку, предыдущий предикат правила respectable, то есть spouse является неоднозначным, то выполняется откат на следующий экземпляр этого предиката, а именно: spouse (X,Y) :- spouse (Y, X). Смысл отката заключается в поиске другой жены для Филиппа. Будет поставлена следующая подцель: spouse (filipp, _). Таким образом, будет происходить бесконечное углубление в рекурсию. Совершенно очевидно, что, найдя одну жену Филиппа, мы должны сообщить Прологу, что это решение является единственным, и искать другие не нужно. respectable(X) :- spouse (X,_), !, has_home(X). spouse(alla, filipp) :- !. spouse (X,Y) :- spouse (Y, X). has_home(alla). 1.9. Списки в Прологе Все переменные, с которыми мы работали ранее, были скалярами. Теперь рассмотрим агрегаты данных в Прологе. Один из них – список. Список – это упорядоченная последовательность однотипных элементов. Элементы списка заключаются в квадратные скобки и разделяются запятыми: [ 1, 2, 3, 4, 6, 7, 8] – integer [mon,tue, wed, thu, fri, sat, sun] – symbol ["Иванов", "Петров"] – string [1.5, 2.22, 0.001, 0] – real [] – пустой список Объявляются списки следующим образом: domains sym = symbol* % список символьных значений intlist = integer* % список целых realist = real* % список действительных чисел Единственная операция, которая допускается над списком – это отсечение головы от хвоста, причем «разместить» эту операцию можно только в аргументах предикатов. Напишем некоторые полезные предикаты для работы со списками. В частности, как определить является ли некоторая переменная элементом списка? Разобьем список на голову и хвост. Искомое значение находится либо в голове списка, либо в хвосте: member (H, [H | _ ] ). member (X, [H | T] ) :- member (X, T). Вышеописанным приемом можно искать не только один элемент, но и больше (например пару последовательных значений в списке) 22 memb2(H1, H2, [H1, H2 | _ ] ). memb2(H1, H2, [H | T] ) :- memb2(H1, H2, T) Чтобы включить значение в список (проще всего в голову) можно составить такое правило: incl (H, T, [H | T]). Исключить значение из списка несколько сложнее: excl (H, [H | T], T ). % исключаем из головы excl (X, [H,T], [H | TT] ) :- excl (X, T, TT). % исключаем из хвоста Ниже приведены другие примеры предикатов работы со списками: 1. Программа вывода на экран элементов списка по одному: print_list([]). % выход из рекурсии print_list([ H | T ]) :- write(H, “ “), % вывод головы списка и пробела print_list(T). % вывод хвоста Если задать цель printlist([“я”, “помню”,”чудное”,”мгновенье”]). то результат будет следующим: я помню чудное мгновенье 2. Та же программа, но выводящая список в обратном порядке: print_inverse([]). % выход из рекурсии print_inverse ([ H | T ]) :- print_inverse (T), % вывод хвоста write(H, “ “). % вывод головы списка и пробела Цель: write_inverse ([“я”, “помню”,”чудное”,”мгновенье”]). Результат: мгновенье чудное помню я 3. Программа, подсчитывающая сумму элементов списка: sum([], 0). % выход из рекурсии, sum([ H | T ], S ) :- sum(T,S1), % S1 – сумма элементов в хвосте списка S = S1 + H. % S – остается добавить к сумме только голову Цель: sum([1,2,3,4,5,6], S), write (“Сумма =”,S). Результат: Сумма=21 4. Программа, подсчитывающая количество элементов списка: count([], 0). % выход из рекурсии, count([ H | T ], S ) :- count(T,S1), % S1 – счетчик элементов % в хвосте списка S = S1 + 1. % S – остается добавить к сумме единицу Цель: count([1,2,3,4,5,6], S), write (“Количество =”,S). Результат: Количество =6 1.10. Пример: Решение логической задачи о волке, козе и капусте Рассмотрим известную логическую задачу о волке, козе и капусте. Фермер 23 должен переправить на другой берег реки волка, козу и капусту. Грузоподъемность лодки такова, что за один раз можно взять на борт что- нибудь одно: или волка, или козу, или капусту. В присутствии старика никто никого не ест. Если же он отлучится, то волк съест козу, а коза – капусту. Для решения этой задачи организуем два списка. Один список будет отражать содержимое левого берега, второй – правого. Первоначально все находятся на левом берегу. Список левого берега: [wolf, goat, cabbage], список правого берега пустой: [ ]. Определим предикаты, описывающие задачу. stuff(wolf). % перечисление груза stuff(goat). stuff(cabbage). /* условия возникновения конфликта */ conflict(X): - member(wolf, X), member(goat, X). conflict(X); - member(goat, X), member(cabbage, X). /* Предикаты, описывающие перемещения лодки: С левого берега на правый */ go_right([ ], _). % условие завершения (список левого берега пуст) go_right( L, R) :- stuff(X), % выбираем груз, member(X, L), % который есть на левом берегу excl(X, L, LL), % исключаем из списка левого берега not(conflict(LL)), % на левом берегу конфликта нет incl(X,R,RR), % включаем в список правого берега write(LL,"--",X,”-->”,R), % выводим сообщение go_left(LL,RR). % гребем назад /* Движение влево возможно в двух вариантах. Если на правом берегу конфликт не возникает, то фермер едет один */ go_left(L,R) :- not(conflict(R)), write(L,"<-------”,R), % выводим сообщение go_right(L, R). % вызываем предикат движение вправо /* Если на правом берегу возникает конфликт надо кого-нибудь увезти обратно. Это единственная подсказка, которую мы сообщаем программе. В остальном Пролог будет искать решение вполне самостоятельно */ go_left(L,R) :- stuff(X), % выбираем груз, member(X, R), % который есть на правом берегу excl(X, R, RR), % исключаем из списка правого берега not(conflict(RR)), % на правом берегу конфликта нет incl(X,L,LL), % включаем в список левого берега write(L,"<--",X,”--”,RR), % выводим сообщение go_right(LL,RR). % гребем назад Вызов цели должен быть следующим: go_right([wolf, goat, cabbage], [ ]). 24 Если запустить эту программу, то быстро обнаружится, что первым рейсом старик отвезет на правый берег козу. Вторым рейсом – волка. Оставить волка с козой на правом берегу нельзя, поэтому он отвезет первый попавшийся груз, а им окажется волк, обратно. И так будет возить его бесконечно. Недостаток данной программы заключается в том, что фермер не помнит, кого он только что привез. Для укрепления его памяти добавим в предикаты go_left и go_right название последнего перевезенного груза. Финальный вариант программы выглядит следующим образом (изменения выделены полужирным шрифтом): /* Задача о волке, козе и капусте */ domains % раздел требуется для PDC-Пролога. В SWI-Прологе не нужен stuff = wolf; goat; cabbage; nil % создаем свой тип данных ( nil – пустое ) list = stuff* % тип данных список predicates % раздел требуется для PDC-Пролога. В SWI-Прологе не нужен member(stuff,list) incl(stuff,list,list) excl(stuff,list,list) conflict(list) go_right(list, list, stuff) go_left(list, list, stuff) clauses stuff(wolf). stuff(goat). stuff(cabbage). member (H, [H | _ ] ). member (X, [H | T] ) :- member (X, T). incl (H, T, [H | T]). excl (H, [H | T], T ). excl (X, [H,T], [H | TT] ) :- excl (X, T, TT). conflict(X): - member(wolf, X), member(goat, X). conflict(X); - member(goat, X), member(cabbage, X). go_right( L, R,Last) :- stuff(X), % выбираем груз, X <> Last, % но не тот, что везли только что и member(X, L), % который есть на левом берегу excl(X, L, LL), % исключаем из списка левого берега not(conflict(LL)), % на левом берегу конфликта нет incl(X,R,RR), % включаем в список правого берега write(LL,"--",X,”-->”,R), % выводим сообщение go_left(LL,RR,X). % гребем назад /* Если на правом берегу конфликт не возникает, то едет один */ go_left(L, R, Last) :- not(conflict(R)), write(L,"<-------”,R), % выводим сообщение |