Эта лекция посвящена способам организации управления программой при программировании на Прологе. Конечно, какую-то часть способов организации в явном или неявном виде мы уже рассмотрели в предыдущих лекциях. Здесь будет сформулировано явно то, что до сих пор использовалось в неявном виде. Мы разберем, в каких случаях применяются эти методы, как они работают и как ими пользоваться. Также мы рассмотрим некоторые новые методы, которых до сих пор не касались.
Начнем c того, что еще раз обсудим бэктрекинг, (или откат, или поиск с возвратом, или механизм поиска в глубину). Откат уже упоминался в предыдущих лекциях. Суть этого механизма такова: в том месте программы, где возможен выбор нескольких вариантов, Пролог сохраняет в специальный стек точку возврата для последующего возвращения в эту позицию. Точка возврата содержит информацию, необходимую для возобновления процедуры при откате. Выбирается один из возможных вариантов, после чего продолжается выполнение программы.
Во всех точках программы, где существуют альтернативы, в стек заносятся указатели. Если впоследствии окажется, что выбранный вариант не приводит к успеху, то осуществляется откат к последней из имеющихся в стеке точек программы, где был выбран один из альтернативных вариантов. Выбирается очередной вариант, программа продолжает свою работу. Если все варианты в точке уже были использованы, то регистрируется неудачное завершение и осуществляется переход на предыдущую точку возврата, если такая есть. При откате все связанные переменные, которые были означены после этой точки, опять освобождаются.
|
|
При объяснении сущности бэктрекинга часто приводят пример с поиском пути в лабиринте. Один из возможных способов найти выход из лабиринта — это на каждой развилке поворачивать в одну и ту же сторону, до тех пор, пока не попадешь в тупик. После попадания в тупик нужно вернуться до ближайшей развилки. На ней нужно выбрать другое направление. После этого нужно опять на всех развилках выбирать поворот в том же направлении, что и в самом начале. Продолжаем этот алгоритм до тех пор, пока не выберемся из лабиринта.
Пример. Рассмотрим работу механизма отката на примере слегка модифицированной программы, описывающей родственные отношения. Разделы описания доменов и предикатов оставим без изменения, а порядок фактов в разделе предложений изменим, для того чтобы он лучше соответствовал нашим целям. Получим следующую программу.
DOMAINS /* раздел описания доменов */
s=string /* вводим синоним для строкового типа данных */
PREDICATES /* раздел описания предикатов */
mother(s,s) /* предикат мама будет иметь два аргумента
|
|
строкового типа */
grandmother(s,s) /* то же имеет место и для предиката
бабушка */
CLAUSES /* раздел описания предложений */
mother("Даша","Маша"). /* "Даша" и "Маша" связаны
отношением мама */
mother("Наташа","Даша"). /* "Наташа" является мамой
"Даши" */
mother("Наташа","Глаша"). /* "Наташа" и "Глаша" связаны
отношением мама */
mother("Даша","Саша"). /* "Даша" является мамой "Саши" */
grandmother(X,Y):– /* X является бабушкой Y,
если найдется такой Z, что */
mother(X,Z), /* X является мамой Z, а */
mother(Z,Y). /* Z является мамой Y */
В качестве внешней цели, после запуска программы зададим вопрос об именах всех бабушек и внучек (grandmother(B,V)).
Чтобы проследить процесс работы Пролог-системы при поиске ответа на наш вопрос, можно включить трассировку, записав в начале программы директиву компилятору trace. В окне редактирования курсор указывает подцель, которая выполняется на данном шаге. В окне трассировки отображается дополнительная информация. Напомним, что переход от подцели к подцели осуществляется с помощью функциональной клавиши F10.
Для выполнения цели grandmother(B,V) должны быть удовлетворены две подцели: mother(B,Z) и mother(Z,V). Первая подцель унифицируется с первым предложением, описывающим отношение "быть мамой". При этом переменная B конкретизируется именем "Даша", а переменная Z — "Маша". В окне трассировки в этот момент результат вычисления текущей подцели (mother("Даша","Маша")), выводящийся после слова RETURN, сопровождается звездочкой (*), которая показывает, что у подцели есть альтернативные решения. Это то самое место, указатель на которое Пролог заносит в стек точек возврата для возможного последующего возвращения.
Затем делается попытка удовлетворить вторую подцель mother(Z,V), причем переменная Z означена именем "Маша". Попытка унифицировать эту подцель с одним из фактов, имеющих отношение к предикату mother, оказывается неудачной. Это происходит потому, что в нашей базе знаний нет никакой информации о детях Маши. О неуспехе говорит слово FAIL в окне трассировки. Происходит откат до места, сохраненного в стеке точек возврата. При этом переменные B и Z, означенные к моменту отката, вновь становятся свободными.
Выбирается вторая альтернатива. Переменная B при этом становится равной имени "Наташа", а переменная Z получает значение "Даша". Звездочка в окне трассировки, как и при первом проходе этой точки, показывает нам, что исчерпаны еще не все из имеющихся альтернатив, удовлетворяющих нашей подцели.
Делается попытка найти решение для второй подцели mother(Z,V) (при Z = "Даша"). Первое же предложение в процедуре, реализующей предикат mother, унифицируется с текущей подцелью, переменная V получает значение "Маша". Очередная звездочка в окне трассировки отмечает, что указатель на это место помещен в стек точек возврата, для того чтобы вернуться сюда, и что возможны другие означивания для переменной V, приводящие текущую подцель к успеху.
Получаем, что ответ на наш вопрос возможен при следующих значениях переменных: B=Наташа, V=Маша. Этот ответ отображается в окне диалога, после чего осуществляется откат к последнему месту, записанному в стек точек возврата. При этом освобождается переменная V, которая уже была означена именем "Маша". Подцель mother(Даша,V) унифицируется с заголовком последнего предложения процедуры, определяющей предикат mother. Переменная V означивается именем "Саша". В диалоговом окне выводится второй возможный ответ на заданный нами в качестве внешней цели вопрос: B=Наташа, V=Саша.
Альтернативных решений для подцели mother(Даша,V) больше нет. Соответственно, в окне трассировки отсутствует звездочка, а в стеке точек возврата нет больше указателя на то место, куда можно было возвращаться для того, чтобы выбирать новые значения для второй подцели правила, определяющего отношение grandmother.
|
|
Однако в стеке точек возврата еще остается указатель на тот участок программы, где находились означивания переменных для первой подцели в теле правила, определяющего отношение "быть бабушкой". Пролог-система осуществляет откат, попутно освобождая переменные.
Первая подцель сопоставляется с третьим фактом mother("Наташа","Глаша"). В окне трассировки видим уже знакомый символ звездочки, который свидетельствует о том, что испробованы еще не все возможные варианты для текущей подцели mother(B,Z). Делаются последовательные попытки сопоставить подцель mother("Глаша",V) с одним из фактов, имеющихся в базе знаний. Однако эти попытки заканчиваются неудачей, поскольку наша программа не содержит информации о детях Глаши. В окне трассировки отображается слово FAIL, информирующее нас об этой неудаче.
Процесс выполнения программы в очередной, последний, раз откатывается к тому месту, где можно выбрать решение для первой подцели. Подцель унифицируется с последним предложением в процедуре, описывающей знания, касающиеся мам. Переменная B конкретизируется именем "Даша", а переменная Z — "Cаша". Других вариантов для сопоставления первой подцели не остается. Стек точек возврата пуст. В окне трассировки нет индикатора, сообщающего об альтернативных решениях, к которым возможно возвращение. Пролог-система пытается сопоставить с чем-нибудь вторую подцель mother("Саша",V), однако ей не удается этого сделать. Ни один из фактов не содержит в качестве первого аргумента имя "Саша". Очередная неудача в попытке найти внуков для Даши.
Программа завершается. В диалоговом окне — два найденных в процессе работы решения:
B=Наташа, V=Маша
B= Наташа, V=Саша
2 Solutions
Теперь посмотрим, какие имеются у программиста возможности по управлению откатом.
Рассмотрим модификацию механизма поиска в глубину, которая позволяет получать дополнительные решения и называется метод отката после неудачи. Этот метод используется в ситуации, когда нужно получить не один ответ, а все возможные в данной ситуации ответы. Например, если вопрос является внутренней целью, то Турбо Пролог останавливает поиск после первого же успешного вычисления цели. При этом выявляется только первое решение.
|
|
Пример. Давайте зададим тот же вопрос, что и в предыдущем примере, но уже не как внешнюю цель, а укажем ее в разделе описания внутренней цели:
GOAL
grandmother(B,V)
Если запустить эту программу, она завершит свою работу, так ничего и не выдав в окне диалога. Дело в том, что при наличии в программе внутренней цели Турбо Пролог не отображает в диалоговом окне значений переменных, тогда как при выполнении внешней цели Турбо Пролог выводит в окне значения всех содержащихся в вопросе переменных. Это первое существенное отличие внешней и внутренней цели.
Однако мы можем сами организовать отображение результатов вычисления внутренней цели, добавив к ней в качестве подцелей вывод значений переменных B и V на экран, используя встроенный предикат write. Раздел описания внутренней цели при этом может выглядеть, например, так:
GOAL
grandmother(B,V),write("Имя бабушки — ",B), write(",
имя внучки — ",V),nl
В этом случае мы увидим на экране имена бабушки и внучки, но в окне диалога отобразится не два решения, а всего одно:
Имя бабушки — Наташа, имя внучки — Маша
Дело в том, что при наличии в программе внутренней цели Турбо Пролог находит только одно возможное означивание переменных, а не все возможные, как в случае внешней цели. Это второе отличие внешней и внутренней цели. Если нам необходимо получить все решения, нужно организовать это специально, например, с помощью метода отката после неудачи. Обычно внешние цели используются на этапе отладки новых предикатов. Если же нам нужна программа, которая может запускаться вне среды разработки, в ней обязательно должна быть внутренняя цель.
В методе отката после неудачи обычно используется всегда ложный предикат fail, о котором говорилось в прошлой лекции. Хотя, по большому счету, вместо этого предиката можно воспользоваться каким-нибудь заведомо ложным выражением. Например, 1=2 или чем-то в этом роде.
Если добавить к нашей внутренней цели предикат fail, то получим в окне диалога оба решения, которые мы могли наблюдать, когда задавали этот вопрос, используя внешнюю цель:
Имя бабушки — Наташа, имя внучки — Маша
Имя бабушки — Наташа, имя внучки — Саша
Пример. Теперь давайте напишем предикат, который будет выводить на экран с помощью стандартного предиката write имена всех дочек.
show_names:–
mother(_,Name), /* означивает переменную Name
именем дочки */
write(" ", Name), nl,
/* выводит значение переменной
Name на экран */
fail. /* вызывает откат на место, сохраненное
в стеке точек возврата */
Допишем этот предикат к нашей программе про мам и бабушек, не забыв добавить его описание в раздел PREDICATES.
В качестве внутренней цели укажем вывод сообщения "Имена дочек:" (с помощью встроенного предиката write), переведем курсор на следующую строку стандартным предикатом nl. В качестве третьей подцели запишем предикат show_names, выводящий имена всех дочек.
GOAL
write("Имена дочек:"),nl,
show_names.
Как будет работать эта программа? Сначала будет выведена строка "Имена дочек:", произойдет переход на следующую строку. После этого выполняется подцель show_names.
Во время попытки вычисления этой подцели механизм унификации означивает переменную именем дочери, указанном в качестве второго аргумента в первом предложении процедуры, описывающей предикат mother. Переменная Name получает значение "Маша". При этом в окне трассировки можно видеть звездочку, которая говорит о том, что в стек точек возврата помещен указатель на место, в которое возможен откат для получения других решений подцели mother(_,Name). Имя "Маша" выводится на экран встроенным предикатом write.
После этого предикат fail вызывает неуспешное завершение правила, затем осуществляется откат в точку, помещенную в стек последней. Процесс повторяется до тех пор, пока не будут исчерпаны все варианты достижения подцели mother(_,Name). В окне диалога будут выведены имена всех дочек в том порядке, в котором они упоминались в нашей программе:
Имена дочек:
Маша
Даша
Глаша
Саша
Пример. Давайте изменим наш предикат, чтобы он выводил имена не всех дочек, а только дочек одной мамы. Для этого нужно добавить предикату аргумент, в качестве которого будет указываться имя мамы. Кроме того, в первой подцели требуется заменить анонимную переменную некоторой обычной переменной, которую затем нужно сравнить с именем мамы, указанной в качестве аргумента предиката.
show_names2(Mother):–
mother(M,Name), /* означивает переменную Name
именем дочки мамы Mother */
M=Mother, /* проверяет совпадение имен мам M
и Mother */
write(" ", Name), nl, /* выводит значение
переменной Name
на экран */
fail. /* вызывает откат к месту, сохраненному
в стеке точек возврата */
Вместо первых двух подцелей mother(M,Name), M=Mother можно записать альтернативный вариант: mother(Mother,Name). Результат будет тем же, но процесс вычисления будет отличаться.
Выведем с помощью модифицированного предиката имена дочек Даши. Для этого изменим внутреннюю цель следующим образом:
GOAL
write("Имена дочек Даши:"),nl,
show_names2("Даша").
Отличие в работе этого предиката от предиката, который выводил имена всех дочек, заключаются в следующем. После того, как переменная M будет означена именем очередной мамы, будет проверяться совпадение ее значения с именем "Даша". В случае совпадения будет выведено имя дочери Даши и осуществится откат. Если же имя окажется отличным от "Даша", откат произойдет немедленно. Выполнение программы в этом случае не доберется до вывода имени дочери на экран. Предикат fail не потребуется, так как подцель M=Mother будет неуспешной сама по себе. Тем не менее, наличие стандартного предиката fail в качестве последней подцели правила необходимо для того, чтобы вызвать откат, если подцель M=Mother окажется успешной.
По завершении работы этой программы можно будет увидеть в диалоговом окне результаты:
Имена дочек Даши:
Маша
Саша
Рассмотрим теперь так называемый метод отсечения и отката. В основе этого метода лежит использование комбинации предикатов fail (для имитации неудачи и искусственной организации отката) и "!" (отсечение или cut), который позволяет прервать этот процесс в случае выполнения какого-то условия. Об отсечении мы уже говорили в третьей лекции. Разберем этот метод на примере.
Пример. Модифицируем еще раз предикат, выводящий имена всех дочек, так чтобы он выводил их не все, а только до определенного имени. У предиката будет один входной аргумент, где указывается имя дочери, на котором должен оборваться вывод на экран имен дочек. В тело правила нужно добавить подцель, в которой текущее имя дочки будет сравниваться с именем дочки, указанным в качестве аргумента предиката. После этой подцели
show_names3(Daughter):–
mother(_,Name), /* означивает переменную Name именем
дочки */
write(" ", Name), nl, /* выводит значение переменной
Name */
Name=Daughter, /* проверяет совпадение имен дочек Name
и Daughter. В случае несовпадения
вызывает откат на место, указатель
на которое хранится в стеке точек
возврата. В случае совпадения, за счет
наличия отсечения, завершает поиск
и вывод имен дочек */
write("Искомый человек найден!"),!.
Этот предикат будет конкретизировать переменную Name именем чьей-то дочери, выводить на экран значение этой переменной. После этого будет сравниваться значение переменной Name со значением переменной Daughter. В случае несовпадения эта подцель терпит неудачу, вызывая откат на первую подцель правила. В случае совпадения имен подцель успешна, управление получает предикат отсечение. Он всегда истинен и запрещает откат для подцелей, расположенных левее. На этом работа предиката show_names3 завершается. То есть откаты в этом правиле будут продолжаться до тех пор, пока текущее значение переменной Name не совпадет со значением переменной Daughter.
Еще один способ организации повторяющихся действий — так называемый метод повтора, определяемый пользователем. Он также использует откат, однако, в отличие от метода отката после неудачи, в котором откат осуществляется только после специально созданной неудачи, в этом методе откат возможен всегда за счет использования специального предиката, обычно кодируемого в виде следующего предложения:
repeat.
repeat:–
repeat.
Этот предикат всегда успешен. После выполнения первого предложения процедуры в стек точек возврата запоминается указатель, поскольку имеется еще один альтернативный вариант для него. В теле второго предложения опять вызывается предикат repeat.
Предикат repeat не является встроенным предикатом, а имя "repeat" — зарезервированным словом. Соответственно, вместо этого имени можно использовать какое-нибудь другое.
С помощью этого предиката можно организовывать циклы, подобные циклам в императивных языках программирования. Нужно не забыть добавить в правило, организующее цикл, кроме предиката repeat, условие завершения цикла и отсечение, чтобы не получилось зацикливания.
Пример. Создадим предикат, который будет дублировать символ, введенный пользователем с клавиатуры. Завершиться этот процесс должен, когда пользователь введет некий ключевой символ, о котором мы заранее договоримся, что его появление означает окончание процесса дублирования символов. Давайте, для определенности, возьмем в качестве такого символа точку (.).
double_char:–
repeat,
readchar(C), /* читаем символ с клавиатуры
в переменную C */
write(C,C), nl,/* выводим на экран значение
переменной C */
C=’.’,!, /* сравниваем значение переменной C
с символом ‘.’*/
nl,write("Была введена точка. Закончили.").
Первой подцелью нашего правила записан вызов предиката repeat. Он обеспечивает нам повторное выполнение следующих за ним подцелей. Можно эксперимента ради закомментировать предикат repeat, дабы убедиться, что в этом случае цикла не получится. Последующие подцели выполнятся всего один раз.
Далее, используя стандартный предикат readchar, осуществляем чтение символа с клавиатуры в переменную C. Посредством встроенного предиката write выводим два экземпляра введенного пользователем символа на экран; стандартным предикатом nl переводим курсор на следующую строку. Затем значение переменной C сравнивается с символом точка (‘.’). Это условие, которое, с одной стороны, обеспечивает откат на первую подцель (предикат repeat), а с другой обеспечивает выход из цикла. Если поступивший с клавиатуры символ отличен от точки, подцель C=’.’ терпит неуспех. Пролог-система осуществляет откат на последнее место, указатель на которое записан в стеке точек возврата. Из подцелей, расположенных левее, альтернативы имелись только у первой подцели (предиката repeat). Все повторяется еще раз. Пользователь вводит символ, он дважды отображается на экране, сравнивается с точкой. Процесс повторяется до тех пор, пока введенный символ не окажется точкой. В этом случае подцель C=’.’ окажется успешной, управление перейдет на подцели, расположенные правее. Предикат nl сдвинет курсор на начало следующей строки, стандартный предикат write выводит на экран сообщение: "Была введена точка. Закончили." — и процесс дублирования символов на этом завершается.
Напишем внутреннюю цель, которая проинформирует пользователя о правилах работы нашей программы, после чего запустит предикат double_char.
GOAL
write("Вводите символы, которые нужно повторить (точка —
завершение)"),nl,
double_char.