# Logic Programming and Prolog

# 12.3. Logic Programming and Prolog¶

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.

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).

If in addition the two `student_of`

clauses are swapped, only the second answer `{A→peter,B→maria}`

is pruned.

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)`

.

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)`

.

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.

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.

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.
```

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.

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.

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.

```
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.

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).
```

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).
```

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.