**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