# Homework 6
- Chiao Lu
- UID: 204848946
- Email: [e-mail]
- Aishni Parab
- UID: 905526328
- Email: [e-mail]

## Problem 1
### (a)

let r = ref 41 in let x = (r:=!r +1) in !r

### (b)

let r = ref 41 in 
let x = ((function (r: int ref) -> (r := 41; 500))
(r:=!r+1;ref 404)) in !r;;

### (c\)

let f = (let r = ref 5 in function() 
-> (r:=!r+1;!r)) in
(f ()) * (f ());;

## Problem 2
### (a)
<pre>
<let x = ref 0 in let y = x in let z = x:=5 in !y, {}> &rightarrow;
<let x = l1 in let y = x in let z = x:=5 in !y, {(l1,0)}> &rightarrow;
<let y = l1 in let z = l1:=5 in !y, {(l1,0)}> &rightarrow;
<let z = l1:=5 in !l1, {(l1,0)}> &rightarrow;
<let z = () in !l1, {(l1, 5)}> &rightarrow;
<!l1, {(l1, 5)}> &rightarrow;
<5, {(l1, 5)}>
</pre>

### (b)
Let <code>&Sigma;={(l1, Int), (l2, Int→Int)}</code>
<pre>
&Sigma;(l1)=Int
----------- (T-LOC) -------- (T-NUM)
{};&Sigma; &RightTee; l1:(Ref Int) {};&Sigma; &RightTee; 5:Int &#10112
---------------------------------(T-ASSIGN) ------------------- (T-APP)
{};&Sigma; &RightTee; (l1:=5):True {x:True};&Sigma; &RightTee; !l2 !l1 : Int
----------------------------------------------------------------- (T-LET)
{};&Sigma; &RightTee; let x = l1:=5 in !l2 !l1 : Int
</pre>
Where &#10112; is shown below
<pre>
&Sigma;(l2) = (Int&rightarrow;Int) &Sigma;(l1) = Int
---------------------- (T-LOC) ----------------- (T-LOC)
{x:True};&Sigma; &RightTee; l2:(Ref Int&rightarrow;Int) {x:True};&Sigma; &RightTee; l1:(Ref Int)
---------------------- (T-DEREF) ------------ (T-DEREF)
{x:True};&Sigma; &RightTee; !l2:(Int&rightarrow;Int) {x:True};&Sigma; &RightTee; !l1:Int
</pre>

### (c\)

The following program,

let a = ref 0 in
let b = ref (function x -> x+1) in 
let x = a := 5 in !b !a

eventually steps to

let x = l1 := 5 in !l2 !l1

Evaluation steps:

<pre>
<let a = ref 0 in
let b = ref (function x &rightarrow; x+1) in
let x = a := 5 in !b !a
, {}>

&rightarrow;

<let a = l1 in
let b = ref(function x &rightarrow; x+1) in
let x = a :=5 in !b !a
, {(l1, 0)}>

&rightarrow;

<let b = ref(function x &rightarrow; x+1) in
let x = l1 :=5 in !b !l1
, {(l1, 0)}>

&rightarrow;

<let b = l2 in
let x = l1 := 5 in !b !l1
, {(l2, function x &rightarrow; x+1), (l1, 0)}>

&rightarrow;

<let x = l1 :=5 in !l2 !l1,
{(l2, function x &rightarrow; x+1), (l1, 0)}>
</pre>
## Problem 3
### (a)
The following program typechecks and is eventually stuck by the following steps:
<pre>
<let x = ref 0 in
let y = x in
let z = free x in
free y, {}>

&rightarrow;
<let x = l1 in
let y = x in
free x in
free y, {(l1, 0)}>

&rightarrow;

<let y = l1 in
free l1 in
free y, {(l1, 0)}>

&rightarrow;

<free l1 in
free l1, {(l1, 0)}>

&rightarrow;
<free l1, {}>

&rightarrow;

<b style="color: #ff0000">stuck</b>

</pre>

### (b)
Program in (a) is a counter example.

### (c\)
This statement holds.