Solutions and marking guide for COMP2100 exam, 2002 QUESTION 1 (a) (i) Child will become Void also. [1 mark] (ii) The assignment attempt will fail, and child will become Void. [1 mark] (iii) The assignment attempt will succeed, and child will become attached to the same object as parent. [1 mark] (b) [2 marks: One mark each for any of the following reasons, up to a maximum of 2 marks.] - A new revision may introduce a worse bug than it fixes. - Different customers may have different version of the system. - The client may decide they liked the old version better. - The project may involve more than one developer, and they need a safe way of sharing files without both modifying the same file. (c) Each time a new font object is created, the existing object becomes an orphan (not referenced) and will eventually be garbage-collected. But GTK also allocates memory on the C side of the application and the Eiffel garbage collector can't recover that. So more and more memory gets allocated on the C side but never recovered. Using once functions instead of ordinary functions would mean that each font only got created once, and that later calls to the function would just get a reference to the font object that was created the first time. No new objects created, no new memory allocated, no garbage collection, no uncollectable memory on the C side wasted: no memory leak. [3 marks: 2 marks for explanation, 1 for how once functions solve it.] (d) create x (or create x.make or !!x or !!x.make...) x.copy (y) [1 mark, 1/2 if they don't create a new object] (e) [1 mark: Give a mark for either of the following:] - No flow of control - No variables or assignments [Give zero for guesses like "Everything is a function".] (f) [2 marks: one mark for each of the following, up to a maximum of 2.] - Large number of trained programmers - Extensive libraries and existing code - They usually compile to faster executables - C gives better access to hardware, good for operating systems (g)(i) The Model stores the underlying data, contains the functional core of application. It registers dependent views and controllers. It notifies views and controllers of changes to its internal state. (ii) The View is the graphical part of the interface, which displays information about the model to the user. It updates itself when the model changes, and retrieves data from the model. (iii) The Controller is the the decision-making part. It accepts user inputs and other events, and translates these into service requests for the model or display requests for the view. [1 mark each. Give half marks if they have some but not all of a part.] (h) The C compiler checks that all calls to a function have the correct number and type of arguments, the correct return type by comparing with the declaration of the function that it finds in that file. If the function is defined in the same file, it also checks that the definition matches the declaration. But the linker does not do any type checking, so it is possible to declare the same function name with different signatures in different modules, and still have each module compile correctly and the two modules link together, causing a type clash. Using header files can solve this problem if the same header file, containing the declaration of a function, is #included at the start of the module that defines a function and every module that uses it. Because the same declaration is used in each file, the internal type checking is enough to make sure that the definition and all calls have matching signatures. [3 marks: 2 marks for the explanation, 1 mark for the solution.] (i) A pointer is a memory address. [1 mark] (j) A function declaration specifies the signature: the name, the return type and the number and types of arguments, so that later references to the function can be checked. A function definition actually specifies the implementation. [1 mark, half if they're reversed.] ---------------------------------------------------------------- QUESTION 2 (a) class ADDITION creation make feature {NONE} -- Creation make (l, r: EXPRESSION) is -- Initialise left and right hand sides. require l /= Void r /= Void do left := l right := r ensure left = l right = r end feature {ANY} -- Attributes left, right: EXPRESSION -- The two subexpressions to be added feature {ANY} -- Commands accept (v: VISITOR) is -- Tell `v' what type this is. require v /= Void -- (should be in parent class though) do v.visit_addition (Current) end end -- class ADDITION [6 marks: 1 for having a correct class framework 1 for correct implementation of make 1 for declaration of left and right 1 for correct implementation of accept 1 for header comments 1 for require or ensure clauses, class invariant etc.] (b) class PRINTER feature {ANY} -- Commands visit_constant (x: CONSTANT) is -- Print out a constant expression. do std_output.put_integer (x.value) end visit_addition (x: ADDITION) is -- Print out an addition expression. do std_output.put_character ('(') x.left.accept (Current) std_output.put_character ('+') x.right.accept (Current) std_output.put_character (')') end visit_multiplication (x: MULTIPLICATION) is -- Print out a multiplication expression. do std_output.put_character ('(') x.left.accept (Current) std_output.put_character ('*') x.right.accept (Current) std_output.put_character (')') end end -- class PRINTER [6 marks: 1 for correct class framework 1 for printing on std_output (or io, but not allowed to print to a string like the lecture example) 1 for visit_constant 1 for visit_addition 1 for visit_multiplication 1 for no creation clause or make routine] (c) create a.make (1) create b.make (2) create c.make (3) create d.make (4) create g.make (b, c) create f.make (a, g) create e.make (f, d) create printer e.accept (printer) [4 marks: 1 for correct creation of the constants 1 for creating and assembling the tree 1 for creating the printer 1 for a correct call to accept] (d) class NORMALISER feature {ANY} visit_constant (x: CONSTANT) is do end visit_addition (x: ADDITION) is -- Apply the associative law to move this to the right. local y: ADDITION do x.left.accept (Current) x.right.accept (Current) y ?= x.left if y /= Void then x.set_left (y.left) y.set_left (y.right) y.set_right (x.right) x.set_right (y) end end visit_multiplication (x: MULTIPLICATION) is -- Just make recursive calls to children do x.left.accept (Current) x.right.accept (Current) end end -- class NORMALISER Changes to make to existing classes: Need to add new features set_left and set_right to class ADDITION, so that the NORMALISER can change the values of x.left, x.right, y.left and y.right. These would be simple attribute-setting features, e.g. set_left (x: EXPRESSION) is -- Make `x' the new left sub-expression. require x /= Void do left := x end [4 marks: 1 for seeing that it involves modifying the attributes of ADDITION objects, so that class ADDITION needs new "set" methods. 1 for the assignment attempt 1 for the rotation 1 for the recursive calls in visit_addition and visit_multiplication] ---------------------------------------------------------------- QUESTION 3 There are 15 defects: 1. Line 1 - Incorrect formatting of class name [1 mark] 2. Line 3 - Missing creation clause [1 mark] 3. Line 6 - Bad header comment, should say "Make change" like an order, rather than "Makes change" like a description [1 mark] 4. Line 46 - Variable n is not declared [1.5 marks] 5. Line 67 - Missing keyword "is" [1 mark] 6. Line 31 - Missing keyword "end" for inspect statement [1.5 marks] 7. Line 36 - Should be / not // [1.5 marks] 8. Line 48 - Should be >=, not > [1.5 marks] 9. Line 52 - It prints even if n=0, needs "if n > 0 then" and a matching "end" [2 marks] 10. Line 56 - Need to set n back to 0 [1.5 marks] 11. Line 58 - Off by one: never prints the number of the last coin [2 marks] 12. Line 48 - Should be coin_values, not coins (also Line 50) [1.5 marks] 13. Line 39 - Should either be put_string, or single quotes [1.5 marks] 14. Line 25 - Should be \\ not // (also Line 26) [1.5 marks] 15. Line 17 - If n < 3 it says "too large" [1 mark] [Maximum possible 21 marks] ---------------------------------------------------------------- QUESTION 4 (a) class HARNESS creation make feature make is -- Run the strcnt function on the command line -- arguments. local s, t: STRING n: INTEGER do s := argument (1) t := argument (2) n := strcnt (s.to_external, t.to_external) std_output.put_integer (n) std_output.put_new_line end feature {NONE} -- Wrappers strcnt (p1, p2: POINTER): INTEGER is -- The number of occurrences of the C string starting -- at location `p1' in the one starting at location -- `p2'. external "C" end end -- class HARNESS Notes: No need to declare locals. It could all be done in one line with something horrible like std_output.put_string (strcnt (argument (1).to_external, argument (2).to_external).to_string, "%N") or anything in between. The wrapper could also be called something nicer like string_count, in which case its implementation would have to be external "C" alias "strcnt" end [7 marks (too many? too late now) 1 for having a complete class rather than a fragment 1 for using to_external 1 for correct signature of the wrapper (POINTER not STRING) 1 for correct wrapper implementation 1 for good header comments 1 for correct body of make 1 for getting command-line arguments, not reading them from stdin] (b) #!/bin/bash total=0 passed=0 while read string1 string2 expected do total=$[${total}+1] actual=$(harness ${string1} ${string2}) if [ ${expected} -eq ${actual} ] then echo Test ${total}: Passed passed=$[${passed}+1] else echo -n Test ${total}: Failed - expected ${expected}, echo actual ${actual} fi done echo echo Passed ${passed}/${total} tests = $[100*${passed}/${total}]% [7 marks: 1 mark for correct #!/bin/bash at the top 1 mark for reading from stdin, not cases (read the instructions!) 1 mark for correct use of while read a b c 1 mark for good call to harness and catching result 1 mark for passing arguments on command line 1 mark for good messages 1 mark for keeping track of total and passed and writing a good summary line] (c) report.txt / | \ harness cases tester / \ ----- ------ strcnt.o harness.e / --------- strcnt.c -------- [2 marks (not enough?, again, too late now) 1 for the right dependencies 1 for the underlined source files] (d) report.txt: harness cases tester tester < cases > report.txt harness: strcnt.o harness.e compile -o harness harness make strcnt.o strcnt.o: strcnt.c gcc -c -Wall strcnt.c [4 marks (too many?) 1 for having report.txt first, or otherwise (e.g. using a default target) making sure it gets rebuilt if the user types "make" without a target. 1 for correct (tricky) line to rebuild report.txt 1 for matching the diagram 1 for good compile and gcc calls (in particular, don't forget the -c flag; the -Wall is optional)] [Oops! Forgot the last part of (d), adding a "clean" target. Just add an extra mark for that (so it's now out of 5).] ---------------------------------------------------------------- QUESTION 5 Later ...