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([],[]).
permutation([Head|Tail],?Permutation):-
    /* do something with Head */
    permutation(Tail,Permutation).

Inserting Head somewhere in Permutation should yield ?Permutation:

permutation([],[]).
permutation([Head|Tail],WholePermutation):-
    insert_somewhere(Head,Permutation,WholePermutation),
    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,[Head|Tail],[Head|Inserted]):-
    insert_somewhere(X,Tail,Inserted).
insert_somewhere(X,[Head|Tail],[X,Head|Tail]).

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,[Head|Tail],[Head|Inserted]):-
    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.