Механизм возврата

Механизм возврата и процедурная семантика

При согласовании целевого утверждения в Прологе используется метод, известный под названием механизма возврата. В этой главе мы показываем, в каких случаях применяется механизм возврата, как он работает и как им пользоваться. Описывается декларативная и процедурная семантика процедур Пролога. Завершается глава об­суждением вопросов эффективности.

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

В качестве примера рассмотрим утверждения:

меньше(X.Y):-

XY, write(X),

write ('меньше, чем'),write(Y).

меньше(Х.У):-

XY, write(Y),

write ('меньше, 4CM'),write(X).

Целевое утверждение

?- меньше (5, 2).

сопоставляется с головой первого утверждения при Х=5 и У=2. Одна­ко не удается согласовать первый член конъюнкции в теле утвержде­ния X<Y. Значит, Пролог нс может использовать первое утвержде­ние для согласования целевого утверждения меньше(5, 2). Тогда Пролог переходит к следующему утверждению, голова которого со­поставима с целевым утверждением. В нашем случае это второе утверждение. При значениях переменных Х=5 и Y=2 тело утверждения согласуется. Целевое утверждение меньше(5,2) доказано, и Пролог выдает сообщение «2 меньше, чем 5». Запрос

?-меньше (2, 2).

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

Такой процесс согласования целевого утверждения путем прямого продвижения по программе мы называем прямой трассировкой (forward tracking). Даже если целевое утверждение согласовано, с помощью прямой трассировки мы можем попытаться получить другие варианты его доказательства, т.е. вновь согласовать целевое утверждение.

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

Пример: задача поиска пути в лабиринте

В качестве примера использования механизма возврата напишем процедуру для поиска пути в лабиринте. Лабиринт представлен фак­тами вида:

стена(I, J) для позиции в I-м ряду и J-й колонке, где есть стена

отсутств_стена(I, J) для позиции в I-м ряду и J-й колонке, где нет стены

выход (I, J) для позиции в 1-м ряду и J-й колонке, являющейся выходом

Рассмотрим небольшой лабиринт:

Выход

Последний ряд лабиринта описывается фактами:

стена(4,1).

стена(4,3).

стена(4,4).

отсутств_стена(4,2).

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

Граничное условие:

Если исходная позиция является выходом, то путь найден.

Рекурсивные условия:

Ищем путь из исходной позиции в северном направлении. Если пути нет, идем на юг. Если пути нет, идем на запад. Если нельзя, идем на восток. Если соседняя позиция на севере (юге, западе, восто­ке) является стеной, то нет смысла искать путь из начальной пози­ции к выходу. Чтобы не ходить кругами, будем вести список пози­ций, в которых мы побывали.

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

/* Терм a(I, J) представляет позицию в

/* I-м ряду и J-й колонке.

/* Нашли путь?

путь(а(I, J),[а(I, J)], Были):- выход(I, J).

/* Пытаемся идти на север

путь(а(I, J),[а(I, J) | Р], Были):-

К is I-1,

можем_идти(a (K, J), Были),

путь(а(I, J),Р, [a(K, J) | Были]).

/* Пытаемся идти на юг

путь(а(I, J),[а(I, J) | Р], Были):-

К is I+1,

можем_идти(a (K, J), Были),

путь(а(I, J),Р, [a(K, J) | Были]).

/* Пытаемся идти на запад

путь(а (I, J), [a (I, J) | P], Были):-

L is J-1,

можем_идти(а(I, L), Были),

путь(а(I, L), Р, [а(I, L)| Были]).

/* Пытаемся идти на восток

путь(а (I, J), [a (I, J) | P], Были):-

L is J+1,

можем_идти(а(I, L), Были),

путь(а(I, L), Р, [а(I, L)| Были]).

/* в позицию a(I, J) можно попасть при

/* условии, что там нет стены и мы

/* не побывали в ней прежде

можем_идти(а(I, J)), Были):-

отсутств_стена(I, J),

not (принадлежит (a (I, J), Были)).

Для того чтобы понять, каким образом процедура ищет путь к выходу, рассмотрим процесс согласования запроса с описанием лаби­ринта, описанного выше:

?-путь(а(4,2), Р, [а(4.2)]).

Выходом из лабиринта является позиция выход (3,1).

Выбор первого утверждения не приводит к согласованию целево­го утверждения, поскольку а (4,2) - не выход. Во втором утверждении делается попытка найти путь в северном направлении, т.е. согласовать целевое утверждение

путь(а(3, 2), Р2, [а(3, 2), а(4, 2)]).

Целевое утверждение не удается согласовать с первым утвержде­нием

путь(а(3, 2), Р2, [а(3, 2), а(4, 2)])

так как а (3,2) не является выходом. Во втором утверждении пред­принимается попытка найти путь, двигаясь на север, т.е. согласовать целевое утверждение

путь(а(2,2), РЗ, [а(2, 2), а(3, 2), а(4, 2)]).

Ни одно из утверждений не может согласовать

путь(а(2, 2), РЗ, [а(2, 2), а(3, 2), а(4, 2)]).

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

Неудача в согласовании

путь(а(2, 2), РЗ, [а(2, 2), а(3, 2), а(4, 2)])

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

путь(а(3, 2), Р2, [а(3, 2), а(4, 2)]).

Решение пересматривается и выбирается третье утверждение.

В третьем утверждении осуществляется попытка найти путь, двигаясь на юг, но она оказывается неудачной, поскольку мы уже по­бывали в позиции а (4, 2). Тогда, чтобы согласовать

путь(а(3, 2), Р2, [а(3, 2), а(4, 2)]),

выбирается четвертое утверждение. Мы успешно находим путь, дви­гаясь в западном направлении к позиции а(3,1), которая и является выходом. Рекурсия сворачивается, и в результате полу­чается путь

Р=[а(4, 2),а(3, 2), а(3,1)]

другие решения(да/нет)? да

Других решений нет

Альтернативный путь

[a(4,2), a(3,2), a(2,2), a(3,2), a(3,1)]

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

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