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