G6021: Comparative Programming
Some Prolog related questions
1. This question is about comparing paradigms for adding an element at the end of a list.
(a) Consider the following logic program defining the insertion of an element at the end of a list.
insert(X,[],[X]).
insert(X,[S1|S],[S1|S2]) :- insert(X,S,S2).
Draw the SLD-resolution tree for the query:
:- insert(1,[2],Y).
State all answers that Prolog can find for the query above.
Answer:
:- insert(1,[2],Y)
X=1, S1=2, S=[], Y=[S1|S2]=[2|S2]
:- insert(1,[],S2)
succeeds with: X=1, S2=[X]=[1]
Putting all the substitutions together, we have: Y=[2,1]
There is only one branch leading to success, Prolog finds only one answer.
(b) Write a Prolog query/clauses to give a list with the last element removed (use the list
[1,2,3,4,5] as an example). Answer:
:- insert(_,X,[1,2,3,4,5])
(c) Write a Prolog query/clauses to give the last element in a given list (again, use the list [1,2,3,4,5] as an example).
Answer:
:- insert(X,_,[1,2,3,4,5])
(d) Write a polymorphic Haskell function to add an element at the end of a list. Include in your answer:
• The type of your function.
• A reduction graph of insert 2 [1].
Answer:
insert :: t -> [t] -> [t]
insert n [] = [n]
insert n (h:t) = h:(insert n t)
insert 2 [1] -> 1:(insert 2 []) -> 1:[2] = [1,2]
1
(e) Write two Haskell functions: one find the last element of a list, and another to return a given list with the last element removed.
Answer: Left as an exercise. Observe that there is more work to do here than was needed for the Prolog versions above.
2. In the Rock-Paper-Scissors game, the rules are that paper beats rock, rock beats scissors, and scissors beats paper.
(a) Define a type RPS to represent rock, paper and scissors as used in the game in both Haskell and Java. In no more that 10 sentences, compare the two.
Answer:
data RPS = Rock | Paper | Scissors deriving (Show)
class RPS {}
class Rock extends RPS {}
class Paper extends RPS {}
class Scissors extends RPS {}
Haskell: disjoint union types are directly implementable as shown. Types are immediately available (both input and output).
Java: need to use the object stricture. Each class in separate file makes main- tenance of methods more difficult. More verbose than Haskell. Quite a lot of effort needed to build objects of this new type to test code, etc.
(b) Write a function in Haskell: beats :: RPS -> RPS -> Bool that encodes that paper beats rock, rock beats scissors, and scissors beats paper.
Answer:
beats :: RPS -> RPS -> Bool
beats Paper Rock = True
beats Rock Scissors = True
beats Scissors Paper = True
beats _ _ = False
(c) Write beats using Prolog clauses.
Answer:
beats(paper,rock)
beats(rock,scissors)
beats(scissors,paper)
2
3. (a) What is the purpose of the occur-check in the unification algorithm?
Answer: The occur-check is a test that checks whether a variable X occurs in a term t. If it occurs it causes a failure of the unification algorithm, to avoid self-referential bindings (such as X → f(X)).
(b) Consider the following program and queries:
even(0).
even(s(s(X))) :- even(X).
odd(s(0)).
odd(X) :- even(s(X)).
:- odd(s(0)).
:- even(s(s(0))).
Write an SLD-resolution tree for each query using the computation rule that always selects the leftmost literal as the one resolved upon.
Answer:
odd(s(0)) /\
SUCCESS even(s(s(0)) .
even(s(s(0)))
|
even(0)
|
SUCCESS
(c) We now replace the fourth clause of the program by:
odd(X) :- greater(X,s(0)), even(s(X)).
Write the clauses defining the predicate greater such that greater(m,n) holds when the number m is greater than n. Give the SLD-tree for the query :-odd(s(0)) with the modified program.
Answer:
greater(s(X),0).
greater(s(X),s(Y)) :- greater(X,Y). The SLD-tree is now:
odd(s(0)) /\
SUCCESS
greater(s(0),s(0)),even(s(s(0)))
|
greater(0,0),even(s(s(0)))
|
FAIL
3