---
# System prepended metadata

title: Homework 6

---

# Homework 6
- Chiao Lu
    - UID: 204848946
    - Email: josephlu85@engineering.ucla.edu
- Aishni Parab
    - UID: 905526328
    - Email: aishni@cs.ucla.edu

## Problem 1
### (a)

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

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

### (c\)
```ocaml=
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,
```ocaml= 
let a = ref 0 in
let b = ref (function x -> x+1) in 
let x = a := 5 in !b !a
```
eventually steps to
```ocaml=
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.