Comparative Programming
January 2018 Paper
1. Given the ¦Ë-terms: I = ¦Ëx.x, T = ¦Ëx.xIII and U = ¦Ëzy.y(¦Ëx.xz):
(a)
(b) (c) (d)
2. (a)
(b)
(c)
(d) (e)
3. (a) (b)
(c)
Write the ¦Ë-term TU out in full (without abbreviations, and including
ALL brackets).
Draw the ¦Â-reduction graph of the ¦Ë-term TU.
By building a type derivation, find the type of the term U.
[5 marks] [10 marks] [25 marks]
For ¦Ë-terms X and Y , explain how the pair (X, Y ) can be represented as a ¦Ë-term. Include in your answer ¦Ë-terms to build and to project each component of a pair. Write (T,U) in your chosen encoding. [10 marks]
Write a function rev in Haskell syntax that uses an accumulating parameter to reverse a list. Include the type of your function in your answer. [10 marks]
Write a function equal in Haskell syntax that takes two lists of elements (where each element has a type that is an instance of the Eq class) and checks whether they are equal (i.e., returns True if they have exactly the same elements in the same order, False otherwise). Give the most general (polymorphic) type for equal. [10 marks]
Using equal and rev write a function palindrome that checks whether a list is a palindrome. A list is a palindrome if the list is the same in reverse. The lists [1,0,0,1], [True, False, True] and [0,1,2,3,3,2,1,0] are examples of palindromes. [10 marks]
WriteasetofPrologclausesthatcanbeusedtotestifalistisapalindrome. State clearly what your predicates represent. [10 marks]
Using your answer to part (d), give two example SLD trees to demonstrate your clauses, using the lists: [1,0,1] and [1,0,0]. [10 marks]
Explain the concept of dynamic lookup. To what extent is this concept related to overloading? [10 marks]
Explain the main problem associated with multiple inheritance, and possible solutions to this problem. Provide examples to support your explanations. [15 marks]
Explain how to write the Haskell function
f x = if x==0 then 1 else x*f(x-1)
1
G6021 Comparative Programming
as the fixed point of a functional. Use the syntax of PCF, and include types in your answer. [10 marks]
(d) Define CPS, and explain how to convert the Haskell function:
f x = if x==0 then 1 else x*f(x-1)
so that it can compiled into a loop (i.e., without recursion). [15 marks]
2 End of Paper