**1. Give the types that the OCaml will infer for the following definitions, or write ERROR if type inference would fail let a = 1 + 2.0;; let b = (let b = 2 in (string_of_int b)) in b+b;; let c x (y,z) = (x::y,z) let d x y = x y let e s = print_string s;; let f = fun x -> fun y -> y;; let g = f 1;; let h = g (fun x -> 1) **2. Consider the following code. type 'a reflist = Nil | Cons of 'a * 'a reflist ref let single x = Cons (x, ref Nil);; let rec foldr_rl f a l = match l with Nil -> a | Cons(x,rl) -> foldr_rl f (f a x) !rl let mystery1 l = "[ "^(foldr_rl (fun a x -> (string_of_int x)^"; "^a) "]" l) let rec mystery2 l a = match l with Nil -> single a | Cons (x,rl) -> rl := (mystery2 !rl a); l a. What is the type of the mystery1 function? b. What does it do (at a high level)? c. What is the type of the mystery2 function? d. What does it do? e. Suppose we executed the following code: let l = mystery2 (mystery2 (single 1) 2) 3;; mystery1 l;; What does the second expression return? f. Now suppose we execute the code from (e) above, but then additionally execute this code: let m = mystery2 l 4;; mystery1 l;; What does the second expression return (that's not a typo: it is calling (mystery1 l) not (mystery1 m)? **3. Consider the following code let f x = let g y = x + y in let h z = x - z in (g,h);; let (m,n) = f 6;; let x = 5;; (m 6)+(m 7);; a. What does the final expression return when this is run in OCaml? b. If OCaml used dynamic scoping instead, what would the last expression return? **4. How would you encode the following Java class declaration in OCaml using the encoding that we discussed in class? public class A { private int x; private int y; public A(int x, int y) { this.x = x; this.y = y; } public void incr(int n) { x += n; y += n; } public int diff() { return x-y; } public String toString() { return "("+x+","+y","+")"; } **5. Give a derivation that proves the following, using the operational semantics rules from the slides: A; if z then x+1 else y+1 => 2 when A is the environment .,x=1,y=2,z=true **6. Suppose I extend the expression grammar from the slides as follows E ::= ... | try E1 onfail E2 | fail Then I add the following operational semantics rules to handle these constructs A; E1 => v --------------------------- A; try E1 onfail E2 => v A; E1 => fail A; E2 => v --------------------------- A; try E1 onfail E2 => v A; fail => fail Moreover I add variants of rules I already have to propagate failure. For example, I add the following two rules for addition: A; E1 => fail -------------- A; E1 + E2 => fail A; E1 => v A; E2 => fail ---------------------------- A; E1 + E2 => fail a. Write rules for propagating failure in a similar way for other expressions, in particular, give rules for let bindings and conditionals. b. Give a derivation to prove the following evaluation: A; try (1+fail) onfail 2 => 2 ====================================================================== ANSWERS: **1. a : ERROR b : ERROR c : 'a -> ('a list * 'b) -> 'a list * 'b d : ('a -> 'b) -> 'a -> 'b e : string -> unit f : 'a -> 'b -> 'b g : 'a -> 'a h : 'a -> int **2. a. int reflist -> string b. converts a reflist to a string (but in reverse!) c. 'a reflist -> 'a -> 'a reflist d. adds an element to the end of the list e. "[ 3; 2; 1; ]" f. "[ 4; 3; 2; 1; ]" **3. a. 25 b. 23 **4. let makeA x y = let x = ref x in let y = ref y in let incr n = x := !x + n; y := !y + n in let diff () = !x - !y in let toString () = "("^(string_of_int !x)^","^(string_of_int !y)^")" in (incr, diff, toString) **5. A(x) = 1 ----------- A(z) = true A; x => 1 A; 1 => 1 ------------ -------------------------- A; z => true A; x+1 => 2 ------------------------------------------ A; if z then x+1 else y+1 => 2 **6. a. Define r ::= v | fail A; E1 => fail ---------------------------- A; let x = E1 in E2 => fail A; E1 => v A,x=v; E2 => r -------------------------------- A; let x = E1 in E2 => r A; E1 => fail --------------------------------- A; if E1 then E2 else E3 => fail A; E1 => true A; E2 => r ------------------------------- A; if E1 then E2 else E3 => r A; E1 => false A; E3 => r ------------------------------- A; if E1 then E2 else E3 => r b. A; 1 => 1 A; fail => fail ---------------------------- A; 1+fail => fail A; 2 => 2 -------------------------------------- A; try (1+fail) onfail 2 => 2