Опасность возникновения бесконечных циклов

Рассмотрим следующее предложение:

Р:- Р-

Часть I. Язык Prolog

В этом предложении содержится утверждение о том, что "р является истинным, если р является истинным". Это утверждение с декларативной точки зрения явля­ется полностью правильным, но с процедурной точки зрения — совершенно беспо­лезным. В действительности подобное предложение может привести к возникнове­нию проблемы в системе Prolog. Рассмотрим следующий вопрос: ?- р.

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

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

В программе решения задачи с обезьяной и бананом предложения, касающиеся отношения move, были упорядочены следующим образом: grasp, climb, push, walk (возможно, для полноты следовало бы добавить предложение unclimb — слезть). В этих предложениях утверждается, что обезьяна имеет возможность схватить банан, залезть на ящик и т.д. Согласно процедурной семантике Prolog, порядок предложе­ний указывает на то, что обезьяна предпочитает схватить банан, а не лезть на ящик, не двигать его и т.д. Такой порядок предпочтений фактически помогает обезьяне ре­шить проблему. Но что могло бы произойти, если бы этот порядок был иным? Пред­положим, что предложение "walk" стоит на первом месте. На этот раз выполнение первоначальной цели предыдущего раздела: ?- cangetl state ( atdoor, onfloor, atwindow, hasnot)) .

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

1) cangetl state atdoor, onfloor, atwindow, hasnot) )

Применяется второе предложение canget( 'can2'), что приводит к получению приведенного ниже результата.

2) move; state ( atdoor, onfloor, atwindow, hasnot), M', S2') ,

cangetl S2') В результате выполнения действия walk (atdoor, P2 ') будет получен следую­щий результат:

3) cangetl state! Р2', onfloor, atwindow, hasnot) )

После повторного применения предложения - an 2 список целей принимает вид

4) novel state! Р2 ' , onfloor, atwindow, hasnot), M" , S2 " ),

cangetl £2'') Теперь ситуация изменяется. В настоящее время первым предложением, голова которого согласуется с первой целью, приведенной выше, становится walk (а не climb, как перед этим). Соответствующая конкретизация такова: S2" - state! P2", onfloor, atwindow, hasnot)

Поэтому список целей принимает вид

5) cangetl state' Р2 ' ', onfloor, atwindow, hasnot)) Применяя предложение сап2, получим следующее:

6) movel state ( Р2", onfloor, atwindow, hasnot), H" ' , S2"'),

canget( S2'''} И снова в первую очередь предпринимается попытка применить предложение walk, что приводит к получению следующего результата:

7) cangetl state ( P2"\ onfloor, atwindow, hasnot))

Глава 2. Синтаксис и значение программ Prolog

Теперь сравним цели 3), 5) и 7). Они являются одинаковыми, за исключением од­ной переменной; эта переменная последовательно принимает вид Р',Р' ' иР'¹'. Как известно, успех достижения цели не зависит от конкретных имен переменных в це­ли. Это означает, что, начиная со списка целей 3), трассировка выполнения не обна­руживает никакого прогресса. Фактически можно видеть, что просто повторно при­меняются два предложения, сап2 и walk. Обезьяна ходит по комнате, даже не пыта­ясь использовать ящик. Поскольку отсутствует какой-либо прогресс, эти действия (теоретически) могут продолжаться до бесконечности; система Prolog не получает информации о том, что нет смысла продолжать в том же духе.

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

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