# 12.3. Logic Programming and Prolog#

Solution 3.2 #

Draw the SLD-tree for the following program:

list([]).
list([_H|T]):-list(T).


and the query ?-list(L).

This is one of the simplest infinite SLD-trees:

The query succeeds infinitely often, producing the answers:

L = [];
L = [X1,X2];
L = [Y1,Y2,Y3];
L = [Z1,Z2,Z3,Z4];


and so on. Note that reversing the order of the clauses means that Prolog gives no answer at all.

Solution 3.3 #

Draw the SLD-tree for the query ?-likes(A,B), given the following program:

likes(peter,Y):-friendly(Y).
likes(T,S):-student_of(S,T).
student_of(maria,peter).
student_of(paul,peter).
friendly(maria).


Add a cut in order to prune away one of the answers {A→peter,B→maria}, and indicate the result in the SLD-tree. Can this be done without pruning away the third answer?

This program produces three answers:

Adding a cut to the first clause (before or after friendly(Y)) will prune away two answers (Figure 12.1). Adding a cut to the second clause can be done in two places: placing it just before the literal student_of(S,T) has no effect, while placing it at the end will only prune the answer {A→peter,B→paul} (Figure 12.2). Figure 12.1 Adding a cut to the first clause.# Figure 12.2 Adding a cut to the second clause.#

If in addition the two student_of clauses are swapped, only the second answer {A→peter,B→maria} is pruned.

Solution 3.5 #

Given the program

bachelor(X):-not(married(X)),man(X).
man(fred).
man(peter).
married(fred).


draw the SLD-trees for the queries ?-bachelor(fred) and ?-bachelor(peter).

Solution 3.6 #

Change the first clause to

bachelor(X):-not(married(X)),man(X)


and show that the modified program produces the right answer, by drawing the SLD-tree for the query ?-bachelor(X).

Solution 3.7 #

Given the program

p:-q,r,s,!,t.
p:-q,r,u.
q.
r.
u.


show that the query ?-p succeeds, but that q and r are tried twice.

Solution 3.8 #

Given the equivalent program with if-then-else

p:-q,r,if_s_then_t_else_u.
if_s_then_t_else_u:-s,!,t.
if_s_then_t_else_u:-u.


show that q and r are now tried only once.

Solution 3.9 #

Write a predicate zero(A,B,C,X) which, given the coefficients $$a$$, $$b$$ and $$c$$, calculates both values of $$x$$ for which $$ax^2 + bx + c = 0$$.

zero(A,B,C,X):-
X is (-B + sqrt(B*B - 4*A*C)) / 2*A.
zero(A,B,C,X):-
X is (-B - sqrt(B*B - 4*A*C)) / 2*A.


Solution 3.10 #

Given the program

length([],0).
length([H|T],N):-length(T,M),N is M+1.


draw the proof tree for the query ?-length([a,b,c],N).

Notice that the maximum number of literals in the resolvent is proportional to the depth of the recursion, which is typical for non-tail recursive predicates. When proofs are long, such programs will be quite inefficient.

Solution 3.11 #

Given the program

length_acc(L,N):-length_acc(L,0,N).
length_acc([],N,N).
length_acc([H|T],N0,N):-N1 is N0+1,length_acc(T,N1,N).


draw the proof tree for the query ?-length_acc([a,b,c],N).

In this program, the is literals are solved immediately after they are added to the resolvent:

Here, the length of the resolvent is independent of the level of recursion, which makes tail-recursive loops very similar to iterative loops with regard to memory requirements.

Solution 3.13 #

In the naive_reverse predicate, represent the reversed list by a difference list, use append_dl instead of append, and show that this results in the predicate reverse_dl by unfolding the definition of append_dl.

The reversed lists are represented by difference lists as follows:

• (partly) specified lists are extended with a variable representing the minus list, e.g. [] becomes R-R, and [H] becomes [H|Minus]-Minus;

• a variable representing a list is replaced by two variables representing the plus and minus lists, e.g. R becomes RPlus-RMinus.

reverse([],R-R).
reverse([H|T],RPlus-RMinus):-
reverse(T,R1Plus-R1Minus),
append_dl(R1Plus-R1Minus,[H|Minus]-Minus,RPlus-RMinus).


Unfolding the call to append_dl/3 means that R1Plus should be unified with RPlus, R1Minus with [H|Minus], and Minus with RMinus, which yields

reverse([],R-R).
reverse([H|T],RPlus-RMinus):-
reverse(T,RPlus-[H|RMinus]).


Renaming the variables results in the same definition as reverse_dl/2.

This illustrates that the translation from simple lists to difference lists can (to a large extent) be automated.

Solution 3.14 #

Rewrite the program for rel, using =..

rel(R,[],[]).
rel(R,[X|Xs],[Y|Ys]):-
Goal =.. [R,X,Y],
call(Goal),
rel(R,Xs,Ys).


Note that, in contrast with the original program, this program conforms to the syntax of clausal logic: there are no variables in functor or literal positions.

Solution 3.15 #

Write a program which sorts and removes duplicates from a list, using setof.

The basic idea is to use element/2 to generate the elements of the list on backtracking, and to collect and sort them by means of setof/2.

sort(List,SortedList):-
setof(X,element(X,List),SortedList).

element(X,[X|Ys]).
element(X,[Y|Ys]):-
element(X,Ys).


Solution 3.18 #

Implement a predicate permutation/2, such that permutation(L,P) is true if P contains the same elements as the list L but (possibly) in a different order, following these steps. (One auxiliary predicate is needed.)

As usual, we start with the declarative specification:

% permutation(L,P) <- P contains the same elements as L
%                     (possibly in a different order)


Taking the first argument as the recursion argument and the second as the output argument, we obtain the following skeleton:

permutation([],[]).
/* do something with Head */
permutation(Tail,Permutation).


Inserting Head somewhere in Permutation should yield ?Permutation:

permutation([],[]).
permutation(Tail,Permutation).


The predicate insert_somewhere/3 can be obtained in the same way as the predicate insert/3 (Section 3.9) by ignoring the arithmetic conditions:

insert_somewhere(X,[],[X]).
insert_somewhere(X,Tail,Inserted).


This program, which is declaratively and procedurally correct, can be slightly improved by noting that the first and third clauses can be combined into a single base case:

insert_somewhere(X,List,[X|List]).
insert_somewhere(X,Tail,Inserted).


Solution 3.19 #

Implement an alternative sorting method by using the partition/4 predicate.

This predicate implements the famous quicksort algorithm, which is one of the most efficient sorting algorithms:

quicksort([],[]).
quicksort([X|Xs],Sorted):-
partition(Xs,X,Littles,Bigs),
quicksort(Littles,SortedLittles),
quicksort(Bigs,SortedBigs),
append(SortedLittles,[X|SortedBigs],Sorted).


The program can still be improved by employing difference lists.