Comparative Programming: 2020 Paper
1. (a) Define multiple inheritance and state any problems associated with this concept. Briefly show how these problems can be circumvented, using examples to support your argu- ment. [10 marks]
(b) •
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.
Describe briefly the call-by-name and call-by-value strategies of evaluation of func- tions, highlighting the differences between them. [5 marks]
Solution notes:
The call-by-name strategy attempts to evaluate an expression by using the definition of a function first and then evaluating its arguments if neces- sary. The call-by-value strategy on the other hand will first evaluate the arguments of the function, before applying its definition.
• Consider the two functions zero and loop below: zero :: Integer -> Integer
zero x = 0
loop :: Integer -> Integer
loop x = loop (x + 1)
What would happen if the expression zero (loop 10) were to be evaluated us-
ing
each of the call-by-name and call-by-value strategies? Justify your answer. [5 marks]
Solution notes:
If call-by-value were to be used, the expression loop 10 would be evalu- ated first, but this never terminates, so zero (loop 10) would also not terminate. If call-by-name is used, then the definition of zero n would be used first. This is independent of the value of n, so the expression would be evaluated as 0.
(c) Consider the following definition of the function iterate_until: iterate_until p f x = if (p (f x)) then (f x)
(d)
To type the function we need to compute a type for each argument and a type for the result and build an arrow type. The full type is:
iterate_until:: (α→Bool)→(α→α)→α→α
i. Define a non-terminating term in PCF, and include types in your answer. Can you define such a term in the pure lambda calculus and in the simply typed lambda-
else iterate_until p f (f x)
Give the most general type for this function.
Solution notes:
[10 marks]
calculus?
[10 marks]
1
Solution notes:
PCF term: fix(λx.x). Fix has type (A → A) → A where in this case, A = B → B.
A non-terminating term in the pure calculus: (λx.xx)(λx.xx)
It is not possible to define such a term in the typed calculus.
ii. Show how to define the function iterate_until (given in Part 1(c)) as the fix point of a functional in PCF. [10 marks]
Solution notes:
F = λhpfx.cond(p(fx)) (fx) (h p f (fx)) Then the we have: iterate_until = fix F
2
2. (a)
Consider the λ-term t = vw(λxy.vx).
i. Write t in full, inserting all the missing parentheses and λ’s.
ii. List the free variables and bound variables of t. Solution notes:
((vw)(λx.(λy.(vx))))
Free variables: {v, w}. Bound variables: {x, y}.
(b) Give the β-reduction graph of the λ-term (λxy.x)(II)I, where I = λx.x. Underline all
redexes in the graph.
Solution notes:
[15 marks]
(λxy.x)(II)I E (λxy.x)II cc
(λy.II)I E (λy.I)I cc
II EI
[10 marks]
(c) Define and explain the term disagreement set as used in the unification algorithm as part of the algorithm for type reconstruction. Include in your answer an example to illustrate the concept. [10 marks]
Solution notes: Bookwork – this question is covered in the notes. D(τ,τ′) = ∅(ifτ=τ′)
= {(σ,σ′)}
where σ,σ′ are the first two subterms at which τ,τ′ disagree, using depth first
comparison. Some examples are:
D(α→β,α→β)
D(σ → τ,α → β)
D(int,α → β)
D((int → int) → int,α → β)
= ∅
= {(σ,α)}
= {(int,α → β)} = {(int → int,α)}
(d) Build a type derivation to find the type of λx.(λy.y)x. Solution notes:
x : A, y : A ⊢ y : A
x : A ⊢ λy.y : A → A x : A ⊢ x : A
x : A ⊢ (λy.y)x : A ⊢ λx.(λy.y)x : A → A
[15 marks]
3
3. This question is about comparing paradigms for adding an element at the end of a list.
(a) Consider the following logic program defining the insertion of an element at the end of a list.
insert(X,[],[X]).
insert(X,[S1|S],[S1|S2]) :- insert(X,S,S2).
Draw the SLD-resolution tree for the query:
:- insert(1,[2],Y).
Indicate the answers that Prolog finds for the query above.
Solution notes:
[15 marks]
The SLD-tree for this query has the query as root, and then one branch for the resolvent
:- insert(1,[],S2)
which terminates successfully with the answer Y = [2,1].
There is only one branch leading to success, Prolog finds only one answer.
(b) Write a polymorphic Haskell function insert to add an element at the end of a list. Include in your answer:
• The type of your function.
• A reduction graph of insert 2 [1].
Solution notes:
insert :: t -> [t] -> [t]
insert n [] = [n]
insert n (h:t) = h:(insert h t)
insert 2 [1] -> 1:(insert 2 []) -> 1:[2] = [1,2]
[15 marks]
(c) Compare the different paradigms studied in this module for adding an element to the end of a list. Your answer should incorporate features of different paradigms such as Prolog difference lists, accumulating parameters, objects, and any other appropriate concept to justify your answer. [20 marks]
Solution notes:
Main issues that should be addressed include: Haskell and Prolog need to traverse the entire list to add to end. However, if we use difference lists in Prolog (or other kinds of lists in Haskell) then it’s possible to write a constant time function (but we need to change the data structure). Difference lists could be:
insert(X,A-[X])
append(L1-T1, T1-T2, L1-T2).
?- append([1,2,3,4| T1]-T1, [5| T2]-T2, Result).
T1 = [5|T2],
Result = [1, 2, 3, 4, 5|T2]-T2.
Accumulating parameters are of little use, as the list would be reversed.
Data types defined in C, Java, etc. can be designed to allow access to last element.
4