G6021 Comparative Programming
January 2018 Paper: Solution notes
These notes contain full solutions to some parts, but not all. These are not inteded to be model answers: consider them to be hints to help you answer these questions.
2018 Paper: solution notes
G6021 Comparative Programming
1/14
Question 1a
Given the λ-terms: I = λx.x, T = λx.xIII and U = λzy.y(λx.xz):
Write the λ-term TU out in full (without abbreviations, and including ALL brackets).
Solution notes:
TU = (λx.xIII)(λzy.y(λx.xz))
First expand λzy… to λz.λy… and put all the brackets in:
((λx .((xI )I )I )(λz .(λy .(y (λx .(xz )))))) Finally, expand I to (λx.x):
((λx .((x (λx .x ))(λx .x ))(λx .x ))(λz .(λy .(y (λx .(xz ))))))
It’s possible to write the last line directly, but showing some working is advised in case mistakes are made.
a
2018 Paper: solution notes
G6021 Comparative Programming
2/14
Question 1b
b
Draw the β-reduction graph of the λ-term TU.
Solution notes: There is only one reduction at each step:
TU = (λx.xIII)(λzy.y(λx.xz))
→ (λzy .y (λx .xz ))III → (λy .y (λx .xI ))II → I(λx.xI)I
→ (λx .xI )I
→ II →I
Can you underline each redex?
2018 Paper: solution notes
G6021 Comparative Programming
3/14
Question 1c
c
By building a type derivation, find the type of the term U. Solution notes: Let T = ((A → B) → B) → C in the following:
z : A,y : T,x : A → B ⊢ x : A → B z : A,y : T,x : A → B ⊢ z : A z : A,y : T,x : A → B ⊢ xz : B
z : A,y : T ⊢ y : T z : A,y : T ⊢ λx.xz : (A → B) → B z : A,y : T ⊢ y(λx.xz) : C
z : A ⊢ λy.y(λx.xz) : (((A → B) → B) → C) → C
⊢ λzy.y(λx.xz) : A → (((A → B) → B) → C) → C
2018 Paper: solution notes
G6021 Comparative Programming
4/14
Question 1d
d
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.
Solution notes:
pair = λuvx.xuv,
fst = λx.x(λxy.x),
snd = λx.x(λxy.y).
(T,U) = pairTU = λx.xTU
Test if this works: fst(T,U) should reduce to T, for example.
2018 Paper: solution notes
G6021 Comparative Programming
5/14
Question 2a
a
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.
Solution notes:
rev :: [a] -> [a] -> [a]
rev [] acc = acc
rev (x:s) acc = rev s (x:acc)
called with rev l []
2018 Paper: solution notes
G6021 Comparative Programming
6/14
Question 2b
b
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.
Solution notes:
equal::Eqa=>[a]->[a] ->Bool
equal [] [] = True
equal (x:s) [] = False
equal [] (y:p) = False
equal (x:s)(y:p) = (x == y) && (equal s p)
2018 Paper: solution notes
G6021 Comparative Programming
7/14
Question 2b
b
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.
Solution notes: Application of ideas developed in previous parts.
palindrome :: [a] -> Bool
palindrome l = equal l (rev l [])
2018 Paper: solution notes
G6021 Comparative Programming
8/14
Question 2c
c
Write a set of Prolog clauses that can be used to test if a list is a palindrome. State clearly what your predicates represent.
Solution notes: A number of answers possible, for instance: palindrome(X) :- reverse(X,[],X).
reverse([],X,X).
reverse([X|Y],Z,T) :- reverse(Y,[X|Z],T).
2018 Paper: solution notes
G6021 Comparative Programming
9/14
Question 2d
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].
Solution notes: Here is the case for success. Try to do the other (it should fail).
palindrome([1, 0, 1]) c
reverse([1, 0, 1], [], [1, 0, 1]) c
reverse([0, 1], [1], [1, 0, 1]) c
reverse([1], [0, 1], [1, 0, 1]) c
reverse([], [1, 0, 1], [1, 0, 1]) c
Success Can you put the substitutions in?
d
2018 Paper: solution notes
G6021 Comparative Programming
10/14
Question 3a
a
Explain the concept of dynamic lookup. To what extent is this concept related to overloading?
Solution notes:
Dynamic Lookup: when a message is sent to an object, the method executed is determined by the object implementation. Different objects can respond differently to the same message. The response is not based on the static property of the variable or pointer.
Related to overloading to some extent, but overloading is a static concept: it is the static type information that dictates which code is executed.
2018 Paper: solution notes
G6021 Comparative Programming
11/14
Question 3b
a
Explain the main problem associated with multiple inheritance, and possible solutions to this problem. Provide examples to support your explanations.
Solution notes:
The example should exhibit name clashes (a simple example will suffice).
Possible solutions:
Implicit resolution, defined by language semantics. Explicit resolution, i.e. programmer decides. Disallow multiple inheritance in the language.
2018 Paper: solution notes
G6021 Comparative Programming
12/14
Question 3c
c
Explain how to write the Haskell function
f x = if x==0 then 1 else x*f(x-1)
as the fixed point of a functional. Use the syntax of PCF, and include types in your answer.
Solution notes:
fix λf int→int .λx int .cond (iszero x ) 1mult x (f (pred x )) int→int int
2018 Paper: solution notes
G6021 Comparative Programming
13/14
Question 3d
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).
Solution notes: The idea of CPS is that every function takes an extra argument: a continuation. A continuation is a function which consumes the result of a function, and produces the final answer. Thus, a continuation represents the remainder of the current computation.
CPS form:
factcps n k = if n==0 then k 1
else factcps (n-1) (\r -> k (n*r))
factcps 4 (\x -> x)
We can simplify the continuation:
factacc n acc = if n==0 then acc
else factacc (n-1) (n*acc)
factacc 4 1
which can then be compiled as a loop (tail recursive).
d
2018 Paper: solution notes
G6021 Comparative Programming
14/14