G6021 Comparative Programming
January 2019 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.
2019 Paper: solution notes
G6021 Comparative Programming
1/15
Question 1a
Consider the Haskell function to compute x y .
power x y = if y==0 then 1 else x*(power x (y-1))
Define what is meant by a tail recursive function, and explain how this relates to Continuation Passing Style (CPS).
Solution notes: Tail recursion: no operations after the recur- sive call. Can be converted into a simple loop. All functions can be converted to tail recursive by using Continuations.
i
2019 Paper: solution notes
G6021 Comparative Programming
2/15
Question 1a
ii
Write a tail recursive version of the function power using an accumulating parameter. State the initial values of any additional parameters.
Solution notes:
poweracc x y z = if y==0 then z
else poweracc x (y-1) (z*x)
The starting values are poweracc x y 1.
2019 Paper: solution notes
G6021 Comparative Programming
3/15
Question 1a
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.
Solution notes:
F = λfint→int→int.λxint.λyint.condint(iszero y) 1 mult x (f x (pred y))
power = fixint→int→intF
2019 Paper: solution notes
G6021 Comparative Programming
4/15
Question 1b
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.
Solution notes:
Parametric polymorphism: operates uniformly across different types. Example: length of list on Haskell.
Subtype polymorphism: operates through an inclusion rela- tion. Example: Object in Java.
Ad-hoc polymorphism is another name for overloading and is about the use of the same name for different functions. Example: + in many programming languages.
2019 Paper: solution notes
G6021 Comparative Programming
5/15
Question 2a
This 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.
Solution notes: There are three redexes in the initial term: I(II)(II)
a
II(II) cc
I(II)I 2
I(II)
III
II
c
I
2019 Paper: solution notes
G6021 Comparative Programming
6/15
‘
‘
2
E
E
2
E
Question 2b
b
Define weak head normal form. Reduce the term WI to weak head normal form using the least number of reductions.
Solution notes:
Weak head normal form: λx.M, where M is any term (if we consider closed terms). WI → λy.Iyy (one reduction is all that is needed).
2019 Paper: solution notes
G6021 Comparative Programming
7/15
Question 2c
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 form.
Solution notes:
A normal form is a term that does not contain any redex. Call-by-name, or a leftmost outermost strategy, guarantees termination.
WI(WI) → (λy.Iyy)(WI) → I(WI)(WI) → WI(WI) (the original term).
Thus this term does not terminate.
2019 Paper: solution notes
G6021 Comparative Programming
8/15
Question 2d
d
Build a typing derivation for the term W .
Solution notes:
The derivation will end with (A → A → B) → A → B. This derivation can be found on the notes on typing.
2019 Paper: solution notes
G6021 Comparative Programming
9/15
Question 2e
e
Does WI have a type? Justify your answer using unification.
Solution notes: No – the term is not typeable.
W : (A → A → B) → A → B, I : C → C.
Occur check: to unify: (A → (A → B)) with C → C, we get A = C and need to unify C → B with C, so we fail because of the occur check.
2019 Paper: solution notes
G6021 Comparative Programming
10/15
Question 3a
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.
Solution notes:
insert x [] n = error “cannot insert to empty list”
insert x (y:ys) n = if n==1 then x:y:ys
else y:(insert x ys (n-1))
insert :: a -> [a] -> Int -> [a]
insert x ys 1 = x:ys
insert x (y:ys) n = y:insert x ys (n-1)
a
2019 Paper: solution notes
G6021 Comparative Programming
11/15
Question 3b
b
Write Prolog clauses to insert an element at a given position into a list, analogous to the Haskell function in Part (a).
Solution notes:
insertAt(I,L,[I|L],1).
insertAt(I,[H|T],[H|T2],X) :-
insertAt(I,T,T2,Y), X is Y+1.
It’s also acceptable (for this module only) to write this using the following pattern matching:
insertAt(I,L,[I|L],1).
insertAt(I,[H|T],[H|T2],X+1) :-
insertAt(I,T,T2,X).
2019 Paper: solution notes
G6021 Comparative Programming
12/15
Question 3c
c
Using your clauses from Part (b), show how to write a query to:
1 insert 20 in the list [5,2,12,8] at position 4;
2 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.
Solution notes:
1 ?insertAt(20,[5,2,12,8],R,4).
2 ?insertAt(20,R,[5,2,12,20,8],4).
2019 Paper: solution notes
G6021 Comparative Programming
13/15
Aside (not required): SLD tree for this example
Let’s give a bit more detail to help understand the this question:
insertAt(I,L,[I|L],1).
insertAt(I,[H|T],[H|T2],X) :-
insertAt(I,T,T2,Y), X is Y+1
insertAt(20, [5, 2, 12, 8], R, 4)
I′ = 20,H′ = 5,T′ = [2,12,8],R = [H′|T2′],X′ = 4
insertAt(20, [2, 12, 8], T2′, 3)
I′′ = 20,H′′ = 2,T′′ = [12,8],T2′ = [H′′|T2′′],X′′ = 3
insertAt(20, [12, 8], T2′′, 2)
I′′′ = 20, H′′′ = 2, T′′′ = [12, 8], T2′′ = [H′′′|T2′′′], X′′′ = 2
insertAt(20, [8], T2′′′, 1)
I′′′′ = 20, L′ = [8], T2′′′ = [I′′′′|L′]
success
Collecting the substitutions, we get: R = [5,2,12,8,20,8].
2019 Paper: solution notes
G6021 Comparative Programming
14/15
Question 3d
d
1 Explain how two functions can be combined using composition. Give the definition and type of the composition function.
2 Explain how two clauses can be combined. Write a clause to illustrate this.
Solution notes:
Functional programs can be combined using composition: comp x y z = x(yz),
comp : (B → C) → (A → B) → (A → C)
Prolog programs be combined by combining relations, for example:
R(A, B), S(B, C)
The “output” of R is unified with the “input” of S.
2019 Paper: solution notes
G6021 Comparative Programming
15/15