Facit 2008-10-24

Logic programming

1DL022, 2AD201, 2AD089

Computing Science Department
Information Technology
Uppsala University

1 Unification

What does Prolog anser to the following queries? Motivate your answers by showing the steps of the unification algorithm in all cases.

a. (3) p([H|T], U, [H|U], T) = p([a|X], [b|Y], Z, Z).
{[H|T] = [a|X], U = [b|Y], [H|U] = Z, T=Z}
{H=a, T=X,
U = [b|Y], [H|U] = Z, T=Z}
{H=a, T=X, U = [b|Y], Z= [a,b|Y], T=Z}
{H=a, X=[a,b|Y], U = [b|Y], Z= [a,b|Y], T=[a,b|Y]}

b. (2) p(h(T), U, h(U), T) = p(a(X), b(Y), Z, Z).
{h(T) = a(X), ...}
fails

c. (2) p(h(T), U, h(U), T) = p(h(X), b(X), Z, Z).
{h(T)=h(X), U=b(X), h(U)=Z, T=Z}
{T=X, U=b(X), h(U)=Z, T=Z}
{X=h(U), U=b(X), Z=h(U), T=h(U)}
{X=h(b(X)), U=b(X), Z=h(b(X)), T=h(b(X))}
Since Prolog lacks the occurs check, it answers
X=h(b(h(b(...)))) and the same for Z and T, while
U=  
b(h(b(...)))

d. (2)  p(h(T), U, h(U), _T) = p(h(_X), b(_X), Z, Z).
{h(T)=h(_X), U=b(_X), h(U)=Z, _T=Z}
{T=_X, U=b(_X), h(U)=Z, _T=Z}
{_X=T, U=b(T), Z=h(b(T)), _T=h(b(T))}
Note that T and _T are two different variables. Prolog answers
U=b(T), Z=h(b(T))

e. (4) Explain why Prolog by default does not apply the occurs check in unification.
See the course material for details. In short
- it is too expensive (3)
- circular terms can be useful (1)

2 Concepts

Give a brief (a few lines) definition/description of the following concepts:
a. (3) Accumulator pair.
A pair of arguments to a recursive predicate. One is an input argument that will pass the result obtained "so far". When the recursion reaches the base case, this argument contains the final answer, which is copied to the other argument of the pair (which thus is an output argument).
b. (3) Soundness
If an answer is found, then it is correct, meaning that it is a logical consequence of the program
c. (3) Steadfast code
The behaviour of the program is consistent w.r.t. instantiation of variables, meaning
If test(Var) succeeds with answer Var=t, then test(t) succeeds.
If test(Var) fails, then test(t) also fails.
d. (3) Global constraint
A constraint that can apply to an arbitrary number of variables, for example
alldifferent(A,B,C,...).

See the course material for more details.

3 Built-in predicates

What is Prolog's answer to the following queries?  Why?

a. (1) X+1 =:= 3+1.
Instantiation error: X+1 cannot be evaluated

b. (1) X+1 is 3+1.
No: X+1 does not unify with 4.

c. (1) X = 3+1, number(X).
No: 3+1 is not a number, but a compound term

d. (1) X = Y, var(X).
X=Y: X (=Y) is still a variable

e. (1) X-2 @< X-1.
No. Compares - with -, then X with X, then 2 with 1. 2 @< 1 is false.

f. (1) functor(T, f, 3), arg(2, T, a).
T = f(_A,a,_B) or T = f(_,a,_) or similar.
After the call to functor, T=f(_,_,_). Then the second argument is set to a.

g. (1) f(Args) =.. [F,a,b,c].
No.  f(Args) =..  [f,Args] which does not unify with [F,a,b,c].
I can write Args, but it is still only one argument!

4 A small predicate

a. (4) Write a predicate insert(+E, +List, -New) that assumes that
List
is a sorted list of numbers (lowest first), and E is a number.
It is true if New is List with E inserted (in the correct position, such that New is also sorted).
For example:
| ?- insert(3, [2,5], X).
X = [2,3,5] ? ;
no
| ?- insert(6, [2,5], X).
X = [2,5,6] ? ;
no

Try to write as declarative as possible (no cut, if-then-else, ...).

insert(E, [], [E]).
insert(E, [H|T], [E,H|T]) :- E =< H.
insert(E, [H|T], [H|U]) :- E > H, insert(E, T, U).

b. (2)
Write a predicate sort(+List, -New) that assumes that List is a list of numbers,
and that is true if New is a list that contains the same numbers, but is sorted.
Implement insertion sort, and use the predicate insert from question a. For example:

| ?- sort([3,5,2,5], X).
X = [2,3,5,5] ? ;
no


sort([], []).
sort([H|T], Sorted) :-
sort(T, SortedtT),
insert(H, SortedT, Sorted).

c. (4) Obviously, insertion sort is not an efficient sorting algorithm in general, but for short lists that is not a problem. However, when used in a context, the program from question a and b may cause other problems. Point out what shortcomings you might have to address to make the program more memory-efficient. Don't write a new program.

The main problem is that insert is leaving choice points. To this end, you would want to
- change the specification to insert(+List, +E, -New)
- use if-then-else to treat the two cases of the comparison without choice.
You may also note that sort is not tail-recursive, which can be fixed using an accumulator.
However, given the fact that we use insertion sort at all, this could be considered overkill.

Example (not required for full marks):
insert([], E, [E]).
insert([H|T], E, Result) :-
 ( E =< H ->
   Result = [E,H|T]

 ; Result=[H|U],
   insert(E, T, U)
 ).

sort(List, Sorted) :-
   insertall(List, [], Sorted).

% insertall(+List1, +List2, ?Sorted)
% assumes List2 is sorted, and
% is true if Sorted is a sorted list
% that consists of all elements of List1 and List2.
insertall([], Sorted, Sorted).
insertall([H|T], Sofar, Sorted) :-
   insert(Sofar, H, NewSofar),
   insertall(T, NewSofar, Sorted).

5 Program analysis

Consider the following program.

% select2(+Elt, +List1, +List2, ?Rest)
% assumes List1 and List2 are lists
% is true if Elt occurs in List1 or List2
% and Rest is the rest of the list from which Elt is removed.

select2(X, [X|Xs], _, Xs).
select2(X, _, [X|Xs], Xs).
select2(X, [Y|Ys], [Y|Zs], [Y|Rest]) :- !, select2(X, Ys, Zs, Rest).
select2(X, [Y|Ys], _, [Y|Rest]) :- select2(X, Ys, [], Rest).
select2(X, _, [Y|Ys], [Y|Rest]) :- select2(X, Ys, [], Rest).

test(Rest) :- select2(a, [1,2,a], [1,a,3], Rest).

a. (5) Draw the resultant tree for this program and the query test(R).
Draw the complete tree, including branches clipped by a cut.

b. (2) Show for the cut:

test(R) <- test(R)
|
test(R) <- select2(a, [1,2,a], [1,a,3], R)
|(3) |(4) |(5)
| ==A====C====== cut clips here
|cut is introduced and activated here
|
test([1|Rest]) <- !, select2(a, [2,a], [a,3], Rest)
|
test([1|Rest]) <- select2(a, [2,a], [a,3], Rest)
|(2) |(4) |(5)
| B D
|
test([1,3])<-

(A)
test([1|R]) <- select2(a, [2,a], [], R)
|(4)
B

(B)
test([1,2|Rest]) <- select2(a, [a], [], Rest)
|(1) |(4)
test([1,2])<- test([1,2,a|Rest]) <- select2(a, [], [], Rest)

(C)
test([1|R]) <- select2(a, [a,3], [], R)
|(1) |(4)
test([1,3])<- D

(D)
test([1,a|Rest]) <- select2(a, [3], [], Rest)
|(4)
test([1,a,3|Rest]) <- select2(a, [], [], Rest)
c. (3) Explain how this program behaves regarding the creation and deletion of choice points. You can use the query from question a. as an example.

A choice point is created upon every call. No indexing is used, since the first argument of each clause is X.
The choice point is removed only if
- clause 3 is applied (which must be a rare exception in general)
- backtracking proceeds to clause 5 (which it almost never does).

d. (2) The rule with the cut binds the output argument before the cut.
Explain why this is not recommended in general, and explain why it is harmless in this particular case.

In general:
if the output argument is actually given as input, and the unification fails on that, we can "miss" a cut that was supposed to prevent us from ending up in a clause that was not designed for this case.
In this case:
if the output argument does not unify with [Y|Rest], neither of the following clauses can be applied.

e. (2) Is this a red cut or a green cut? Why?
It is a green cut, in the sence that it only prunes solutions that are found elsewhere in the tree.

6 Search using backtracking

Given is a directed graph, represented by facts that give the edges:
edge(a,b).
edge(b,c).
edge(a,d).
...

Another fact lists all nodes:

nodelist([a,b,c,d,...]).
Note that the graph is directed, so the relation edge need not be symmetric. 

a. (3) Write a predicate chain(+List) that succeeds if the nodes in List form a chain. 
That is, if List = [a1,...,an], then edge(a1,a2) and edge(a2,a3) and ... and edge(an-1,an) are true.
chain([]).
chain([_]).
chain([N1,N2|Nodes]) :- edge(N1, N2), chain([N2|Nodes]).

A Hamiltonian chain is a chain that passes through each node exactly once.

b. (3) Write a predicate hamilton(-NodeList) that returns a Hamiltonian chain, if it exists. The predicate must generate a permutation of the nodes, and test if it is a chain.
hamilton(Chain) :-
   nodelist(Nodes),
   permutation(Nodes, Chain),
   chain(Chain).
You must write select and permutation too, see the compendium.

c. (6) Write a predicate hamilton2(-NodeList) that returns a Hamiltonian chain, if it exists. But this time, write a more efficient solution using standard backtracking.

hamilton2([First|Answer]) :-
   nodelist(Nodes),
   select(First, Nodes, Rest),
   hamilton2(Rest, First, Answer).

% hamilton2(+Nodes, +Now, -Chain)
% is true if Chain is a permutation of Nodes such that [Now|Chain] is a chain.
hamilton2([], _, []).
hamilton2(Nodes, Now, [Next|Answer]) :-
   select(Next, Nodes, Rest),
   edge(Now, Next),
   hamilton2(Rest, Next, Answer).

7 DCGs

Given is the following grammar:
sentence --> np, vp.

np --> det, noun.

vp --> verb.
vp --> verb, np.

det --> [a] ; [the].

noun --> [cat] ; [dog] ; [chair] ; ...

verb --> [likes] ; [eats] ; [sits] ; [sleeps] ; ...

a. (3) How is this DCG translated to Prolog (for the vocabulary, one example is enough)?

sentence(S0,S1) :- np(S0,S2), vp(S2,S1).

np(S0,S1) :- det(S0,S2), noun(S2,S1).

vp(S0,S1) :- verb(S0,S1).
vp(S0,S1) :- verb(S0,S2), np(S2,S1).

det(S0,S1) :- S0=[a|S1] ; S0=[the|S1].

b. (4) We want to add pronouns to our grammar, both as subjects (he, she) and as objects (him, her). We want to recognize correct sentences ("he likes the cat", "the cat likes her", "she likes him"), but refuse incorrect ones ("her likes he"). Modify the grammar to achieve this.

There are several variations, here is one:

sentence --> np_s, vp.

np_s --> det, noun.
np_s --> pron_s.

pron_s --> [he] ; [she].

vp --> verb.
vp --> verb, np_o.
np_o --> det, noun.
np_o --> pron_o.

pron_o --> [him] ; [her].

c. (2) Add a rule for questions of the form "Why does he/the cat  ...?".
(Now the verbs should occur without the "s": like, eat ... - but you can ignore that detail.)
question --> [why, does], sentence.

 b. (5) Modify this grammar to write a predicate correspond(?Statement, ?Question) that is true if the question corresponds to the statement, for example: correspond([he, likes, her], [why, does, he, likes, her]) is true.
The intention of this question was that you pass a parse tree between the sentence and the question.
Unfortunately, I made this two too similar, so the following simple solution works:
correspond(S, [why,does|S]) :- phrase(sentence,S).

8 Higher order predicates

Given is a program defining the relation parent/2 by facts.
parent(erik, anna)
means that erik is the parent of anna.

a. (2) Write a query that returns all children of erik.
findall(C, parent(erik, C), Children).
Using _C is ok, but not necessary. bagof/setfof is ok.

b. (3) Write a query that returns all grandchildren of erik.
findall(GC, (parent(erik, C), parent(C, GC)), GrandChildren). or
bagof(GC, C^(parent(erik, C), parent(C, GC)), GrandChildren).

c. (3) Assume that we also have a relation age/2: for example age(anna, 32).
Write a query that returns all children of erik and their age, sorted by their age.
(You may assume that all children of erik have different names.)

setof(pair(Age,C), (parent(erik, C),age(C, Age)), Pairs).
In order to sort by age, we need to use setof and Age needs to be first in the pair.

?- halt.