1. (a)
Comparative Programming
January 2019 Paper
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. This question uses the ¦Ë-terms: I = ¦Ëx.x and W = ¦Ëxy.xyy.
(a) Draw the reduction graph starting from the term I(II)(II). Underline all
redexes in the graph. [10 marks]
(b) Define weak head normal form. Reduce the term W I to weak head normal form using the least number of reductions. [10 marks]
(c) 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
3. (a)
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]
form.
(d) Build a typing derivation for the term W .
(e) Does WI have a type? Justify your answer using unification.
[10 marks] [12 marks] [8 marks]
1
G6021
(b) (c)
(d)
Comparative Programming
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]
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]
2 End of Paper