Explanation for why append/3 produces infinite number of solutions in these cases

Viewed 209

I'm having trouble understanding this question about Prolog. The question is as follows:

Select all of the following goals that have an infinite number of solutions.

And here are the possible answers:

append([a,b,c,d], Y, Z)
append(X, Y, X)
append(X, [a,b,c,d], Z)
append(X, Y, [a,b,c,d])

Apparently the correct answers are 2 and 3, but I don't get why 1 isn't also correct - wouldn't there be infinite possibilities for Z and hence also Y? Also, why would 2 be correct, since the first argument and the third argument ("the result") are identical? Sounds like Y could just be [].

Thanks a lot!

2 Answers

append(X, Y, X) can only be true of Y == [] (that's a "theorem for free" à la Wadler) but under that constraint, X can be any of infinite set of possibilities:

SWI-Prolog finds out about Y == [] and is noncommittal about the content of the X list, giving it only as a list of unbound variables:

?- append(X,Y,X).
X = Y, Y = [] ;   % alternative writing of X = [], Y = []
X = [_6696],
Y = [] ;
X = [_6696, _7824],
Y = [] ;
X = [_6696, _7824, _8952],
Y = [] ;
X = [_6696, _7824, _8952, _10080],
Y = [] ;
X = [_6696, _7824, _8952, _10080, _11208],
Y = [] 
...

And you are correct that append([a,b,c,d], Y, Z) should be listed as admitting an infinite number of solutions.

Interestingly, SWI-Prolog does not enumerate templates / lists of placeholder variables / candidates in this case but spits out what is essentially a rewrite of the constraint append([a,b,c,d], Y, Z), i.e. it behaves more theorem-proverish than in case 1:

?- append([a,b,c,d],Y,Z).
Z = [a, b, c, d|Y].

(That's a Prolog ambiguity: When does it enumerate and when not? If there were a Prolog notation for "list of N values of unspecified content, N an integer between 0 and +oo" such a notation could be used as output of append(X,Y,X) instead.)

The alternative, not chosen here, would be:

?- append([a,b,c,d],Y,Z).
Y = [], 
Z = [a,b,c,d] ;
Y = [_1], 
Z = [a,b,c,d,_1] ;
Y = [_1,_2], 
Z = [a,b,c,d,_1,_2] ;
...

Are there any Prologs that do the above? There might be.

If you want to be precise in talking about Prolog, it's necessary to distinguish between (at least) answers and solutions to a query. An answer is a procedural notion, it is a substitution of variables produced by Prolog every time a query succeeds. A solution is a substitution of variables under which a query succeeds. Every answer substitution is a solution, but this does not make these notions synonymous.

Consider this predicate:

foo(a).
foo(a).

This has two answers (which happen to look the same):

?- foo(X).
X = a ;
X = a.

It has a single solution: Only the substitution X = a makes it succeed, and Prolog can even prove this:

?- X = a, foo(X).
X = a ;
X = a.

?- dif(X, a), foo(X).
false.

In this case there were more answers than solutions. The opposite is also possible:

bar(f(_X)).

Here the query bar(T) has a single answer, but more than one solution (in fact, infinitely many):

?- bar(T).
T = f(_708).

?- T = f(1), bar(T).
T = f(1).

?- T = f(2), bar(T).
T = f(2).

So now let's look at the first query from the question:

?- append([a, b, c, d], Y, Z).
Z = [a, b, c, d|Y].

With the definitions from above, this has a single answer. But as you point out, we can substitute infinitely many different values for the variables, getting infinitely many solutions, for example:

?- Y = [1], append([a, b, c, d], Y, Z).
Y = [1],
Z = [a, b, c, d, 1].

?- Y = [1, 2], append([a, b, c, d], Y, Z).
Y = [1, 2],
Z = [a, b, c, d, 1, 2].

Now, the bad news is that your teacher doesn't seem to be using the same convention as I am using here. Using the terms defined above, the teacher was asking about answers, while you are thinking in terms of solutions. It would be interesting to know if they understand this distinction, and what terms they use for these distinct notions. If they really meant answers, then they are correct that this query does not have infinitely many. If they really meant solutions, then you are correct that it does have infinitely many of those.

As for the second query:

?- append(X, Y, X).
X = Y, Y = [] ;
X = [_818],
Y = [] ;
X = [_818, _824],
Y = [] ;
X = [_818, _824, _830],
Y = [] .

You're right that Y can only be [], but that still leaves an infinite number of solutions for X. And here Prolog also produces infinitely many answers describing those solutions.

Related