CPSC 312 2021 – Final Exam Practice Questions
This exam will cover both Logic and Functional Programming (so that all of the exams put together will cover both topics approximately equally).
You will be given any predefined functions/predicates you need (but
you will need to know Prolog’s syntax, and Haskel’s syntax including
lambda, list constructors (: and []), tuple constructors, etc.)
Everything in the exam has been covered in lectures and/or assignments
and/or on Canvas and/or in projects
See the schedule for the sections of Textbooks covered.
See the practice midterms (and the actual midterms) for practice
questions. Here we will give some questions that were not in the
practice midterms. Also try the Haskell questions in Prolog and the
Prolog questions in Haskell.
The exam will be worth 120 marks. This is designed to be a mark per
minute, so 4 marks does *not* mean we expect 4 points.
The most important part is to read and answer the questions
asked. Writing true but irrelevant points will not give you extra
marks. Marks will be deducted if you write false statements, even if
you also gave a full and complete answer.
If you are asked to explain something, explain why it is like
that. (E.g., in the question in the 1st midterm, that asked to explain
something like Num a in
sum :: Num a => [a] -> a
you needed to explain why it was like this, and not just as if it was
sum :: [Num] -> Num
which is not legal Haskell. Particularly as it was worth 4 marks.)
There are many more questions here than would be asked in an exam. To
see the level of difficulty of an exam, see the posted past exam.
Question 1 (Prolog Programming)
a) [7 marks] Define zip(L1,L2,R) that is true if R consists of a list of pairs, such that
zip([e1,e2,…,ek],[f1,f2,..fn],[(e1,f1),(e2,f2),…,(er,fr)]) where r = min(k,n).
This should only ever have one answer. You may not use any built-ins
except you may use dif.
(b) [5 marks] Define notin(E,L) that is true if E is not a member of
L. This should not use negation as failure, but can use ‘dif’.
(c) [7 marks] Define apply(L,S,R) where L is a list of constants, S is
a list of terms of the form sub(X,Y) where X and Y are constants (and
no two elements have the same X-value), is true when R is the same as
L, but with X replaced by Y for each sub(X,Y) in L. You can use a
helper function if it helps. You can only use dif as a built-in.
For example, apply([a,b,c,d,e,c],[sub(a,f), sub(c,3), sub(f,7)],R) has
the unique answer R=[f,b,3,d,e,3]
(c’) Do the same a (c) but where L is an arithmetic expression (and so
is R); assume that an arithmetic expression uses on * and +. You can only use atomic and dif as built-ins.
apply(a+b*c*d+e*c,[sub(a,f), sub(c,3), sub(f,7)],R) has the unique
anwser R=f+b*3*d+e*3
(d) [7 marks] Define deln(N,E,L,R) which is true when R is the result of removing N instances of E from L.
for example, deln(2,a,[a,v,a,t,a,r],R) has as answers R=[v,t,a,r], R=[v,a,t,r], R=[a,v,t,r]
it should fail if there are not N instances of E in L.
(e) [5 marks] Write a predicate that is true a person who is enrolled in a
computer science course and is not enrolled in a 3rd-year math
course. It can use negation as failue, but no built-in predicates.
(f) [5 marks] Write the procedure can_enrol(X,cpsc330) where the prerequisite
structure of CPSC 330is given in
http://www.calendar.ubc.ca/vancouver/courses.cfm?code=CPSC You can
use whatever predicates you like as long as you explain them. (Of
course, in the exam, you will be given the description).
Question 2
Unification:
For each of the following pairs of atoms, either give a most general
unifier or say why one does not exist (3 marks each):
(a) np([dog,ate,seven,grapes],R,X) and np([dog|L],L,fido)
(b) p(X,Y,X) and p(Z,Z,c)
(c) p(X,Y,X) and p(a,b,c)
(d) bar(f(X),g(g(b))) and bar(W,g(Y))
(e) foo(Z, [a,z|X],X) and foo([a,m|W],W,[i,n,g])
(f) dl([a,b|X],X) and dl(Z,Z).
Question 3
Given a logic program and a query, give a top-down proof. [Read the
question carefully to see if we want substitutions.] Try it for any
of the programs you have written (with say 3-6 steps in the
proof). E.g., given the program
above(X,Y) :- on(X,Z), above(Z,Y).
above(X,Y) :- on(X,Y).
on(a,b).
on(b,c).
on(c,d).
on(e,d).
on(d,f).
Give a top-down derivation for the first answer that Prolog finds to
the query:
?- above(X,d).
At each step, show the answer clause, the renamed clause chosen, and
the mgu. Show the answer produced.
Question 4
Convert the following to triples (use RDF/RFDS type, subClassOf, domain, range as appropriate)
course(cpsc312) CPSC 312 is a course
only students can get grades, and students only get grades in courses
grade(s12345,cpsc312,2017,mid1,41) meaning s12345 got 41 on the first midterm of CPSC 312 in 2017
student(s12345,”Sam”,”Family”,1995,10,21) meaning s12345 is a student named Sam Family who was born on October 21, 1995.
Question 5
Given a program in Prolog, write the Haskell version or the the other
way around.
(a) given the Prolog program
del1(E,[E|R],R).
del1(E,[H|T],[H|R]) :-
del1(E,T,R).
(i) Write a Haskell program that gives the same answer as Prolog’s first
answer.
(ii) Write a Haskell program that gives a list of all of the answers that
Prolog produces.
(iii) What can the Prolog program do that the Haskell program cannot?
Give a specific example.
(iv) What can the Haskell program do that the Prolog program cannot?
Give a specific example
(b) Given the Haskell program, write the corresponding Prolog program:
— myremoveduplicates lst removes duplicates from a list; returns a list with
— the same elements as lst, but with only one instance of each element
myremoveduplicates :: Eq t => [t] -> [t]
myremoveduplicates [] = []
myremoveduplicates (e1:r)
| elem e1 r = myremoveduplicates r
| otherwise = e1 : myremoveduplicates r
myremoveduplicatesfirst :: Eq t => [t] -> [t]
myremoveduplicatesfirst lst = remdupfirst lst []
where
— remdupfirst lst1 lst2 returns the elements in lst1 without duplicates that are not in lst2
remdupfirst [] _ = []
remdupfirst (h:t) lst2
| h `elem` lst2 = remdupfirst t lst2
| otherwise = h : remdupfirst t (h:lst2)
(c) Given shuffle in Prolog
shuffle([],[],[]).
shuffle([H|T],L,[H|R]) :- shuffle(T,L,R).
shuffle(T,[H|L],[H|R]) :- shuffle(T,L,R).
Try the query ?- shuffle([1,2,3],[5,6,7],S).
Write shuffle in Haskell. Hint: think about what it should return.
What can the Prolog version do that the Haskell version cannot?
Question 6
Suppose David tried to mix logic and functional programming in Prolog using the predicates
% def(F,A,FA) function F on argument A returns FA
def(sq,X,X2) :- X2 is X*X.
def(plus,X,plus(X)).
def(plus(X),Y,Z) :- Z is X+Y.
def(gt,X,gt(X)). % gt(X) is \Y -> X>Y
def(gt(X),Y,true) :- X>Y. % this would be (x>) in Halskell
def(gt(X),Y,false) :- X =< Y.
% eval(E,V) is true if expression E evaluates to V
% this uses square brackets as parentheses, values separated by commas
eval(N,N) :- number(N).
eval([V],V).
eval([P,A|R],V) :-
eval(A,AV),
def(P,AV,R1),
eval([R1|R],V).
% eval([sq,[plus,3,7]],V). % evaluates to 100
Define
mapWhile(F,P,[X1,X2,...,Xn]) = [f X1,f X2,...,f Xk]
where k is the largest index such that P Xi is true for all i=
that returns the left tree if it exists and Nothing otherwise.
Write the corresponding Prolog program.
(d) Why doesn’t Prolog need a constructor that corresponds to Just?
(e) Write a Prolog programs
insert(K,V,T0,T1)
that inserts key K with value V into tree T0 giving tree T1.
You can use the Prolog predicate < that is true if its left argument
is less than its right.
(f) Write a Prolog program that corresponds to the Haskell program
(use the same names for the corresponding variables and constructors as
much as possible):
-- tolist without append (++), using accumulators
tolista :: BSTree k v -> [(k,v)]
tolista lst =
tolist2 lst []
— tolist2 tree lst returns the the list of elements of tree followed by the elements of lst
tolist2 :: BSTree k v -> [(k,v)] -> [(k,v)]
tolist2 Empty acc = acc
tolist2 (Node key val lt rt) acc =
tolist2 lt ((key,val) : tolist2 rt acc)
Question 9
Based on the posts on Canvas
(e.g.,
https://code.facebook.com/posts/745068642270222/fighting-spam-with-haskell/
Natural Language Processing With Prolog in the IBM Watson System
)
(a) What is the main advantage of strong typing?
(b) What is an advantage of interactive development?
(c) What is an advantage of Haskell over Prolog?
(d) What is an advantage of Prolog over Haskell?