Основы современных компьютерных технологий
Управление вычислениями
Основными средствами управления процессом вычислений в Прологе являются стандартные предикаты fail (неуспех) и ! (отсечение).
Назначение этих предикатов и методы их использования рассмотрим на примере следующей программы на Турбо-Прологе:
domains
st=student(fam,pr,oc)
312
fam.pr=symbol
num,oc=integer
g=gr(num,st)
predicates
kurs_22(g)
clauses
kurs_22(gr(261 ,student("ПETPOB П.Р.","Программирование",5))).
kurs_22(gr(261,student("ИBAHOB Б.О. ","Операционные системы",5))).
kurs_22(gr(261,student("CИДOPOB Т.К.","Системы управления",4))).
kurs_22(gr(262,student("ЖИГAPEB С.И. "."Программирование''3))).
kurs_22(gr(262,student(" ДЕМИН ", "Системы управления", 5))).
kurs_22(gr(261 ,student(" ПETPOB П.Р.","Иностранный язык",4))).
kurs_22(gr(263,student(" СИДОРОВ ","Операционные системы",5)))
Приведенная программа в разделе clauses содержит утверждения-факты, в данном случае информацию о результатах пересдачи экзаменов студентами соответствующих групп (номер группы - первый компонент структуры gr) по соответствующим дисциплинам (фамилия, дисциплина, оценка - компоненты структуры student, которая входит в состав структуры gr). Если теперь после компиляции программы в качестве внешней цели ввести запрос:
kurs_22(X)
то в диалоговом окне будет выведена информация:
X=gr(261 ,student("ПETPOB П.Р.","Программирование",5))
Х= gr (261 ,student("ИBAHOB Б.О.", " Операционные системы",5))
Х= gr (261,student ("СИДОРОВ Т.К.", "Системы управления " ,4))
X=gr (262, student(" ЖИГAPEB С.И. "."Программирование" 3 ))
X=gr (262, student(" ДEMИH С.Л. ", "Системы управления", 5))
Х= gr (261 ,student(" ПETPOB П.Р.","Иностранный язык",4))
X=gr (263, student("CИДОРОВ Е.P. ","Операционные системы",5))
7 Solutions
т.е. будут найдены все варианты решений, так как в запросе не задано ограничений на значения переменной X.
Наложим ограничение, например, на номер учебной группы. Для внешнего запроса
kurs_22(gr(261,X))
результатом будет:
X=student(" ПETPOB П.Р.","Программирование",5)
X=student(" ИBAHOB Б.О."."Операционные системы",5)
X=student(" СИДОPOB Т.К.", "Системы управления", 4)
X=student(" ПETPOB П. R", "Иностранный язык",4)
4 Solutions
Продемонстрируем еще один внешний запрос:
kurs_22(gr(Z,student(" ПETPOB П.Р.", X, Y)))
313
Система ответит:
Z=261,Х=Программирование, Y=5
Z=261, Х=Иностранный язык, Y=4
2 Solutions
Если теперь любой из этих запросов сделать внутренним, т.е. записать в разделе goal, откомпилировать и выполнить программу, то, кроме сообщения Press the SPACE bar, в диалоговом окне не будет результатов, так как мы не задавали предикатов вывода значений результата внутреннего запроса.
Изменим внутренний запрос:
goal
kurs_22(X),write(X)
Здесь для вывода значений переменной X после сопоставления используется системный предикат write(...). Результаты такого запроса будут помещены в диалоговое окно в виде:
gr(261 ,student(" ПETPOB П.Р.","Программирование",5))
т.е. будет найдено первое подходящее решение. Если теперь не меняя запроса изменить порядок предложений в программе, например, поменять местами первое со вторым, то результат будет другим:
gr(261 ,student(" ИBAHOB Б.О.", "Операционные системы",5))
Как видим, Пролог чувствителен к порядку предложений в программе: правила просматриваются сверху вниз. Для того, чтобы заставить Пролог осуществить поиск всех вариантов решения задачи при использовании внутренней цели в программе (в данном варианте это вывод на экран всех фактов), необходимо организовать циклический перебор альтернативных решений. В Прологе это можно сделать различными способами.
Один из них - использовать свойство Пролога выполнять поиск альтернативного решения при неудачной попытке применения текущего. В этом случае Пролог выполняет откат до ближайшей альтернативы, восстанавливает первоначальные условия поиска и процесс начинается заново с найденной новой альтернативы. Для организации таких вычислений в языке есть специальный предикат fail, который всегда завершается неуспехом и вызывает откат до ближайшей альтернативы.
Для цели перебора всех альтернативных фактов в примере и вывода их на экран в состав программы введем нульместный предикат show и правило вида: show:-kurs_22(X),write(X),fail. Для этого в раздел predicates добавим строку show, в разделе clauses поместим строку show:- kurs_22(X),write(X),fail.
Зададим также внутреннюю цель вида:
goal
show.
В этом случае на экран будут выведены все 7 альтернативных решений - после нахождения первого переменная X будет означена константой первого факта, полученное значение переменной X сопоставляется аргументу предиката write(X), который выведет его на экран, после чего выполняется предикат fail, который завершается неуспехом и
314
Пролог выполнит откат до ближайшего недетерминированного предиката (т.е. имеющего несколько вариантов правил), а это в нашем случае предикат kurs_22(X), будет выбран второй факт, выполнено сопоставление и т.д. до тех пор, пока не будут перебраны все альтернативы.
Предписать Прологу выполнять откат можно не только с помощью предиката fail -любой неуспешно завершенный предикат вызывает откат до ближайшей альтернативы (стоящего от него левее в теле правила). Продемонстрируем это на нашем примере. Пусть необходимо получить и вывести на экран информацию о студентах, пересдавших экзамен по дисциплине "Программирование".
Изменим предикат show:
show:-kurs_22(gr(X,student(Y,Z, K))),
Z="Программирование",
write( " Гpyппa-" . X, " Студент-", Y, " Оценка-", K),
nl,
fail.
Тогда для внутреннего запроса:
goal
show
на экран будет выведено:
Группа-261 Студент-ПЕТРОВ П.Р. Оценка-5
Группа-262 Студент-ЖИГАРЕВ С.И. Оценка-3
Таким образом, сравнение 7="Программирование ", выполняет двоякую роль: с одной стороны, это фильтр, который не допускает выполнения предиката write(...) при неуспешном сравнении, а с другой - вызывает из-за неуспешного сравнения откат до ближайшей альтернативы. При этом если бы не было предиката fail, было бы получено только первое решение - fail обеспечивает перебор всех альтернатив. Предикат nl является стандартным, он выполняет переход на следующую строку при выводе информации на экран.
В Турбо-Прологе имеются средства, с помощью которых можно заблокировать поиск с возвратом. Для этих целей служит специальный предикат, который называется отсечение (cut) и обозначается восклицательным знаком. Для демонстрации его использования в нашем примере добавим предикат отсечения в правило show:
show:-kurs_22(gr(X,student(Y,Z,K))),
Z="Программирование",!,
write(Tpynna-",X," Студент-", Y ," Оценка-",К),
nl,
fail.
Тогда для внутреннего запроса:
goal
show
315
на экране будет выведена информация:
Группа-261 Студент-ПЕТРОВ П.Р. Оценка-5
В данном варианте после успешного сравнения Z="Программирование " предикат ! прекращает условия поиска после формирования условия "неуспех" предикатом fail.
Таким образом, использование в правиле предиката отсечения означает, что в дальнейшем не будет производиться перебор других аргументов предикатов, использованных в этом правиле до знака отсечения после формирования признака неуспеха любым из предикатов, стоящим в правиле правее предиката !. Но это не означает, что не будут перебираться альтернативные варианты по неуспеху для других предикатов, стоящих за !.
Преобразуем предикат show к виду:
show:-kurs_22(gr(X,student(Y, Z, K))),
Z="Программирование ", ! , К=3,
write(" Группа -", X ," Студент-", Y, " Оценка-",К),
nl,
fail.
В этом случае не будет получено результатов, так как после поиска первого решения для Z="Программирование " переменная К=5 и сравнение 5#3 сформирует неуспех, который не приведет к возврату для поиска следующей альтернативы для предиката kurs_22(gr(X,student( Y.Z.K")), так как условия возврата уже сброшены отсечением.
Введем в правило еще один предикат kurs_22(gr(>A,student(S,C,D))), который зависит от других переменных - это принципиально. Предикат show будет следующим:
show:-kurs_22(gr(X,student(Y,Z, K))),
Z="Программирование",!,
kurs_22(gr(A,student(B,C,D)),D=3,B=Z,
write(" Группа-", А, " Студент-", В," Оценка-",D),
nl,
fail.
После внутреннего запроса show на экран будет выведена информация в виде:
Группа-262 Студент-ЖИГАРЕВ С.И. Оценка-3
Отметим, что часть правила после отсечения ! осуществляет полный перебор всех фактов программы, начиная с первого, с помощью фильтра D=3, B=Z, а при его выполнении - с помощью fail.
Другими словами, отсечение ограничивает распространение аргументов для подбора новых значений возврата (бэктрекинга) из-за неудачи. Отсечение применяется также для ускорения вычислений путем отбрасывания избыточных ветвей вычислений.
Замечания:
316
317
312 :: 313 :: 314 :: 315 :: 316 :: 317 :: Содержание
