общие_услуги(X):-основные_услуги(X).
общие_услуги(X):-дополнительные_услуги(X).
книга_не_возвращена('С. Уотзер',книга10089),
книга_не_возвращена('А. Джонс', книга29907).
. . .
читатель('А.Джонс'). читатель('В.Метеск').
Зачем понадобилось использовать отсечение в этой программе и какой эффект оно оказывает? Предположим, что вы хотите просмотреть список всех читателей и определить, какие услуги им доступны. В этом случае вам надо обратиться к Прологу со следующим вопросом:
?- читатель(X), услуги(X,Y).
Начав поиск ответа, Пролог выберет первого читателя: А.Джонс.Предположим, что этот читатель имеет на руках несколько не возвращенных в указанный срок книг. Для того чтобы определить, какие услуги доступны ему, Пролог воспользуется первым утверждением для предиката услуги.Это приводит к появлению нового целевого утверждения – книга_не_возвращена.После небольшого поиска среди фактов книга_не_возвращенаобнаружен факт о первой не возвращенной А. Джонсом в срок книги (второй факт для этого предиката). Следующее целевое утверждение – это отсечение. Эта цель автоматически согласуется с базой данных, и в результате этого в системе закрепляются все решения, принятые с момента выбора первого утверждения услуги.
Мы можем представить ситуацию, возникшую непосредственно перед выполнением отсечения, в виде диаграммы, приведенной на рис. 4.4. Когда в программе встречается отсечение, то оно «отсекает» путь, представляющий цепочку выполненных доказательств таким образом, что следующая цель соединяется непосредственно с исходной (см. рис. 4.5). Результат действия отсечения в правиле для предиката услуги(утверждение 1) заключается в том, что все цели, выбранные с момента, когда было выбрано это правило, запоминаются в системе как неизменяемые при обратном просмотре.
Путь, представляющий цепочку найденных доказательств, при этом изменяется так, что исключаются все маркеры, соответствующие целям, расположенным между услугии отсечением включительно. Таким образом, если впоследствии произойдет возврат на точку! (отсечение), то попытка согласовать цель услугинемедленно потерпит неудачу. Система не будет рассматривать альтернативные решения для целевого утверждения книга_не_возвращена ('А. Джонс', Книга),и это совершенно разумно, так как мы интересуемся лишь тем, числится ли за читателем хотя бы однане возвращенная в срок книга, а не тем, каковы всекниги, числящиеся за ним. Утверждение 2 в предикате услугитоже рассматриваться системой не будет, так как при возврате обходится и выбор правила, в котором встречается отсечение. Такое поведение системы в рассматриваемой ситуации тоже является разумным, так как мы не хотим порождать решения, указывающие на то, что А. Джонсудоступны все услуги.
Рис. 4.4.
Рис. 4.5.
Действие отсечения в этом примере можно резюмировать следующим образом:
Если оказывается, что читатель имеет не возвращенную в срок книгу, то ему разрешается пользоваться лишь основными видами услуг, предоставляемыми библиотекой. Нет необходимости выявлять все книги, не возвращенные читателем в срок, равно как нет необходимости рассматривать какие-либо другие правила относительно услуг, предоставляемых читателю.
В этом примере использование отсечения привело к «сокращению» всех решений, принятых после выбора целевого утверждения услуги.Оно называется родительскимцелевым утверждением для отсечения, так как именно это целевое утверждение привело к использованию правила, содержащего отсечение. На наших диаграммах родительским целевым утверждением всегда является целевое утверждение, соответствующее наименьшему прямоугольнику, содержащему прямоугольник с '!'. Формальное определение эффекта, производимого отсечением, формулируется следующим образом:
Если отсечение встречается в качестве целевого утверждения, то после этого система лишается возможности изменять решения, принятые ею с момента вызова родительского целевого утверждения. Все альтернативы принятым решениям отбрасываются. Следовательно, попытка вновь доказать согласованность с базой данных любого целевого утверждения между родительским целевым утверждением и ! (отсечением) закончится неудачей.
Существуют различные способы описания того, что произошло с решениями, попавшими в область действия отсечения. Можно сказать, что эти решения отсекаются или замораживаются, что система лишается возможности изменять эти решения или что оставшиеся альтернативы отбрасываются. Можно также смотреть на символ отсечения как на некий разделитель (забор), отделяющий целевые утверждения. Так, при обработке конъюнкции целей
foo:- а, b, с,!, d, e, f
Пролог без каких-либо ограничений может выполнять возврат среди целей a, bи с до тех пор,пока доказательство согласованности целевого утверждения сс базой данных не приведет к тому, что Пролог «перешагнет» через «забор»! и приступит к доказательству согласованности целевого утверждения d. Далее возврат может осуществляться между целевыми утверждениями d, eи f, при этом, возможно, неоднократно будет достигаться согласованность всей конъюнкции целиком. Однако если произойдет неудача при доказательстве согласованности целевого утверждения d, что вызовет «перешагивание через забор» справа налево, то никаких попыток вновь доказать согласованность целевого утверждения сделаться не будет; доказательство согласованности конъюнкции целей в целом, а следовательно, и цели fooпотерпит неудачу.
Прежде чем перейти к рассмотрению других примеров с использованием отсечения, сделаем еще одно замечание. Мы сказали, что если отсечение появляется в некотором правиле и выбирается в качестве целевого утверждения, то Пролог-система лишается возможности изменять все решения, принятые с момента вызова родительского целевого утверждения.Это значит, что выбор этого правила и всех решений, принятых после него, становится зафиксированным. Далее мы увидим, что есть возможность указывать альтернативы в рамках одного правила,используя встроенный предикат ';' (обозначающий « или»). На выбор альтернатив, сделанный с использованием этой возможности, эффект отсечения действует точно так же, т. е. при отсечении фиксируются все « или»-выборы, сделанные с момента выбора правила, содержащего отсечение.
4.3. Общие случаи использования отсечения
Мы можем выделить три основных случая использования отсечения.
Первый связан с ситуациями, когда мы хотим указать Пролог-системе, что она нашла нужное правило для заданного целевого утверждения. В этом случае отсечение означает: «если вы дошли до этого места, то вы выбрали именно то правило, которое нужно для данного целевого утверждения».
Второй случай относится к ситуации, когда мы хотим указать Пролог-системе, что необходимо немедленно прекратить доказательство согласованности конкретного целевого утверждения, не пытаясь найти для него альтернативные решения. В этом случае используется конъюнкция отсечения с предикатом fail,что означает; «если вы дошли до этого места, то вам следует прекратить попытки доказать согласованность данного целевого утверждения».
К третьему случаю относятся ситуации, когда мы хотим закончить порождение альтернативных решений механизмом возврата. В этом случае отсечение означает: «если вы дошли до этого места, то вы нашли единственное решение задачи и никакой возможности найти другие альтернативные решения нет».
Теперь мы рассмотрим несколько примеров использования отсечения в перечисленных выше ситуациях. Однако необходимо помнить, что во всех этих случаях отсечение имеет один и тот же смысл. Выделение трех случаев использования отсечения обусловлено чисто методическими соображениями, чтобы показать, по каким причинам в программах могут использоваться отсечения.
При программировании на Прологе очень часто возникает желание использовать для описания одного предиката несколько утверждений. Одно утверждение будет использоваться, если аргументы имеют один вид, другое будет использоваться для аргументов иного вида и так далее. Часто мы можем указать, какое правило следует использовать для данного целевого утверждения, указав в качестве аргументов в заголовке правила необходимые образцы структур так, чтобы это правило могло быть сопоставлено лишь с соответствующими целевыми утверждениями. Однако это не всегда возможно. Если мы не можем сказать заранее, какого вида аргументы будут использоваться, или если мы не можем перечислить все множество возможных образцов аргументов, то мы можем принять компромиссное решение. Это значит, что задаются правила для аргументов определенных типов, а в конце задается правило-«ловушка» для всех остальных правил. В качестве примера такого способа рассмотрим следующую программу. Определим предикат сумма таким образом, что при выборе в качестве целевого утверждения сумма(N, X), где N– некоторое целое число, переменной Xприсваивается значение, равное сумме всех целых чисел от 1до N. Так, например, возможен следующий диалог:
?- сумма(5,X).
X = 15;
нет
Полученный ответ объясняется тем, что 1+2+3+4+5 равно 15. Здесь приведена соответствующая программа.
сумма(1,1):-!.
сумма(N,Результат):- N1 is N-1, сумма(N1,Результат),Результат is Результат+N.
Приведенное определение является рекурсивным. Идея состоит в том, что выход на граничное условие происходит в случае, когда первый аргумент равен 1. В этом случае ответ тоже равен 1. Второе утверждение вводит рекурсивное целевое утверждение сумма. Однако первый аргумент нового целевого утверждения на единицу меньше, чем первый аргумент в исходном целевом утверждении. Следующее целевое утверждение, которое будет порождено этим целевым утверждением, снова будет иметь первый аргумент на единицу меньше. И так далее до тех пор, пока не будет достигнуто граничное условие. Так как первый аргумент всегда на единицу меньше, то в конце концов произойдет выход на граничное условие (в предположении, что исходное целевое утверждение имеет первый аргумент не меньше 1) и выполнение программы закончится.
Представляет интерес то, как в этой программе организована обработка двух случаев: когда число, соответствующее первому аргументу, равно 1и когда оно отлично от 1. Когда мы определяли предикаты для обработки списков, то было легко указать два типичных случая: когда список был пустым ([]) и когда он имел вид [A|B].Для чисел это не так просто сделать, потому что мы не можем задать такой аргумент, который был бы сопоставим только с целым числом, не равным 1. Приемлемое решение в данном примере состоит в том, чтобы выделить случай, когда первый аргумент равен 1, и обеспечить сопоставление для всех остальных случаев с помощью переменной. Мы знаем, что в соответствии со стратегией, используемой при поиске в базе данных, Пролог сначала будет пытаться произвести сопоставление с правилом для 1, и только в случае неудачи он попытается использовать второе правило. Таким образом, второе правило используется только для чисел, не равных 1. Но этим дело не кончается. Если когда-либо Пролог будет выполнять возврат и попытается пересмотреть выбор правила с первым аргументом, равным 1, то он обнаружит, что второе правило тоже применимо. Как можно видеть, оба правила являются альтернативными для целевого утверждения сумма(1,X).Мы должны указать Прологу, что ни в коем случае не следует использовать второе правило, если число, соответствующее первому аргументу, равно 1. Один из способов сделать это – вставить отсечение в первое правило (как это и показано в записи этого правила). Это отсечение указывает Прологу, что если выбрано первое правило, то больше не следует принимать нового решения относительно того, какое правило использовать для целевого утверждения сумма. Вслучае если число, соответствующее первому аргументу, действительно равно 1, может произойти только выбор первого правила.
Давайте посмотрим, как все это выглядит на языке диаграмм. Если мы обратимся к предикату сумма(1,X)в следующем контексте:
выполнить:- сумма(1,X), foo(apples)
?-выполнить.
и для цели foo(apples)нет сопоставления, то к моменту, когда обнаружится несогласованность foo(apples)с базой данных, результат работы Пролога будет иметь вид, как показано на рис. 4.6. Если Пролог попытается найти новые сопоставления для целевых утверждений, просматривая их в обратном порядке, то обнаружится, что рассмотренные выше два альтернативных целевых утверждения не могут быть пересмотрены, так как они исключены из цепочки доказательства. Следовательно, наиболее верный путь – не пытаться найти другое сопоставление для предиката сумма(1,X).
Рис. 4.6.
Упражнение 4.1.Что произойдет в процессе возврата при попытке найти новое сопоставление для целевогоутверждения сумма,если из первого правила для предиката суммаудалить отсечение? Какие альтернативные результаты будут получены (если вообще они будут возможны) и почему?
Последний пример показал, как можно использовать отсечение для того, чтобы сделать поведение Пролога чувствительным к случаю, когда мы не можем выделить все возможные случаи путем перечисления образцов в заголовках правил. Более типичная ситуация, в которой мы не можем указать структуру заголовков правил для выполнения сопоставления, возникает, если мы хотим ввести дополнительные условия в виде целевых утверждений Пролога, позволяющих в процессе согласования с базой данных выбрать соответствующие правила. Рассмотрим следующий альтернативный вариант решения последнего примера:
сумма(N,1):- N =‹ 1,!.
cyммa(N,R):- N1 is N-1, сумма(N1,R1), R is Rl+N
В этом случае указывается, что первое правило следует выбрать, когда заданное количество суммируемых чисел меньше или равно единице. Такое определение правила немного лучше, чем предыдущее, потому что соответствующая ему программа даст ответ (вместо того чтобы выполняться бесконечно), если в качестве первого аргумента будет задан 0или отрицательное число. Если условие первого правила выполняется, то сразу же выдается результат 1и не требуется прибегать к рекурсивному порождению целевых утверждений. Второе правило следует попытаться использовать лишь в случае, когда это условие не выполняется. Мы должны указать Прологу, что если уже обнаружено, что N = ‹1, то не следует возвращаться к пересмотру выбора правила. Это как раз и достигается с помощью отсечения.
Общий принцип заключается в том, что использование механизма отсечения для указания Прологу на ситуации, когда он выбрал единственно правильное правило, может быть заменено использованием предиката not.Это встроенный предикат Пролога, т. е. определение этого предиката заранее известно Пролог-системе. Поэтому его можно использовать, не выписывая каждый раз его определение (более полно встроенные предикаты описываются в гл. 6). Предикат notопределен таким образом, что целевое утверждение not(X)истинно, только если X, рассматриваемое как целевое утверждение, не согласуется с базой данных. Таким образом, not(X)означает, что X недоказуемо как целевое утверждение Пролога,т. е. не согласовано с базой данных. В качестве примера использования notвместо отсечения перепишем два варианта определения предиката суммаследующим образом:
сумма(1,1).
cyммa(N,R):- not(N = 1), N1 is N-1, cyммa(N1,R1),R is N1 + R1.
или
сумма(N,1):- N =‹1.
сумма(N,R):- not(N=‹l), N1 is N-1, сумма(N1,R1 ),R is N1 + R1.
В действительности в Прологе имеются другие удобные встроенные предикаты, которые могут заменить оба из приведенных вхождений предиката not.Например, можно заменить not(N=1)на N\=1,a not(N=‹ 1)на N›1.В общем случае это можно сделать не со всеми возможными условиями.
Использование предиката notвместо отсечения свойственно для хорошего стиля программирования. Это связано с тем, что программы, содержащие отсечения, как правило, более трудны для чтения, чем программы, не содержащие их. Если удается локализовать все вхождения отсечения и заменить их с помощью предиката not, то программа станет более понятной. Однако определение not предполагает попытку доказать, что заданное целевое утверждение согласуется с базой данных. Поэтому если мы имеем программу, в общем виде представимую как
A:-B, C
A:-not(B),D
то Прологу для успешного завершения программы может потребоваться две попытки согласовать B.Он должен попытаться согласовать Bпри просмотре первого правила. Но если затем будет выполнен возврат и рассмотрено второе правило, то он будет вынужден попытаться согласовать Bвновь, чтобы убедиться, может ли быть согласовано not(B).Такое дублирование приводит к потере эффективности программы, когда условие Bдостаточно сложно. Этого бы не произошло, если бы вместо приведенной программы мы имели:
A:-B,!,C
A:-D
Таким образом, иногда нужно взвесить преимущества ясной программы по сравнению с преимуществами ее быстрого выполнения. Обсуждение вопроса эффективности приводит нас к последнему примеру, в котором отсечение используется для фиксирования выбора правила. Рассмотрим определение предиката присоединить:
присоединить([],X,X).
присоединить([А|В],С,[А|D]) – присоединить(В,С,D).
Если предикат присоединитьиспользуется лишь в случаях, когда, имея два списка, мы хотим найти список, получающийся в результате добавления элементов второго списка в конец первого, то такая программа неэффективна, поскольку, если выполняется возврат при обработке целевого утверждения вида присоединить([],[a,b,c,d],X), Пролог обязан сделать попытку использовать второе правило, несмотря на то что эта попытка заранее обречена на неудачу. В таком контексте пустота первого списка указывает на то, что первое правило является единственным возможным для использования и эта информация может быть сообщена Прологу с помощью отсечения. В общем случае при применениях Пролог-системы смогут лучше использовать имеющуюся память, если сообщать системе такие сведения, по сравнению с тем, когда она должна хранить информацию о выборе правил, которая в действительности использована не будет. Можно с этой целью переписать наше определение следующим образом:
присоединить([],X,X):-!.
присоединить([А|В],С,[А|D]:- присоединить(В,С,D).
При сделанных предположениях относительно применения предиката присоединитьэто никак не повлияет на то, какие решения найдет программа, но несколько повысит ее эффективность по времени выполнения и объему занятой памяти. В качестве платы за это мы потеряли возможность использования предиката присоединитьв других ситуациях – он больше не будет работать ожидаемым образом, что будет показано в разд. 4.4.
Во втором из перечисленных выше случаев применения отсечение используется в конъюнкции с встроенным предикатом fail– еще одним встроенным предикатом, подобным not. Предикат failне имеет аргументов, это означает, что выполнение целевого утверждения failне зависит от того, какие значения имеют переменные. Действительно, предикат failопределен таким образом, что доказательство его согласованности как целевого утверждения всегда заканчивается неудачей и приводит к включению механизма возврата. Это в точности совпадает с тем, что происходит, когда мы пытаемся найти сопоставление для целевого утверждения, для которого в базе данных нет ни фактов, ни правил. Если failвстречается после отсечения, то нормальное выполнение возврата изменится в результате действия механизма отсечения. Данная комбинация «отсечение- fail» оказывается очень полезной на практике.
Давайте обсудим, как можно было бы использовать эту комбинацию в программе вычисления размера налога, который следует уплатить тому или иному человеку. Один из вопросов, на который мы хотели бы получить ответ – это является ли человек «средним налогоплательщиком». В этом случае вычисления были бы очень простыми и не требовали бы рассмотрения множества особых случаев. Давайте определим предикат средний_налогоплательщик, где средний_налогоплательщик(X)означает, что Xявляется средним налогоплательщиком. Например, Френд Влоггс, который женат, имеет двух детей и работает на велосипедном заводе, мог бы рассматриваться как действительно средний налогоплательщик. Однако директор-распорядитель нефтяной компании получает, по-видимому, достаточно много, а пенсионер – слишком мало, чтобы в обоих случаях был приемлем один и тот же способ вычисления налога. Нам следовало бы начать с особого случая. Возможно, что на иностранного гражданина распространяются особые налоговые законы, так как он может иметь налоговые обязательства также и в своей стране. Поэтому, каким бы средним он ни являлся в других отношениях, иностранец не будет классифицирован как средний налогоплательщик. Мы можем начать запись правил об этом следующим образом:
средний_ налогоплательщик(X):- иностранец(X), fail .
средний_налогоплательщик(X):-…
В этой выдержке из программы (которая является неверной)в первом правиле делается попытка сказать: «если X – иностранец, то доказательство согласованности целевого утверждения средний_налогоплательщик(X)должно закончиться неудачей». Второе правило должно использовать общий критерий того, что значит быть средним налогоплательщиком в тех случаях, когда X– не иностранец. Ошибка заключается в том, что если бы мы обратились с вопросом
?- средний_налогоплательщик(видслевип).
об иностранце по фамилии видслевип,то произошло бы сопоставление с первым правилом и согласованность целевого утверждения иностранецбыла бы доказана. Далее, целевое утверждение failинициировало бы возврат. При попытке найти новое сопоставление для цели средний_налогоплательщикПролог нашел бы второе правило, определяющее общие критерии вычисления налога, и начал бы применять это правило к видслевип.Вполне вероятно, что этот иностранец удовлетворил бы общим критериям, что привело бы к неверному ответу «да».
Таким образом, первое правило оказалось абсолютно неэффективно при «отбраковке» нашего приятеля как среднего налогоплательщика. Почему так получается? Ответ кроется в том, что при возврате Пролог пытается найти новое сопоставление для каждогоцелевого утверждения, рассматривавшегося ранее. Поэтому, в частности, будут исследованы альтернативные способы сопоставления для средний_налогоплательщик(видслевип). Для того чтобы остановить поиск альтернатив в данном случае, необходимо отсечь сделанный выбор правила (заморозить решение), прежде чем будет выполнен предикат fail.Мы можем сделать это, вставив отсечение перед fail.Несколько более обстоятельное определение предиката средний_налогоплательщик,включающее эти изменения, приведено ниже:
средний_налогоплателыцик(Х):- иностранец(Х),!,fail.
средний_налогоплательщика(X):-супруга(Х,Y), доход(Y,Доход), Доход › 3000,!, fail.
средний_налогоплателыцик(Х):- доход(X,Доход),2000 ‹ Доход, 20000 › Доход.
доход(Х,Y):- получаемое_пособие(Х,Р),Р‹5000,!, fail .
доход(Х,Y):-жалованье(Х,Z),доход_от_капиталовложений(X,W),Y is Z + W.
доход_от_капиталовложений(Х,Y):-…
Обратите внимание на использование в этой программе других комбинаций «отсечение- fail». Во втором правиле средний_налогоплательщикговорится, что попытка показать, что некоторый человек является средним налогоплательщиком, может быть прервана, если можно показать, что заработок его супруги превышает некоторый порог. Точно так же в определении предиката доходуказано (в первом правиле), что если человек получает пособие, сумма которого меньше некоторого порога, то независимо от других обстоятельств мы будем рассматривать его как вовсе не имеющего дохода.
Интересный пример использования комбинации «отсечение- fail»представляет предикат not.Большинство реализаций имеют этот предикат как встроенный, но интересно рассмотреть, как можно описать его с помощью правил. Мы требуем, чтобы целевое утверждение not(P),где Pобозначает некоторое другое целевое утверждение, было истинным тогда и только тогда, когда доказательство согласованности целевого утверждения Pтерпит неудачу. Это не совсем точно соответствует нашему интуитивному пониманию «не является истинным» – далеко не всегда мы можем без опасения считать, что что-то не является истинным, если мы не в состоянии доказать это. Но как бы то ни было, здесь приводится соответствующее определение: