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 [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 mark] for y 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
