CSE 305 Homework #1 Due: Thursday, Oct. 17, 11:59 pm
Function Equivalence:
Consider the following three OCaml functions :
let foo1 ls =
let rec foo ls a =
match ls with
| [] -> a
| hd::tl -> foo tl (hd + a)
in
foo ls 0
let rec foo2 ls =
match ls with
| [] -> 0
| hd::tl -> hd + (foo2 tl)
What is the type of foo1 and foo2? foo1:
foo2:
Are foo1 and foo2 equivalent, in the sense that on the same inputs they return the same output? If they are not equivalent give an example of two possible outputs for the same inputs. Assume that all lists are finite.
1
Type Inference:
Consider the following program:
let f x = [x]
let rec foo3 g n =
if n = 1
then [g 1]
else (g n) :: foo3 g (n-1)
let res = foo3 f 5 What is the type of f?
What is the type of foo3?
2
Consider the following program:
type days = Mon | Tue | Wed | Thu | Fri type wedays = Sat | Sun
let foo x y =
match y with
| Sat -> [x]
| Sun -> match x with
| Mon -> []
| Tue -> [Mon]
| Wed -> [Tue]
| Thu -> [Wed]
| Fri -> [Thu]
What is the type of the function foo?
3
Grammar:
Consider the following grammar:
::=
::=
–
::=
0|1|2
Draw the parse tree for generating the expression -2 + 1 * 2 + 0 from this grammar:
Is the grammar ambiguous or unambiguous? If it is ambiguous, use parse trees to explain why.
4
Consider the following grammar:
::=
::=
::=
0|1
::=
c|d
Are the following sentences can be generated by the grammar defined above? If so, draw their parse tree.
(1). c * d / 1 – 1
(2). 0 + c + 0 + 1
(3). 0 + d * c – c
Is the grammar ambiguous? If it is ambiguous, use parse trees to explain why.
5