ERROR: Out of global stack with append/3

Question

I have a problem. I want to implement a replace(E1, L1, E2, L2) predicate. This holds when L1 and L2 are the same lists,except that in one place where L1 has the value E1, L2 has E2. In addition, only one occurrence is replaced and it must work in any mode.

For example:

replace(2,[1,2,3,4],5,X) should have only the solution X = [1,5,3,4].

replace(2,[1,2,3,2,1],5,X) should backtrack over the solutions X = [1,5,3,2,1] and X = [1,2,3,5,1].

replace(2,X,5,[1,5,3,5,1]) should backtrack over the solutions X = [1,2,3,5,1] and X = [1,5,3,2,1].

replace(X,[a,b,c,d],Y,[a,e,c,d]) should have only the solution X = b, Y = e.

replace(X,[1,2,3,2,1],Y,[1,5,3,5,1]) should have no solutions (it should fail).

My implementation:

 replace(E1, L1, E2, L2) :- 
    append(X, [E1|L_Tail], L1),
    append(X, [E2|L_Tail], L2).

This code is fine. However when replace(2,X,5,[1,5,3,5,1]), it should return X = [1,2,3,5,1] and X = [1,5,3,2,1] and false. It only return the first 2 results, and the false didn't came up. The program end up with ERROR: Out of global stack.

Answer 1

This question has been asked and it has two answers: the one you used and a better one. However, I will answer the question "why does this solution not work and how to fix it?".

When the third argument to append/3 is a variable or a partial list, it gives infinitely many solutions:

?- append(X, Y, [a|Z]).
X = [],
Y = [a|Z] ;
X = [a],
Y = Z ;
X = [a, _1860],
Z = [_1860|Y] ;
X = [a, _1860, _1872],
Z = [_1860, _1872|Y] ;
X = [a, _1860, _1872, _1884],
Z = [_1860, _1872, _1884|Y] . % and so on

So, when the first list L1 is a partial list, the call to append(X, [E1|Y], L1) will keep "hallucinating" longer and longer lists. The second call to append/3 will fail every time, Prolog will backtrack, make an even longer list with the first append/3, and so on. This is why you are caught in an infinite loop and will eventually run out of memory (when the lists get too long).

One cheap way to avoid this is to make sure that both lists are proper lists of the same length before giving them to the two appends. For example:

same_length([], []).
same_length([_|A], [_|B]) :- same_length(A, B).

If you are using SWI-Prolog you could do this with maplist and a yall lambda:

maplist([_,_]>>true, L1, L2)

The example query:

?- L2 = [1,5,3,5,1],
   maplist([_,_]>>true, L1, L2),
   append(X, [2|Y], L1),
   append(X, [5|Y], L2).
L2 = [1, 5, 3, 5, 1],
L1 = [1, 2, 3, 5, 1],
X = [1],
Y = [3, 5, 1] ;
L2 = [1, 5, 3, 5, 1],
L1 = [1, 5, 3, 2, 1],
X = [1, 5, 3],
Y = [1] ;
false.