CPSC 312 2024 - 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.) You may bring in one sheet of letter-sized paper with anything you like on it. E.g., a photo of your pet, example programs, things you tend to forget,... Anything you like. 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. But you should expect these to be applied to problems you have never seen. 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,2024,mid1,41) meaning student s12345 got 41 on the first midterm of CPSC 312 in 2024 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= Maybe (BSTree k v) 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/ https://www.cs.nmsu.edu/ALP/2011/03/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?