## Abstract Stack Machine Practice

During this lab we'll practice using the Abstract Stack Machine you saw during lecture. The examples below involve primitive types, user-defined datatypes, matches, and functions. In each example, draw the workspace, stack, and heap just after the first time an x is pushed onto the stack.

The problems below assume you have access to this datatype declaration:

```  let rec 'a tree =
| Empty
| Node of 'a tree * 'a * 'a tree
```

### Problem 1

```  let y = 3 in
let f (z: int): int = y * z * z in
let x = f 5 in
x
```

### Problem 2

```  let y = Node(Node(Empty, 1, Empty), 20, Empty) in
let x = begin match y with
| Empty -> Empty
| Node(lt, v, rt) ->
begin match lt with
| Empty -> rt
| Node(_, v', _) -> Node(Empty, v * v', rt)
end
end
in Node(Empty, 1, x)
```

### Problem 3

```  let rec f(y: int tree): int =
begin match y with
| Empty -> 1
| Node(Empty, x, Empty) -> x
| Node(lt, z, rt) -> (f lt) * (f rt)
end
in f (Node(Empty, 5, Node(Empty, 6, Empty)))
```

### Problem 4

```  let rec map (f: 'a -> 'b) (y: 'a list): 'b list =
begin match y with
| [] -> []
| h :: t -> (f a) :: (map f t)
end in
let x = map (fun t -> t + 1) [0; 1; 2] in
0 :: x
```

### Problem 5

```  let rec map_tree (f: 'a -> 'b) (y: 'a tree): 'b tree =
begin match y with
| Empty -> Empty
| Node(lt, v, rt) ->
let lt' = map_tree f lt in
let rt' = map_tree f rt in
let x = f v in
Node(lt', x, rt')
end in
let rec map (f: 'a -> 'b) (y: 'a list): 'b list =
begin match y with
| [] -> []
| h :: t -> (f h) :: (map f t)
end in
map (fun t -> map_tree string_of_int t) [Node(Empty, 10, Node(Empty, 5, Empty), Empty); Empty]
```