Prolog append with cut operator

It sometimes really makes sense to introduce green cuts — even into append/3, but care must be taken that such a cut remains a green cut. That is, a cut that does improve efficiency (on a certain level) and does not affect answers.

There is a very simple rule-of-thumb for introducing green cuts: If you add a cut into a pure, monotonic program without any guard, you can be pretty sure that it will be a red cut which destructs the meaning of your program.

There are very few exceptions to this rule-of-thumb. For example, you may add a cut after a variable free goal, provided there is no further rule etc. It is definitely a good training to try to figure out cases that are affected by a cut.

But back to your program append2/3. Currently, the cut always cuts, even if the alternate rule does apply, in which case the cut removes answers which is what we want to avoid.

So when will the first clause be the only one of relevance?

If the first argument is [], thus append2([], Xs, Ys). - but also if the last argument is [] (there are even more cases which are more complex). Lets try both cases with the original cut-free definition:

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

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

So in the first case, the system was able to determine that there is a single solution immediately, while producing the answer. In the second case, however, the Prolog system was not sure whether or not another answer will be necessary — it "left a choicepoint open" so to speak. This is a pity, since it is fairly trivial to determine that also in this case, only a single answer exists. A cut would have been ideal here to help. But an unguarded cut does more harm than it helps.

The cut may cut, provided the third argument is a []:

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

This program is now more efficient in the sense that it does not leave a choicepoint open, if only the 3rd argument is known.

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

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

The program is not necessarily faster, since the test itself might be expensive. Ideally, a Prolog system would be able to do such things internally, but sometimes the programmer has to help a bit.

There are two kinds of cuts; green cuts and red cuts. Green cuts are inserted just to improve efficiency and don't change the semantics of the program. Red cuts, on the other hand, do. By definition, green cuts do not cause any problems.

So, is there any way that the behaviour would change if the cut wasn't there?

Lets see; for the first clause to match, L1 should be unifiable with [], L2 with L and L3 with L or, in other words, L2 unifiable with L3.

When L1 is [] the second clause cannot match; so the cut doesn't have any effect

When L1 is not instantiated: if the length of L2 and L3 are known at this point, then they must be equal otherwise the first clause wouldn't match; thus, the second clause cannot match since at each step the length of L3 is decreased by 1 and the only way to terminate requires L2=L3

if the length of L3 or L2 is not known: then we have a problem since the second clause may produce solutions.

Indeed:

    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].

while we expect:

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.

Try for example the most general query:

?- append2(X, Y, Z).

It won't work when the first two arguments are variable:

?- 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].