Starter code for Assignment #7 for CS4400 Spr24

main.ml

(* exercise 1: basic OCaml *)

exception Not_implemented

let rec sum_if (l: int list) (f: int -> bool) : int = raise Not_implemented

type btree =
  Leaf of int
  | Node of int * btree * btree

let rec sum_tree_if (t : btree) (f : int -> bool) : int = raise Not_implemented

(**********************************************************************************)
(* exercise 2: environment-passing untyped lambda-calculus interpreter *)
module StringMap = Map.Make (String)

exception Runtime of string

type lexp =
    App of lexp * lexp
  | Abs of string * lexp
  | Let of string * lexp * lexp
  | Var of string
  | Num of int
  | Add of lexp * lexp

type lamvalue =
  | LamV of lamvalue StringMap.t * string * lexp
  | NumV of int

type env = lamvalue StringMap.t

let mt_env = StringMap.empty

let get_num v =
  match v with
  | LamV(_) -> raise (Runtime("runtime: expected number"))
  | NumV(v) -> v

let rec interp_l (env:env) e = raise Not_implemented

(**********************************************************************************)
(** exercise 3: a typechecker and interpreter for a language with references *)
module IntMap = Map.Make (Int)

type hvalue =
  | NumV of int
  | LocV of int

type heap = { fresh: int; state: hvalue IntMap.t }

type henv = hvalue StringMap.t

(** returns a pair (new_loc, new_heap) where new_heap is the result of inserting value
    into h at location loc *)
let alloc_heap (h:heap) (value:hvalue) : int * heap =
  let ret_address = h.fresh in
  let new_heap = IntMap.add ret_address value h.state in
  (ret_address, { fresh = ret_address + 1; state = new_heap })

(** looks up location in h *)
let lookup_heap (h:heap) (loc:int) : hvalue =
  IntMap.find loc h.state

(* returns a new heap equal to h except at location loc is equal to v *)
let update_heap (h: heap) (loc:int) (v:hvalue) =
  { fresh = h.fresh; state = IntMap.add loc v h.state }

let empty_heap = { fresh = 0; state = IntMap.empty }

(* atoms do not affect the heap *)
type atom =
  | Num of int
  | Var of string

type hexp =
  Let of string * hexp * hexp
  | Box of atom
  | Unbox of atom
  | Set of atom * atom
  | Atom of atom

let get_loc v =
  match v with
  | LocV(v) -> v
  | _ -> raise (Runtime("expected location"))

let rec interp_h (env:henv) (heap:heap) (e:hexp) : heap * hvalue = raise Not_implemented

(**********************************************************************************)
(* problem 3b *)
type typ =
  TNum
  | TRef of typ

type tenv = typ StringMap.t

exception Typecheck of string

let rec type_of tenv e = raise Not_implemented