Книга: Программирование на языке Пролог для искусственного интеллекта
5.4. Трудности с отсечением и отрицанием
5.4. Трудности с отсечением и отрицанием
Используя отсечение, мы кое-что выиграли, но не совсем даром. Преимущества и недостатки применения отсечения были показаны на примерах из предыдущих разделов. Давайте подытожим сначала преимущества:
(1) При помощи отсечения часто можно повысить эффективность программы. Идея состоит в том, чтобы прямо сказать пролог-системе: не пробуй остальные альтернативы, так как они все равно обречены на неудачу.
(2) Применяя отсечение, можно описать взаимоисключающие правила, поэтому есть возможность запрограммировать утверждение:
если условие P, то решение Q,
иначе решение R
Выразительность языка при этом повышается.
Ограничения на использование отсечения проистекают из того, что есть опасность потерять такое важное для нас соответствие между декларативным и процедурным смыслами программы. Если в программе нет отсечений, то мы можем менять местами порядок предложений и целей, что повлияет только на ее эффективность, но не на декларативный смысл. Если же отсечения в ней присутствуют, то изменение порядка предложений может повлиять на ее декларативный смысл. Это значит, что программа с измененным порядком, возможно, будет давать результаты, отличные от результатов исходной программы. Вот пример, демонстрирующий этот факт:
p :- а, b.
p :- с.
Декларативный смысл программы: p истинно тогда и только тогда, когда истинны одновременно и а, и b или истинно с. Это можно записать в виде такой логической формулы:
p <===> (а & b) U с
Можно поменять порядок этих двух предложений, но декларативный смысл останется прежним. Введем теперь отсечение
p :- а, !, b.
p :- с.
Декларативный смысл станет теперь таким:
p <===> (а & b) U ( ~а & с)
Если предложения поменять местами
p :- с.
p :- а, !, b.
декларативный смысл станет таким:
p <===> с U ( а & b)
Важным моментом здесь является то, что при использовании отсечения требуется уделять больше внимания процедурным аспектам. К несчастью, эта дополнительная трудность повышает вероятность ошибок программирования.
В наших примерах из предыдущего раздела мы видели, что удаление отсечений из программы может привести к изменению ее декларативного смысла. Но были также в такие случаи, когда отсечение на него не влияло. Использование отсечений последнего типа требует меньшей осторожности, и поэтому такие отсечения иногда называют "зелеными отсечениями". С точки зрения наглядности программы такие отсечения "невинны" и их использование вполне приемлемо. При чтении программы их можно просто игнорировать.
Напротив, отсечения, влияющие на декларативный смысл, называются "красными". Красные отсечения — это такие отсечения, которые делают программу трудной для понимания, и их нужно применять с особой осторожностью.
Отсечение часто используется в комбинации со специальной целью fail
. В частности, мы определили отрицание какой-либо цели (not
), как ее неуспех. Определенное таким образом отрицание представляет собой просто особый (более ограниченный) вид отсечения. Из соображений ясности программ мы предпочтем пользоваться not
вместо комбинации отсечение — неуспех (всюду, где возможно), поскольку отрицание является понятием более высокого уровня, чем отсечение — неуспех.
Следует заметить, что использование оператора not
также может приводить к неприятностям, и его тоже следует применять с осторожностью. Трудность заключается в том, что тот оператор not
, который был нами определен, не в точности соответствует отрицанию в математике. Если спросить
?- not человек( мэри).
система, возможно, ответит "да". Не следует понимать этот ответ как "мэри не человек". Что в действительности пролог-система хочет сказать своим "да", так это то, что программе не хватает информации для доказательства утверждения "Мэри — человек". Это происходит потому, что при обработке цели not
система не пытается доказать истинность этой цели впрямую. Вместо этого она пытается доказать противоположное утверждение, и если такое противоположное утверждение доказать не удается, система считает, что цель not
— успешна. Такое рассуждение основано на так называемом предположении о замкнутости мира. В соответствии с этим постулатом мир замкнут в том смысле, что все в нем существующее либо указано в программе, либо может быть из нее выведено. И наоборот — если что-либо не содержится в программе (или не может быть из нее выведено), то оно не истинно и, следовательно, истинно его отрицание. Это обстоятельство требует особого внимания, поскольку мы обычно не считаем мир замкнутым: если в программе явно не сказано, что
человек( мэри)
то мы этим обычно вовсе не хотим сказать, что Мэри не человек.
Дальнейшее изучение опасных аспектов использования not
проведем на таком примере:
r( а).
g( b).
p( X) :- not r( X).
Если спросить теперь
?- g( X), p( X).
система ответит
X = b
Если же задать тот же вопрос, но в такой форме
?- p( X), g( X).
система ответит
nо
(нет)
Читателю предлагается проследить работу программы по шагам, чтобы понять, почему получились разные ответы. Основная разница между вопросами состоит в том, что переменная X к моменту вычисления p( X)
в первом случае была уже конкретизирована, в то время как во втором случае этого еще не произошло.
Мы детально обсудили аспекты применения отсечения, которое неявно присутствует в not
. При этом нами руководило желание предупредить пользователей о соблюдении необходимой осторожности, а вовсе не желание убедить их совсем не пользоваться этим оператором. Отсечение полезно, а часто и необходимо. А что касается трудностей Пролога, порождаемых отсечением, то подобные неудобства часто возникают и при программировании на других языках.
- 14.5.7. Цели с отрицанием
- Стратегические требования против подтверждающих фактов
- Социальный класс
- Пример из практики: процесс замыкания обратной связи с корпоративными клиентами в компании BearingPoint
- 2.3. Использование Crystal Reports для создания отчетов
- 2.11. Мероприятия прямого взаимодействия с покупателем
- Лекция 12. Регистрация в Яндекс.Директе
- A7.3.4. Постфиксные операторы инкремента и декремента
- Родственные схемы
- Глава 5 Управление перебором
- Отсечение
- ГЛАВА 4. ВОЗВРАТ И ОТСЕЧЕНИЕ