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

Клоксин У.

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

not(P):- call(P),!, fail.

not(P)

Определение предиката notсодержит обращение к аргументу Pкак к целевому утверждению с использованием встроенного предиката call.Предикат callпросто интерпретирует свой аргумент как целевое утверждение и пытается доказать его

согласованность. Мы хотим, чтобы первое правило применялось в тех случаях, когда согласуется Pс базой данных, а в противном случае должно применяться второе правило. Таким образом, мы говорим, что если Пролог может согласовать call(P),то он должен прекратить на этом правиле доказательство целевого утверждения not.Другая возможность имеет место, если Пролог не может согласовать call(P).В этом случае он никогда не дойдет до отсечения. Так как доказательство согласованности call(P)потерпело неудачу, то происходит возврат, и Пролог обнаруживает второе правило. Следовательно, доказательство согласованности целевого утверждения not(P)закончится успешно в случае, когда Pнедоказуемо.

Как и в первом случае применения отсечения, мы можем заменить любое употребление комбинации «отсечение- fail»использованием предиката not.Такая замена требует несколько большей реорганизации программы, чем ранее, но при этом не приводит к потере эффективности. Если бы мы стали с этой целью переписывать нашу программу для предиката средний_ налогоплательщик,то следовало бы начать ее примерно так:

средний_налогоплателыцик(X):-

nоt(иностранец(X)),not((супруга(X,Y),доход(Y,Доход), Доход›3000)), доход(Х, Доход1),…

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

Теперь мы можем рассмотреть последнюю основную область применения отсечения в программах на Прологе – завершение последовательности порождения и проверки вариантов. Очень часто программа состоит из частей, соответствующих следующей общей модели. Имеется последовательность целей, которые могут быть согласованы множеством различных способов и которые порождают много возможных решений при возврате. Кроме того, имеются цели, проверяющие приемлемость порожденных решений для последующего использования. Если поиск сопоставлений для этих целевых утверждений закончится неудачей, то возврат приведет к тому, что будет предложено новое решение. Новое решение будет подвергнуто проверке на пригодность и так далее. Процесс завершится, либо когда будет порождено приемлемое решение (успех), либо когда нельзя больше найти решений (неудача). Мы можем назвать «генератором» целевые утверждения, которые порождают все возможные альтернативы, а целевые утверждения, которые проверяют пригодность решения, - «контролером». Давайте рассмотрим пример такой программы. Приводимый ниже фрагмент мог бы быть частью программы, играющей в крестики-нолики. Эта программа использует встроенные предикаты varи arg,которые подробно рассмотрены в гл. 6.

вынужденный ход(Доска,K):- линия(Клетки), угроза(Клетки,Доска,K),!.

линия([1,2,3]).

линия([4,5,6]).

линия([7,8,9]).

линия([1,4,7]).

линия([2,5,81).

линия([3,6,9]).

линия ([1,5,9]).

линия([3,5,7]).

угроза([X,Y,Z],B,X):- пусто(Х,В), крестик (Х,В), крестик(Z,B).

угроза([X,Y,Z],B,Y):- пусто(Y,B), крестик (Х,В), крестик(Z,B).

угроза([X,Y,Z],B,Z):- пусто(Z,B), крестик(Х,В), крестик(Y,B).

пусто(К,Доска):- arg(K,Дocкa,C), var(C).

крестик(К,Доска):- arg(K,Дocкa,C), nonvar(C), C=X.

нолик(К,Доска):- arg(К,Доска,С), nonvar(C), С=0.

Для тех, кто не знаком с этой игрой, вкратце объясним ее правила. Два игрока по очереди заполняют клетки на доске размером 3x3. Один игрок использует для этого символ 0, а другой игрок — символ X. Цель игры — расположить три своих символа подряд по одной линии (вертикальной, горизонтальной или диагональной). Мы можем перенумеровать девять клеток на доске следующим образом: