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.
(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).
(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).
(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].
(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.
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.
(b) Write a function in Haskell: beats :: RPS -> RPS -> Bool that encodes that paper beats rock, rock beats scissors, and scissors beats paper.
(c) Write beats using Prolog clauses.
1
3. (a) What is the purpose of the occur-check in the unification algorithm? (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.
(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.
2