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