Программирование на языке пролог (ЛП)

Мы можем представить ситуацию, возникшую непосредственно перед выполнением отсечения, в виде диаграммы, приведенной на рис. 4.4. Когда в программе встречается отсечение, то оно «отсекает» путь, представляющий цепочку выполненных доказательств таким образом, что следующая цель соединяется непосредственно с исходной (см. рис. 4.5). Результат действия отсечения в правиле для предиката услуги(утверждение 1) заключается в том, что все цели, выбранные с момента, когда было выбрано это правило, запоминаются в системе как неизменяемые при обратном просмотре.

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

Рис. 4.4.

Рис. 4.5.

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

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

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

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

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

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

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