У Клоксин - ПРОГРАММИРОВАНИЕ НА ЯЗЫКЕ ПРОЛОГ

Путь, представляющий цепочку найденных доказательств, при этом изменяется так, что исключаются все маркеры, соответствующие целям, расположенным между услугии отсечением включительно. Таким образом, если впоследствии произойдет возврат на точку! (отсечение), то попытка согласовать цель услугинемедленно потерпит неудачу. Система не будет рассматривать альтернативные решения для целевого утверждения книга_не_возвращена ('А. Джонс', Книга),и это совершенно разумно, так как мы интересуемся лишь тем, числится ли за читателем хотя бы одна не возвращенная в срок книга, а не тем, каковы все книги, числящиеся за ним. Утверждение 2 в предикате услугитоже рассматриваться системой не будет, так как при возврате обходится и выбор правила, в котором встречается отсечение. Такое поведение системы в рассматриваемой ситуации тоже является разумным, так как мы не хотим порождать решения, указывающие на то, что А. Джонсудоступны все услуги.

Рис. 4.4.

Рис. 4.5.

Действие отсечения в этом примере можно резюмировать следующим образом:

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

В этом примере использование отсечения привело к «сокращению» всех решений, принятых после выбора целевого утверждения услуги.Оно называется родительским целевым утверждением для отсечения, так как именно это целевое утверждение привело к использованию правила, содержащего отсечение. На наших диаграммах родительским целевым утверждением всегда является целевое утверждение, соответствующее наименьшему прямоугольнику, содержащему прямоугольник с '!'. Формальное определение эффекта, производимого отсечением, формулируется следующим образом:

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

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

foo:- а, b, с,!, d, e, f

Пролог без каких-либо ограничений может выполнять возврат среди целей a, bи с до тех пор, пока доказательство согласованности целевого утверждения сс базой данных не приведет к тому, что Пролог «перешагнет» через «забор»! и приступит к доказательству согласованности целевого утверждения d. Далее возврат может осуществляться между целевыми утверждениями d, eи f, при этом, возможно, неоднократно будет достигаться согласованность всей конъюнкции целиком. Однако если произойдет неудача при доказательстве согласованности целевого утверждения d, что вызовет «перешагивание через забор» справа налево, то никаких попыток вновь доказать согласованность целевого утверждения сделаться не будет; доказательство согласованности конъюнкции целей в целом, а следовательно, и цели fooпотерпит неудачу.

Прежде чем перейти к рассмотрению других примеров с использованием отсечения, сделаем еще одно замечание. Мы сказали, что если отсечение появляется в некотором правиле и выбирается в качестве целевого утверждения, то Пролог-система лишается возможности изменять все решения, принятые с момента вызова родительского целевого утверждения. Это значит, что выбор этого правила и всех решений, принятых после него, становится зафиксированным. Далее мы увидим, что есть возможность указывать альтернативы в рамках одного правила, используя встроенный предикат ';' (обозначающий « или»). На выбор альтернатив, сделанный с использованием этой возможности, эффект отсечения действует точно так же, т. е. при отсечении фиксируются все « или»-выборы, сделанные с момента выбора правила, содержащего отсечение.