Prolog append с оператором cut

Ответ 1

Существует два вида cuts; зеленые порезы и красные порезы. Зеленые сокращения вставляются только для повышения эффективности и не изменяют семантику программы. С другой стороны, красные разрезы. По определению, зеленые сокращения не создают никаких проблем.

Итак, есть ли способ изменить поведение, если разрез там не был?

Давайте посмотрим; для первого предложения, чтобы соответствовать, L1 должен быть унифицирован с [], L2 с L и L3 с L или, другими словами, L2, унифицируемый с L3.

Когда L1 является [], второе предложение не может совпадать; поэтому разрез не имеет никакого эффекта

Когда L1 не создается: если длина L2 и L3 известны в этой точке, то они должны быть равны, иначе первое предложение не будет соответствовать; таким образом, второе предложение не может совпадать, поскольку на каждом шаге длина L3 уменьшается на 1, и единственный способ прекращения требует L2 = L3

если длина L3 или L2 неизвестна: то у нас есть проблема, так как второе предложение может создавать решения.

Действительно:

    3 ?- append2(L1,L2,[1,2,3]).
    L1 = [],
    L2 = [1, 2, 3].

    4 ?- append2(L1,[1,2,3],L3).
    L1 = [],
    L3 = [1, 2, 3].

    5 ?- append2(L1,L2,L3).
    L1 = [],
    L2 = L3.

    6 ?- append2(L1,[E1,E2],L3).
    L1 = [],
    L2 = [E1, E2].

    7 ?- append2(L1,L2,[E1,E2]).
    L1 = [],
    L2 = [E1, E2].

пока мы ожидаем:

8 ?- append(L1,L2,[1,2,3]).
L1 = [],
L2 = [1, 2, 3] ;
L1 = [1],
L2 = [2, 3] ;
L1 = [1, 2],
L2 = [3] ;
L1 = [1, 2, 3],
L2 = [] ;
false.

9 ?- append(L1,[1,2,3],L3).
L1 = [],
L3 = [1, 2, 3] ;
L1 = [_G24],
L3 = [_G24, 1, 2, 3] ;
L1 = [_G24, _G30],
L3 = [_G24, _G30, 1, 2, 3] ;
L1 = [_G24, _G30, _G36],
L3 = [_G24, _G30, _G36, 1, 2, 3] ;
L1 = [_G24, _G30, _G36, _G42],
L3 = [_G24, _G30, _G36, _G42, 1, 2, 3] ;
...

10 ?- append(L1,L2,L3).
L1 = [],
L2 = L3 ;
L1 = [_G22],
L3 = [_G22|L2] ;
L1 = [_G22, _G28],
L3 = [_G22, _G28|L2] ;
....

11 ?- append(L1,[E1,E2],L3).
L1 = [],
L3 = [E1, E2] ;
L1 = [_G78],
L3 = [_G78, E1, E2] ;
L1 = [_G78, _G84],
L3 = [_G78, _G84, E1, E2] ;
L1 = [_G78, _G84, _G90],
L3 = [_G78, _G84, _G90, E1, E2] ;
...

12 ?- append(L1,L2,[E1,E2]).
L1 = [],
L2 = [E1, E2] ;
L1 = [E1],
L2 = [E2] ;
L1 = [E1, E2],
L2 = [] ;
false.

Ответ 2

Иногда действительно имеет смысл вводить зеленые порезы; даже в append/3, но следует позаботиться о том, чтобы такой разрез оставался зеленым. То есть сокращение, которое повышает эффективность (на определенном уровне) и не влияет на ответы.

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

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

Но вернемся к вашей программе append2/3. В настоящее время разрез всегда сокращается, даже если применяется альтернативное правило, и в этом случае разрез удаляет ответы, которые мы хотим избежать.

Итак, когда первое предложение будет единственным релевантным?

Если первый аргумент [], таким образом, append2([], Xs, Ys). - но также и последний аргумент [] (еще более сложные случаи). Давайте попробуем оба случая с оригинальным безрежимным определением:

?- append([], Ys, Zs).
Ys = Zs.

?- append(Xs, Ys, []).
Xs = Ys, Ys = [] ;
false.

Итак, в первом случае система смогла определить, что есть одно решение сразу, при этом получается ответ. Во втором случае, однако, система Prolog не была уверена, нужен ли другой ответ /mdash; он "оставил точку выбора открытой", так сказать. Это очень жалко, так как довольно тривиально определить, что и в этом случае существует только один ответ. Разрез был бы идеальным здесь, чтобы помочь. Но неохраняемый разрез приносит больше вреда, чем помогает.

Разрез разрезается, если третий аргумент равен []:

append3(Xs, Ys, Zs) :-
   (  Zs == [] -> ! ; true ),
   Xs = [],
   Ys = Zs.
append3([X|Xs], Ys, [X|Zs]) :-
   append3(Xs, Ys, Zs).

Эта программа теперь более эффективна в том смысле, что она не оставляет открытой точку выбора, если известен только третий аргумент.

?- append(Xs,Ys,[1]).
Xs = [],
Ys = [1] ;
Xs = [1],
Ys = [] ;
false.

?- append3(Xs,Ys,[1]).
Xs = [],
Ys = [1] ;
Xs = [1],
Ys = [].

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

Ответ 3

Попробуйте, например, самый общий запрос:

?- append2(X, Y, Z).

Ответ 4

Он не будет работать, когда первые два аргумента являются переменными:

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

?- append2(X, Y, [1, 2, 3]).
X = [],
Y = [1, 2, 3].