Prolog append with cut operator

Question

What problem can occur when we use append with cut operator?

   append2([],L,L):-!.
   append2([H|T],L,[H|TL]):-append2(T,L,TL).

I have tried several different inputs, but it always succeeds.

?- append2([1,2],[5],L).
L = [1, 2, 5].

?- append2([1,2],[1,2],L).
L = [1, 2, 1, 2].

?- append2([],[1,2],L).
L = [1, 2].

?- append2([1,2],[],L).
L = [1, 2].

Endoblast

Answer 1

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.

Seow

Answer 2

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.

Lubber

is this in the standard that the cut inside a parenthesized expression has the whole predicate as its scope (so to speak - what's the proper terminology here?)? I remember seen a discussion about this somewhere. A given Prolog implementation could conceivably have the expression itself as the cut's scope, could it, in which case the cut wouldn't have any effect there. Is it so? Also you don't show append3(Xs,Ys,[]). Did the additional cut help there to eliminate the choice point? Which Prolog were you using to run this? – Tithing

@Will Ness: The cuts cuts through (',')/2, (;)/2, (->)/2 and (in a sense) (:-)/2. However, in order to do so, the cut must be present at the point in time of term-to-body/goal conversion. For a simple Prolog text rule, that means it must appear as a concrete ! and not as a variable to be instantiated later on to !. call((!,fail;true)) fails whereas call((G=!,G,fail;true)) succeeds, since actually call((G=!,call(G),fail;true)) is executed. For append3(Xs,Ys,[]) this works for all Prologs I know of: They have first-argument indexing, but no or weak indexing on the other arguments. – Lubber

thank you! That was what I vaguely remembered - the subtleties of call. Thanks! But what about append3(Xs,Ys,[])? Did it remove the choice-point there? – Tithing

@Will Ness: Of course, append(Xs,Ys,[]) leaves no choice-point open. Why do you believe it does not? It executes Zs == [] and thus the !. – Lubber

thank you. Just wanted to be sure (my installed SWI is pretty old, it retries even the first example, append([], Ys, Zs). and I always have to press ;). – Tithing

@Will Ness: Please update by all means! Your version must be very old, 2007 or so... Things have progressed a lot recently, also in SWI... – Lubber

Of interest; monotonic, purity and guard – Amylo

@WillNess: upon rereading my first comment, the cut does not cut through the first argument of (->)/2. – Lubber

Answer 3

Try for example the most general query:

?- append2(X, Y, Z).

Beatify

Answer 4

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

Parlous