- August 14, 2020

COMP3141 Software System Design and Implementation SAMPLE EXAM Term 2, 2020 Declaration I, Stefan Gao (5211215), declare that these answers are entirely my own, and that I did not complete this exam with assistance from anyone else. Part A (25 Marks) Answer the following questions in a couple of short sentences. No need to be verbose. 1. (3 Marks) What is the difference between a partial function and partial application? 2. (3 Marks) Name two methods of measuring program coverage of a test suite, and explain how they differ. 3. (3 Marks) How are multi-argument functions typically modelled in Haskell? Total Number of Parts: 5.● Total Number of Marks: 125● All parts are of equal value.● Answer all questions.● Excessively verbose answers may lose marks● Failure to make the declaration or making a false declaration results in a 100% mark penalty. ● Ensure you are the person listed on the declaration.● All questions must be attempted individually without assistance from anyone else.● You must save your exam paper using the button below before time runs out.● Late submissions will not be accepted.● You may save multiple times before the deadline. Only your final submission will be considered. ● 4. (3 Marks) Is the type of getChar below a pure function? Why or why not? getChar :: IO Char 5. (3 Marks) What is a functional correctness specification? 6. (3 Marks) Under what circumstances is performance important for an abstract model? 7. (3 Marks) What is the relevance of termination for the Curry-Howard correspondence? 8. (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] 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? Part B (25 Marks) The following questions pertain to the given Haskell code: getChar getChar :: data Stock = | | stocks = [,,] type Report = [Price] foldr :: (a → b → b) → b → [a] → b foldr f z (x : xs) = f x (foldr f z xs) — (1) foldr f z [] = z — (2) 1. (3 Marks) State the type, if one exists, of the expression foldr ( : ) ([] :: [Bool]). 2. (4 Marks) Show the evaluation of foldr ( : ) [] [1, 2] via equational reasoning. 3. (2 Marks) In your own words, describe what the function foldr ( : ) [] does. 4. (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 ii. (9 Marks) Next, we have the case where ys = (k : ks) for some item k and list ks. a. (3 Marks) What is the inductive hypothesis about ks? foldr :: (a → b → b) → b → [a] → b foldr f z (x : xs) foldr f z [] = = f x (foldr f z xs) z — — () () foldr (:) ([] :: []) foldr (:) [] [1, 2] foldr (:) [] xs ys foldr (:) xs ys = ys ++ xs ys = [] ++ ls ls = [] ++ ls ys = (k : ks) k ks ks b. (6 Marks) Using this inductive hypothesis, prove the above theorem for the inductive case using equational reasoning. 5. (2 Marks) What is the time complexity of the function call foldr ( : ) [] xs, where xs is of size n? 6. (2 Marks) What is the time complexity of the function call foldr (λa as → as ++ [a]) [] xs, where xs is of size n Part C (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 Just v → v For example, the SVec value SV 5 [(0, 2.1), (4, 10.2)] is foldr (:) [] xs xs n foldr (λa as → as ++ [a]) [] xs xs n data SVec = [(, )] expand expand :: SVec → [] expand ( n vs) = map check [0. . n − 1] where check x = case lookup x vs of v → → 0 v SVec 5 [(0, 2.1), (4, 10.2)] expanded into [2.1, 0, 0, 0, 10.2] 1. (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 SVecvalue. 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. 2. (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 this function. Hint: All the other functions you need to define the properties have already been mentioned in this part. It should maintain data invariants as well as refinement from the abstract model. [2.1, 0, 0, 0, 10.2] SVec SVec SVec wellformed :: SVec → Bool SVecvalue nub :: ( a) ⇒ [a] → [a] SVec vsm :: SVec → Float → SVec vsm ( n vs) s = n (map (λ(p, v) → (p, v ∗ s)) vs) vsmA Part D (25 Marks) 1. (10 Marks) Imagine you are working for a company that maintains this library for a database of personal records, about their customers, their staff, and their suppliers. newtype Person = … name:: Person → String salary :: Person → Maybe String fire :: Person → IO () company:: Person → Maybe String The salary function returns Nothing if given a person who is not a member of company staff. The fire function will also perform no-op unless the given person is a member of company staff. The company function will return Nothing unless the given person is a supplier. Rewrite the above type signatures to enforce the distinction between the different types of person statically, within Haskell’s type system. The function name must work with all kinds of people as input. Hint: Attach phantom type parameters to the Person type. 2. (15 Marks) Consider the following two types in Haskell: newtype Person = … name :: Person → String salary :: Person → String fire :: Person → () company :: Person → String salary fire company name Person data List a where Nil :: List a Cons :: a → List a → List a data Nat = Z | S Nat data Vec (n :: Nat) a where VNil :: Vec Z a VCons :: a → Vec n a → Vec (S n) a What is the difference between these types? In which circumstances would Vec be the better choice, and in which List? i. (5 Marks) ii. (5 Marks) Here is a simple list function: zip :: List a → List b → List (a, b) zip Nil ys = Nil zip xs Nil = Nil zip (Cons x xs) (Cons y ys) = Cons (x, y) (zip xs ys) Define a new version of zip which operates on Vec instead of List wherever possible. You can constrain the lengths of the input. data List a where data Nat = | Nat data Vec (n :: Nat) a where :: :: :: :: List a a → List a → List a Vec a a → Vec n a → Vec ( n) a Vec List zip :: List a → List b → List (a, b) zip zip zip xs ( x xs) ys ( y ys) = = = (x, y) (zip xs ys) zip Vec List iii. (5 Marks) Here is another list function: filter :: (a → Bool) → List a → List a filter p Nil = Nil filter p (Cons x xs) | p x = Cons x (filter p xs) | otherwise = filter p xs Define a new version of filter which operates on Vec instead of List wherever possible. Part E (25 Marks) 1. (10 Marks) An applicative functor is called commutative iff the order in which actions are sequenced does not matter. In addition to the normal applicative laws, a commutative applicative functor satisfies: f ⟨$⟩ u ⟨ ∗ ⟩ v = flip f ⟨$⟩ v ⟨ ∗ ⟩ u i. (2 Marks) Is the Maybe Applicative instance commutative? Explain your answer. filter :: (a → ) → List a → List a filter p = filter p ( x xs) | p x | otherwise = = x (filter p xs) filter p xs filter Vec List f ⟨$⟩ u ⟨∗⟩ v = flip f ⟨$⟩ v ⟨∗⟩ u ii. (3 Marks) We have seen two different Applicative instances for lists. Which of these instances, if any, are commutative? Explain your answer. iii. (5 Marks) A commutative monad is the same as a commutative applicative, only specialised to monads. Express the commutativity laws above in terms of monads, using either do notation or the raw pure/bind functions. 2. (10 Marks) Translate the following logical formulae into types, and provide Haskell types that correspond to proofs of these formulae, if one exists. If not, explain why not. i. (2 Marks) (A ∨ B) → (B ∨ A) ii. (2 Marks) (A ∨ A) → A iii. (3 Marks) (A ∧ (B ∨ C)) → ((A ∧ B) ∨ (A ∧ C)) iv. (3 Marks) ¬((A → ⊥) ∨ A) 3. (5 Marks) Here is a Haskell data type: do (A ∨ B) → (B ∨ A) (A ∨ A) → A (A ∧ (B ∨ C)) → ((A ∧ B) ∨ (A ∧ C)) ¬((A → ⊥) ∨ A) data X = First () A | Second () Void | Third (Either B ()) Using known type isomorphisms, simplify this type as much as possible. END OF SAMPLE EXAM (don’t forget to save!) data X = | | () () ( ()) Loading [MathJax]/jax/output/HTML-CSS/jax.js Time Remaining 2h 9m 33s Save