Управление выполнением программы на Прологе
Эта лекция посвящена способам организации управления программой при программировании на Прологе. Конечно, какую-то часть способов организации в явном или неявном виде мы уже рассмотрели в предыдущих лекциях. Здесь будет сформулировано явно то, что до сих пор использовалось в неявном виде. Мы разберем, в каких случаях применяются эти методы, как они работают и как ими пользоваться. Также мы рассмотрим некоторые новые методы, которых до сих пор не касались.
Начнем 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.
