ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 31.03.2021
Просмотров: 6827
Скачиваний: 51
346
лог возвращается к первои части запроса: любнт(Х,чтение) , «развязывает» переменную Х и про-
должает поиск подходящих фактов, начиная с ранее установленного в списке фактов указателя
Подходит факт «любит(лена,чтение)», переменная Х конкретизируется значением «лена», и далее
вторая часть вопроса успешно согласуется с фактом «любит(лена, плавание)». Пролог выполнил в
данном примере поиск с возвратом.
Графически процесс выполнения программы представляется в виде обхода бинарного дере-
ва - дерева вывода, типа изображенного на рис.3.16. Вершины дерева обозначают вопросы, а ребра
показывают возможные пути вывода, причем для каждого ребра характерны
свои правила и уни-
фицирующая подстановка значений переменных.
Рис.3.16.
Дерево вывода программы на Прологе
Обход дерева начинается с движения от вершины (запроса) по самой левой ветви вниз до
конца (abed), при этом запоминаются все точки ветвления (точки возврата). При достижении кон-
ца ветви решение будет либо найдено, либо нет. В обоих случаях Пролог продолжает дальнейший
поиск решений. Выполняется возврат в последнюю точку ветвления с. При этом конкретные зна-
чения, присвоенные переменным при движении вниз на сегменте c-d. отменяются, и движение
вниз продолжается по расположенной справа ветви с-е до конца дерева вниз. Затем произойдет
возврат в предыдущую точку ветвления b и движение продолжится по ветви bfg, и так до тех пор,
пока все дерево вывода не будет пройдено.
7.3. РЕКУРСИЯ
Существует целый класс задач, в которых отношения между объектами можно определить,
только пользуясь самими определяемыми соотношениями. Получающиеся при этом правила на-
зываются рекурсивными.
Пример:
рекурсивное определение натурального числа:
1) 1- натуральное число;
2)
число, на 1 большее натурального
числа, также натуральное.
В системах логического программирования рекурсия служит также для
описания
циклов,
повторений и является важнейшим методом программирования.
Рассмотрим простой пример: вычисление факториала натурального числа n (n!) . Опреде-
ление n! рекурсивно:
1)1!=1,
2)n!=(n-l)!*n.
Для описания отношения «факториал» между
n и n! будем использовать двухарный преди-
кат
факт(N,М). Тогда база знаний, соединенная с запросом, приобретает вид (программа 115);
Программа 115
факт(1,1).
факт(N,Х): - факт( N-1 ,V), Х is Y*N.
?- факт(3,А);
В данной программе правило «факт» вызывает само себя - это и есть рекурсия. Запись is
Y*N представляет собой обращение к встроенному предикату «is» («есть») для описания арифме-
347
тического действия.
Процесс работы программы можно изобразить следующим образом:
?факт(3,A0).
ОТВЕТ: А=6
?факт(1,A2).
Х1= 2*3 = 6
факт(1,1)
Х2=1*2=2
Здесь стрелочка вниз означает сопоставление и резолюцию, а стрелочка вверх - возврат и
завершение отложенного вычисления.
Правило «факт» вызывает само себя - происходит углубление рекурсии (прямой ход). При
этом в памяти ЭВМ выделяется место для переменных А,АО,А1,А2 и N,NO,N1,N2, образующих
стеки. При согласовании вопроса с предикатом факт(1,1) рекурсия прекращается и начинается
возврат из рекурсии (обратный ход) - выполнение отложенных на прямом ходе согласований.
Предикат факт(1,1) играет очень важную роль - это ограничитель рекурсии, условие ее заверше-
ния.
Отметим, что Пролог стремится найти все решения поставленной задачи,
а значит, после
появления ответа А=6 происходит возврат к вопросу ?факт(1,А2) и попытке согласовать его с пра-
вилом «факт». Это приводит к бесконечному процессу рекурсии с отрицательными аргументами в
«факт», которая завершается при исчерпании глубины зарезервированных интерпретатором Про-
лога стеков. Ускорить выход из рекурсии можно, добавив к предикату «факт(1,1)» отсечение !:
факт(1,1):-!.
Однако, использование отсечения требует более подробного рассмотрения. В общем случае
последовательность предложений в базе знаний не имеет
значения. Однако это не так для рекур-
сивно-определенных отношений. Например:
родитель(Х):- родитель(Y),отец(Y,Z).
родитель(коля).
отец(коля,петя).
родитель(петя).
В этом случае в первом предложении голова имеет ту же функцию, что и одна из целей -
«родитель». В процессе поиска ответа в этой базе знаний будет применено правило:
предложение,
стоящее первым, будет применено первым
- известное как
принцип поиска в глубину
.
Это приведет к тому, что система будет обращаться только к первому предложению базы
знаний и ответ на вопрос не будет найден никогда (образуется бесконечная петля вывода). Однако
небольшое изменение базы знаний - перестановка двух предложений местами - приведет к удач-
ному поиску решения.
Программа 116
родитель(коля).
родитель(X):- родитель(Y), отец(Y,Х).
отец(коля,петя).
? - родитель(петя).
Неограннчено-повторное обращение к предложению может
быть и более замаскированным
так, как это получается в программе 117.
Программа 117
выше(А,В): - ниже(В,А).
ниже(В,А): - выше(А, В).
выше(коля,петя).
?- ниже(петя,коля).
348
Однако если третье предложение стоит на первом месте, то повторного обращения не про-
изойдет и ответ будет найден.
В общем виде рекурсия на Прологе выглядит так:
Р(1,...).
P(n,...) -Q1,..., Qn, P(n-l,...), R1,... Rm.
Правило Р обращается само к себе, при этом происходит углубление рекурсии. Предикаты
Q1, .... Qn выполняются на прямом ходе рекурсии, а R1,..., Rm - на обратном; n - это некоторый
условный параметр, входящий в условие продолжения рекурсии, а Р(1,...)- факт, завершающий
процесс рекурсии.
Особенно простым случаем рекурсии является простое циклическое повторение. Один из
способов организации повторения связан с наличием в базе знаний процедуры вида repeat, repeat: -
repeat.
Использование repeat в качестве подцели некоторого правила приводит к многократному
повторению остальных подцелей этого правила.
7.4. ПРЕДИКАТ ОТСЕЧЕНИЯ И УПРАВЛЕНИЕ ЛОГИЧЕСКИМ ВЫВОДОМ
В ПРО-
ГРАММАХ
Управление процессом просмотра предложений является важным аспектом программиро-
вания на Прологе. Это осуществляется с помощью специальной встроенной функции «резать»,
обозначаемой символом "!".
Данная встроенная функция может быть использована для
достижения следующих трех це-
лей:
1) исключения бесконечной петли при выполнении программы;
2) программирования взаимоисключающих утверждений;
3)
блокирования просмотра целей.
Продемонстрируем все три случая на примерах.
Пример 1.
Устранение бесконечных циклов. Обратимся к утверждениям, определяющим
последовательность Фибоначчи (числовая последовательность 1, 1, 2, 3, 5, 8,..., в которой каждое
число, начиная с третьего есть сумма двух предыдущих).
Программа 118
fib (0,_,1).
fib (1,1,1).
fib (N,G,H) : - fib ( N-l ,F,G), H is F+G.
На запрос
?- fib (0_ ,F).
получим F = 1, и Пролог сделает попытку сопоставить с запросом второй факт и потерпит
неудачу. Однако сопоставление головы третьего утверждения с запросом происходит успешно и
осуществляется попытка доказать цель fib(-l,FO,Fl), что, в свою очередь, приводит к цели fib(-2, ..,
..) и так далее, т.е. образуется бесконечный цикл.
Однако мы можем устранить такие ситуации, используя отсечение и тем самым указывая
Прологу, что не существует других решении в случае успешного согласования граничного усло-
вия.
Программа 119
fib (0,_,1) : - !.
fib (1,1,1) : - !.
fib (N,G,H) : - fib ( N-l ,F,G), H is F+G.
349
Учитывая данное определение fib и задавая вопрос
?- fib(0_ ,F).
получаем F=l. Других решений нет.
Пример 2.
Программирование взаимоисключающих утверждений. Процедуру нахождения
наибольшего
из двух чисел можно записать в виде отношения
max(X, Y, М).
Здесь М=Х, если X>=Y, и M=Y, если X<Y. Соответствующие правила таковы:
max(X,Y,X):-X>=Y.
max(X, Y, Y) : - X<Y.
Эти правила являются взаимоисключающими. Возможна более экономная формулировка,
использующая понятие «иначе»:
если X>=Y то М=Х иначе M=Y.
На Прологе это записывается при помощи отсечения:
max(X,Y,X):-X>=Y,!
max(X, Y, Y).
Пример 3.
Блокирование просмотра целей.
Программа 120
В.
D
А: - В, С. (1)
С: -D, !, Е. (2)
Е: -F, G, H. (З)
?А.
Говорят, что дизъюнкт (1) «порождает» дизъюнкт (2), так как в правой части (1) есть литера
С и эта же литера - в левой части (2). Аналогично дизъюнкт (2) «порождает» дизъюнкт (3). Если
(3) неудачен, то в (2) выполнится отсечение: дизъюнкт (2) также считается неудачным, восстанав-
ливается «родительская среда» (1), делается попытка найти альтернативное решение для В. Если
бы (2) имело вид С: -D, Е. , то при неудаче в (3) была бы сделана попытка найти альтернативное
решение для D.
В других случаях может
быть необходимым продолжение поиска дополнительных реше-
ний, даже если целевое утверждение уже согласовано. В этих случаях можно использовать встро-
енный предикат fail.
Встроенный предикат fail не имеет аргументов. Он считается всегда ложным.
Пример:
перебор всевозможных решений.
Программа 121
oc(cpm).
ос(msdos).
ос(unix).
печать-всех:-ос(X), write(X), fail.
?-печать-всех.
7.5. ОБРАБОТКА СПИСКОВ
350
На практике часто встречаются задачи, связанные с перечислением объектов. В некоторых
случаях при решении задач важно сохранять информацию об уже сделанных шагах решения, что-
бы их не повторять. Для решения таких задач в языке Пролог предусмотрены списки.
Список можно задать перечислением элементов. Например, имена учеников класса:
[саша,петя,дима,ксюша,лена].
Элементами списка могут быть не только атомы, но и функции, и вообще любые элементы,
даже списки. Заранее длина списка не задается, и в ходе выполнения программы она может ме-
няться.
Альтернативный способ задания списка использует понятия головы и хвоста списка.
Например, в списке [X | Y] Х - это голова списка. Y - его хвост.
Хвост списка по определению также является списком.
Теперь список может быть определен рекурсивно:
1) пустой список [] - список:
2) [X | Y] - список, если Y - список.
Определение списка через его голову и хвост в сочетании с рекурсией лежит в основе
большого числа программ, оперирующих списками. Эти программы состоят
1) из факта, ограничивающего рекурсию и описывающего операцию для пустого списка;
2) из рекурсивного правила, определяющего операцию над списком, состоящим из головы
и хвоста ( в голове правила), через операцию над хвостом (в подцели).
Пример I:
определение числа элементов в списке.
Программа 122
сколько ([], 0).
сколько ([А|В], N) :- сколько (В, М), N is M+1.
?- сколько ([саша, игорь, лена]), X).
Ответ: Х=3.
Пример 2:
принадлежность элемента списку.
Программа 123
принадлежит (X, [X | Y]).
принадлежит (X, [A |Y ]) : - принадлежит (X,Y).
?-принадлежит (4,(1,3,4,9]).
Ответ:да.
Данная программа имеет очень простой декларативный смысл: элемент принадлежит спи-
ску, если он является его головой или принадлежит хвосту списка.
Пример 3:
соединение двух списков.
Эту задачу можно описать с помощью следующих предикатов:
а) ограничение рекурсии состоит в том, что если к пустому списку [ ] добавить список Р, то
в результате получится Р;
б) рекурсия состоит в том, что можно список Р добавить к концу списка [X|Y], если Р будет
добавлен к хвосту Y и затем присоединен к голове Х (при этом получается список [Х|Т]).
Программа 124
присоединить([ ], Р, Р).
присоединить([XIY], Р, [X | Т]):-присоединить(Y, Р, Т).
? присоединить(L,[джим.R],(джек,бил,джим,тим,джим,боб]).
Ответ:
L=[джек,бил]. К=[тим джим,боб].
L=[джек,бил,джим,тим]. R=[бoб].
Существует традиция использовать для обозначения предиката
слияния двух списков пре-
дикативный символ append (по-английски -добавить).
В некоторых случаях постановки вопросов к такого рода программам приходится исполь-