Назад | Содержание| Вперёд 2. 6. Порядок предложений и целей empty-...

Назад | Содержание| Вперёд

2. 6. Порядок предложений и целей

2. 6. 1. Опасность бесконечного цикла

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

р :- р.

В нем говорится: "р истинно, если ристинно". С точки зрения декларативного смыслаэто совершенно корректно, однако в процедурномсмысле оно бесполезно. Более того, дляпролог-системы такое предложение может породитьсерьезную проблему. Рассмотрим вопрос:

?- р.

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

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

В программе об обезьяне и банане предложения,касающиеся отношения ход, былиупорядочены следующим образом: схватить,залезть, подвинуть, перейти (возможно, дляполноты следует добавить еще "слезть"). Вэтих предложениях говорится, что можно схватить,можно залезть и т.д. В соответствии с процедурнойсемантикой Пролога порядок предложенийуказывает на то, что обезьяна предпочитаетсхватывание залезанию, залезание - передвиганиюи т.д. Такой порядок предпочтений на самом делепомогает обезьяне решить задачу. Но что моглослучиться. если бы этот порядок был другим?Предположим, что предложение с "перейти"оказалось бы первым. Процесс вычисления нашейисходной цели из предыдущего раздела

?-можетзавладеть( состояние( удвери, наполу, уокна,неимеет) ).

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

(1) можетзавладеть( состояние(удвери, наполу, уокна, неимеет) ).

Применение второго предложения из можетзавладеть("может2") породило бы

(2) ход( состояние( удвери, наполу,уокна, неимеет), М', S2'),

можетзавладеть(S2')

С помощью хода перейти( уокна, Р2')получилось бы

(3) можетзавладеть( состояние( Р2',наполу, уокна, неимеет) )

Повторное использование предложения"может2" превратило бы список целей в

(4) ход( состояние(Р2', наполу,уокна, неимеет), М'', S2''),

можетзавладеть(S2")

С этого момента начались бы отличия. Первымпредложением, голова которого сопоставима спервой целью из этого списка, было бы теперь"перейти" (а не "залезть", как раньше).Конкретизация стала бы следующей:

S2" =состояние( Р2", наполу, уокна, неимеет).

Поэтому список целей стал бы таким:

(5) можетзавладеть( состояние( Р2'',наполу, уокна, неимеет) )

Применение предложения "может2" дало бы

(6) ход( cocтояниe( P2", наполу, yoкнa,неимeeт), M" ', S2'' '),

можетзавладеть(S2" ')

Снова первый было бы попробовано "перейти"и получилось бы

(7) можетзавладеть( состояние(Р2" ', наполу, уокна, неимеет) )

Сравним теперь цели (3), (5) и (7). Они похожи и отличаются лишь одной переменной,которая по очереди имела имена Р', Р'' и P" '. Как мы знаем, успешность цели независит от конкретных имен переменных в ней. Этоозначает, что, начиная со списка целей (3), процессвычислений никуда не продвинулся. Фактически мызамечаем, что по очереди многократноиспользуются одни и те же два предложения:"может2" и "перейти". Обезьянаперемещается, даже не пытаясь воспользоватьсяящиком. Поскольку продвижения нет, такаяситуация продолжалась бы (теоретически)бесконечно: пролог-система не сумела бы осознать,что работать в этой направлении нет смысла.

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

Теперь уместно спросить: "Не можем ли мывнести какое-либо более существенное изменение внашу программу, так чтобы полностью исключитьопасность зацикливания? Или же нам всегдапридется рассчитывать на удачный порядокпредложений и целей?" Как оказывается,программы, в особенности большие, были бычересчур ненадежными, если бы можно былорассчитывать лишь на некоторый удачный порядок.Существует несколько других методов,позволяющих избежать зацикливания и являющихсяболее общими и надежными, чем сам по себе методупорядочивания. Такие методы будутсистематически использоваться дальше в книге, вособенности в тех главах, в которых пойдет речь онахождении путей (в графах), о решенияинтеллектуальных задач и о переборе.

2. 6. 2. Варианты программы, полученыепутем переупорядочивания предложений и целей

Уже в примерах программ гл. 1 существоваласкрытая опасность зацикливания. Определениеотношения предок в этой главе былотаким:

предок( X, Z) :-

родитель(X, Z).

предок( X, Z) :-

родитель(X, Y),

предок(Y, Z).

Проанализируем некоторые варианты этойпрограммы. Ясно, что все варианты будут иметьодинаковую декларативную семантику, но разныепроцедурные семантики.

В соответствии с декларативной семантикойПролога мы можем, не меняя декларативного смысла,изменить

(1) порядок предложений впрограмме и

(2) порядок целей в телахпредложений.

Процедура предок состоит из двухпредложений, и одно из них содержит в своем теледве цели. Возможны, поэтому, четыре вариантаданной программы, все с одинаковым декларативнымсмыслом. Эти четыре варианта можно получить, если

(1) поменять местами обапредложения и

(2) поменять местами цели вкаждом из этих двух последовательностейпредложений.

Соответствующие процедуры, названные пред1,пред2, пред3 и пред4,показаны на рис. 2.16.

Есть существенная разница в поведении этихчетырех декларативно эквивалентных процедур.Чтобы это продемонстрировать, будем считать,отношение родитель определенным так,как показано на рис. 1.1 гл. 1. и посмотрим, чтопроизойдет, если мы спросим, является ли Томпредком Пат, используя все четыре вариантаотношения предок:

?- пред1(том, пат).

да

?- пред2( том, пат).

да

?- пред3( том, пат).

да

?- пред4( том, пат).

% Четыре версии программы предок

% Исходная версия

пред1( X, Z) :-

родитель( X, Z).

пред1( X, Z) :-

родитель( X, Y),

пред1( Y, Z).

% Вариант а: изменение порядкапредложений в исходной версии

пред2( X, Z) :-

родитель( X, Y),

пред2( Y, Z).

пред2( X, Z) :-

родитель( X, Z).

% Вариант b: изменение порядкацелей во втором предложении

% исходной версии

пред3( X, Z) :-

родитель( X, Z).

пред3( X, Z) :-

пред3( X, Y),

родитель( Y, Z).

% Вариант с: изменение порядкапредложений и целей в исходной

% версии

пред4( X, Z) :-

пред4( X, Y),

родитель( Y, Z).

пред4( X, Z):-

родитель( X, Z).

Рис. 2. 16. Четыре версиипрограммы предок.

В последнем случае пролог-система не сможетнайти ответа. И выведет на терминал сообщение:"Не хватает памяти".

На рис. 1.11 гл. 1 были показаны все шагивычислений по пред1 (в главе 1 онаназывалась предок), предпринятые дляответа на этот вопрос. На рис 2.17 показанысоответствующие вычисления по пред2, пред3и пред4. На рис. 2.17 (с) ясно видно, чторабота пред4 - бесперспективна, а рис.2.17(а) показывает, что пред2 довольнонеэффективна по сравнению с пред1: пред2производит значительно больший перебор и делаетбольше возвратов по фамильному дереву.

Такое сравнение должно напомнить нам об общемпрактическом правиле при решении задач: обычнобывает полезным прежде всего попробовать самоепростое соображение. В нашем случае все версииотношения предок основаны на двухсоображениях:

более простое - нужно проверить, не удовлетворяют ли два аргумента отношения предок отношению родитель;

более сложное - найти кого-либо "между" этими двумя людьми (кого-либо, кто связан с ними отношениями родитель и предок).

Из всех четырех вариантов отношения предок,пред1 использует наиболее простоесоображение в первую очередь. Впротивоположность этому пред4 всегдасначала пробует использовать самое сложное. Пред2и пред3 находятся между этими двумякрайностями. Даже без детального изученияпроцессов вычислений ясно, что пред1следует предпочесть просто на основании правила"самое простое пробуй в первую очередь".

Наши четыре варианта процедуры предокможно далее сравнить, рассмотрев вопрос: "Накакие типы вопросов может отвечать тот или инойконкретный вариант и на какие не может?"Оказывается, пред1 и пред2 обаспособны найти ответ на любой вид вопросаотносительно предков; пред4 никогда ненаходит ответа, а пред3 иногда можетнайти, иногда нет. Вот пример вопроса, на который пред4ответить не может:

?- пред3(лиз, джим).

Такой вопрос тоже вводит систему в бесконечнуюрекурсию. Следовательно и пред3 нельзяпризнать верным с точки зрения процедурногосмысла.

Рис. 2. 17. Поведение трехвариантов формулировки отношения

предок при ответе на вопрос,является ли Том предком Пат?

2. 6. 3. Сочетание декларативного ипроцедурного подходов

В предыдущем разделе было показано, что порядокцелей и предложений имеет существенное значение.Более того, существуют программы, которые верны вдекларативном смысле, но на практике не работают.Такое противоречие между декларативным ипроцедурным смыслами может вызватьнедовольство. Кто-нибудь спросит: "А почемувообще не забыть о декларативном смысле?"Такое пожелание становится особенно сильным,когда рассматриваются предложения типа:

предок( X, Z) :-предок( X, Z).

Это предложение верно в декларативном смысле,но совершенно бесполезно в качестве рабочейпрограммы.

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

Назад | Содержание| Вперёд

Оглавление