Exam II

Sample Solutions

Problem 1.

Note that predicate q1(Xs) succeeds for list Xs provided that every element unifies with either 'a' or 'b'. Predicate q2(X,Xs) succeeds provided every element in Xs unifies with X -- e.g., q2(a,Xs) succeeds for lists whose items are all 'a'. Also, since both q1 and q2 are defined by negation as failure, neither will ever solve for a variable value.

Resolution of the given queries requires careful, but mechanical, tracing of behavior.

(a) (i) queries p1([b,a]) and p2([b,a]) both succeed

* both clauses apply to p1([b,a]); the first clause solves X=b, Xs=[a] and makes the recursive call p1([a]), and only the first clause applies to this call which leads to another recursive call p1([ ]) which fails since no clause matches; backtracking to the second clause for p1([b,a]) solves Xs=[ ] and makes the call q1([ ]), and this succeeds since the negated call member(X,[ ]) fails.

* p2([b,a,]) solves Xs=[b,a] and then reverses the response to the query append(Ys, Zs, [b,a]), q2(a,Ys), q2(b,Zs); in this query append will succeed in three different ways, and in the first case q2(b,Zs) fails and in the other two q2(a,Ys) fails -- hence this goal fails and its reversed outcome is success.

(ii) queries p1([b,b]) and p2([b,b]) both fail

* only clause one applies to p1([b,b]), this solves X=b, Xs=[b] and makes the recursive call p1([b]), again only the first clause applies to this call which leads to another recursive call p1([ ]) which fails since no clause matches.

* similar to case (a)-i above, p2([b,b]) leads to reversing the response to the query append(Ys, Zs, [b,b]), q2(a,Ys), q2(b,Zs); in this query, append will succeed first with Ys=[ ] and Zs=[b,b] so both the remaining goals succeed, and then this response is reversed for failure.

(b) These programs do agree for queries not involving variables. However, since p2 is defined by negation as failure, it will never solve for any variables, while p1 will. So a successful goal for p1 involving a variable will differentiate them -- for instance, the query p1([X,a]). succeeds with X=b (essentially as shown in case (a)-i above), while p2([X,a]) doesn't just leave X unsolved, it fails since the response of query append(Ys, Zs, [X,a]), q2(a,Ys), q2(b,Zs) is reversed, and this goal succeeds for Ys=[X,a] and Zs=[ ].

Problem 2.

(a) these terms unify with X/7, Y/7, Z/g(7,7) and yield common instance p(g(7,7),f(7,g(7,7)),g(7,g(7,7)))

(b) these terms fail to unify since, after solving Z/f(Y,1), X/1, and Y/1, 1=7 fails

(c) these terms unify with X/f(Z,3) , Y/7, Z/f(Z,3) and yield common instance

p(f(Z,3), f(7,f(Z,3), f(7,f(Z,3)); because of the occur-check violation, the solved variable Z still appears in the result as an unknown -- performing this unification on the system (and asking to see the entire answer) will cause an infinite loop

Problem 3.

Since the break predicate requires extracting an initial portion of the list Ys, use of the append predicate may come to mind. For such a solution we can directly follow the informally stated conditions to build the program.

break(Xs, Ys, Zs) :-

append(Zs, [B|_], Ys), % split list Ys into two pieces

member(B,Xs), % with a break item at the boundary, and

\+((member(Z,Zs), member(Z,Xs))). % for all Z in Zs it fails that Z is in Xs

This solves the problem unless Ys contains no break items, and then it fails. So we need another clause for this case, namely

break(Xs, Ys, Ys) :- findall(Y, (member(Y,Ys), member(Y,Xs)), [ ]).

Alternatively, we can use recursion (in fact, tail-recursion) to extract items from list Ys until encountering a break item.

break(Xs, [ ], [ ]). % end of list, extraction ends

break(Xs, [Y|Ys], [ ]) :- member(Y,Xs). % break item, extraction ends

% otherwise place item in result and continue

break(Xs, [Y|Ys], [Y|Zs]) :- \+member(Y,Xs), break(Xs, Ys, Zs).