19/08/2020
COMP3141 Sample Exam
COMP3141
Software System Design and Implementation
SAMPLE EXAM
Term 2, 2020
● 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 nal submission will be
considered.
Declaration
I, name, 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?
A partial function is a function not de ned for its whole domain, whereas partial application is where a -argument function is applied to fewer than values.
2. (3 Marks) Name two methods of measuring program coverage of a test suite, and explain how they differ.
Function coverage measures whether or not a given function is executed by the test suite, whereas path coverage measures all possible execution paths. Function coverage is easier to compute than path coverage.
nn
https://cgi.cse.unsw.edu.au/~cs3141/cgi-bin/gal/20T2/solns_sample_exam 1/13
19/08/2020 COMP3141 Sample Exam
https://cgi.cse.unsw.edu.au/~cs3141/cgi-bin/gal/20T2/solns_sample_exam 2/13
3. (3 Marks) How are multi-argument functions typically modelled in Haskell?
4. (3 Marks) Is the type of below a pure function? Why or why not?
Mutliple argument functions are usually modelled by one-argument functions that in turn return functions to accept further arguments. For example, the add function
takes an and returns a function.
It is not a pure function, but not because it is impure, but because it is not a function. It is instead an procedure.
5. (3 Marks) What is a functional correctness speci cation?
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-de ned.
A functional correctness speci cation is a set of properties that completely specify the de nition of correctness for a program. It is often expressed as the combination of data invariants and a re nement from an abstract model.
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.
The Curry-Howard correspondence assumes that function types are pure and total. Non-termination makes the logic the type system corresponds to inconsistent.
rahC OI :: rahCteg
rahCteg
tnI )tnI → tnI( → tnI :: )+(
OI
19/08/2020 COMP3141 Sample Exam
https://cgi.cse.unsw.edu.au/~cs3141/cgi-bin/gal/20T2/solns_sample_exam 3/13
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:
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?
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:
which at least ensures that the right stocks are associated with the right price.
Part B (25 Marks)
The following questions pertain to the given Haskell code:
1. (3 Marks) State the type, if one exists, of the expression .
2. (4 Marks) Show the evaluation of via equational reasoning.
)]looB[ :: ][( ):( rdlof
)2( ][:2:1 = )1( )][][):(rdlof(:2:1 =
)1(
)]2[ ][ ):( rdlof( : 1 = ]2 ,1[ ][ ):( rdlof
]2 ,1[ ][ ):( rdlof
][zfrdlof )1( — )sxzfrdlof(xf = )sx:x(zfrdlof b → ]a[ → b → )b → b → a( :: rdlof
)2( —
z =
])ecirP ,kcotS([ = tropeR epyt
]ecirP[ = tropeR epyt
]LPPA ,TFSM ,GOOG[ = skcots LPPA | TFSM | GOOG = kcotS atad
]looB[ → ]looB[
19/08/2020 COMP3141 Sample Exam
https://cgi.cse.unsw.edu.au/~cs3141/cgi-bin/gal/20T2/solns_sample_exam 4/13
3. (2 Marks) In your own words, describe what the function does.
It is the identity function on lists.
4. (12 Marks) We shall prove by induction on lists that, for all lists and :
i. (3 Marks) First show this for the base case where You may assume the left identity property for
using equational reasoning. , that is, for all :
ii. (9 Marks) Next, we have the case where
a. (3 Marks) What is the inductive hypothesis about ?
b. (6 Marks) Using this inductive hypothesis, prove the above theorem for the inductive case using equational reasoning.
for some item and list .
sk k
sk
)sk : k( = sy
sy
sx
sl
sl ++ ][ = sl ++
sx ++ sk = sk sx ):( rdlof
)di( )2(
sx ++ ][ =
sx = ][ sx ):( rdlof
][ ):( rdlof
][ = sy
sx ++ sy = sy sx ):( rdlof
19/08/2020 COMP3141 Sample Exam
https://cgi.cse.unsw.edu.au/~cs3141/cgi-bin/gal/20T2/solns_sample_exam 5/13
5. (2 Marks) What is the time complexity of the function call , where is of size ?
6. (2 Marks) What is the time complexity of the function call , where is of size
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 to represent the overall length of the vector:
We can convert a sparse vector back into a dense representation with this function:
For example, the value is expanded into
]2.01 ,0 ,0 ,0 ,1.2[ ])2.01 ,4( ,)1.2 ,0([ 5 VS ceVS
sx
sx ][ ):( rdlof
dnapxe
)++(fo.fed H.I
sx++)sk:k( = )sx++sk(:k = )sk sx ):( rdlof( : k = )sksx):(rdlof(k):( =
pmis )1(
)sk:k(sx):(rdlof
v → v tsuJ
0 → gnihtoN
fo sv x pukool esac = x kcehc
erehw ]1 − n..0[ kcehc pam = )sv n VS( dnapxe ]taolF[ → ceVS :: dnapxe
])taolF ,tnI([ tnI VS = ceVS atad tnI
n
sx
) 2n(O sx ][ )]a[ ++ sa → sa aλ( rdlof
)n(O n
19/08/2020 COMP3141 Sample Exam
https://cgi.cse.unsw.edu.au/~cs3141/cgi-bin/gal/20T2/solns_sample_exam 6/13
1. (16 Marks) There are a number of 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 value? Describe the invariants in informal English.
For a value , the list should contain only one value for a given position, and the positions of all values in should all be and .
ii. (4 Marks) Give two examples of values which violate these invariants.
Violates “only one value for a position”: Violates “all positions and “:
iii. (6 Marks) De ne a Haskell function which returns iff the data invariants hold for the input . Your Haskell doesn’t
have to be syntactically perfect, so long as the intention is clear.
You may nd the function useful, which removes duplicates from a list.
2. (9 Marks) Here is a function to multiply a vector by a scalar:
)sv ))s ∗ v ,p( → )v ,p(λ( pam( n VS = s )sv n VS( msv ceVS → taolF → ceVS :: msv
sp == sp bun && sp )n < x && 0 ≥ x → xλ( lla ni
])1.1,3([2VS n< 0≥ ])3.5 ,1( ,)1.1 ,1([ 2 VS
n<0≥ sv
ceVS
sv tsf pam = sp tel = )sv n VS( demrofllew
]a[ → ]a[ ⇒ )a qE( :: bun
eulavceVS
looB → ceVS :: demrofllew
eurT
ceVS
sv
sv n VS
ceVS
ceVS
19/08/2020 COMP3141 Sample Exam
https://cgi.cse.unsw.edu.au/~cs3141/cgi-bin/gal/20T2/solns_sample_exam 7/13
i. (3 Marks) De ne a function that performs the same operation, but for dense vectors (i.e. lists of ).
ii. (6 Marks) Write a set of properties to specify functional correctness of this function. Hint: All the other functions you need to de ne the properties have already been mentioned in this part. It should maintain data invariants as well as re nement from the abstract model.
Data invariants: Data re nement:
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.
The function returns if given a person who is not a member of company staff. The function will also perform no-op unless the given person is a member of company staff. The function will return unless the given person is a supplier.
gnihtoN ynapmoc
erif
gnirtS ebyaM → nosreP :: ynapmoc )( OI → nosreP :: erif gnirtS ebyaM → nosreP :: yralas gnirtS → nosreP :: eman
... = nosreP epytwen
s )sx dnapxe( Amsv == )s sx msv( dnapxe
)ssxmsv(demrofllew ⟹ sxdemrofllew
sx )s ∗( pam = s sx Amsv
gnihtoN
yralas
taolF Amsv
19/08/2020 COMP3141 Sample Exam
https://cgi.cse.unsw.edu.au/~cs3141/cgi-bin/gal/20T2/solns_sample_exam 8/13
Rewrite the above type signatures to enforce the distinction between the different types of person statically, within Haskell's type system. The function must work with all kinds of people as input.
Hint: Attach phantom type parameters to the type.
2. (15 Marks) Consider the following two types in Haskell:
What is the difference between these types? In which circumstances would be the better choice, and in which ?
tracks its length in the type level, whereas does not. Usually, one would only use if one frequently needed to express static pre-conditions about the length of the list. This way, the type checker can ensure these preconditions are met automatically.
ceV
eman
tsiL
ceV
a)nS(ceV→anceV→a :: snoCV a Z ceV :: liNV
erehw a )taN :: n( ceV atad taNS|Z = taNatad
atsiL→atsiL→a :: snoC atsiL :: liN
gnirtS → reilppuS nosreP :: ynapmoc :ereh dedeen regnol on ebyaM -- )( OI → ffatS nosreP :: erif gnirtS → ffatS nosreP :: yralas :ereh dedeen regnol on ebyaM -- gnirtS → t nosreP :: eman
erehw a tsiL atad
... = t nosreP epytwen reilppuS atad remotsuC atad ffatS atad
nosreP
tsiL
ceV
19/08/2020 COMP3141 Sample Exam
https://cgi.cse.unsw.edu.au/~cs3141/cgi-bin/gal/20T2/solns_sample_exam 9/13
i. (5 Marks)
ii. (5 Marks) Here is a simple list function:
De ne a new version of which operates on instead of possible. You can constrain the lengths of the input.
wherever
iii. (5 Marks) Here is another list function:
De ne a new version of which operates on instead of possible.
wherever
tsiL ceV
retlif
sx p retlif = esiwrehto | )sxpretlif(xsnoC = xp|
)sx x snoC( p retlif liN = liN p retlif a tsiL → a tsiL → )looB → a( :: retlif
)sy sx Vpiz( )y ,x( snoCV = liNV = liNV =
)sy y snoCV( liNV sy
tsiL ceV
piz
)sy sx piz( )y ,x( snoC = )sy y snoC( liN = liN liN = sy
)sx x snoCV( Vpiz sx Vpiz liNV Vpiz )b ,a( n ceV → b n ceV → a n ceV :: Vpiz
)sx x snoC( piz sx piz liN piz )b ,a( tsiL → b tsiL → a tsiL :: piz
19/08/2020 COMP3141 Sample Exam
https://cgi.cse.unsw.edu.au/~cs3141/cgi-bin/gal/20T2/solns_sample_exam 10/13
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 satis es:
i. (2 Marks) Is the Applicative instance commutative? Explain your answer.
Yes. If either or are , the result is on both sides of the law. If both are not Nothing, then the result is applied to their contents.
ii. (3 Marks) We have seen two different instances for lists. Which of these instances, if any, are commutative? Explain your answer.
The ZipList instance obeys the law above - the size is the minimum of the two
input lists, and each element is combined with combinatorial instance does not. For example if
, then the left hand side of the law is side gives us - they are different.
in the same order. The
and and
and the right hand
We can't return a because we don't know how long it will be.
]5,4[ = v
]51 ,21 ,01 ,8[ ]3,2[ = u
)∗( = f
sx p Vretlif = esiwrehto | )sxpVretlif(xsnoC = xp|
gnihtoN
gnihtoN
v u ebyaM
)sx x snoCV( p Vretlif liN = liNV p Vretlif a tsiL → a n ceV → )looB → a( :: Vretlif
f
evitacilppA
f
u⟩∗⟨v⟩$⟨fpilf = v⟩∗⟨u⟩$⟨f
]51 ,01 ,21 ,8[
ceV
19/08/2020 COMP3141 Sample Exam
https://cgi.cse.unsw.edu.au/~cs3141/cgi-bin/gal/20T2/solns_sample_exam 11/13
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 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)
ii. (2 Marks)
x tfeL = )x thgiR( f
x thgiR = )x tfeL( f )A B rehtiE( → )B A rehtiE( :: f
)y x f( erup u←x v←y
)y x f( erup v←y u←x
od =
od
A → )A ∨ A(
)A ∨ B( → )B ∨ A(
od
19/08/2020 COMP3141 Sample Exam
https://cgi.cse.unsw.edu.au/~cs3141/cgi-bin/gal/20T2/solns_sample_exam
iii. (3 Marks)
iv. (3 Marks)
This function cannot be implemented in Haskell or simply-typed lambda calculus as it states the law of the excluded middle is false. While constructive logics do not admit the law of the excluded middle, they do not refute it either.
3. (5 Marks) Here is a Haskell data type:
Using known type isomorphisms, simplify this type as much as possible.
This is equivalent to (using plus for and times for products):
12/13
))( B rehtiE( drihT | dioV )( dnoceS |
rehtiE
A )( tsriF = X atad
dioV → )A )dioV → A( rehtiE( :: f
)A ∨ )⊥ → A((¬
)x ,a( thgiR = )x thgiR ,a( f )x,a( tfeL = )x tfeL,a( f ))C ,A( )B ,A( rehtiE( → ))C B rehtiE( ,A( :: f
))C ∧ A( ∨ )B ∧ A(( → ))C ∨ B( ∧ A(
x = )x thgiR( f x = )x tfeL( f A → )A A rehtiE( :: f
19/08/2020
https://cgi.cse.unsw.edu.au/~cs3141/cgi-bin/gal/20T2/solns_sample_exam 13/13
COMP3141 Sample Exam
END OF SAMPLE EXAM
(don't forget to save!)
)B A rehtiE( ebyaM = ))(+B+A( = ))(+B(+A = ))(+B(+dioV(+A =
))( + B( + )dioV × )((( + )A × )((