(apx:c.3)=
# Logic Programming and Prolog #
````{solution} ex:3.2
Draw the SLD-tree for the following program:
```Prolog
list([]).
list([_H|T]):-list(T).
```
and the query `?-list(L)`.
````
This is one of the simplest infinite SLD-trees:
```{figure} /src/fig/appendices/image008.svg
---
width: 50%
name: 'fig:a.4'
---
```
The query succeeds infinitely often, producing the answers:
```Prolog
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} ex:3.3
Draw the SLD-tree for the query `?-likes(A,B)`, given the following program:
```Prolog
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:
```{figure} /src/fig/appendices/image010.svg
---
width: 50%
name: 'fig:a.5'
---
```
Adding a cut to the first clause (before or after `friendly(Y)`) will prune away two answers ({numref}`fig:a.6-left`). 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}` ({numref}`fig:a.6-right`).
```{figure} /src/fig/appendices/image012.svg
---
width: 50%
name: 'fig:a.6-left'
---
Adding a cut to the first clause.
```
```{figure} /src/fig/appendices/image014.svg
---
width: 50%
name: 'fig:a.6-right'
---
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} ex:3.5
Given the program
```Prolog
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)`.
````
```{figure} /src/fig/appendices/image016.svg
---
width: 100%
name: 'fig:a.7'
---
```
+++
````{solution} ex:3.6
Change the first clause to
```Prolog
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)`.
````
```{figure} /src/fig/appendices/image018.svg
---
width: 90%
name: 'fig:a.8'
---
```
+++
````{solution} ex:3.7
Given the program
```Prolog
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.
````
```{figure} /src/fig/appendices/image020.svg
---
width: 40%
name: 'fig:a.9'
---
```
+++
````{solution} ex:3.8
Given the equivalent program with if-then-else
```Prolog
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.
````
```{figure} /src/fig/appendices/image022.svg
---
width: 40%
name: 'fig:a.10'
---
```
+++
```{solution} ex:3.9
```
```Prolog
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} ex:3.10
Given the program
```Prolog
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)`.
````
```{figure} /src/fig/appendices/image024.svg
---
width: 85%
name: 'fig:a.11'
---
```
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} ex:3.11
Given the program
```Prolog
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:
```{figure} /src/fig/appendices/image026.svg
---
width: 100%
name: 'fig:a.12'
---
```
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} ex:3.13
```
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`.
```Prolog
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
```Prolog
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} ex:3.14
```
```Prolog
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} ex:3.15
```
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`.
```Prolog
sort(List,SortedList):-
setof(X,element(X,List),SortedList).
element(X,[X|Ys]).
element(X,[Y|Ys]):-
element(X,Ys).
```
+++
```{solution} ex:3.18
```
As usual, we start with the declarative specification:
```Prolog
% 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:
```Prolog
permutation([],[]).
permutation([Head|Tail],?Permutation):-
/* do something with Head */
permutation(Tail,Permutation).
```
Inserting `Head` somewhere in `Permutation` should yield `?Permutation`:
```Prolog
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` ({numref}`sec:3.9`) by ignoring the arithmetic conditions:
```Prolog
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:
```Prolog
insert_somewhere(X,List,[X|List]).
insert_somewhere(X,[Head|Tail],[Head|Inserted]):-
insert_somewhere(X,Tail,Inserted).
```
+++
```{solution} ex: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:
```Prolog
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.