Prolog Supervision Work

Specify the rules Prolog uses for unification.

Does the following unify, and what substitutions does it have? What is the fully unified term? tree(C,tree(Z,C)) and tree(tree(tree(1,2),A,B),tree(C,tree(E,F,G)))

Describe the possibilities of unifying a(A) with A, and the advantages of each. How does unification relate to type-inference as found in Standard ML? What would be the term with a type that would involve unifying a(A) with A?

Can you implement making change, from your ML course?

?- change(20, [8, 5, 3], X).
X = [8, 3, 3, 3, 3] ;
X = [5, 5, 5, 5] ;
X = [5, 3, 3, 3, 3, 3] ;

1. Consider the implementation of append given below. Explain how it should be used and draw out a search tree for a representative example.

   append([],A,A).
   append([H|T],A,[H|R]) :- append(T,A,R).
   

2. You are given two implementations of member

   member(H,[H|_]).
   member(H,[_|T]) :- member(H,T).
   % or, alternatively
   member(X,Y) :- append(_,[X|_],Y).
   

   1. Discuss how the second implementation compares with the use of 'partial application' from functional programming, and how it differs.
   2. If the two implementations are equivalent, should a programmer simply inline all calls to member with a call to append?
   3. If the two implementations are equivalent, what advantages does one form of expression have over the other?
   4. Prove (informally) why the two are logically equivalent.

What is the purpose of the following clauses:

a([]).
a([H|T]) :- a(T,H).
a([],_).
a([H|T],Prev) :- H >= Prev, a(T,H).

What does the following do and how does it work?

b(X,X) :- a(X).
b(X,Y) :- append(A,[H1,H2|B],X), H1 > H2, append(A,[H2,H1|B],X1), b(X1,Y).

Given the following clauses,

a(4).
a(x).
b(3,x).
b(1,7).
c(A, B, C) :- a(A), b(B, _), !, a(D).
c(A, _, B) :- b(A, B).

1. List the solutions reported by Prolog to the query c(P, Q, R), for each giving any binding of variables that occurs. [2 marks]
2. Explain whether the query c(P, Q, R) can bind P to x. [1 mark]
3. List the solutions to the query c(1, 6, R), for each giving any binding of variables that occurs. [1 mark]

We represent a binary tree using a term of the form [Left,NodeName,Right] or null. Here is an example perhaps recording a tree of excursions between countries:

[[null,de,null],uk,[[null,ua,null],pt,null]]

Write a predicate p(+Tree, +NNames, -Ps) where Tree is a tree as above, NNames is a list of node names, and Ps is to be unified with a list of elements of the form [N,P] where N is in NNames and P is N’s parent in Tree. [For example, supposing T is bound to the above tree, the query p(T, [ua, za], Ps) binds Ps to [[ua, pt]].] [5 marks]

Recall question 7 from supervision 1. If you have access to my implementation of the answer, you might like to consider that code (it recurs first on the tree, then the list).

We represent a binary tree using a term of the form [Left,NodeName,Right] or null. Here is an example perhaps recording a tree of excursions between countries:

[[null,de,null],uk,[[null,ua,null],pt,null]]

Write a predicate p(+Tree, +NNames, -Ps) where Tree is a tree as above, NNames is a list of node names, and Ps is to be unified with a list of elements of the form [N,P] where N is in NNames and P is N’s parent in Tree. [For example, supposing T is bound to the above tree, the query p(T, [ua, za], Ps) binds Ps to [[ua, pt]].] [5 marks]

1. Difference lists are a powerful tool for increasing efficiency but they address a very specific problem. Does this issue arise in your implementation of p/3? In other words, can p/3 be made more efficient using difference lists and why (or why not)? You should also look at my answer to the previous question (if I have e-mailed my answers out to you.) [2 marks]
2. Regardless of your answer above, write a predicate pdl/3 that behaves just like p/3 but uses difference lists in its implementation. [4 marks]

A binary tree has nodes whose values are non-empty lists. A tree node is represented using a term that takes the form Left-SomeList+Right or nil (note that parentheses can be used to enforce precedence). For example, the following term would be a valid tree:

nil-[root,1,2]+(nil-[child,4]+nil)

1. Write a predicate preorder(+Tree,-ValueList) that unifies ValueList with a list containing all of the tree nodes’ values from a pre-order tree walk (i.e. emit node value, then left subtree, then right subtree). The predicate should fail if any of the tree nodes’ values are not of the correct form. For the above example tree, preorder/2 would unify ValueList with [[root,1,2],[child,4]]. You may assume that append/3 has been defined already. [6 marks]
2. Now write a predicate preorderdl/2 that behaves exactly like your preorder/2 predicate (i.e. returns a normal list), but in its implementation makes use of difference lists, instead of querying append/3. [6 marks]

1. Consider the predicate p/4 defined as:

   p(_,[],[],[]).
   p(P,[X|Xs],[X|L1],L2) :- X < P, p(P,Xs,L1,L2).
   p(P,[X|Xs],L1,[X|L2]) :- X >= P, p(P,Xs,L1,L2).
   

   1. What does p/4 do? Show an example query and response. [2 marks]
   2. What types of terms cannot be used as the first p/4 argument? [2 marks]
   3. Describe where and why red and green cuts can be usefully employed within the p/4 predicate, modifying the predicate if necessary. [3 marks]

   4. The quicksort algorithm requires selection of a pivot value, forming two sublists, and then building the sorted list from the results of recursively quicksorting the sublists. The first sublist contains all elements that are less than the pivot value. The second contains the remaining elements.

      Implement quicksort in a predicate qs(+In,-Out) that binds Out to a sorted version of the list In, and uses the p/4 predicate above. Assume that In only contains numbers. Do not optimise your choice of pivot value: just use the head of the input list. [5 marks]

2. The predicate flatten(+In,-Out) is defined to expect that In be unified with a list that may contain elements that are themselves lists (and likewise for those lists, up to any depth). In such cases, Out is unified with a list that never has elements that are lists—all lists are expanded in place. For example, flatten([1,2,[3,4],[[5],6]],[1,2,3,4,5,6]) would be true.

   Implement the flatten/2 predicate. When given a valid query, your solution should not provide any spurious results. [6 marks]

In this question you should ensure that your predicates behave appropriately with backtracking and avoid over-use of cut. You should provide an implementation of any library predicates used. You may not make use of extra-logical built-in predicates such as findAll. Minor syntactic errors will not be penalised.

1. Rewrite choose without using cut. [2 marks]

   choose(0,_,[]) :- !.
   choose(N,[H|T],[H|R]) :- M is N-1, choose(M,T,R).
   choose(N,[_|T],R) :- choose(N,T,R).
   

2. Explain the operation of not (also written as \+) in a Prolog program. [1 mark]

3. Rewrite chooseAll without using not and cut (!). [10 marks]

   chooseAll(N,L,Res) :- chooseAll(N,L,[],Res).
   chooseAll(N,L,Seen,Res) :- choose(N,L,R),
                              not(member(R,Seen)), !,
                              chooseAll(N,L,[R|Seen],Res).
   chooseAll(_,_,Res,Res).
   

4. What is Last Call Optimisation and why is it beneficial? [3 marks]

5. Rewrite pos to enable Last Call Optimisation. [2 marks]

   pos([],[]).
   pos([H|T],[H|R]) :- H >= 0, pos(T,R).
   pos([H|T],R) :- H < 0, pos(T,R).
   

Solve the following constraint satisfaction problems using a constraint logic programming library. (You could solve it without the library, but why make your task more difficult).

1. Assign colours red, green, and blue to each of the nodes, so that no two connected nodes have the same colour.

   graph G {
     /* Graphing settings */
     layout=neato;
     splines=true;
     node [shape=circle];
   
     /* The edges, so that you can easily encode them with search&replace */
     1 -- 2; 1 -- 3; 1 -- 6;
     2 -- 6;
     3 -- 6; 3 -- 8; 3 -- 9;
     4 -- 5; 4 -- 6; 4 -- 9;
     5 -- 8; 5 -- 9; 5 -- 10;
     6 -- 7; 6 -- 10;
     7 -- 8;
     /* The len=2 is just for the graphing software */
     8 -- 9 [len=2];
   }
   

2. For each edge, how many solutions are there, if you remove that edge? Ignore permutations of existing solutions (e.g. ignore replacing all red with blue, blue with green, and green with red, and the like).

   You might find findall(+Template, :Goal, -Bag) useful, e.g.

   ?- member(X, [1,2,3,4,5]), 0 is X mod 2. % Find even numbers
   % X = 2 ;
   % X = 4 ;
   
   ?- findall(X, (member(X, [1,2,3,4,5]), 0 is X mod 2), Evens).
   % Evens = [2, 4].
   

   It is an extra-logical predicate, and it might not always be allowed in the exam though.