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 final submission will be considered.
Declaration
I, 5092119 Xinze Song, 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 defined for its whole domain, whereas partial application is where a n
n
-argument function is applied to fewer than n
n
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.
3. (3 Marks) How are multi-argument functions typically modelled in Haskell? Mutliple argument functions are usually modelled by one-argument functions that in turn return functions to accept further arguments. For example, the add function (+) :: Int→(Int→Int)
(
+
)
::
I
n
t
→
(
I
n
t
→
I
n
t
)
takes an Int
I
n
t
and returns a function.
4. (3 Marks) Is the type of getChar
g
e
t
C
h
a
r
below a pure function? Why or why not? getChar::IO Char
g
e
t
C
h
a
r
::
I
O
C
h
a
r
It is not a pure function, but not because it is impure, but because it is not a function. It is instead an IO
I
O
procedure.
5. (3 Marks) What is a functional correctness specification? 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.
6. (3 Marks) Under what circumstances is performance important for 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.
7. (3 Marks) What is the relevance of termination for the Curry-Howard correspondence? The Curry-Howard correspondence assumes that function types are pure and total. Non-termination makes the logic the type system corresponds to inconsistent.
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]
9. d
a
t
a
S
t
o
c
k
=G
O
O
G
|
M
S
F
T
|
A
P
P
L
10. s
t
o
c
k
s
=[G
O
O
G
,
M
S
F
T
,
A
P
P
L
]
11.
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]
t
y
p
e
R
e
p
o
r
t
=
[
P
r
i
c
e
]
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: type Report=[(Stock,Price)]
t
y
p
e
R
e
p
o
r
t
=
[
(
S
t
o
c
k
,
P
r
i
c
e
)
]
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:
foldr::(a→b→b)→b→[a]→b
foldr f z (x:xs)
foldr f z []
=
=
f x (foldr f z xs)
z
—
—
(1)
(2)
f
o
l
d
r
::
(
a
→
b
→
b
)
→
b
→
[
a
]
→
b
f
o
l
d
r
f z (x:
x
s
)
=
f x (
f
o
l
d
r
f z
x
s
)
—
(1)
f
o
l
d
r
f z []
=
z
—
(2)
1. (3 Marks) State the type, if one exists, of the expression foldr (:) ([]::[Bool])
f
o
l
d
r
(
:
)
(
[
]
::
[
B
o
o
l
]
)
. [Bool]→[Bool]
[
Bool
]
→
[
Bool
]
2. (4 Marks) Show the evaluation of foldr (:) [] [1,2]
f
o
l
d
r
(
:
)
[
]
[
1
,
2
]
via equational reasoning.
=
=
=
foldr (:) [] [1,2]
1:(foldr (:) [] [2])
1:2:(foldr (:) [] [])
1:2:[]
(1)
(1)
(2)
3.
4. f
o
l
d
r
(:) [] [1,2]
5. =
6. 1:(f
o
l
d
r
(:) [] [2])
7. (1)
8. =
9. 1:2:(f
o
l
d
r
(:) [] [])
10. (1)
11. =
12. 1:2:[]
13. (2)
14.
15. (2 Marks) In your own words, describe what the function foldr (:) []
f
o
l
d
r
(
:
)
[
]
does. It is the identity function on lists.
16. (12 Marks) We shall prove by induction on lists that, for all lists xs
x
s
and ys
y
s
: foldr (:) xs ys=ys ++ xs
f
o
l
d
r
(
:
)
x
s
y
s
=
y
s
++
x
s
i. (3 Marks) First show this for the base case where ys=[]
y
s
=
[
]
using equational reasoning. You may assume the left identity property for ++
++
, that is, for all ls
l
s
: ls=[] ++ ls
l
s
=
[
]
++
l
s
foldr (:) xs []
=
=
xs
[] ++ xs
(2)
(id)
ii. f
o
l
d
r
(:) x
s
[]
iii. =
iv. x
s
v. (2)
vi.
vii. =
viii. [] ++
x
s
ix. (id)
x.
xi. (9 Marks) Next, we have the case where ys=(k:ks)
y
s
=
(
k
:
k
s
)
for some item k
k
and list ks
k
s
.
a. (3 Marks) What is the inductive hypothesis about ks
k
s
? foldr (:) xs ks=ks ++ xs
f
o
l
d
r
(
:
)
x
s
k
s
=
k
s
++
x
s
b. (6 Marks) Using this inductive hypothesis, prove the above theorem for the inductive case using equational reasoning. foldr (:) xs (k:ks)
=
=
=
=
(:) k (foldr (:) xs ks)
k:(foldr (:) xs ks)
k:(ks ++ xs)
(k:ks) ++ xs
(1)
simp
I.H
def. of (++)
c. f
o
l
d
r
(:) x
s
(k:k
s
)
d. =
e. (:) k (f
o
l
d
r
(:) x
s
k
s
)
f. (1)
g.
h. =
i. k:(f
o
l
d
r
(:) x
s
k
s
)
j. simp
k.
l. =
m. k:(k
s
++
x
s
)
n. I.H
o.
p. =
q. (k:ks) ++
x
s
r. def. of
(++
)
s.
17. (2 Marks) What is the time complexity of the function call foldr (:) [] xs
f
o
l
d
r
(
:
)
[
]
x
s
, where xs
x
s
is of size n
n
? O(n)
O
(
n
)
18. (2 Marks) What is the time complexity of the function call foldr (λa as→as ++ [a]) [] xs
f
o
l
d
r
(
λ
a
a
s
→
a
s
++
[
a
]
)
[
]
x
s
, where xs
x
s
is of size n
n
O(n
2
)
O
(
n
2
)
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
I
n
t
to represent the overall length of the vector:
data SVec=SV Int [(Int,Float)]
data
S
V
e
c
=
S
V
I
n
t
[
(
I
n
t
,
F
l
o
a
t
)
]
We can convert a sparse vector back into a dense representation with this
expand
e
x
p
a
n
d
function:
expand::SVec→[Float]
expand (SV n vs)=map check [0..n−1]
where
check x=case lookup x vs of
Nothing
Just v
→
→
0
v
e
x
p
a
n
d
::
S
V
e
c
→
[
F
l
o
a
t
]
e
x
p
a
n
d
(
S
V
n
v
s
)
=
m
a
p
c
h
e
c
k
[
0
.
.
n
−
1
]
where
c
h
e
c
k
x
=
case
l
o
o
k
u
p
x
v
s
of
N
o
t
h
i
n
g
→
0
J
u
s
t
v
→
v
For example, the
SVec
S
V
e
c
value
SV 5 [(0,2.1),(4,10.2)]
S
V
5
[
(
0
,
2.1
)
,
(
4
,
10.2
)
]
is expanded into
[2.1,0,0,0,10.2]
[
2.1
,
0
,
0
,
0
,
10.2
]
1. (16 Marks) There are a number of SVec
S
V
e
c
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
S
V
e
c
value? Describe the invariants in informal English. For a value SV n vs
S
V
n
v
s
, the list vs
v
s
should contain only one value for a given position, and the positions of all values in vs
v
s
should all be ≥0
≥
0
and