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

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