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

В действительности в Прологе имеются другие удобные встроенные предикаты, которые могут заменить оба из приведенных вхождений предиката 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инициировало бы возврат. При попытке найти новое сопоставление для цели средний_налогоплательщикПролог нашел бы второе правило, определяющее общие критерии вычисления налога, и начал бы применять это правило к видслевип.Вполне вероятно, что этот иностранец удовлетворил бы общим критериям, что привело бы к неверному ответу «да».