Лабораторная работа 3.
Управление ходом выполнения программ в системе Турбо-Пролог.
Цель работы:
- Познакомиться с процессами унификации и помеха с возвратом.
- Изучить правила унификации термов.
- Изучить работу системы Турбо-Пролог при выполнении запроса.
- Ознакомиться с методом отката после неудачи.
1. Работа системы Турбо-Пролог при выполнении запросов
Запрос к системе - это всегда последовательность, состоящая из одной или нескольких целей. Для ответа на запрос система пытается достичь всех целей, т.е. показать, что утверждения, содержащиеся в запросе, истинны в предположении, что все отношения программы истинны. Другими словами, достичь цели - это показать, что она логически следует из фактов и правил программы, а если в запросе есть переменные, то еще и конкретизировать их, т.е. найти те конкретные объекты, которые, будучи подставленные вместо переменных, обеспечат достижение цели.
Для этого система опускается в структуру программы так глубоко, как это необходимо, чтобы найти факты, требующиеся для доказательства истинности запроса. Затем система вернется в исходное состояние, доказав или оказавшись не в состоянии доказать истинность запроса. В основе работы системы лежит рекурсивный циклический процесс унификации (т.е. сопоставления с образцом) и доказательства подцелей.
При задании запроса система просматривает всю программу в поисках первого предложения, заголовок которого будет унифицироваться с запросом. Д"1Я того, чтобы запрос и заголовок предложения унифицировались между собой, необходимо:
- совпадение у них имени предиката;
- совпадение количества аргументов предиката;
- возможность унификации всех аргументов предиката (правила унификации термов приведены ниже).
Если предложение, унифицирующееся с запросом, будет обнаружено, то оно начинает обрабатываться:
- если тело предложения является пустым (т.е. это факт), то запрос сразу оказывается успешным, переменные запроса конкретизируются объектами факта, и это решение помечается указателем возврата.
- если тело предложения содержит подцели, то, последовательно слепа направо, каждая из них обрабатывается точно так же, как исходный запрос-
Если система в тексте программы не находит предложения, унифицирующегося с запросом, то она:
- возвратится к последней успешно доказанной подцели;
- ликвидирует конкретизацию всех переменных, явившуюся результатом успешной обработки этой подцели, т.е. делает переменные свободными;
- приступает к поиску во множестве предложений текущей программы; заголовка другого предложения, унифицирующегося с данной подцелью.
Такая процедура обработки запроса получила название поиск с возвратом. Применяя ее, при успешном выполнении запроса система выдает:
- либо значения всех переменных, входящих в состав запроса, которые были конкретизированы в результате обработки;
- либо слова да или кет, если переменные в запросе отсутствовали.
Если запрос был сформирован как внешняя цель решения задачи, то система после найденного первого ответа вернется в точку, помеченную указателем возврата и попытается найти иной ответ.
2. Унификация термов
Наиболее важной операцией над термами является унификация, при которой осуществляется: конкретизация переменных, доступ к структурам данных через общий механизм согласования и определенные виды тестов на равенство. Процесс унификации соответствует передаче параметров в других языках программирования. Унификация термов регулируется следующими правилами:
- Свободная переменная унифицируется с константой или структурой. В результате этого переменная становится конкретизированной, т.е. принимает значение этой константы или структуры.
Goal: Х = john
Х = john
- Переменная унифицируется с переменной, при этом обе они становятся одной и той же переменной.
Goal: X=Y
Х=_1
Y=_1
- Анонимная переменная унифицируется с чем угодно.
? _ = john
- Константа может быть унифицирована с другой константой, если они идентичны или со свободной переменной соответствующего типа.
Goal: "джон" = "джон"
True
- Структура унифицируется с другой структурой при условии, что их функторы одинаковы, а аргументы могут попарно унифицироваться.
? father(X) = father(john)
X = john
Для того, чтобы познакомиться с процессом унификации различных классов объектов Пролога, рассмотрим выполнение программой 7 нескольких запросов.
/* Программа 7 */
- domains
- title , author = symbol
pages = integer
publication = book(title , pages)
- predicates
- written_by(author,publication)
long_novel(publication)
- clauses
- written_by("И.Бpaтко", book("Программирование на языке Пролог",5б0)).
written_by("Ц.Ин,Д.Соломон" ,book( "Использование Турбо-Пролога",608)).
long_novel(book(Title,Lcngth)) :- written_by( _ , book(Title , Length)), Length &rt; 600.
Рассмотрим запрос вида: written_by(X,Y) . При решении задачи система должна поочередно согласовать цель с предложениями программы, пытаясь достичь соответствия между параметрами Х и Y с одной стороны и параметрами предложений программы с другой, выполняя операцию унификации.
Так как в данном запросе переменные Х и Y являются свободными и могут согласовываться с любой константой, то самое первое предложение для предиката written_by дает желаемое соответствие:
written_by( Х , Y )
I I
written_by("H.Бpaтко" , book(" Программирование на языке Пролог",560) ).
т.е. Х конкретизируется константой "И.Братко", а Y принимает значение структуры book( "Программирование на языке Пролог" ,560). Система Турбо-Пролог помечает эту точку указателем возврата и выдаст на экран сообщение.
Х = "И.Братко" Y = book(" Программирование на языке Пролог" ,560)
Так как мы задавали запрос как внешнюю цель, система возвращается в точку, помеченную указателем возврата и продолжает, начиная с этой точки, процесс унификации и находит второе предложение, которое также может быть согласовано с запросом. После унификации переменных система выдает на экран Х = "Ц.Ин, Д.Соломон" Y = bооk("Использование Турбо-Пролога",608) 2 и заканчивает процесс унификации.
Если введем запрос written_by(Х,book("Использование Турбо-Пролога",Y)), то попытка унификации переменных с первым предложением программы будет выглядеть так:
written_by( Х , book( "Использование Турбо-Пролога", Y )
l l
written_by("И.Братко" , book("Программированис на языке Пролог" ,560) ).
Так как Х свободна, то она принимает значение константы "И.Братко", и делается попытка установить соответствие между двумя структурами. Но составной объект согласуется с другим составным объектом при условии, что они оба имеют один и тот же функтор, одинаковое количество аргументов, и все аргументы могут быть попарно унифицированы. Однако, константа "Использование Турбо-Пролога" может быть унифицирована только со свободной переменной или сама с собой. Так как между первыми двумя компонентами структуры book соответствие невозможно, то формируется признак неудачи, и система пытается согласовать цель со следующим предложением программы, переходя к проверке соответствия между:
written_by( Х , book(" Использование Турбо-Пролога", Y ) ).
l l
written_by("Ц.Ин, Д.Соломон " ,book(" Использование Турбо-Пролога",608) ).
Свободная переменная Х унифицируется с константой "Ц.Ин, Д.Соломон". Обе структуры имеют один и тот же функтор book, содержат равное число компонентов, и первые компоненты обеих структур - одинаковые константы. Т.е. эти структуры могут быть унифицированы, и при этом константа 608 унифицируется с переменной Y. Т. е. цель достигнута, и Турбо-Пролог выводит сообщение:
Х = "Ц.Ин, Д.Соломон" Y = 608
Наконец, рассмотрим выполнение запроса: Iong_novel (X). Прежде всего система пытается отыскать предложения, заголовки которых согласуются с запросом.
long_novel( Х )
l
long_novel( Title ) :-written_by( _ , book(Title,Length)) , Length > 600.
После этого согласовываются левая и правая части правила. Переменные Х и Title согласуются, т.к. они свободны и становятся одной и той же переменной. Затем Турбо-Пролог объявляет первое предложение указанного выше правила подзадачей и делает попытку ее унификации:
written_by( _ ,book( Title , Length) )
1 1 1
written_by("И.Бpaткo" ,book(" Программирование на языке Пролог", 5б0 ) ).
Так как анонимная переменная согласуется с любым объектом и структуры book также согласуются, то эти два предиката могут быть унифицированы. В результате этого переменная Title принимает значение "Программирование на языке Пролог", а переменная "Length' становится равной 560.
После этого делается попытка согласовать вторую подзадачу тела правила, а именно: Length &rt; 600. Перед попыткой унификации связанная переменная Length заменяется своим численным значением 560. Так как выражение: 560 > 600 ложно, то Турбо-Пролог делает возврат назад к уже доказанной подцели и пытается его передоказать. Т.е. снова пытается унифицировать первую подзадачу
written_by( _ ,book(Title,Length)),
используя следующий из имеющихся фактов
written_by( _ ,book(Title,Length)), используя следующий из имеющихся фактов
written_by( _ ,book( Title , Length) )
1 1 1
written_by("Ц.Ин, Д.Соломон " ,book(" Использование Турбо-Пролога", 608 ) ).
который связывает Title с "Использование Турбо-Пролога" и Length с 608. В данном случае оказывается: Length &Rt; 600, т.е. вторая подзадача также становится истинной. Правило полностью согласовано при полученных значениях переменных, задача решена, о чем выдается сообщение:
Х = "Использование Турбо-Пролога"
1
Исходная цель является полностью доказанной, и функционирование системы Турбо-Пролог по выдаче ответа на введенный запрос заканчивается. Система готова к приему новых запросов.
3. Поиск с возвратом при выполнении Пролог-программ
Знание метода поиска с возвратом, реализованном в Пролог-системе, позволит Вам правильно составлять Пролог-программы и управлять поиском решений. Более подробно рассмотрим этот процесс на примере программы б из лабораторной работы 2.
Задание 1.
- Загрузите в систему Турбо-Пролог программу б из предыдущей лабораторной работы, войдите в режим редактирования и введите директиву пошагового выполнения программы. Для сокращения пространства поиска последнее правило в базе данных work(...) сделайте комментарием !!!.
- Сформируйте запрос о поиске всех сослуживцев Сидорова и в режиме пошаговой трассировки отследите процесс поиска решений.
Решая любую задачу. Пролог строит дерево подзадач, отмечает, какие подзадачи решены, а какие еще нет. Так при решении поставленной в задании задачи дерево подзадач будет иметь вид:
colleague("Сидорoв",Y)
/ | \
/ | \
work(Man1,W) ) work(Man2,W) Маn1<>Маn2
В данном примере будет истинным.
При решении любых подзадач Турбо-Пролог использует два основных правила:
- Поиск решений подзадач производится слева направо.
- Выбор предикатов для рассмотрения при решении каждой подзадачи осуществляется в том порядке, в котором они появляются в программе.
При этом, если какая-либо из подзадач не может быть успешно согласована, то выполняется возврат (или откат), чтобы найти другие возможные пути ее вычисления.
Рассмотрим процессы поиска с возвратом и унификации, реализуемые Пролог-системой при выполнении запроса colleague("Сидоров",Y). На рис.2, приведена схема работы Пролог-системы при выводе ответа на поставленный запрос. Решение всей задачи представляет собой последовательность четко определенных этапов (шагов) выполнения задачи:
- После ввода, запрос помещается в вершину стека активных запросов, тут же система приступает к поиску предложений с тем же самым именем предиката, что и у запроса.
- Анализируя найденное предложение, система унифицирует каждый аргумент запроса с соответствующим аргументом предложения (правила). После унификации запроса с заголовком, система переходит к телу предложения и унифицирует все его переменные в соответствии с заголовком правила.
- Тело правила составное, поэтому первая подцель помещается в стек запросов, становится активным запросом и начинает обрабатываться как запрос. На данном этапе стек запросов имеет вид:
colleague("Cидоров",Y)
work("Сидоров",W) <- активный запрос
- Новый активный запрос приступает к поиску предложений программы с тем же самым именем предиката, что и у активного запроса.
Рис.2. Схема работы Пролог-системы при выводе ответа на запрос.
- Если попытка унификации запроса с заголовком фразы заканчивается неудачей, то система переходит к анализу следующего предложения. Этот процесс продолжается до тех пор, пока не обнаружится предложение, которое будет унифицироваться с запросом. Если его не будет, то запрос завершится неудачей.
- И
- Если унифицирующее предложение найдено и оно является фактом, то подцель сразу же оказываете успешной, переменные унифицируются с фактом и в стек запросов заносится вторая подцель, которая становится активной:
colleague("Сидоров",Y)
work("Сидоров",101) * (истина)
work(Y,101) <-- активный запрос
- И
- Данные шаги аналогичны п.5-п.7. с той лишь разницей, что если в первом случае поиск в базе work(...) осуществлялся по фамилии, то во втором - поиск в той же базе выполняется по номеру отдела. Первое предложение базы work(...),
являющееся фактом, делает активный запрос успешным. Его система помечает маркером возврата, унифицирует переменную Y с константой "Петров", и третья подцель загружается в стек запросов:
colleague("Сидоров","Петров")
work("Сидоров",101) * (истина)
work("Петров",101) * (истина)
"Сидоров"<>"Петров" <- активный запрос
- Проверка активного запроса показывает, что последняя подцель является истинной, а так как значения истины приняли ранее и первые две подцели, то и вся цель является истинной при значении переменной Y="Петров", о чем выдается сообщение на дисплей. Т.е. задача решена.
- Но так как цель является внешней, то после поиска первого решения и вывода его на экран система искусственно генерирует состояние неудачи и делает откат к повторному доказательству предыдущей подцели с освобождением персмсннь1х. При этом новое состояние стека запросов будет иметь вид:
colleague("Сидоров",Y)
work("Сидоров",101) * (истина)
work(Y,101) <- активный запрос
- Повторяется процесс аналогичный и.8. Существенное отличие в том, что поиск осуществляется не сначала, а с той позиции, которая отмечена маркером возврата, что сокращает пространство поиска.
- После согласования активного запроса с базой и унификации переменной Y константой "Сидоров", система помечает эту позицию базы маркером возврата, и стек запросов принимает вид:
colleague("Сидоров","Сидоров")
work("Сидоров",101) * (истина)
work("Сидоров",101) * (истина)
"Сидоров"<>"Сидоров" <- активный запрос
- Сопоставление в активном запросе дает ложное значение, что приводит к тому, что и весь запрос является ложным. Пролог-система автоматически пытается его передоказать, вызывая ситуацию отката (возврата) к последней успешной подцели, освобождая конкретизованные в последнем запросе переменные. Стек запросов аналогичен п. 11.
- и
- Поиск в базе, начиная с позиции, помеченной маркером возврата согласование с фактом, унификация переменной Y новым значением и переход к третьей подцели приведут к тому, что состояние стека запросов будет иметь вид:
colleague("Сидоров","Иванов")
work("Сидоров",101) * (истина)
work("Иванов",101) * (истина)
"Сидоров"<>"Иванов" <- активный запрос
- Проверка в активном запросе показывает, что последняя подцель является истинной, а так как значения истины приняли ранее и первые две подцели, то и вся цель является истинной при значении переменной Y="Иванов", о чем выдастся сообщение на дисплей. Т.е. задача решена.
А так как маркер возврата стоит на конце базы данных, то у оболочки Турбо-Пролога отсутствует возможность искусственного вызова состояния неудачи, что приводит к окончанию задачи.
Задание 2.
Выполните трассировку программы и составьте упрощенную схему работы Пролог-системы для случая поиска всех сослуживцев.
Задание 3.
Повторите задание 2 для случая выполнения запроса о поиске всех коллег Козлова: all_colleague("Козлов",X,Y).
Откат (или возврат) автоматически инициируется системой Турбо-Пролога, если не используются специальные средства управления им.
Для управления процессом отката в Прологе предусмотрены два предиката: fail (неудача) и cut (отсечение).
Использование внешней цели побуждает переменные получать все возможные значения одно вслед за другим. При этом все их значения в не отформатированной форме выдаются в окне диалога системы. Если их число велико, то текст в окне будет быстро меняться и прочитать его будет довольно сложно или даже невозможно. Поэтому в этом случае встает задача обеспечения некоторого интерфейса вывода.
4. Использование отката после неудачи при использовании внутренней цели для организации простейшего интерфейса вывода
Если простейший интерфейс вывода будет реализован как Внутренняя цель программы, то внутренние унификационные процессы Турбо-Пролога закончат поиск решения сразу после первого успешного вычисления цели. Для поиска всех значений Пролог-программа должна заставить повторно работать внутренние унификационные средства Турбо-Пролога.
Одним из способов реализации данной задачи является использование метода отката после неудачи (ОПН), использующий предикат fail. Пример использования этого предиката демонстрирует программа 8.
/* программа 8 */
- include "lab3.рго"
- predicates
- query
do_answer(namc) goal
query.
- clauses
query :-
- makewindow(2,7,15," Запрос коллеги :", 18,0,6,50),
cursor 1,10),
write("Введи фамилию -> "),
readln(Who),
makcwindow( 1,7,15," Коллеги :", 1,50,22,29),
do_answer(Who).
do_answer(X) :- colleague(X.Y), write(" ",X," -&rt; ",Y),nl,fail.
Два предиката этой программы позволяют формировать запрос и получать на него ответ. Текстовая подстановка файла программы б из лабораторной работы 3 обеспечивает доступ ко всем се предикатам и базам данных.
Таким образом эта программа являет собой пример интерфейса для ввода и вывода данных программы 6.
Программа содержит внутреннюю цель в виде предиката query, который создает па экране окно ввода данных, выдает подсказку, обеспечивает ввод и означивание переменной Who. а также формирует окно вывода данных.
Предикат do_answer(...) обеспечивает запрос на поиск сослуживцев введенного служащего. Действия, выполняемые системой по данному запросу, аналогичны первым 11 шагам, приведенным на рис.2. Однако на 11 шаге система не будет осуществлять принудительный возврат, и решение задачи остановится.
Чтобы этого не случилось в программу введен предикат fail, который всегда вызывает состояние неудачи, что заставляет систему выполнять, откат после неудачи к предыдущей подцели и фактическое продолжение функционирования программы в режиме, аналогичном приведенному на рис.2.
5. Содержание отчета по лабораторной работе
Отчет по лабораторной работе должен содержать:
- Результаты трассировки программы 7 для трех запросов, описанных в параграфе 1 данной лабораторной работы.
- Результаты выполнения заданий 1,2 и 3 данной лабораторной работы.
- Результаты исследования программы 8 при наличии и отсутствии предиката fail в программе.
- Модифицированный вариант программы 8 для случая, когда окно вывода занимает целый экран, а окно ввода присутствует на экране только на момент ввода.
- Список, назначение и описание простейших предикатов Турбо-Пролога для ввода-вывода данных разного типа.