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]