Page 1 COMP2221-WE01

Examination Paper
Examination Session:
May/June
Year:
2020
Exam Code:
COMP2221-WE01

Title: PROGRAMMING PARADIGMS


Time Allowed: 2 hours
Additional Material provided:
Materials Permitted:
Calculators Permitted: Yes Models Permitted: Casio FX-83 GTPLUS, Casio
FX-85GTPLUS or Casio FX85-GTX
Visiting Students may use dictionaries: Yes


Instructions to Candidates: Answer ALL questions.

Please answer each question in a separate answer booklet.
Revision:

Page 2 of 12 COMP2221-WE01
Section A Functional Programming
(Dr Lawrence Mitchell)
Except where otherwise stated, any code you write in this section should be in
Haskell.
Question 1
(a) Consider an operation scan which computes the prefix sum on lists of
arbitrarily large integers. When given a list [x0, x1, x2, . . . , xn−1], scan
should return the list [y0, y1, y2, . . . , yn−1] where y0 = x0, y1 = x0 + x1,
and generally yj =
∑j
i=0 xj.
i. Write down the type signature of the function scan [3 Marks]
Solution: Comprehension, Application
scan :: [Integer] -> [Integer]
• Use of Integer, not Int (since the integers must be arbitrarily large)
[1 mark]
• Remainder, [2 marks]
ii. Implement scan recursively. Make use of pattern matching in your
answer. [8 Marks]
Solution: Knowledge, Application
scan :: [Integer] -> [Integer]
scan [] = []
scan [x] = [x]
scan (x:y:xs) = x : scan (x+y:xs)
• scan :: [Integer] -> [Integer] (Optional: no marks, already
marked above)
• scan [] = [] [1 mark]
• scan [x] = [x] [1 mark]
• scan (x:y:xs) [2 marks] for the pattern match x:y:xs, [1 mark]
for the brackets.
continued
Page 3 of 12 COMP2221-WE01
• = x : scan (x+y:xs) [1 mark] for the concatenation, [1 mark]
for the recursive call, [1 mark] for application to (x+y:xs).
(b) Now turn scan into a higher-order function
i. Rewrite scan as a new function, scanf, which accepts an additional
argument that can be any binary operator. Ensure that scanf contin-
ues to yield the results of scan if you pass in (+) as the higher-order
argument. [4 Marks]
Solution: Comprehension, Application
scanf :: (Integer -> Integer -> Integer) -> [Integer] -> [Integer]
scanf _ [] = []
scanf _ [x] = [x]
scanf f (x:y:xs) = x : scanf f (x `f` y : xs)
• Function argument is binary (three arguments) [1 mark]
• Function type enclosed in brackets [1 mark]
• Extra parameter f (or similar) [1 mark]
• Replacing x+y with x `f` y or similar [1 mark]
ii. What is currying? Why is it useful? Explain briefly with reference to
your implementation of scanf. [2 Marks]
Solution: Knowledge
Curried functions take arguments “one at a time” [1 mark]. Allows us to
partially apply scanf to build new functions [1 mark].
iii. Write the type signature of scanf so that it is polymorphic. Think
about the types of the input list, the higher-order function arguments,
and the output list. [3 Marks]
Solution: Comprehension, Application
scanf :: (a -> a -> a) -> [a] -> [a]
• All parameters have generic type variables [1 mark]
continued
Page 4 of 12 COMP2221-WE01
• First two arguments to function and input list have same type [1
mark]
• Output list has same type as result type of function argument, which
is used as an input, so must also be of type a [1 mark]
(c) Express the following using list comprehensions
i. All even integers between 2 and 111 (inclusive) [2 Marks]
Solution: Comprehension, Knowledge
[x | x <- [2..111], even x]
[1 mark] for [2..111], [1 mark] for the rest.
ii. All pairs of integers (x, y) with x ∈ [1, 100], y odd, 1 ≤ y ≤ x, and
x+ y < 100 [3 Marks]
Solution: Comprehension, Knowledge
[(x, y) | x <- [1..100], y <- [1..x], odd y, x + y < 100]
[1 mark] for y <- [1..x], [1 mark] for odd y and x + y < 100, [1
mark] for the rest.
Question 2
(a) Haskell uses lazy evaluation rules. Describe how this differs from ea-
ger evaluation (as seen in Java) with reference to functions and their
arguments. [4 Marks]
Solution: Comprehension, Knowledge
In eager evaluation, the arguments to functions are always fully evaluated before
the function is applied [2 marks]. In contrast, in lazy evaluation, the function
is applied first, before its arguments are evaluated [2 marks].
(b) The Haskell evaluator treats expressions as graphs which contain a combi-
nation reducible expressions (or redexes) and irreducible expressions.
continued
Page 5 of 12 COMP2221-WE01
Two particularly important types of expression graphs are normal form
and weak head normal form (WHNF). A WHNF expression graph is
either in normal form, or the topmost node in the graph is a data con-
structor.
i. What properties must an expression graph have to be in normal
form? [3 Marks]
Solution: Knowledge
The expression graph must contain no redexes, it must be finite, and it
must be acyclic. [1 mark] for each.
(c) Draw the corresponding expression graph for each of the following Haskell
expressions, and state if they are in normal form, WHNF, or neither.
i. 1 + 2 [2 Marks]
Solution: Comprehension, Application
Neither normal form, nor WHNF.
+
1 2
ii. 1 : 2 : [] [2 Marks]
Solution: Comprehension, Application
Normal form.
:
1 :
2 []
iii. fact = 1 : zipWith (*) [1..] fact [4 Marks]
Solution: Comprehension, Application
WHNF.
:
1 zipWith
(*) [1..]
continued
Page 6 of 12 COMP2221-WE01
(d) Show why outermost evaluation is preferable to innermost when evaluating
the expression snd (product [1..100000], 5*2). [6 Marks]
Solution: Comprehension, Application, Synthesis
Outermost evaluation has this sequence of steps. [2 marks]
snd (product [1..100000], 5*2)
= -- applying snd
5*2
= -- applying *
10
Innermost evaluation in contrast does [2 marks]
snd (product [1..100000], 5*2)
= -- applying product
snd (some_big_number , 5*2)
= -- applying *
snd (some_big_number , 10)
= -- applying snd
10
So we see that innermost evaluation must do the large computation of the
product, even though the result is immediately discarded. In contrast, outer-
most evaluation never does that computation. [2 marks]
(e) Explain why outermost evaluation (as in Haskell) removes the need for
language-level specification of short-circuiting operators (such as the boolean
operator || in Java), and why innermost evaluation requires language-level
choices to obtain short-circuiting. [4 Marks]
Solution: Synthesis, Analysis
With outermost evaluation, arguments to a function are only evaluated if they
are needed in a subsequent computation. As a consequence, all functions nat-
urally implement short-circuiting behaviour [1 mark]2. In contrast, innermost
evaluation requires that function arguments are always all evaluated: conse-
quently the language must define special semantics for those operators that
need short-circuit behaviour [1 mark]2.
End of Section A continued
Page 7 of 12 COMP2221-WE01
Section B Object Oriented Programming
(Dr Steven Bradley)
Except where otherwise stated, any code you write in this section should be in
Java.
Question 3
(a) The following Java class definition contains four errors that will prevent it
from being compiled. Identify and correct the errors.
1 public class Hamster
2 {
3 private double weight;
4 private boolean groovy;
5 public Hamster(weight)
6 {
7 this.weight = weight;
8 groovy = false;
9 }
10 public boolean isHeavy()
11 {
12 weight >50;
13 }
14 public dance(){
15 weight -= 0.1;
16 groovy = true
17 }
18 }
[8 Marks]
Solution: Comprehension, Application
Issues are
• Missing type for constructor to parameter on line 5, should be
public Hamster(double weight)} [2 marks]
• Missing return statement on line 12, should be return weight>50; [2
marks]
continued
Page 8 of 12 COMP2221-WE01
• Missing return type on line 14, should be public void dance(){ [2
marks]
• Missing semicolon on line 16, should be groovy = true; [2 marks]
(b) With reference to this Java fragment
List hamsters = new ArrayList();
explain the terms
• Type parameter [3 Marks]
• Interface [3 Marks]
• Concrete class [3 Marks]
Solution: Knowledge, Comprehension
• A type parameter is passed to a generic class which works can work with
any class. In this example the generic class is ArrayList which is invoked
with the type parameter Hamster. Angle brackets < ... > are used in
Java to enclose type parameters [3 marks]
• An interface specifies a set of methods and/or static variables that are to
be provided by an implementing class, and defines a type. An interface
only provides the signature of methods, not their implementation. In this
example List is an interface [3 marks]
• A concrete class is a class that is not abstract: it contains no abstract
methods. An interface can be thought of as a fully abstract class. In this
example ArrayList is a concrete class [3 marks]
(c) Explain the difference between assignment to variables that have primitive
types and object types. Your explanation should include an example using
the hamsters object defined above. [8 Marks]
Solution: Comprehension, Application
For primitive types (e.g. int, boolean, double) the data value is stored directly
inside the memory allocated to the variable. [1 mark]In object types the variable
continued
Page 9 of 12 COMP2221-WE01
contains a reference to an object rather than the value of the object itself. [1
mark]This means that two variables of object type can refer to the same object
and that changes to that object are reflected in all the variables that contain a
reference to it [1 mark]. For example, if suppose the following code is executed
after the above fragment
List hammys = hamsters;
hammys.add(new Hamster(20));
int numHamsters = hamsters.size()
int numCages = numCages;
numCages++;
System.out.println("Hamsters: " + numHamsters + " Cages: " + numCages);
[3 marks] Then the output number of hamsters will be 1 rather than 0, be-
cause hamsters and hammys refer to the same list object. Initially the list
has no members (size 0), but when an object is added to hammys it also in-
creases the size of hamsters to 1. However the variables numHamsters and
’numCages have primitive type, so changing the value of numCages has no effect
on numHamsters. [2 marks]
Question 4
(a) By considering the following fragment of Java code, explain the concept
of operator overloading
1 int age = 21;
2 String name = "Steven";
3 System.out.println(name + " is " + age);
[5 Marks]
Solution: Comprehension, Analysis
Operator overloading occurs where an operator (+ in this example) is imple-
mented differently for different types. Here + is used for string concatenation,
but can also be used for numerical addition. The choice of which operator is
to be used depends on the types of the values it operates upon. Here the types
are int and String, so the int age is converted to a String by the com-
piler before string concatenation takes place. The + operator is also overloaded
between the different numeric types defined in Java e.g. int double.
continued
Page 10 of 12 COMP2221-WE01
(b) Suppose you have written a Java class Dancer, which defines relevant
fields and constructors, but with no methods. The Dancer class is then
used in the following Java fragment
1 int age = 21;
2 Dancer hammy = new Dancer("Hammy");
3 System.out.println(hammy + " is " + age);
• Explain the output that would be produced by executing that frag-
ment [3 Marks]
• Show and explain how to adapt your class so that the output would
be
Hammy is 21
[6 Marks]
Solution: Comprehension, Application
• Here hammy is automatically converted to a string, by calling the
toString() method from the Object class. This string will include the
name of the class and an identifier for the object. [3 marks]
• To produce this output the toString() method from the Object class
needs to be overridden by providing a method with the same signature
in the class Dancer, but which returns a value more meaningful in the
context of that class. In this case the method would look something like
this (assuming there is a field name that is initialised with the parameter
of the constructor)
public String toString(){
return name;
}
[6 Marks]
(c) Dancers can more generally thought of as performers and there are other
types of performers, such as musicians. Dancers usually have another
dancer as a partner, which is not generally true of entertainers. Musicians
play one or more instruments, which is not generally true of entertainers
continued
Page 11 of 12 COMP2221-WE01
• Draw a class diagram to show the relationships between the classes
Dancer, Entertainer and Musician. You don’t need to show
the fields or methods, only the relationships between the classes
[3 Marks]
• For both python and Java partially implementng the Dancer clas in
both Java and python, assuming that the Entertainer class has
already been defined. In each case you should include the relevant
definitions for the fields and constructors, but you do not need to
include any method declarations. [8 Marks]
Solution: Analysis, Synthesis
• [3 marks]
• class Dancer(Entertainer):
def __init__(self, name, partner):
Entertainer.__init__(self, name)
self.partner = partner
[4 marks]
public class Dancer extends Entertainer
{
private Dancer partner;
public Dancer(String name, Dancer partner){
super(name);
this.partner = partner;
}
}
continued
Page 12 of 12 COMP2221-WE01
[4 marks]
END OF PAPER