Отсечение

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

?- member(X, [1, 2, 3]). % X = 1 ; X = 2 ; X = 3.

?- member(X, [1, 2, 3]), !. % X = 1.

?- !, member(X, [1, 2, 3]). % X = 1 ; X = 2 ; X = 3.

?- member(X, [a, b]), member(Y, [c, d]). % X = a, Y = c ; X = a, Y = d ; X = b, Y = c ; X = b, Y = d.

?- member(X, [a, b]), !, member(Y, [c, d]). % X = a, Y = c ; X = a, Y = d.

?- member(X, [a, b]), member(Y, [c, d]), !. % X = a, Y = c.

?- member(X, [2, 1, 3]), member(Y, [2, 1, 3]), X > Y. % X = 2, Y = 1 ; X = 3, Y = 2 ; X = 3, Y = 1 ; false.

?- member(X, [2, 1, 3]), member(Y, [2, 1, 3]), !, X > Y. % false.

?- member(X, [2, 1, 3]), !, member(Y, [2, 1, 3]), X > Y. % X = 2, Y = 1 ; false.

likes(alice, john).

likes(mary, john).

likes(john, mary).

?- likes(X, Y), likes(Y, X). % X = mary, Y = john ; X = john, Y = mary.

?- likes(X, Y), likes(Y, X), !. % X = mary, Y = john.

?- likes(X, Y), !, likes(Y, X). % false.

Областью действия отсечения является запрос (конъюнкция целей); поэтому отсечение, встретившееся в правой части правила не воздействует на цели, предшествовавшие запуску этого правила. Однако если предикат имеет несколько предложений, то отсечение воздействует на все предложения. Например:

gcd(A, 0, C) :- !, C = A.

gcd(A, B, C) :- D is A mod B, gcd(B, D, C).

?- gcd(4, 6, 2). % true.

?- gcd(4, 6, 1). % false.

?- gcd(4, 6, N). % N = 2.

?- N = [4, 6, 3, 9], member(X, N), member(Y, N), gcd(X, Y, 1).

N = [4, 6, 3, 9], X = 4, Y = 3 ; N = [4, 6, 3, 9], X = 4, Y = 9 ;

N = [4, 6, 3, 9], X = 3, Y = 4 ; N = [4, 6, 3, 9], X = 9, Y = 4 ; false.

?- N = [4, 6, 3, 9], member(X, N), member(Y, N), gcd(X, Y, 1), !.

N = [4, 6, 3, 9], X = 4, Y = 3.

Правильное положение отсечения важно.

gcd1(A, 0, C) :- A = C, !.

gcd1(A, B, C) :- D is A mod B, gcd1(B, D, C).

?- gcd1(4, 6, 1). % ERROR: mod/2: Arithmetic: evaluation error: `zero_divisor'

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

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

contains(X, [X | _]) :- !.

contains(X, [_ | T]) :- contains(X, T).

?- contains(b, [a, b, c]). % true.

?- contains(b, [a, b, b, b, c]). % true.

?- contains(b, [a, c]). % false.

?- contains(X, [a, b, c]). % X = a.

?- contains(X, [a, b, c]), X = b. % false.

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

unique([]).

unique([H | T]) :- contains(H, T), !, fail.

unique([_ | T]) :- unique(T).

?- unique([a, b, c]). % true.

?- unique([a, b, b]). % false.

?- unique([a, b, X]). % false.

Если отсечение опустить, то результат будет неверным:

unique1([]).

unique1([H | T]) :- contains(H, T), fail.

unique1([_ | T]) :- unique1(T).

?- unique1([a, b, b]). % true.

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

count(_, [], 0).

count(X, [X | T], N) :- !, count(X, T, M), succ(M, N).

count(X, [_ | T], N) :- count(X, T, N).

?- count(b, [a, b, c], N). % N = 1 ; false.

?- count(b, [a, b, b, c, b], N). % N = 3 ; false.

?- count(b, [a, c], N). % N = 0 ; false.

Если отсечение опустить, то результат будет неверным:

count1(_, [], 0).

count1(X, [X | T], N) :- count1(X, T, M), succ(M, N).

count1(X, [_ | T], N) :- count1(X, T, N).

?- count1(b, [a, b, b, c], N). % N = 2 ; N = 1 ; N = 1 ; N = 0 ; false.

Разное