Computing Science Department
Information Technology
Uppsala University
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(...)))
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.
| ?- 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).
% 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)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.
|
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)
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).
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.