Quiz #4

main.ml

exception NotYetImplemented

(********************************************************************************)
(* Question 1 *)

let rec map l f = map_h l f (fun x -> x)  
and map_h l f k = match l with
| [] -> k []
| x :: xs -> map_h xs f (fun c -> k ((f x) :: c))

let rec map2 l f = map2_h l f (fun x -> x)
and map2_h l f k = match l with
| [] -> k []
| x :: xs -> map2_h xs f (fun c -> (f x) :: (k c))

type multichoice = A | B | C | D;;
let problem1_1: multichoice = raise NotYetImplemented;;
let problem1_2: multichoice = raise NotYetImplemented;;
let problem1_3: string = "
  <write your answer here>
";;

(********************************************************************************)
(* Question 2 *)

type 'a btree = 
| Leaf 
| Node of  'a btree * 'a * 'a btree

let rec exists (t : 'a btree) (f : 'a -> bool) (succ : 'a -> 'b) (fail :  unit -> 'b) : 'b =
  raise NotYetImplemented

(********************************************************************************)
(* Question 3 *)

type impexpr =
  Var of string
  | Add of impexpr * impexpr
  | Lt of impexpr * impexpr
  | Eq of impexpr * impexpr
  | Num of int

type impstmt =
  Assgn of string * impexpr
  | While of { guard: impexpr; body: impstmt }
  | Break_if of impexpr
  | Seq of impstmt * impstmt

type impprog = { body: impstmt; ret: impexpr }

type impvalue =
    VInt of int
  | VBool of bool

module StringMap = Map.Make(String)

type env = impvalue StringMap.t

exception Runtime

(* converts a value to a integer or raises an exception if it is not possible *)
let to_int v =
  match v with
  | VInt(v) -> v
  | _ -> raise Runtime

(* converts a value to a Boolean or raises an exception if it is not possible *)
let to_bool v =
  match v with
  | VBool(v) -> v
  | _ -> raise Runtime

(* Evaluate an impexpr; this is not required to be in tail-form *)
let rec interp_impexpr (env:env) (e:impexpr) : impvalue =
  match e with
  | Var(s) ->
    (match StringMap.find_opt s env with
     | Some(v) -> v
     | None -> raise Runtime)
  | Num(n) -> VInt(n)
  | Add(e1, e2) ->
    VInt((to_int (interp_impexpr env e1)) + (to_int (interp_impexpr env e2)))
  | Lt(e1, e2) ->
    VBool((to_int (interp_impexpr env e1)) < (to_int (interp_impexpr env e2)))
  | Eq(e1, e2) ->
    VBool((to_int (interp_impexpr env e1)) = (to_int (interp_impexpr env e2)))

let rec interp_stmt_h (env:env) (s:impstmt) (default_cont: env -> env) (break_cont: env -> env) : env =
  raise NotYetImplemented

let interp_prog (p:impprog) : impvalue =
  raise NotYetImplemented


(********************************************************************************)
(* problem 4, CS5400 Only *)

(* answers must be bool options *)
(* an answer of "true" is `Some true` *)
(* an answer of "false" is `Some false` *)
let prob4_1: bool option = None
let prob4_2: bool option = None
let prob4_3: bool option = None
let prob4_4: bool option = None
let prob4_5: bool option = None
let prob4_6: bool option = None
let prob4_7: bool option = None
let prob4_8: bool option = None