Назад | Содержание| Вперёд 5. 4. Трудности с отсечением иотрицанием ...

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

5. 4. Трудности с отсечением иотрицанием

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

(1) При помощи отсечениячасто можно повысить эффективность программы.Идея состоит в том, чтобы прямо сказатьпролог-системе: не пробуй остальныеальтернативы, так как они все равно обречены нанеудачу.

(2) Применяя отсечение,можно описать взаимоисключающие правила,поэтому есть возможность запрограммироватьутверждение:

если условие Р, торешение Q,

иначе решение R

Выразительность языка при этом повышается.

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

р :- а, b.

р :- с.

Декларативный смысл программы: р истинно тогдаи только тогда, когда истинны одновременно и а, и bили истинно с. Это можно записать в виде такойлогической формулы:

р <===> (а & b) Uс

Можно поменять порядок этих двух предложений,но декларативный смысл останется прежним. Введемтеперь отсечение

p :- а, !, b.

р :- с.

Декларативный смысл станет теперь таким:

р <===> (а & b) U( ~а & с)

Если предложения поменять местами

р :- с.

р :- а, !, b.

декларативный смысл станет таким:

р <===> с U ( а& b)

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

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

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

Отсечение часто используется в комбинации соспециальной целью fail. В частности, мыопределили отрицание какой-либо цели (not),как ее неуспех. Определенное таким образомотрицание представляет собой просто особый(более ограниченный) вид отсечения. Изсоображений ясности программ мы предпочтемпользоваться not вместо комбинации отсечение- неуспех (всюду, где возможно), посколькуотрицание является понятием более высокогоуровня, чем отсечение - неуспех.

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

?- not человек(мэри).

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

человек( мэри)

то мы этим обычно вовсе не хотим сказать, чтоМэри не человек.

Дальнейшее изучение опасных аспектовиспользования not проведем на такомпримере:

r( а).

g( b).

р( X) :- not r( X).

Если спросить теперь

?- g( X), р( Х).

система ответит

Х = b

Если же задать тот же вопрос, но в такой форме

?- р( X), g( X).

система ответит

nо (нет)

Читателю предлагается проследить работупрограммы по шагам, чтобы понять, почемуполучились разные ответы. Основная разница междувопросами состоит в том, что переменная Х кмоменту вычисления р( X) в первом случаебыла уже конкретизирована, в то время как вовтором случае этого еще не произошло.

Мы детально обсудили аспекты примененияотсечения, которое неявно присутствует в not.При этом нами руководило желание предупредитьпользователей о соблюдении необходимойосторожности, а вовсе не желание убедить ихсовсем не пользоваться этим оператором.Отсечение полезно, а часто и необходимо. А чтокасается трудностей Пролога, порождаемыхотсечением, то подобные неудобства частовозникают и при программировании на другихязыках.

Резюме

Отсечение подавляет перебор. Его применяют как для повышения эффективности программ, так и для повышения выразительности языка.

Эффективность повышается путем прямого указания (при помощи отсечения) пролог - системе не проверять альтернативы, про которые нам заранее известно, что они должны потерпеть неудачу.

Отсечение дает возможность сформулировать взаимно исключающие утверждения при помощи правил вида:

если Условие то Утверждение1 иначе Утверждение2

Отсечение дает возможность ввести отрицание как неуспех: not( Цель) определяется через неуспех цели Цель.

Иногда бывают полезными две особые цели true и fail. true - всегда успешна и fail - всегда терпит неудачу.

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

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

Литература

Различать "зеленые и "красные"отсечения предложил ван Эмден (1982).

van Emden M. (1982). Red and green cuts. Logic Programming Newsletter: 2.

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

Оглавление