Student Number: Full Name: Signature:
The University of New South Wales
COMP3141
Software System Design and Implementation
Sample Final Exam
Term 2, 2019
Time Allowed: 2 hours, excluding reading time. Reading Time: 10 minutes.
Total Number of Questions: 4
Answer all questions.
The questions are of equal value.
You are permitted two hand-written, single-sided A4 sheets of notes.
Only write your answers on the provided booklets.
Answers must be written in ink, with the exception of diagrams.
Drawing instruments or rules may be used.
Excessively verbose answers may lose marks.
There is a 3% penalty if your name and student number are not filled in correctly. Papers and written notes may not be retained by students.
Question 1 (25 marks)
Answer the following questions in a couple of short sentences. No need to be verbose.
(a) (3 marks) What is the difference between a partial function and partial application?
(b) (3 marks) Name two methods of measuring program coverage of a test suite, and explain how they differ.
(c) (3 marks) How are multi-argument functions typically modelled in Haskell?
(d) (3 marks) Is the type of getChar below a pure function? Why or why not? getChar :: IO Char
(e) (3 marks) What is a functional correctness specification?
(f) (3 marks) Under what circumstances is performance important for an abstract model?
(g) (3 marks) What is the relevance of termination for the Curry-Howard correspondence?
(h) (4 marks) Imagine you are working on some price tracking software for some company stocks. You have already got a list of stocks to track pre-defined.
data Stock = GOOG | MSFT | APPL stocks = [GOOG, MSFT, APPL]
Solution: A partial function is a function not defined for its whole domain, whereas partial application is where a n-argument function is applied to fewer than n values.
Solution: Functioncoveragemeasureswhetherornotagivenfunctionisexecutedby the test suite, whereas path coverage measures all possible execution paths. Function coverage is easier to compute than path coverage.
Solution: Mutliple argument functions are usually modelled by one-argument func- tions that in turn return functions to accept further arguments. For example, the add function (+) :: Int -> (Int -> Int) takes an Int and returns a function.
Solution: It is not a pure function, but not because it is impure, but because it is not a function. It is instead an IO procedure.
Solution: A functional correctness specification is a set of properties that completely specify the definition of correctness for a program. It is often expressed as the combination of data invariants and a refinement from an abstract model.
Solution: If we are testing using an abstract model (for example with QuickCheck), then we are still computing with it and thus intractable or uncomputable abstract models would not be suitable.
Solution: The Curry-Howard correspondence assumes that function types are pure and total. Non-termination makes the logic the type system corresponds to incon- sistent.
Page 2
Your software is required to produce regular reports of the stock prices of these companies. Your co-worker proposes modelling reports simply as a list of prices:
type Report = [Price]
Where each price in the list is the stock price of the company in the corresponding position of the stocks list. How is this approach potentially unsafe? What would be a safer representation?
Question 2 (25 marks)
The following questions pertain to the given Haskell code:
foldr ::(a→b→b)→b→[a]→b foldrfz(x:xs) = fx(foldrfzxs) — (1) foldrfz[] = z — (2)
(a) (3 marks) State the type, if one exists, of the expression foldr (:) ([] :: [Bool]).
(b) (4 marks) Show the evaluation of foldr (:) [] [1, 2] via equational reasoning.
(c) (2 marks) In your own words, describe what the function foldr (:) [] does.
(d) (12 marks) We shall prove by induction on lists that, for all lists xs and ys: foldr (:) xs ys = ys ++ xs
i. (3 marks) First show this for the base case where ys = [] using equational reasoning. You may assume the left identity property for ++, that is, for all ls:
ls = [] ++ ls
Solution: It is not guaranteed that the prices will line up to the stocks, or that there will be a stock for every price and a price for every stock. An alternative would be:
type Report = [(Stock,Price)]
which at least ensures that the right stocks are associated with the right price.
Solution: [Bool] → [Bool]
Solution:
foldr (:) [] [1, 2]
= 1 : (foldr (:) [] [2]) (1)
= 1:2:(foldr (:)[][]) (1) = 1:2:[] (2)
Solution: It is the identity function for lists.
Solution:
foldr (:) xs [] = xs (2) = [] ++ xs (id)
Page 3
ii. (9 marks) Next, we have the case where ys = (k : ks) for some item k and list ks. α) (3 marks) What is the inductive hypothesis about ks?
β) (6 marks) Using this inductive hypothesis, prove the above theorem for the in- ductive case using equational reasoning.
(e) (2 marks) What is the time complexity of the function call foldr (:) [] xs, where xs is of size n?
(f) (2 marks) What is the time complexity of the function call foldr (λa as → as ++ [a]) [] xs, where xs is of size n?
Solution:
foldr (:) xs ks = ks ++ xs
Solution:
foldr(:)xs(k:ks) = (:)k(foldr(:)xsks) = k : (foldr (:) xs ks)
= k:(ks++xs) = (k:ks)++xs
(1) simp I.H def. of(++)
Solution: O(n)
Solution: O(n2)
Page 4
Question 3 (25 marks)
A sparse vector is a vector where a lot of the values in the vector are zero. We represent a sparse vector as a list of position-value pairs, as well as an Int to represent the overall length of the vector:
data SVec = SV Int [(Int, Float)]
We can convert a sparse vector back into a dense representation with this expand function:
expand :: SVec → [Float]
expand (SV n vs) = map check [0..n − 1]
where
check x = case lookup x vs of
Nothing → 0 Justv →v
For example, the SVec value SV 5 [(0, 2.1), (4, 10.2)] is expanded into [2.1, 0, 0, 0, 10.2]
(a) (16 marks) There are a number of SVec values that do not correspond to a meaningful vector — they are invalid.
i. (6 marks) Which two data invariants must be maintained to ensure validity of an SVec value? Describe the invariants in informal English.
ii. (4 marks) Give two examples of SVec values which violate these invariants.
iii. (6 marks) Define a Haskell function wellformed :: SVec → Bool which returns True iff the data invariants hold for the input SVec value. Your Haskell doesn’t have to be syntactically perfect, so long as the intention is clear. You may find the function nub :: (Eq a) ⇒ [a] → [a] useful, which removes duplicates from a list.
(b) (9 marks) Here is a function to multiply a SVec vector by a scalar: vsm :: SVec → Float → SVec
vsm (SV n vs) s = SV n (map (λ(p, v) → (p, v ∗ s)) vs)
i. (3 marks) Define a function vsmA that performs the same operation, but for dense
vectors (i.e. lists of Float).
ii. (6 marks) Write a set of properties to specify functional correctness of the function vsm.
Hint: All the other functions you need to define the properties have already been
Solution: For a value SV n vs, the list vs should contain only one value for a given position, and the positions of all values in vs should all be ≥ 0 and < n.
Solution: Violates “only one value for a position”: SV 2 [(1, 1.1), (1, 5.3)] Violates “all positions ≥ 0 and < n”: SV 2 [(3, 1.1)]
Solution:
wellformed (SV n vs)
= let ps = map fst vs
inall (λx→x≥0&&x