How is suffix/prefix working internally in prolog?

Question

Can anyone explain how prolog finds a suffix(L1,L2) or prefix(L1,L2) internally?
I know the rule is suffix(L1,L2):- append(_,L2,L1).
But, I can't seem to understand how the variables _, L1 and L2 going inside append and working the query out?

append([],X,X).
append([H|T],Y, [H|W]):- append(T,Y, W).

Answer 1

If you understand append, then the definition

suffix( A, B) :- append( _X, B, A).   

is ... well, actually, what is the meaning of append( X, B, A)?

It's that (in pseudocode) [...X, ...B] == A: the list of elements of X, followed by elements of B, together, is the list of elements in A.

This means that B is a (suffix / prefix -- make a choice, please) of A, right? and we don't care what X is. In particular it can be empty, or not.

This explains suffix. For append please see the linked answer, and the answer it links.

This gives us an idea for a follow up question:

• Define the predicate proper_suffix(A, B) such that "proper_suffix of A is B" holds, i.e. B is a suffix of A, and B is not the same as A.

---

You write

I am not understanding how _ for the suffix's argument is going inside append([H|T], Y, [H|W]):- append(T,Y, W). How is append processing the _ for the H of the append to find whether L2 is suffix of L1? if I pass _, how does Prolog figure out the H and T, coz by anonymous variable we mean that 'we don't care about its value' .

So we have

suffix(        A, B) :- 
   append( _X,    B,
               A).

Whatever the A and B were in the call to suffix(A, B), they will be the same in the call to append( _X, B, A). When that call returns with logic variables _X, A and B holding their (possibly updated) values, the call to suffix returns with its A and B holding those same values as in the append call. The value of _X is not made use of by the suffix/2 predicate, but it is found out just the same, by append/3.

You seem to be confused about the anonymous variable, _. It doesn't matter that it is named that way, it is still a variable. Forget the "don't care" thing, it is confusing and imprecise. Imagine it is named _X, as I showed. it will work exactly the same with _Y, _, Abracadabra, etc., as long as it is not the same as the other variables' names in that rule.

Just one caveat: without the leading _ Prolog will warn us about "singleton variable" i.e. a variable that isn't used anywhere else. It is with respect to this that we signal our intention that "we don't care", with the (leading) _.

Its value is still going to be found, as usual!

And when we use _, the additional convenience is that we don't have to make sure that the name is unique. Each _ is treated as if it were unique, automatically.

---

You ask (in the comments) how does the query append(_X, [a,b], [1,2,a,b]) work.

Prolog works by choosing a rule whose head matches the query.

This query matches the second clause's head:

append(_X, [a,b], [1,2,a,b]) = append([H|T], Y, [H|W])

with

_X = [H|T], Y = [a,b], [H|W] = [1,2,a,b]

Which also means

H = 1, W = [2,a,b], 

and hence

_X = [H|T] = [1|T]

See? This doesn't deconstruct _X, it builds it up!

Since its head matches the query, the second clause of your append definition is thus chosen, and so its body is fired up as the new query under the same substitution, i.e. set of "assignments" to the logic variables involved. So it calls

_X = [H|T], Y = [a,b], [H|W] = [1,2,a,b], append(T,Y,W).

as the new query. That is,

_X = [1|T], Y = [a,b], W = [2,a,b], append(T,Y,W).    %% or,
_X = [1|T1], append(T1, [a,b], [2,a,b]).

If we apply the same reasoning, we see again the second clause matching up, and end up with

_X = [1|T1], T1 = [2|T2], append(T2, [a,b], [a,b]).

But now the first clause matches,

append(T2, [a,b], [a,b]) = append([],X,X)

which entails

T2 = [].

Thus

_X = [1|T1]
        T1 = [2|T2]
                T2 = [].

The list now held by _X has thus been built in a top-down fashion.