5. Средства управления ходом выполнения программы. Предикат сократить (отсечение).

Рассмотренный выше способ управления ходом выполнения программы путем изменения порядка расположения предложений и целей программы не является единственным. Рассмотрим другие средства управления.

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

Встроенный предикат “сократить” – "!" (отсечение) применяется для уменьшения размера пространства поиска запроса, т.е. ограничивает перебор всех возможных вариантов ответов или полностью подавляет его.

Он дает указание интерпретатору не возвращаться назад далее той точки, где стоит этот предикат. Предикат "! " - это псевдоцель, которая всегда истинна. Этот предикат по разному действует на составной запрос и на множество фраз, образующих процедуру. Эти два вида действия предиката четко различаются между собой. Предикат “сократить” является одной из подцелей составного запроса, например:

?- a(X), b(Y), ! , c(X, Y, Z).

При выполнении этого запроса, если подцели a(X) и b(Y) окажутся успешными, интерпретатор пройдет через предикат !. После этого интерпретатор не сможет возвратиться назад к подцелям, стоящим перед !, и обязан использовать при выполнении подцели c(X,Y,Z) те значения X и Y, которые они получили при конкретизации. Если подцель c(X,Y,Z) окажется неуспешной при данных конкретизациях X и Y, то и весь запрос потерпит неудачу. Если предикат ! будет последней подцелью составного запроса, то это гарантирует получение только одного ответа на запрос;

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

возраст(петров,18).

возраст(сидоров, 16).

возраст(иванов, 18).

Запрос ?- возраст (петров, Х), ! .

Можно записать правила с отсечением других вариантов ответов. Тогда, если интерпретатор дойдет до этого предиката, то он не сможет вернуться назад для рассмотрения остальных фраз программы:

возраст(петров,18):- ! .

возраст(сидоров, 16) :- !.

возраст(иванов, 18) :- !.

Запрос ?- возраст (петров, Х) .

Пример 2. Влияние отсечения на процедуру.

predicates a(integer) b(integer) clauses a(1):-write("один"). a(X):-b(X),write("два"). a(3):-write("три"). b(21). b(22).

Результат запроса ?- a (N). один N=1; два N=21; два N=22; три N=3;

Поместим отсечение в середину второго правила:

predicates a(integer) b(integer) clauses a(1):-write("один"). a(X):-b(X),!,write("два"). a(3):-write("три"). b(21). b(22).

Результат запроса ?- a (N). один N=1; два N=21;

С помощью отсечения можно повысить эффективность программы, указав Пролог-системе не проверять альтернативы, про которые заранее известно, что они должны потерпеть неудачу. Отсечение дает возможность сформулировать взаимно исключающие утверждения при помощи правил вида:

если Условие то Утверждение1 иначе Утверждение2 (1)

Пример 3. Реализация правила (1). Поиск наибольшего из двух чисел.

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

predicates

max(integer,integer,integer)

clauses

max(X,Y,X):- X>Y,!.

max(X,Y,Y):- Y>X,!.

max(X,_,X):- write("Числа равны"),!.

Отсечением следует пользоваться с осторожностью, так как его применение может нарушить соответствие между декларативным и процедурным смыслами программы:

изменение порядка следования фраз в программе без использования «отсечения» влияет только на ее эффективность, но не нарушает декларативного смысла программы;

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

Пример. Отсечение отсутствует:

p :- a, b.

p :- c.

Декларативный смысл: р истинно тогда и только тогда, когда истинны а и в, или истинно с:

р  (а И в) ИЛИ с

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

Введем отсечение:

p :- a, ! ,b.

p :- c.

Декларативный смысл: р  (а И в) ИЛИ (Не а И с)

Поменяем порядок предложений:

p :- c.

p :- a, ! ,b.

Декларативный смысл изменился: р  с ИЛИ (а И в)