Лабораторная работа 4
Управление ходом выполнения Пролог-программ

       Цель работы:
  1. Ознакомление с действиями предикатов неудачи и отсечения.
  2. Изучение методов организации повторного выполнения группы задач.
  3. Знакомство со способом построения программ-меню.
  4. Управление ограничением пространства поиска с использованием отсечения.

1. Организация повторяющихся процессов

       При выполнении запросов программа последовательно обращается к фактам и правилам. При этом правила часто требуют, чтобы задачи типа поиска элементов в базе, ввода или вывода данных выполнялись многократно. Однако в Прологе отсутствует возможность непосредственного задания итерационного процесса, т.е. не реализованы синтаксические конструкции типа FOR, WHILE или REPEAT.

       Существует два способа построения правил, выполняющих одну и ту же задачу несколько раз. Это повторение, использующее возврат, и рекурсия, использующая вызов процедуры самой себя.

       Повторение реализуется с использованием метода отката после неудачи, когда осуществляется возврат к последней, имеющей альтернативное решение, подцели, реализация альтернативы и очередной возврат. Поэтому поиск с возвратом можно использовать для выполнения повторяющихся процессов. Примером построения правила, использующего повторение, является предикат do_answer() в программе 8.

       Но если этот подход применить к предикату query той же программы, т.е. искусственно вызвать состояние неудачи, добавив предикат fail в виде последней подцели правила, то никакого повторного запроса на ввод мы не получим.

       Задание 1.
Вызовите программу 8, добавьте fail в конец описания query и, запустив программу на выполнение, убедитесь что процесс не повторяется.        Объясняется это тем, что предикаты формирования окна и ввода не являются альтернативами, т.е. не имеют альтернативных решений, а предикат do_answer() все альтернативные решения получил, т.е. цель query является истинной и решение задачи заканчивается.

       Для того, что обеспечить многократный ввод данных, необходимо, чтобы откат выполнялся к некоторому предикату, имеющему альтернативное решение, с одной стороны, и чтобы это решение было бы постоянно истинным, с другой стороны. При невыполнении последнего условия откат может произойти к еще более ранним подцелям и не обеспечит повторения именно нужной нам группы действий.

       Используя простейшую рекурсию, процедура задания предиката для правила повтора, определяемого пользователем, может иметь вид:
repeat.
repeat :- repeat.
       Первая строка - это факт, который всегда успешен и объявляет предикат repeat истинным. Однако, так как есть для этого предиката еще одно правило, то указатель отката устанавливается на первый repeat. Вторая строка - это правило, которое использует самовызов. Правило (второй repeat) вызывает подцель (третий repeat), и этот вызов вычисляется успешно, так как факт (первый repeat) удовлетворяет подцели. Следовательно, правило также всегда успешно. Предикат repeat будет успешно вычисляться при каждой новой попытке его вызвать после отката. Таким образом, repeat - это рекурсивное правило, которое никогда не бывает неуспешным.

       Задание 2.
Введите в программу описание предиката repeat. Вставьте обращение к этому предикату в качестве первой подцели правила query. Запустите на выполнение программу. Теперь у Вас появилась возможность повторного ввода, но нет признака окончания и единственный вариант выхода из программы - это Ctrl+Break.

       Но для того, чтобы сформировать признак окончания повторений, давайте разберемся, как работает программа, и кто инициирует повтор. Первым выполняется repeat, который ничего не делает, далее - не имеющие альтернатив стандартные предикаты и последним предикат do_answer, который и обеспечивает откат после неудачи к предикату repeal за счет присутствия в нем предиката fail.

       Задание 3.
Закомментируйте в правиле do_answer предикат fail и запустите программу на выполнение. Обратите внимание, что наличие в программе предиката repeat еще не обеспечивает повторов, что для организации повторов необходим возврат к предикату repeat. Снимите комментарий.

       Но если откат к repeat вызывает do_answer, то он должен и обеспечить, при определенных условиях, окончание этого процесса. Если за условие выхода будет принят, например, ввод слова stop вместо фамилии, то можно доопределить предикат do_answer еще одним правилом:
do_answer(X) :- X="stop",
write("good bye").
которое будет истинным при согласовании, и которое, ввиду отсутствия признака неудачи, не вызовет отката к предикату repeat.

       Задание 4.
Добавьте новое правило в последнюю строку процедуры. Запустите программу на выполнение сначала в обычном режиме, а затем - в режиме трассировки, но только предиката do_answer. Переставьте новое правило на первую строку процедуры и выполните трассировку. Какой получился результат? Что будет, если правило для условия выхода записать в виде:
do_answer("stop"):-write("good bye").? Какой из этого следует вывод?
       Обобщая изложенное, можно сделать вывод о том, что условие выхода из цикла может определяться любым предикатом, одно из множества альтернативных описаний которого должно содержать предикат fail или вызывать поиск с возвратом, т.е. обеспечивать откат.

       Из анализа даже простейших случаев организации повторяющихся процессов, как реализуемых самой Пролог-системой, так и определяемых пользователем, можно сделать вывод о необходимости управления этими процессами со стороны пользователя.

2. Управление поиском с возвратом

       Один из вариантов управления поиском с возвратом можно иллюстрировать на примере предиката do_answer, записанного в несколько другой форме.
do_answer(X) :-colleague(Z.Y),X==Z,write(" ",X," -> ",Y),nl,fail.
       Альтернативная форма записи не изменяет сути данного правила, но дает возможность показать, что введением новых подцелей в правило можно управлять поиском с возвратом. Из этого примера видно, что вторая подцель может оказаться неуспешной из-за несоответствия служащего, унифицированного по первой подцели, со служащим, унифицированным через заголовок правила, т.е. введенного с клавиатуры. Неуспех унификации второй подцели приведет к тому, что откат возникнет до выдачи информации на экран и предикат fail не потребуется. Включен предикат fail в правило, чтобы вызвать откат, если условия правила будут выполнены и все правило окажется успешным.
show_menu:-makcwindow(l,7,15," Меню ",1,50,10,20), repeat, clearwindow, write(" 1 - процесс 1"), nl, write(" 2 - процесс 2"), nl, write(" 0 - выход "), nl, nl, write(" Ваш выбор -> "), readint( Menu ), Menu < 3, process( Menu ), stop_menu( Menu).
stop_menu( 0 ) .
stop_menu( _ ) :- fail.
       Еще одним примером по управлению поиском с возвратом является процедура построения меню show_menu.

       В ней repeat используется так, что после выхода из любого модуля, вызываемого предикатом process(), идет возврат в меню.

       Исключением является выбор нуля, что вызывает око1гчанис программы.

       В данном правиле управление откатом используется дважды: в виде предикатов Menu<3 и slop_menu(Menu).

       Подцель Menu<3 проверяет значение, введенное с клавиатуры. Если введено значение большее или равное трем, то подцель закончится неуспехом, и произойдет откат. Если введено значение меньшее 3, то подцель закончится успехом и будет сделана попытка выполнения следующей подцели process().

       Если процедура process() завершится успехом, то система делает попытку выполнить процедуру stop_menu(), которая при любых, кроме 0, значениях выбора завершается неудачей, что вызывает откат к предикату repeat. При значении выбора равном 0 - она является истинным фактом, и программа завершается.

       Задание 5.
Сохраните на диске Ваш рабочий файл с именем lab4.рго. Он нам скоро понадобится. Создайте новый файл lab4menu.pro, в котором, используя приведенные выше предикаты, напишите программу организации выполнения двух произвольных процессов с выбором их через меню. Процессы должны быть описаны соответствующими предикатами и иметь простейший вид. Например, открытие окна и выдача сообщения.

       Запустите программу па выполнение. Затем, используя трассировку, внимательно изучите ход решения задачи, откаты и повторы, выполняемые программой.

3. Управление ходом выполнения программ с использованием отсечения

       Турбо-Пролог содержит средство, препятствующее поиску с возвратом в определенных условиях. Эта операция называется отсечением и выполняется предикатом cut, который в программах обозначается восклицательным знаком (!). Воздействие этого средства просто сводится к прекращению поиска. Отсечение используется в двух случаях:
       1. Для ограничения пространства поиска в случаях, когда заранее известно, что некоторые возможные пути не приведут к интересующим вас решениям, т.е. обработка их приведет к ненужной потере времени. С использованием отсечения программа решается быстрее и требует меньшего объема памяти.
       2. Когда отсечение требуется по логике программы для:
       - Недопущения возврата к предыдущей подпели правила при откате. Пусть какое-либо правило имеет вид:
r1(X,Y,Z) if a(X) , b(Y) , ! , c(X,Y,Z).
       Правило, записанное в такой форме, указывает на то, что система пройдет через предикат cut только в том случае, если и подцель а(Х), и подцель b(Y) будут успешными. После того, как предикат cut будет обработан, система не сможет вернуться назад для повторного рассмотрения подцелей а(Х) и b(Y). если подцель c(X,Y^) потерпит неудачу при текущих значениях переменных X,Y и Z.
       - Предотвращения перехода к следующему предложению процедуры.

       Пусть процедура описания предиката г состоит из трех правил. Обозначим через r1. r2 и r3 - записи одного и того же предиката r в каждом из трех предложений процедуры. Тогда два варианта записи этой процедуры в виде: 
a) r1(X,Y) if I, a(X),b(Y), c(X.Y).         6)  r1(X,Y) if a(X), b(Y), c(X,Y), !.
   r2(X,Y) if !,d(X,Y)                          r2(X,Y) if d(X,Y), !.
   r3(X,Y) if e(X,Y)                            r3(X,Y) if e(X,Y)
       соответствуют тому, что, в первом случае, при обработке предиката r будет использовано лишь одно из правил r1, r2, r3, а, во втором случае, истинность какого-либо одного из правил приводит к окончанию процедуры и исключению из рассмотрения всех записанных ниже.

       Пример.
Процедуру поиска максимального из двух чисел можно записать в виде двух правил для предиката max. Но эти правила взаимно исключающие. Если неудачу терпит первое, то второе будет выполняться. Поэтому с использованием отсечения возможна значительно более короткая формулировка процедуры.
max(X,Y,X):-X> =Y
max(X,Y,Y):-X< Y

max(X,Y,X):-X> =Y,!
max(X,Y,X)
       Таким образом, если предикат fail инициирует бектрекинг (возврат к перебору очередных альтернатив после первой найденной), то предикат cut его завершает.

       Рассмотрим на простых примерах использование различных вариантов отсечения для управления ходом выполнения Пролог-программ.

4. Использование метода отката и отсечения

       Использование этого метода начнем с рассмотрения задачи о сослуживцах" когда возникают требования по выдаче ответов на более широкий круг вопросов, чем определение сослуживцев только одного конкретного служащего, задаваемого с клавиатуры (как это было в предыдущем примере). Предположим, что перечень возможных для обращения к системе запросов включает в себя требования по:
       - поиску всех сослуживцев,
       - поиску всех сослуживцев конкретного служащего,
       - выяснению наличия сослуживцев у конкретного служащего,
       - выдаче списка всех сослуживцев, ограниченного снизу некоторым служащим.

       Один из вариантов реализации требований по запросам к системе может иметь вид расширенной процедуры do_answer()
/* правило 1 */

do_answer("stop") :- write("good bye"). /* правило 2 */

do_answer(X) :- X="all", colleague(Z,Y), write(" ",Z," -> ",Y),nl, fail,!.

/* правило 3 */
do_answer(X) :- frontchar(X,"!",Z), colleague(Z,_),!, write(Z." имеет сослуживцев"), nl, fail.

/* правило 4 */
do_answer(X) :- frontchar(X,"< ",Z), colleague(Q,Y), write(" ",Q," -> ",Y),nl, Q=Z,!. fail.

/* правило 5 */
do_answer(X) :- colleague(X,Y), write(" ",X," -> "Y),nl, fail.
       Процедура do_answer() состоит из пяти правил. Два из них, первое и пятое, уже были рассмотрены ранее.

       Задание 6.
Загрузите с диска Ваш файл lab4.pro и дополните процедуру do_answer() недостающими правилами. Изучите их назначение, способ организации и исполнения системой Турбо-Пролог.

       Правило 1 обеспечивает прекращение повтора запросов за счет того, что его истинность при согласовании не вызывает отката к предикату repeat.

       Правило 5 реализует второе требование ни запросам к системе и выдаче всех сослуживцев конкретного служащего. Рассмотрим подробнее остальные правила.

       Правило 2 обеспечивает поиск и выдачу всех сослуживцев при условии, что в ответ на запрос о фамилии вводится слово ail (т.е. вес). Если с клавиатуры введено любое другое значение, первая подцель этого правила не согласуется и выполняется откат, который приводит к дальнейшему поиску согласующих предложений среди заголовков правил процедуры do_answer().

       Если первая подцель согласуется, то выполнение второй подцели обеспечит поиск первой пары коллег, а третья подцель выводит их на экран. Предикат fail, вызывая неудачу, обеспечивает откат ко второй подцели для поиска всех альтернативных решений, которые затем выдаются на экран.

       Разработчику программы заранее известно, что для обработки слова all никаких других правил в процедуре do_answer не предусмотрено, но это неизвестно системе, которая будет просматривать все правила процедуры и проводить их унификацию.

       В этом случае имеет смысл ограничить время и пространство поиска, закончив выполнение всей процедуры do_answer после обработки слова all. С этой целью в данное правило последним введен предикат отсечения, который приводит к прекращению процедуры do_answer, т.е. исключению из дальнейшего согласования правил 3,4 и 5.

       Правило 3 реализует третье требование к запросам, при условии, что в ответ па приглашение к вводу, фамилия вводится, начиная с восклицательного знака. Выбор начального символа абсолютно произволен. Здесь этот символ выбран, как еще одно напоминание об отсечении.

       Пусть, например, с клавиатуры введено ! Иванов. При согласовании заголовка правила 3 переменная Х унифицируется со строковой константой "!Иванов" и начинается обработка тела правила.

       Первая подцель вызывает предикат frontchar(X,"!",Z) обработки символьных строк (см. приложение 1). Если первый символ Х совпадает с '!', то переменная Z принимает значение остатка строки X, начиная со второго символа (Z = "Иванов"). Если первый символ в Х отличный от '!', то первая подцель заканчивается неуспехам и происходит откат к обработке, следующего правила процедуры.

       Вторая подцель будет успешна, если будет согласован предикат colleague(Z,_)

       при каком-либо значении Z. Использование анонимной переменной обусловлено характером запроса, в котором требуется определить только наличие коллег, а не их фамилии. Успешное согласование второй подцели вызовет переход к предикату отсечения, который установит признак запрета на откат в этом месте правила.

       После этого согласование правила продолжается в порядке слева направо, и осуществляется вывод на экран дисплея сообщения "Иванов имеет сослуживцев".

       Последняя подцель вызывает состояние неуспеха в доказательстве правила, что ведет к откату. Но так как предикат write() альтернатив не имеет, то происходит откат к предикату отсечения, которым уже установлен запрет на дальнейший откат.

       Это приводит к тому, что в отличие от предыдущих примеров, повторное согласование предиката colleague() выполняться не будет.

       На этом завершается согласование данного правила, но не только его, но и всей процедуры do_answer(). Причем завершение процедуры неудачей ведет к тому, что неудачей завершится и последняя подцель в query и, как следствие, произойдет откат к предикату repeat и повтору ввода данных.

       Задание 7.
Что будет, если из этого правила исключить предикат fail? Попробуйте это сделать. Изучите процесс выполнения программы в этом случае. Восстановите программу. В отчете приведите описание процесса выполнения программы.

       Правило 4 реализует требование на ограничение выводимого списка некоторым условием. В качестве условия выступает фамилия служащего, которым должен оканчиваться список коллег. При этом фамилия этого служащего вводится, начиная с символа '<'. Выбор этого символа произволен и никакой смысловой нагрузки, с точки зрения языка Пролог, не имеет.

       Первая подцель даст истинный результат, если первым символом Х будет '<'. Переменная Z в этом случае примет значение остатка строки X. начиная со второго символа. В иных случаях, подцель закончится неуспехом, вызывая неуспех и всего правила. Фактически эта подцели является условием входа на обработку правила.

       Следующие две подцели согласуют и выводят на экран первую пару коллег, а четвертая - обеспечивает возврат к поиску следующей пары, если фамилия первого из коллег не совпадает с введенной с клавиатуры. Как только эти фамилии совпадут, т.е. Q=Z станет истиной, выполнится отсечение, которое не позволит предикату fail обеспечить откат к поиску новой пары коллег, что вызовет окончание выполнения данного правила.

       Наличие в правиле предиката отсечения не только ограничивает область поиска в базе данных заданной фамилией, но и обеспечивает завершение всей процедуры do_answer0. Завершение процедуры приводит к возврату в query.

       Следует особо обратить внимание на то, что откат к поиску альтернативных решений подцели colleague(Q, Y) в данном правиле, в отличие от правил 2 или 5, выполняет не fail, а подцель Q=Z. Тогда встает вопрос, а нужен ли в этом правиле вообще предикат fail, а если нужен, то зачем?

       Все дело заключается в том, что процедура do_answer() выполняется не сама по себе, а вызывается как последняя цель правила query. Поэтому, кроме функций по поиску данных в базе, на нее возложена функция управления откатом к предикату repeat, т.е. организация повторений по вводу.

       Присутствие в правиле 4 предиката fail приводит к тому, что несмотря на успешно выполненный запрос к базе данных, правило заканчивается неудачей. Неудачей завершается и запрос из query к процедуре do_answer(), что вызывает откат к repeat и повторение ввода данных.

       Если в правиле 4 не будет предиката fail, то после выполнения поиска в базе правило будет успешно выполненным. Успешным будет и обращение из query к процедуре do_answer(), что ведет к тому, что и правило query станет истинным. Это вызовет его окончание, а вместе с этим и окончание ввода запросов.

       Но так как признаком окончания ввода должен быть ввод слова stop, то окончание работы программы по другому требованию явилось бы ошибкой, что и требует обязательного включения предиката fail в правило 4.

       Задание 8.
Выполните программу в пошаговом режиме для правила 4. Изучите процесс выполнения отсечения. Повторите то же самое без fail. В отчете приведите схему выполнения программы для этих случаев.

       Рассмотренные выше подходы к организации откатов и отсечении могут аналогичным способом использоваться и при формировании внешних целей в виде составных запросов.

       Задание 9.
Сформируйте внешние пели для запросов, аналогичных реализованным в процедуре do_answer() и выполните их.

5. Откат и отсечение при реализации отношений вида "один-ко-многим"

       Учет ассоциаций (связей) между объектами отношений служит средством оптимизации запросов в Прологе. Рассмотрим это на примере простого отношения
ОТЕЦ( ИМЯ , РЕБЕНОК )
       которое в программе определяется набором некоторых фактов. Между объектами данного отношения существует ассоциация "один-ко-многим". Запрос к данной базе может заключаться:
       - либо в поиске родителя конкретного ребенка (в этом случае имеет место простая связь)
       - либо в поиске всех детей конкретного родителя (в этом случае имеет место множественная связь)

       Самый примитивный способ реализации простой связи заключается в написании правила, которое должно выполнить поиск факта, а затем пройти через предикат отсечения. Для реализации сложной связи необходим поиск всех альтернативных решений в базе данных. Использование новой процедуры parent (родитель), которая учитывает введенные замечания, обеспечит интерфейс работы с БД father() .

       Причем этот интерфейс учитывает имеющуюся связь между объектами отношения БД father() и оптимизирует выполнение запроса Прологом

       Предикат bound(C) успешен в случае, если переменная С означена, а предикат free(C) успешен, если переменная С свободная.

       Следует отметить, что два правила процедуры являются взаимоисключающими.

       А если это так, то проверку во втором правиле состояния переменной С можно не выполнять, так как если она будет несвободной, то будет обработана первым правилом. Однако, если эти правила поменять местами, то этого делать нельзя.
/* программа 10 */
domains
namе,child = symbol
predicates
father(name,child)
parеnt(namе,child)
clauses
father( "иван" , "петр" ).
father( "иван" , "павел" ).
father( "петр" , "олег" ).
father( "олег" , "борис" ).
/* поиск родителя (отца) конкретного ребенка */
parent(F,C) :- bound(C), fathеr(F,C),!.
/* поиск всех детей конкретного родителя */
parent(F,C) :- free(C), fathеr(F,C).
       Задание 10.
Модифицируйте программу 6 таким образом, чтобы интерфейс по работе с БД work() учитывал ассоциации между объектами этого отношения и позволял оптимизировать выполнение запросов Прологом за счет использования нового отношения СЛУЖАЩИЙ(ИМЯ,ОТДЕЛ)

       С целью тестирования программы выполните различные варианты запросов, используя внешние цели. Результаты их выполнения вместе с текстом модифицированной программы приведите в отчете по лабораторной работе.

       Используя режим пошагового выполнения, выясните, как сказывается отсечение на режиме выполнения программы и поиске по базам данных.

       Задание 11.
Используя результаты выполнения задания 10, па основе программы формирования меню lab4menu.pro сформируйте запросную систему, которая должна выдавать ответы на вопросы: "В каком отделе работает конкретный служащий" (процесс 1) и "Кто работает в конкретном отделе" (процесс 2).

6. Ступенчатые функции и отсечение

       Часто в экономических расчетах приходится использовать ступенчатые функции для вычисления различных коэффициентов, зависящих от диапазонов изменения объемов производства, прибыли или совокупного годового дохода. Для примера рассмотрим двухступенчатую функцию, аналогичную вычислению процента подоходного налога, считая, что D - совокупный доход, а N - величина налога:

       На Прологе данную функцию выражают с помощью бинарного отношения F(N,D), которое можно определить набором фактов вида
F(D ,0) :- D< 10.
F(D, 12) :- 10=<D,D< 15.
F(D, 15) :- 15=<D.
       Три правила, входящие, в отношение F(), являются взаимоисключающими, поэтому успех возможен самое большое в одном из них. Следовательно, мы (но не Пролог) знаем, что, как только успех наступил в одном из них, нет смысла проверять иные, поскольку они все равно обречены на неудачу. Для предотвращения ненужного перебора следует воспользоваться отсечением. Предикат отсечения предотвращает возврат из тех точек программ, где он поставлен. С учетом этого новая процедура
F(D ,0) :- D< 10,!.
F(D, 12) :- D< 15,!.
F(D, 15).
дает тот же результат, что и исходная, но она значительно более эффективна при реализации в программе на Прологе.

7. Содержание отчета по лабораторной работе

       Отчет по лабораторной работе должен содержать:
  1. Результаты выполнения задания 4 данной лабораторной работы.
  2. В соответствии с заданием 5 текст отлаженной программы формирования меню, которая в ответ на выбор опции меню открывает некоторое окно, а после нажатия клавиши возвращается в основное меню, закрывая окно.
  3. Полный текст программы запросной системы по сослуживцам и результаты ее исследований в соответствии с заданиями 6,7,8.
  4. Список внешних целей, аналогичных реализованным в запросной системе, и результаты их выполнения (задание 9)
  5. Результаты выполнения задания 10.
  6. Текст отлаженной программы запросной системы по служащим и отделам, с использованием меню и ее описание.
  7. В качестве дополнительного задания - программа полной запросной системы.