Вопрос 40. Отсечение.
Если предикат имеет несколько клозов, то при доказательстве одного из них остальные сохраняются в памяти ЭВМ как нерассмотренные.
В случае неудачи при доказательстве какого-либо предиката происходит возврат к таким нерассмотренным клозам. Если требуется исключить такую возможность, применяется стандартный предикат отклонения(!).
Пример.
Имеются факты, описывающие работу сотрудников над проектами, и характеристики проектов. Требуется составить программу, которая будет запрашивать фамилию сотрудника и название заказчика.
Если сотрудник работает над проектом заказчика, то программа выводит «Да», в противном случае – «Нет»
Predicates
nondeterm vyvod
nondeterm otvet(string,string)
nondeterm rabota(string,string)
nondeterm proekt(string,string,integer)
nondeterm repeat
goal
vyvod.
clauses
vyvod:-repeat
clearwindow, write (“Сотрудник:”),
readln (F),
write (“Заказчик:”), readln (Z),
otvet (F, Z),
nl, write (“Продолжить?”), readchar(Prod),
Prod = “H”.
otvet (Fam, St):-rabota(Fam, Shifr),
proekt(Shifr, Zak, _),
write(“Да”), nl,!.
otvet(_,_):-write (“Нет”), nl.
repeat.
repeat:-repeat.
rabota (“Antonov”, “P20”),
rabota (“Ivanov”, “P70”).
rabota (“Ivanov”, ”P100”).
rabota (“Petrov”, “P100”).
rabota (“Vasiliev”, “P70”).
rabota (“Ivanov”, “P120”).
rabota (“Vasiliev”, “P120”).
proekt (“P20”,”Rubin”,700).
proekt (“P100”,”Rubin”,500).
proekt (“P70”,”Gorizont”,500).
proekt (“P120”,”Kristall”,1100).
Например, введена фамилия Ivanov и заказчик Gorizont. Доказывется предикат otvet, где F сопоставляется с Ivanov, а Z - с Gorizont.
Предикат rabota сопоставляется в rabota (“Ivanov”, “P70”), proekt - proekt (“P70”,”Gorizont”,500).
На экран выводится «Да». Предикат отсечения удаляется из памяти 2-й клоз предиката otvet, где предусмотрен вывод ответа «Нет», и затем на вопрос продолжения, если ответить «Да», то произойдет возврат к ближайшей развилке repeat.
Если не использовать предикат отсечения, то «Да» будет выведено, но 2-й клоз предиката otvet сохранится в качестве неиспользованной альтернативы. Если на вопрос продолжения ответить «Да», ближайшей развилкой в vyvod будет otvet, который напечатает «Нет» и спросит «Продолжить?».
Вопрос 41. Рекурсия.
Рекурсия – вызов предиката из тела самого предиката.
Рекурсия обычно применяется при обработки списков, строк, при вычислении сумм и др.
Пример
predicates
nondeterm start
nondeterm fact (integer, long)
clauses
start:-clearwindow
write (“Введите число”), readint (N),
fact(N, NF), write (“Факториал”, NF).
fact(0, 1):-!
fact(N, NF): - N1 = N-1, fact(N1, N1F), NF = N1F*N.
goal
sart.
При вызове предиката fact сначала рассматривается его 1 клоз. Попытка их сопоставления заканчивается неудачей из-за несовпадения 1-го аргумента.
Вызывается второй клоз предиката fact. N связывается с 2, NF – свободная переменная, вычисляется N1 = N-1=1. Далее вызывается fact, где N1 = 1, N1F –свободная. Таким образом, рекурсия fact (N1, N1F) вызывает саму себя и рассматривается 1-й клоз предиката fact. Идет сопоставление fact (N1, N1F) и fact (0, 1), оно заканчивается неудачей, так как N1 = 1.
Таким же образом происходит работа программы далее пока N1 не станет равно 0.
Вопрос 42. Списки.
Список представляет собой основную структуру данных на Прологе.
Список-последовательность из произвольного числа элементов некоторого типа без ограничения на длину списка. Тип данных Список объявляется:
Domins
Списковый_тип=тип*
*Говорит, что перем. – список.
Тип_тип элементолв списка (стандартный, заданный пользователем в domains).
domins
int_list=integer*
predictes
nonderterm numbers(int_list)
Аргумент предиката-список целых чисел. Ввод списков с клавиатуры выполняется стандартным предикатом readtern.
domains
int_list=integer*
predicates
nonderterm dal (int_list, integer, int_list)
nondeterm оbvab
goal
obvab.
….
В Прологе введены понятия головы и хвоста списка. Голова 1-й элемент списка, хвост-остальная часть списка. Хвост сам является спискам.
Пустой список [ ], список из одного элемента [x]
Пусть имеется список Z=[6,8], М и N – свободные переменные. Тогда передает 2 [M/N] доказательство успешно, M связывается с 6, а N- со списком из одного элемента.
Y=M+1 допустима
X=N+1 не допустима
| Предикат1 | Предикат2 | Результат |
| Obrab(l) L=[1,2,3] Obrab(l) L=[1,2,3] Obrab(L) L=[2] Obrab(L) L=[2] Obrab(L) L=[] Obrab(L) L=(1,2,3) | Obrab(x) x-свободная переменная Obrab[H/T] H,T-свободный Obrab[H/T] H,T-свободный Obrab(X)X-свободная переменная Obrab[] Obrab[] | Успешное сопоставление X=[1,2,3] Успешное сопоставление H=1,T=[2,3] Успешное сопоставление H=2, T=[] Успешное сопоставление X=2/x-целочисленная переменная, а не список Успешное сопоставление, т.к. аргументы предикатов равны(оба-пустые символы) Успешное сопоставление Неудача, т.к. аргументы не равны |
Общие рекомендации по составлению программ со списками:
1. В операциях со списками всегда есть рекурсия.
2. Предикаты для реализаций операций со списками обычно имеют несколько клозов. 1-ый из них относится к простейшему случаю, последующие клозы относятся к более общим случаям и имеют следующее назначение.
Если список не соответствует простейшему случаю, то следует уменьшить на 1 элемент и применить рекурсию к укороченному списку.
3. Предикаты, предназначенные для получения одного списка из другого всегда имеют не меньше 2-х аргументов. Исходный список, список-результат.
К числу основных операций со списком можно отнести:
- проверка принадлежащему списку;
Добавление элемента в список;
- удаление элемента из списка;
- присоединение списка у другому;
- вывод элементов списка на экран.
Вопрос 43. Удаление элементов из списка.
domains
list=integer*
predicates
del (integer,list,list)
clauses
del(_,[],[]).
del(H,[H|Tail],Tail):!.
del(X,[H|Tail],[H|NewTail]):del(X,Tail,NewTail).
goal
del(3,[1,2,3,4,5,6,7],L).