Quiz 3 starter code

exception NotImplemented

(********************************)
(* Problem 1: OCaml Programming *) 
(********************************)

(* An exception that occurs during a program's evaluation. *)
exception Runtime 
  
(* Helper function for testing whether a program throws a Runtime exception. *)
let assert_runtime (f: unit -> 'a): unit =
  try 
    f() ;
    assert false
  with 
  | Runtime -> assert true
  | _ -> assert false ;;

(**************)
(* Problem 1a *)
(**************)

(* Represents a binary tree. *)
type btree =
  | Leaf of int
  | Node of int * btree * btree ;; 

(* Returns true if the provided binary tree contains an even number of 
   vertices (meaning either a Leaf or a Node) whose value is an even integer. *)
let even_even (bt: btree): bool = raise NotImplemented ;;
  
(**************)
(* Problem 1b *) 
(**************) 
               
(* Finds the longest length string in a list of strings. If the provided list is
   empty (no longest string exists), then this function throws a Runtime 
   exception. *)
let longest_string (l: string list): string = raise NotImplemented ;;

(*********************************)
(* Problem 2: Garbage Collection *) 
(*********************************)

(**************)
(* Problem 2a *)
(**************)
                                  
let removed_1: bool = raise NotImplemented ;;
let removed_2: bool = raise NotImplemented ;;
let removed_3: bool = raise NotImplemented ;;
let removed_4: bool = raise NotImplemented ;;
let removed_5: bool = raise NotImplemented ;;
let removed_6: bool = raise NotImplemented ;;


(*****************************)
(* Problem 3: Dynamic Safety *) 
(*****************************) 
  
(* An exception that is thrown when a Trap statement is encountered. *)
exception Trap
  
(* Helper function for testing whether a program throws a Trap exception. *)
let assert_trap (f: unit -> 'a): unit =
  try 
    f() ;
    assert false
  with 
  | Trap -> assert true
  | _ -> assert false ;;
                              
(* Represents an expression in the tiny assembly language. *)
type tinyasm = 
  | Load of { reg: int; addr: int } 
  | Store of { reg : int; addr: int } 
  | Setreg of { reg: int; value: int } 
  | Trap of int 
  | AddInt 
  (* If the value in register 0 is 0, then sets register regr to the value in 
     regf (the false case); otherwise, sets register regr to the value in regt 
     (the true case). *)
  | CSel of { regr: int; regt: int; regf: int }
  | Ret ;;

(* Represents the internal state of a tiny assembly language, including both
   registers and the heap *)
type state = { reg: int array; heap: int array;} ;;

(* Helper function for interpreting tiny assembly language programs. Mutates the 
   provided state (registers and heap) according to the semantics of tiny 
   assembly. *)
let rec interp_insn (state: state) (asm: tinyasm list): unit =
  match asm with
  | Load { reg=r; addr=addr}::rst  ->
      Array.set state.reg r (Array.get state.heap addr) ;
      interp_insn state rst
  | Store { reg=r; addr=addr }::rst ->
      let v = Array.get state.reg r in
      Array.set state.heap addr v ;
      interp_insn state rst
  | Setreg { reg=r; value=v }::rst ->
      Array.set state.reg r v ;
      interp_insn state rst
  | Trap(i)::rst ->
      if (Array.get state.reg 0) = i 
      then () 
      else raise Trap ;
      interp_insn state rst
  | AddInt::rst ->
      let v = (Array.get state.reg 1) + (Array.get state.reg 2) in
      Array.set state.reg 0 v;
      interp_insn state rst
  | CSel { regr=r; regt=t; regf=f }::rst ->
      if (Array.get state.reg 0) = 0
      then Array.set state.reg r (Array.get state.reg f)
      else Array.set state.reg r (Array.get state.reg t) ;
      interp_insn state rst
  | Ret::rst -> () 
  (* If the program does not end with a return statement, we throw an error. *)
  | [] -> raise Trap ;;

(* Interprets a tiny assembly language program. Each tiny assembly program is 
   ran with 3 registers and a heap size of 100. *)
let interp_asm (l: tinyasm list): int =
  let state = { reg=Array.make 3 (-1); heap=Array.make 100 (-1) } in
  interp_insn state l;
  Array.get state.reg 0 ;;
  
(* Returns a fresh location, given a counter whose value is the current fresh 
   location. As a side effect, this function mutates the provided counter by 
   incrementing it by one. *)
let fresh (iref: int ref) : int =
  let cur = !iref in
  iref := cur + 1;
  cur ;;

(* Represents an expression in the if-lang. *)
type ifexp =
  | Num of int
  | Bool of bool
  | Add of ifexp * ifexp 
  | If of ifexp * ifexp * ifexp ;;
  
(************************)
(* Implementation task: *)
(************************)
                         

(* Tags for both numbers and booleans that are stored in the heap. *)
let num_tag: int = 0 ;;
let bool_tag: int = 1 ;;

(* Compiles a if-lang program into a tiny assembly language program with dynamic
   safety. *)
let rec safe_if_to_asm (e: ifexp) (counter: int ref): int * tinyasm list = 
  match e with
  | Num(n) -> 
      let tag_addr = fresh counter in
      let num_addr = fresh counter in
      let num_prog = [
        Setreg { reg=0; value=num_tag };
        Setreg { reg=1; value=n };
        (* Store both the number and its tag in the heap so that they appear 
           [..., tag, n, ...] *)
        Store { reg=0; addr=tag_addr };
        Store { reg=1; addr=num_addr }
      ] in
      (tag_addr, num_prog)
  | Bool(b) ->
      let bool_v = if b then 1 else 0 in
      let tag_addr = fresh counter in
      let bool_addr = fresh counter in
      let bool_prog = [
        Setreg { reg=0; value=bool_tag }; 
        Setreg { reg=1; value=bool_v };
        (* Store both the boolean and its tag in the heap so that they appear 
           [..., tag, bool_v, ...] *)
        Store { reg=0; addr=tag_addr };
        Store { reg=1; addr=bool_addr }
      ] in
      (tag_addr, bool_prog)
  | Add(l, r) ->
      let (l_addr, l_prog) = safe_if_to_asm l counter in
      let (r_addr, r_prog) = safe_if_to_asm r counter in
      let tag_addr = fresh counter in
      let add_addr = fresh counter in
      let add_prog = [
        (* Check if the left expression is tagged as an integer. *)
        Load { reg=0; addr=l_addr };
        Trap(num_tag);
        (* Check if the right expression is tagged as an integer. *)
        Load { reg=0; addr=r_addr };
        Trap(num_tag);
        (* If the program is still running, then both the left and right 
           expressions are numbers. So we add them and store the result. *)
        Load { reg=1; addr=l_addr + 1 };
        Load { reg=2; addr=r_addr + 1 };
        AddInt;
        Store { reg=0; addr=add_addr } ;
        (* Store both the number and its tag in the heap so that they appear 
           [..., tag, l + r, ...] *)
        Setreg { reg=0; value=num_tag };
        Store { reg=0; addr=tag_addr } 
      ] in
      (tag_addr, List.concat [l_prog; r_prog; add_prog])
  | If(g, thn, els) ->
    (* implement me *)
    raise NotImplemented


(* Runs an if-lang program by compiling it into the tiny assembly language and
   then running it with the tiny assembly interpreter. *)
let run_if_safe (e: ifexp): int =
  let (addr, prog) = safe_if_to_asm e (ref 0) in
  let ret_prog = [Load { reg=0; addr=addr + 1 }; Ret] in
  interp_asm (List.concat [prog; ret_prog]) ;;




(*********************************)
(* Problem 4: Rust               *) 
(*********************************)

let rust_1: bool = raise NotImplemented ;;
let rust_2: bool = raise NotImplemented ;;
let rust_3: bool = raise NotImplemented ;;
let rust_4: bool = raise NotImplemented ;;
let rust_5: bool = raise NotImplemented ;;
let rust_6: bool = raise NotImplemented ;;