CSE 130, Spring 2014 Name/ID Instructor: Ranjit Jhala
Midterm Exam
Instructions: read these first!
Do not open the exam, turn it over, or look inside until you are told to begin.
Switch off cell phones and other potentially noisy devices.
Write your full name on the line at the top of this page. Do not separate pages.
You may refer to a double-sided ¡°cheat sheet¡±, but no computational devices (such as laptops, calculators, phones, iPads, friends, enemies, pets, lovers).
Read questions carefully. Show all work you can in the space provided. Where limits are given, write no more than the amount specified.
The rest will be ignored.
Avoid seeing anyone else¡¯s work or allowing yours to be seen.
Do not communicate with anyone but an exam proctor.
If you have a question, raise your hand.
When time is up, stop writing.
The points for each part are rough indication of the time that part should take.
Question
Points
Score
1
35
2
20
3
25
Total:
80
CSE 130, Spring 2014 Midterm Exam Page 1 of 7
1. [35 points] For each of the following OCaml programs, write down the type or value of the given variable, or circle ¡°Error¡± if you think there is a type or runtime error.
(a) [5 points]
let ans =
let x = 10 in
let f y z = x + y + z in
let x let h hx
Error
(b) [6 points]
= 100 in =f5 in
let rec chain fs = match fs with
| [] -> fun x -> x
| f::fs¡¯ -> fun x -> f (chain fs¡¯ x)
Error Type chain :
(c) [5 points]
letans=chain[(funx->x *x) ; (fun x -> 16 * x)
Value ans =
Error
(d) [3 points]
; (fun x -> x + 1) ]1
Value ans =
type ¡¯a tree = Leaf | Node of ¡¯a * ¡¯a tree * ¡¯a tree
let ans0 = Node (2, Node (1, Leaf, Leaf)
, Node (3, Leaf, Leaf))
Error Type ans0 :
(e) [5 points]
let rec flerb xs = match xs with
| [] -> Leaf
| x::xs¡¯ -> Node (x, Leaf, flerb xs¡¯)
Error Type flerb :
CSE 130, Spring 2014 Midterm Exam (f) [3 points]
let ans = flerb [0;1;2]
Error Value ans =
(g) [5 points]
let rec glub f t = match t with
| Leaf -> Leaf
| Node (x,l,r) -> Node (f x, glub f l, glub f r)
Error Type glub : (h) [3 points]
let ans = glub (fun x -> 2 * x) ans0 Error Value ans =
Page 2 of 7
CSE 130, Spring 2014 Midterm Exam Page 3 of 7 2. [20 points] Consider the two functions sum and fac shown below:
let rec sum n = match n with
| 0 -> 0
| n -> n + sum (n-1)
let rec fac n = match n with
| 0 -> 1
| n -> n * fac (n-1)
(a) [5 points] Write a tail recursive version of sum by filling in the blanks below:
let sumTR n =
let rec helper acc n =
| ->
| -> in
in helper
(b) [5 points] Write a tail recursive version of fac by filling in the blanks below:
let facTR n =
let rec helper acc n =
| ->
| -> in
in helper
CSE 130, Spring 2014 Midterm Exam Page 4 of 7 (c) [6 points] Spot that pattern! Now write a higher-order function
val foldn : (¡¯a -> int -> ¡¯a) -> ¡¯a -> int -> ¡¯a
that generalizes the tail-recursion in sumTR and facTR, by filling in the blanks below: let foldn f b n =
let rec helper acc n = | -> | ->
in
in helper
(d) [4 points] Your solution for foldn should be such that you can now implement sum and fac without recursion simply by passing in appropriate parameters to foldn. What are those parameters?
let sum = foldn
let fac = foldn
CSE 130, Spring 2014 Midterm Exam Page 5 of 7
3. [25 points]
In NanoML, we used exceptions at various places, for example, when looking up a variable that did not exist in the
environment.Abetterapproachistousethe¡¯a optiontype,definedthus: type ¡¯a option = None | Some of ¡¯a
(a) [4 points] Now, instead of throwing an exception (who knows where or how or even if it will get caught!) if a function can possibly fail, we can have it return an option value. For example:
let safeDiv num den = match den with
| 0 -> None
| _ -> Some (num / den)
Since division is undefined (and throws a nasty failure), we instead write a safeDiv that gracefully returns a None if the result is undefined, and Just i when the denominator is non-zero and hence the division is safe. What is the type of safeDiv?
Error Type safeDiv :
(b) [5 points] Fill in the blanks to write a version of lookup that returns an option, that is: val lookup: ¡¯a -> (¡¯a * ¡¯b) list -> ¡¯b option
When you are done, you should get the following behavior:
# lookup “a” [(“a”, 1); (“b”, 2), (“a”, 10)];;
– : int option = Some 1
# lookup “z” [(“a”, 1); (“b”, 2), (“a”, 10)];;
– : int option = None
let rec lookup k kvs =
| ->
| ->
CSE 130, Spring 2014 Midterm Exam Page 6 of 7 (c) [4 points] Fill in the blanks to write a function
val lift1 : (¡¯a -> ¡¯b) -> ¡¯a option -> ¡¯b option
such that when you are done, you get the following behavior
# lift1 string_of_int (Some 1);;
– : string option = Some “1”
# lift1 string_of_int None;;
– : string option = None
let lift1 f xo =
| -> | ->
(d) [5 points] Fill in the blanks to write a function
val lift2 : (¡¯a -> ¡¯b -> ¡¯c) -> ¡¯a option -> ¡¯b option -> ¡¯c option
such that when you are done, you get the following behavior
# lift2 (+) (Some 1) (Some 10);;
– : int option = Some 11
# lift2 (+) (None) (Some 10);;
– : int option = None
# lift2 (+) (Some 1) (None);;
– : int option = None
# lift2 (+) (None) (None);;
– : int option = None
let lift2 f xo yo =
| -> | ->
CSE 130, Spring 2014 Midterm Exam (e) [7 points] Consider the subset of NanoML given by the type:
Page 7 of 7
type expr = Var of string |Con ofint
| Neg of expr
| Plus of expr * expr
Write an interpreter function
(* variable
(* constant
(* negation of an expression *)
(* sum of two expressions *)
val eval : (string * int) list -> expr -> int option
such that when you are done you get the following behavior:
# eval [(“x”, 1); (“y”, 2); (“x”, 100)] (Plus (Var “x”, Var “y”));;
– int option = Some 3
# eval [(“x”, 1); (“y”, 2); (“x”, 100)] (Plus (Var “x”, Con 20));;
– int option = Some 21
# eval [(“x”, 1); (“y”, 2); (“x”, 100)] (Plus (Var “x”, Var “z”));;
– int option = None
# eval [(“x”, 1); (“y”, 2); (“x”, 100)] (Neg (Var “y”));;
– int option = Some (-2)
# eval [(“x”, 1); (“y”, 2); (“x”, 100)] (Neg (Var “z”));;
– int option = None
Note: Your implementation of eval must not use any match-with expressions other than the one given. Instead, use lift1 and lift2. You may also use any other functions you have implemented during this exam.
let rec eval env e = match e with |Varx ->
|Coni ->
|Nege¡¯ ->
| Plus (e1, e2) ->
*) *)