Программирование на языке пролог
Шрифт:
Использование предиката notвместо отсечения свойственно для хорошего стиля программирования. Это связано с тем, что программы, содержащие отсечения, как правило, более трудны для чтения, чем программы, не содержащие их. Если удается локализовать все вхождения отсечения и заменить их с помощью предиката not, то программа станет более понятной. Однако определение not предполагает попытку доказать, что заданное целевое утверждение согласуется с базой данных. Поэтому если мы имеем программу, в общем виде представимую как
A:-B, C
A:-not(B),D
то Прологу для успешного завершения программы может потребоваться две попытки согласовать 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является средним налогоплательщиком. Например, Френд Влоггс, который женат, имеет двух детей и работает на велосипедном заводе, мог бы рассматриваться как действительно средний налогоплательщик. Однако директор-распорядитель нефтяной компании получает, по-видимому, достаточно много, а пенсионер – слишком мало, чтобы в обоих случаях был приемлем один и тот же способ вычисления налога. Нам следовало бы начать с особого случая. Возможно, что на иностранного гражданина распространяются особые налоговые законы, так как он может иметь налоговые обязательства также и в своей стране. Поэтому, каким бы средним он ни являлся в других отношениях, иностранец не будет классифицирован как средний налогоплательщик. Мы можем начать запись правил об этом следующим образом:средний_ налогоплательщик(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». Во втором правиле средний_налогоплательщикговорится, что попытка показать, что некоторый человек является средним налогоплательщиком, может быть прервана, если можно показать, что заработок его супруги превышает некоторый порог. Точно так же в определении предиката доходуказано (в первом правиле), что если человек получает пособие, сумма которого меньше некоторого порога, то независимо от других обстоятельств мы будем рассматривать его как вовсе не имеющего дохода.