У Клоксин - ПРОГРАММИРОВАНИЕ НА ЯЗЫКЕ ПРОЛОГ
Давайте посмотрим, как все это выглядит на языке диаграмм. Если мы обратимся к предикату сумма(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.
4.3.2. Комбинация «отсечение-fail»
Во втором из перечисленных выше случаев применения отсечение используется в конъюнкции с встроенным предикатом fail – еще одним встроенным предикатом, подобным not. Предикат fail не имеет аргументов, это означает, что выполнение целевого утверждения fail не зависит от того, какие значения имеют переменные. Действительно, предикат fail определен таким образом, что доказательство его согласованности как целевого утверждения всегда заканчивается неудачей и приводит к включению механизма возврата. Это в точности совпадает с тем, что происходит, когда мы пытаемся найти сопоставление для целевого утверждения, для которого в базе данных нет ни фактов, ни правил. Если fail встречается после отсечения, то нормальное выполнение возврата изменится в результате действия механизма отсечения. Данная комбинация «отсечение-fail» оказывается очень полезной на практике.
Давайте обсудим, как можно было бы использовать эту комбинацию в программе вычисления размера налога, который следует уплатить тому или иному человеку. Один из вопросов, на который мы хотели бы получить ответ – это является ли человек «средним налогоплательщиком». В этом случае вычисления были бы очень простыми и не требовали бы рассмотрения множества особых случаев. Давайте определим предикат средний_налогоплательщик, где средний_налогоплательщик(X) означает, что X является средним налогоплательщиком. Например, Френд Влоггс, который женат, имеет двух детей и работает на велосипедном заводе, мог бы рассматриваться как действительно средний налогоплательщик. Однако директор-распорядитель нефтяной компании получает, по-видимому, достаточно много, а пенсионер – слишком мало, чтобы в обоих случаях был приемлем один и тот же способ вычисления налога. Нам следовало бы начать с особого случая. Возможно, что на иностранного гражданина распространяются особые налоговые законы, так как он может иметь налоговые обязательства также и в своей стране. Поэтому, каким бы средним он ни являлся в других отношениях, иностранец не будет классифицирован как средний налогоплательщик. Мы можем начать запись правил об этом следующим образом:
