Candidate Number
THE UNIVERSITY OF SUSSEX
BSc FINAL YEAR EXAMINATION MComp THIRD YEAR EXAMINATION January 2019 (A1)
Comparative Programming
Assessment Period: January 2019 (A1)
G6021
DO NOT TURN OVER UNTIL INSTRUCTED TO BY THE LEAD INVIGILATOR
Candidates should answer TWO questions out of THREE. If all three questions are attempted only the first two answers will be marked.
The time allowed is TWO hours.
Each question is worth 50 marks.
At the end of the examination the question paper and any answer books/answer sheets, used or unused, will be collected from you before you leave the examination room.
G6021 Comparative Programming
1. (a) Consider the Haskell function to compute xy.
power x y = if y==0 then 1 else x*(power x (y-1))
i. Define what is meant by a tail recursive function, and explain how this relates to Continuation Passing Style (CPS). [10 marks]
ii. Write a tail recursive version of the function power using an accumulating parameter. State the initial values of any additional parameters. [10 marks]
iii. Write the function power as the fixed point of a functional. Use the syntax of PCF (Programming Language for Computable Functions), and include types in your answer. [20 marks]
(b) Explain and compare the following: parametric polymorphism, subtype polymorphism and ad-hoc polymorphism. Give a small example of each
to help illustrate your answer.
[10 marks]
2
2. This (a)
(b) (c)
(d) (e)
Comparative Programming G6021
question uses the ¦Ë-terms: I = ¦Ëx.x and W = ¦Ëxy.xyy.
Draw the reduction graph starting from the term I(II)(II). Underline all
redexes in the graph. [10 marks]
Define weak head normal form. Reduce the term WI to weak head normal form using the least number of reductions. [10 marks]
Define normal form. Which reduction strategy guarantees termination if a normal form exists? Illustrate your answer by showing a reduction sequence of the term WI(WI), and thus deduce if this term has a normal form. [10 marks]
Build a typing derivation for the term W . [12 marks] Does W I have a type? Justify your answer using unification. [8 marks]
3 Turn over/
G6021
3. (a)
Comparative Programming
Write a function in Haskell to insert an element at a given position into a list. For example:
insert 20 [5,2,12,8] 4
should insert the number 20 at the 4th position in the list [5, 2, 12, 8] to give:
[5,2,12,20,8]
Your answer should not use any library functions. Include the type of the function in your answer. [15 marks]
Write Prolog clauses to insert an element at a given position into a list, analogous to the Haskell function in Part (a). [15 marks]
Using your clauses from Part (b), show how to write a query to:
i. insert 20 in the list [5,2,12,8] at position 4;
ii. remove 20 in the list [5,2,12,20,8] at position 4
Note: you do not need to complete Part (b) to get full marks for this question. [10 marks]
(b) (c)
(d) i.
Explain how two functions can be combined using composition. Give the definition and type of the composition function.
ii. Explain how two clauses can be combined. Write a clause to illustrate this.
[10 marks]
4 End of Paper