Давайте подытожим всю информацию, которую мы почерпнули в гл. 1 и 2 о том, что может произойти с целевым утверждением (целью).

1. Может иметь место попытка доказать согласованность целевого утверждения с базой данных. В процессе доказательства база данных просматривается, начиная с ее вершины. При этом возможны две ситуации:

(а) Может быть найден факт (или заголовок правила), сопоставимый с целевым утверждением. В этом случае мы говорим, что произошло сопоставление цели с утверждением (фактом или правилом) в базе данных. Это место отличается в базе данных маркером и конкретизируются (присваиваются значения) соответствующие переменные, если они не были конкретизированы ранее. Если произошло сопоставление с правилом, то прежде всего необходимо попытаться доказать согласованность подцелей, вводимых этим правилом. Если цель согласуется с базой данных, то предпринимается попытка согласовать следующее целевое утверждение. В используемых нами диаграммах это будет цель, указанная в следующем, нижнем прямоугольнике, на который указывает стрелка. Если исходная цель входит в конъюнкцию, то это будет цель, расположенная в программе непосредственно справа от исходной цели.

(б) В базе данных нет факта (или заголовка правила), сопоставимого с целевым утверждением. В этом случае мы говорим, что попытка доказать согласованность целевого утверждения потерпела неудачу (цель не согласуется с базой данных). Тогда будет предпринята попытка (см. п.2) вновь доказать согласованность целевого утверждения, указанного в прямоугольнике, расположенном выше стрелки. Если исходное целевое утверждение входит в конъюнкцию, то это будет целевое утверждение, расположенное в программе непосредственно слева от рассматривавшегося целевого утверждения.

2. Мы можем сделать попытку вновь доказать согласованность целевого утверждения с базой данных. Для этого прежде всего необходимо попытаться вновь согласовать каждую из его подцелей, при этом стрелка возвращается в некоторую исходную позицию, поднимаясь вверх по странице. Если ни одна из подцелей вновь не может быть согласована каким-либо подходящим образом, делается попытка найти альтернативное утверждение для самой исходной цели. В этом случае необходимо вернуть в исходное (неопределенное) состояние каждую переменную, конкретизированную при выборе предыдущего утверждения. Эти действия мы называем «уничтожением» результатов, полученных ранее при доказательстве согласованности целевого утверждения. Затем возобновляется просмотр базы данных, но начинается этот просмотр с места, отмеченного маркером данной цели. Как и ранее, эта новая цель, выбранная при возврате, может оказаться либо согласованной, либо несогласованной с базой данных. При этом будет иметь место либо шаг (а), либо шаг (б).

В этой главе процесс возврата будет рассмотрен более подробно. Кроме того, будет рассмотрен специальный механизм – «отсечение», который может быть использован в программах на Прологе. Отсечение позволяет указывать, какие из ранее сделанных выборов альтернатив не следует более пересматривать.

Простейшая ситуация, в которой некоторое множество фактов допускает несколько ответов на вопрос, возникает, когда в этом множестве имеется несколько фактов, сопоставимых с вопросом. Например, имеются следующие факты:

отец(мэри, джордж).

отец(джон, джордж).

отец(сью,гарри).

отец(джордж,эдуард).

в которых отец(X, Y) обозначает, что Y является отцом X. Вопрос

?- отец(X,Y).

имеет несколько возможных ответов. Если мы будем вводить после каждого ответа точку с запятой, то Пролог выдаст следующие ответы:

X = мэри, Y = джордж;

X = джон, Y = джордж;

X = сью, Y = гарри;

X = джордж, Y = эдуард.

Пролог найдет эти ответы, просматривая базу данных в поисках фактов и правил с предикатом отец и печатая их в том порядке, в каком они представлены в базе данных. При этом Пролог не проявляет особого «интеллекта» – он ничего не помнит о предыдущих ответах. Так, если мы обратимся с вопросом

?- отец(_,X).

(для каких X верно то, что X является отцом), то мы получим

Х=джордж;

Х=джордж;

Х=гарри;

Х=эдуард.

при этом ответ джордж повторен дважды, так как Джордж является отцом как Мэри, так и Джона. Если Пролог может сделать одно и то же двумя различными способами, то он рассматривает это как два различных решения.

Повторный просмотр выполняется точно таким же способом, если выбор среди альтернатив происходит на более глубоком уровне обработки. Например, для определения отношения «одним из детей X является Y» могло бы быть использовано правило

ребенок(Х,Y):- отец(Y,X).

Тогда вопрос

?- ребенок(Х,Y).

дал бы

X = джордж, Y = мэри;

X = джордж, Y=джон;

X = гарри, Y = сью;

X = эдуард, Y = джордж.

Так как отец(Y, X) имеет четыре решения, то столько же решений имеет и ребенок(Х, Y). Более того, решения порождаются в том же самом порядке. Единственное, что отличает эти решения, - это различный порядок аргументов в соответствии с определением для предиката ребенок. Аналогично, если мы определили

отец(X):- отец(_,X).

(отец (X) обозначает, что X является чьим-либо отцом), то на вопрос

?- отец(X).

были бы получены ответы:

X = джордж;

X = джордж;

X = гарри;

X = эдуард.

Если мы перемешаем факты и правила, то выбор альтернатив вновь будет производиться в соответствии с порядком, в котором представлены факты и правила. Так, мы могли бы определить:

человек(адам).

человек(X):- мать(X,Y).

человек(ева).

мать(каин,ева).

мать(авель,ева).

мать(иавал,ада).

мать(тувалкаин,цилла).

(адам - человек; объект является человеком, если он имеет мать; ева – человек. Перечисленные люди имеют указанных матерей). В этом случае если бы мы сделали запрос

?- человек (X).

то ответом было бы:

X = адам;

X = каин;

X = авель;

X = иавал;

X = тувалкаин;

X = ева.

Давайте рассмотрим более интересный случай, когда имеются два целевых утверждения, для каждого из которых есть несколько решений. Предположим, что мы планируем провести вечеринку и хотим порассуждать о том, кто с кем мог бы танцевать. Мы можем начать писать программу следующим образом:

возможная_пара(X, Y):- парень(Х), девушка(Y).

парень(джон).

парень(мармадук).

парень(бертрам).

парень(чарлз).

девушка(гризелда).

девушка(эрминтруда).

девушка(брунхильда).

В программе определено, что X и Y образуют возможную пару, если X является парнем, a Y — девушкой. Теперь давайте посмотрим, какие возможные пары имеются:

?- возможная_пара(X, Y).

X = джон, Y = гризелда;

X = джон, Y = эрминтруда;

X = джон, Y = брунхильда;

X = мармадук, Y = гризелда;

X = мармадук, Y = эрминтруда;

X = мармадук, Y = брунхильда;

X = бертрам, Y = гризелда;

X = бертрам, Y = эрминтруда;

X = бертрам, Y = брунхильда;

X = чарлз, Y = гризелда;

X = чарлз, Y = эрминтруда;

X = чарлз, Y = брунхильда.

Вы должны быть уверены, что понимаете, почему Пролог породил решения в таком порядке. Прежде всего он ищет сопоставление для цели парень(X) и находит, что первым парнем является джон. Затем он находит сопоставление для цели девушка(Y), выбирая гризелда в качестве первой девушки. В этом месте мы запрашиваем новое решение, вводя ';'. Пролог поэтому считает, что последнее доказательство согласованности цели потерпело неудачу, и делает попытку вновь доказать согласованность последней из рассматривавшихся целей. Этой целью является утверждение девушка, встретившееся при доказательстве согласованности целевого утверждения возможная_пара. Обнаруживается альтернативный вариант эрминтруда, и, следовательно, следующим решением является пара джон и эрминтруда. Аналогично порождается пара джон и брунхильда в качестве третьего решения. При следующей попытке доказать согласованность целевого утверждения девушка(Y) Пролог обнаружит, что маркер, соответствующий этому целевому утверждению, находится в конце базы данных и, следовательно, попытка найти новое сопоставление для этого целевого утверждения терпит неудачу. Тогда делается попытка вновь доказать согласованность целевого утверждения парень(Х), маркер которого был установлен на первый факт предиката парень, и, следовательно, следующим найденным решением, соответствующим второму парню, является мармадук. Теперь, когда для этого целевого утверждения найдено новое решение, Пролог определяет, что следует делать далее – он должен найти сопоставление для цели девушка(Y), осуществляя поиск решения с самого начала базы данных. Так что он выбирает гризелда в качестве первой девушки. Следующие три решения содержат мармадук и имена трех девушек. Очередная попытка найти альтернативное решение для цели девушка заканчивается неудачей. Поэтому ищется другой парень, а поиск среди девушек производится с начала базы данных. Аналогичным образом происходит выполнение программы и далее.

В конце концов сложится ситуация, когда доказательство согласованности целевого утверждения девушка закончится неудачей и при этом будут также исчерпаны все решения для целевого утверждения парень. Программа не может более найти ни одной пары.

Все приведенные примеры являются очень простыми. Они содержат лишь определения большого числа фактов или используют правила для доступа к этим фактам. По этой причине они могут порождать только конечное число возможных решений. В некоторых случаях нам может потребоваться порождать бесконечное число возможных вариантов – не потому, что мы хотим рассмотреть их все, а потому, что мы не знаем заранее, сколько их понадобится. В этом случае необходимо рекурсивное определение (обсуждавшееся в предыдущей главе).

Рассмотрим следующее определение целого числа (здесь под «целым» числом понимается целое положительное число). Целевое утверждение целое_число(N) согласуется с базой данных, если переменная N конкретизирована и ее значением является целое число. Если переменная N неконкретизирована в момент рассмотрения целевого утверждения, то попытка найти соответствие для утверждения целое_число (N) приведет к тому, что будет выбрано целое число, которое будет присвоено N в качестве значения.

/* 1 */ целое_число(0).

/* 2 */ целое_число (X):- целое_число (Y),X is Y+1)

Если мы зададим вопрос

?- целое_число (X).

то получим в качестве возможных ответов все целые числа в порядке возрастания (0, 1, 2, 3,…), по одному числу каждый раз. Всякий раз, когда инициируется возврат (возможно, в результате ввода точки с запятой ';'), для предиката целое_число находится новое сопоставление, в результате чего его аргументу присваивается очередное целое число. Таким образом, это короткое определение порождает бесконечное число решений. Почему? На рис. 4.1, 4.2, 4.3 показана последовательность событий, приводящая к порождению трех первых решений. На каждом этапе самый нижний указатель (1) на рисунке указывает место, где впоследствии будет выбрано иное решение. Первоначально для ответа на вопрос имеется выбор между фактом 1 и правилом 2. Если выбирается факт 1, то ничего более выбирать не придется, и мы получаем X = 0. В противном случае выбирается правило 2 и ищется соответствие для цели, порождаемой этим правилом. Если выбирается факт 1, то завершается доказательство целевого утверждения с ответом X=1; в противном случае используется правило 2 и снова ищется соответствие для появившейся подцели. И так далее. На каждом этапе первое что делает Пролог – это выбирает факт 1. Только при выполнении возврата он изменяет последний сделанный им выбор. Каждый раз, когда он это делает, он возвращается к тому месту, где в последний раз выбирал факт 1, и выбирает вместо него правило 2. При этом выборе появляется новая подцель. Факт 1 представляет первую возможность для сопоставления с этой подцелью.

Рис. 4.1.

Рис. 4.2.

Рис. 4.3.

Большинство правил на Прологе будут порождать альтернативные решения, если они сопоставляются с целями, содержащими большое число неконкретизированных переменных. Например, отношение принадлежности элемента списку:

принадлежит(X,[X |_]).

принадлежит(X,[_ |Y]):- принадлежит(X,Y).

порождает альтернативные решения. Если мы задаем вопрос

?- принадлежит(а,X).

(обратите внимание, что X в вопросе является неконкретизированной переменной), то последовательные значения переменной X будут представлять частично конкретизированные списки, в которых а является первым, вторым, третьим и так далее элементом списка. Убедитесь, что вы понимаете, почему так получается. Другим следствием возврата, допускаемого при выполнении предиката принадлежит, является то, что вопрос

?- принадлежит(а,[а,b,r,а,с,а,d,а,b,r,а]).

фактически может быть согласован пятью способами. Очевидно, что имеются приложения предиката принадлежит, в которых требуется найти лишь одно решение, если оно вообще существует, и затем отбросить (обойти) остальные возможные решения. Такое отбрасывание оставшихся решений может быть реализовано с помощью «отсечения».

Этот раздел посвящен специальному механизму, используемому в программах на Прологе и называемому «отсечением»[8]. Отсечение позволяет указать, какие из сделанных ранее выборов не следует пересматривать при возврате по цепочке согласованных целевых утверждений. Существуют две причины, побуждающие включать в программу такие указания:

• Программа будет выполняться быстрее, так как не будет тратиться время на попытки найти новые сопоставления для целей, о которых заранее известно, что они не внесут более ничего нового в решение.

• Программа может занимать меньше места в памяти ЭВМ, так как отсутствие необходимости запоминать точки возврата для последующего анализа позволяет более экономно использовать память.

В некоторых случаях включение отсечения в программу может означать переход от программы, которая не будет работать, к программе, которая будет работать.

Синтаксически использование в правиле отсечения выглядит как вхождение целевого утверждения с предикатом '!', не имеющим аргументов. Как целевое утверждение этот предикат всегда согласуется с базой данных и не может быть вновь согласован. Однако он имеет побочный эффект, который изменяет процесс последующего возврата. Эффект заключается в том, что маркеры некоторых целей становятся недоступными, так что для этих целей нельзя найти новые сопоставления. Рассмотрим, как это происходит на примере. Предположим, что вы заведуете библиотекой и имеете базу данных на Прологе, содержащую информацию о наличии книг, о том, кто и какие книги взял и когда книги должны быть возвращены. Один из вопросов, который мог бы вас интересовать,- это какие виды услуг, предоставляемых библиотекой, доступны каждому из читателей. Некоторые услуги, которые мы могли бы назвать основными, должны быть доступны любому читателю. Они включают пользование каталогом и справочным бюро. С другой стороны, дополнительные услуги, такие как пользование абонементом или получение книг из других библиотек, хотелось бы предоставлять читателю выборочно. Одно из правил могло бы состоять в том, что если читатель не возвратил в указанный срок книгу, то дополнительные виды услуг ему недоступны до тех пор, пока он не вернет книгу. Здесь приведена часть программы, которая использует это правило:

услуги(Читатель,Вид_услуг):-

 книга_не_возвращена(Читатель,Книга),!,основные_услуги (Вид_услуг).

услуги(Читатель,Вид_услуг):-общие_услуги(Вид_услуг).

основные_услуги(пользование_каталогом).

основные_услуги(получение_справок).

дополнительные_услуги (абонемент).

дополнительные_услуги(межбиблиотечный_абонемент).

общие_услуги(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 потерпит неудачу.

Прежде чем перейти к рассмотрению других примеров с использованием отсечения, сделаем еще одно замечание. Мы сказали, что если отсечение появляется в некотором правиле и выбирается в качестве целевого утверждения, то Пролог-система лишается возможности изменять все решения, принятые с момента вызова родительского целевого утверждения. Это значит, что выбор этого правила и всех решений, принятых после него, становится зафиксированным. Далее мы увидим, что есть возможность указывать альтернативы в рамках одного правила, используя встроенный предикат ';' (обозначающий «или»). На выбор альтернатив, сделанный с использованием этой возможности, эффект отсечения действует точно так же, т. е. при отсечении фиксируются все «или»-выборы, сделанные с момента выбора правила, содержащего отсечение.

Мы можем выделить три основных случая использования отсечения.

Первый связан с ситуациями, когда мы хотим указать Пролог-системе, что она нашла нужное правило для заданного целевого утверждения. В этом случае отсечение означает: «если вы дошли до этого места, то вы выбрали именно то правило, которое нужно для данного целевого утверждения».

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

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. Цель игры — расположить три своих символа подряд по одной линии (вертикальной, горизонтальной или диагональной). Мы можем перенумеровать девять клеток на доске следующим образом:

Предполагается, что программа действует за игрока, делающего свои ходы ноликами. Предикат вынужденный_ход используется для ответа на вопрос: «Нужно ли делать вынужденный ход в конкретной позиции?» Такая ситуация имеет место, если игрок 0 (игрок, делающий ходы ноликами, т. е. программа) не может выиграть немедленно (мы не будем рассматривать этот слу- случай), но есть угроза того, что игрок X может выиграть следую- следующим ходом. Например, в позиции

Игрок 0 вынужден поставить 0 в 4-й квадрат, так как если он не сделает этого, то его противник будет иметь возможность на следующем ходу заполнить линию 1-4-7. Программа работает, пытаясь найти линию, две клетки которой заполнены крестиками, а третья – пустая. Если такая линия имеется, то игрок 0 вынужден сделать ход, поставив нолик в пустую клетку. В утверждении для предиката вынужденный_ход цель

линия(Клетки)

служит «генератором» возможных линий. Эта цель может быть согласована с базой данных несколькими способами, в частности, присваиванием в качестве значения переменной Клетки одного из возможных списков номеров клеток, находящихся на одной линии. Выбрав линию, необходимо проверить, существует ли угроза со стороны противника на этой линии. Это составляет задачу целевого утверждения, выполняющего функции «контролера»:

угроза(Клетки,Доска,К)

В этом целевом утверждении переменная Доска используется для представления текущей позиции на доске (т. е. какие клетки заняты и какими символами), а переменная К получает в качестве значения номер клетки, в которой игрок 0 должен поставить нолик (при условии что доказательство этой цели завершается успешно).

Основная идея программы очень проста – предикат линия выдает линию, а затем предикат угроза проверяет, имеется ли на этой линии угроза. Если это так, то доказательство согласованности исходного целевого утверждения вынужденный_ход заканчивается успешно. Иначе инициируется возврат, и предикат линия предполагает другую возможную линию. Эта линия также подвергается проверке, и, возможно, снова произойдет возврат. Если мы окажемся в ситуации, когда предикат линия не может более порождать линии, то доказательство согласованности целевого утверждения вынужденный_ход закончится неудачей (вынужденных ходов нет).

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

Чтобы понять такое использование отсечения, необходимо лишь рассмотреть общую структуру этой программы. Однако некоторые из деталей также представляют интерес. В программе предполагается, что игровую доску можно описать с помощью структуры, состоящей из девяти компонент. Каждая компонента представляет содержимое клетки с соответствующим номером. Таким образом, в любой момент времени содержимое четвертой клетки доски может быть получено путем выборки четвертого аргумента структуры, представляющей текущую позицию на доске (для этого мы используем встроенный предикат arg). Если клетка ничем не заполнена, то переменная будет неконкретизи-рованной; иначе ее значение равно одному из атомов О или X. Мы используем предикаты var и nonvar для того, чтобы определить, занята клетка или нет.

Давайте рассмотрим другой пример программы, работающей по методу «порождения и проверки». Вернемся к вопросу о делении целых чисел, рассмотренному в разд. 2.5. Большинство Пролог-систем обеспечивают эту возможность автоматически, но здесь представлена программа для целочисленного деления, которая использует лишь операции сложения и умножения.

разделить(N1,N2,Результат):-

 целое_число(Результат), Произведение_1 is Результат*N2, Произведение_2 is (Результат + 1)*N2, Произведение_1 =‹ N1, Произведение_2›N1,!.

Это правило использует предикат целое_число (как он определен ранее) для порождения числа Результат, которое является результатом «деления» N1 на N2. Так, например, результат деления 27 на 6 равен 4, так как 4×6 меньше или равно 27, а 5×6 больше чем 27.

Приведенное правило использует предикат целое_число как «генератор», а остальные целевые утверждения выполняют функцию соответствующего «контролера». Мы заранее знаем, что если заданы конкретные значения N1 и N2, то предикат разделить(N1, N2, Результат) может иметь значение «истина» лишь для одного возможного значения Результат. Несмотря на то что целое_число может породить бесконечное множество кандидатов, лишь для одного из них будут выполняться последние тесты. Мы можем явно выразить это наше знание, вставив отсечение в конце правила. Словами это можно сказать так: «если нам удалось породить число Результат такое, что оно успешно проходит тесты для числа, являющегося результатом деления, то нет надобности пытаться получить другое решение». В частности, нет необходимости пересматривать какой-либо из выборов, которые были сделаны при поиске правил для разделить, целое_число и так далее. Мы нашли единственное решение, и нет оснований искать другое. Если бы мы "не" добавили отсечение, то любой возврат в конце концов снова инициировал бы поиск альтернатив для целое_число. Так что продолжилось бы порождение значений для переменной Результат. Ни одно из новых значений не было бы правильным результатом деления, и, таким образом, генерация целых чисел продолжалась бы до бесконечности.

Мы уже убедились в том, что иногда необходимо учитывать стратегию, используемую в Прологе для поиска в базе данных, и что порядок записи утверждений в программе на Прологе влияет на результат доказательства согласованности целевых утверждений. Проблема, связанная с введением отсечений, заключается в том, что мы должны еще более детально знать, как именно будут использоваться правила программы. Ибо, когда правило используется одним способом, отсечение может быть безвредным или даже полезным, в то время как при другом способе употребления правила отсечение может привести к непредвиденному результату. Рассмотрим измененное определение предиката присоединить, приведенное в предыдущем разделе:

присоединить([],Х,Х):-!.

присоединить[А|В],С,[А|D]:- присоединить(В,С,D).

Когда мы имеем дело с целевыми утверждениями, подобными

присоединить([а,b,с],[d,е],Х)

и

присоединить([а,b,с],Х,Y)

то использование отсечения вполне уместно. Если первый аргумент такого целевого утверждения уже имеет некоторое значение, то единственный смысл отсечения – это подтверждение того, что когда значение первого аргумента есть [], то только первое правило применимо. Однако рассмотрим, что произойдет, если мы имеем целевое утверждение

присоединить(Х,Y,[а,b,с]).

Это целевое утверждение будет сопоставлено с заголовком первого правила, что даст

X = [], Y = [a,b,c]

но затем встретится отсечение. Это приведет к тому, что будет заморожен сделанный нами выбор правила, и как следствие в случае если мы обратимся за новым решением, ответ будет «нет», даже если в действительности для данного запроса имеются другие решения.

Приведем другой интересный пример того, что может произойти, если правило, содержащее отсечение, используется незапланированным способом. Давайте определим предикат число_родителей, который дает информацию о том, сколько родителей имеет человек. Мы можем определить его следующим образом:

число_родителей(адам,0):-!.

число_родителей(ева,0) :-!.

число_родителей(Х,2).

то есть число родителей для адам и ева равно 0, а для всех остальных равно 2. Если мы всегда используем наше определение предиката число_родителей для определения числа родителей некоторого данного человека, то все идет нормально. Мы получаем

?- число_родителей(ева,Х).

X = 0; нет

?- число_родителей(джон,Х).

X = 2;

нет

и так далее, как это и требуется. Отсечение необходимо, чтобы предотвратить процесс возврата, который мог бы привести к третьему правилу в случае, когда человек – это адам или ева. Однако рассмотрим, что произойдет, если мы используем те же самые правила, чтобы проверить, что данный человек имеет данное число родителей. Все хорошо, за исключением того, что мы получаем

?- число_родителей(ева,2).

да

Вам следует самостоятельно разобраться, почему так получается – это просто следствие стратегии, применяемой в Прологе для поиска в базе данных. Наша реализация обработки «остальных» случаев, основанная на использовании отсечения, просто больше не работает надлежащим образом. Существуют два способа изменить определение, которые позволили бы нам устранить указанный эффект:

число_родителей(адам,N):-!, N=0.

число_родителей(ева,N):-!, N=0.

число_родителей(Х,2).

или

число_родителей(адам,0).

число_родителей(ева,0).

число_родителей(Х,2):- X \= адам, X \= ева.

Конечно, эти определения по-прежнему не работают, если задать целевое утверждение вида

?- число_родителей(Х,Y).

ожидая, что возврат позволит перечислить все возможности. Таким образом, можно сделать следующий вывод:

Если вы вводите отсечения для того, чтобы обеспечить правильную работу программы для целевых утверждений определенной формы, то нет гарантии, что при появлении целевых утверждений иной формы будет происходить что-либо разумное. Отсюда следует, что надежное использование отсечения возможно лишь в том случае, когда вы имеете четкое представление о том, как ваши правила будут использоваться. Если характер использования правил меняется, то необходимо пересмотреть все случаи употребления отсечения.

Примечания:

8

В оригинале использован термин Пролога «cut», и при переводе точнее было бы применить термин «сокращение». Однако, следуя терминологии более ранних публикаций о Прологе, мы сохраним термин «отсечение». - Прим. ред.