(* Question 1 *)

type expr = 
  | EVal of int
  | EAdd of expr * expr
  | ESub of expr * expr
  | EMul of expr * expr
  | EDiv of expr * expr

let rec eval = function
  | EVal i -> i
  | EAdd (a,b) -> eval a + eval b
  | ESub (a,b) -> eval a - eval b
  | EMul (a,b) -> eval a * eval b
  | EDiv (a,b) -> eval a / eval b


let _ = eval (EAdd (EVal 1, EVal 2))

(* Question 2 *)

type expr = 
  | EVal of int
  | EAdd of expr * expr
  | ESub of expr * expr
  | EMul of expr * expr
  | EDiv of expr * expr
  | ELet of string * expr * expr
  | EVar of string

let rec eval c = function
  | EVal i -> i
  | EAdd (a,b) -> eval c a + eval c b
  | ESub (a,b) -> eval c a - eval c b
  | EMul (a,b) -> eval c a * eval c b
  | EDiv (a,b) -> eval c a / eval c b
  | ELet (n,a,b) -> eval ((n,eval c a)::c) b
  | EVar n -> 
      try List.assoc n c 
      with Not_found -> failwith ("Value "^n^" not found")

let _ = eval [] (EAdd (EVal 1, EVar "x"))
let _ = eval [] (ELet ("x", EVal 3, EMul (EVar "x", EVar "x")))

(* Question 3 *)

type value = 
  | VInt of int
  | VBool of bool

let int = function VInt i -> i | _ -> failwith "Not an integer!"
let bool = function | VBool b -> b | _ -> failwith "Not a boolean!"

type expr = 
  | EVal of value
  | EAdd of expr * expr
  | ESub of expr * expr
  | EMul of expr * expr
  | EDiv of expr * expr
  | ELet of string * expr * expr
  | EVar of string
  | EEqu of expr * expr
  | EInf of expr * expr
  | ENot of expr 
  | EAnd of expr * expr
  | EIf  of expr * expr * expr

let rec eval c = function
  | EVal i -> i
  | EAdd (a,b) -> VInt (int (eval c a) + int (eval c b))
  | ESub (a,b) -> VInt (int (eval c a) - int (eval c b))
  | EMul (a,b) -> VInt (int (eval c a) * int (eval c b))
  | EDiv (a,b) -> VInt (int (eval c a) / int (eval c b))
  | ELet (n,a,b) -> eval ((n,eval c a)::c) b
  | EEqu (a,b) -> 
      VBool (match eval c a, eval c b with 
	       | VBool a, VBool b -> a = b
	       | VInt a, VInt b -> a = b
	       | _ -> failwith "Type mismatch!")
  | EInf (a,b) -> VBool (int (eval c a) < int (eval c b))
  | ENot a -> VBool (not (bool (eval c a)))
  | EAnd (a,b) -> VBool (bool (eval c a) && bool (eval c b))
  | EIf (i,t,f) -> 
      if (bool (eval c i)) then eval c t else eval c f
  | EVar n -> 
      try List.assoc n c 
      with Not_found -> failwith ("Value"^n^" not found!")

let _ = eval [] (ELet ("n", EVal (VInt 3), 
		       EIf (EEqu (EVar "n", EVal (VInt 2)),
			    EVar "n",
			    EAdd (EVar "n", EVar "n"))))

(* Question 4 *)

type typ = TInt | TBool 
let typename = function 
  | TInt -> "int"
  | TBool -> "bool"

let same a b = 
  if a <> b then failwith 
    ("This expression has type "
     ^ typename a 
     ^ " but is used here with type "
     ^ typename b )

let rec check c = function 
  | EVal (VInt _) -> TInt
  | EVal (VBool _) -> TBool
  | EVar n ->
      (try List.assoc n c 
       with Not_found -> failwith ("Unbound value "^n))
  | EAdd (a,b) | ESub (a,b) | EMul (a,b) | EDiv (a,b) ->
      same (check c a) TInt;
      same (check c b) TInt;
      TInt
  | ELet (n,a,b) -> check ((n,check c a)::c) b
  | EInf (a,b) ->
      same (check c a) TInt;
      same (check c b) TInt;
      TBool
  | EEqu (a,b) ->
      same (check c b) (check c a);
      TBool
  | EIf (i,t,f) ->
      same (check c i) TBool;
      let r = check c t in
	same r (check c f);
	r
  | EAnd (a,b) -> 
      same (check c a) TBool;
      same (check c b) TBool;
      TBool
  | ENot a ->
      same (check c a) TBool;
      TBool

let _ = check [] (ELet ("n", EVal (VInt 3), 
		       EIf (EEqu (EVar "n", EVal (VInt 2)),
			    EVar "n",
			    EAdd (EVar "n", EVar "n"))))

let _ = check [] (ELet ("n", EVal (VInt 3), 
		       EIf (EEqu (EVar "n", EVal (VBool false)),
			    EVar "n",
			    EAdd (EVar "n", EVar "n"))))

(* Question 5 *)

type value = 
  | VInt of int
  | VBool of bool
  | VFun of string * (string * value) list * expr 

and expr = 
  | EVal of value
  | EAdd of expr * expr
  | ESub of expr * expr
  | EMul of expr * expr
  | EDiv of expr * expr
  | ELet of string * expr * expr
  | EVar of string
  | EEqu of expr * expr
  | EInf of expr * expr
  | ENot of expr 
  | EAnd of expr * expr
  | EIf  of expr * expr * expr
  | EFun of string * expr
  | EApp of expr * expr

let int = function VInt i -> i | _ -> failwith "Not an integer!"
let bool = function VBool b -> b | _ -> failwith "Not a boolean!"
let func = function VFun (n,c,e) -> (n,c,e) | _ -> failwith "Not a function!"

let rec eval c = function
  | EVal i -> i
  | EAdd (a,b) -> VInt (int (eval c a) + int (eval c b))
  | ESub (a,b) -> VInt (int (eval c a) - int (eval c b))
  | EMul (a,b) -> VInt (int (eval c a) * int (eval c b))
  | EDiv (a,b) -> VInt (int (eval c a) / int (eval c b))
  | ELet (n,a,b) -> eval ((n,eval c a)::c) b
  | EEqu (a,b) -> 
      VBool (match eval c a, eval c b with 
	       | VBool a, VBool b -> a = b
	       | VInt a, VInt b -> a = b
	       | _ -> failwith "Type mismatch!")
  | EInf (a,b) -> VBool (int (eval c a) < int (eval c b))
  | ENot a -> VBool (not (bool (eval c a)))
  | EAnd (a,b) -> VBool (bool (eval c a) && bool (eval c b))
  | EIf (i,t,f) -> 
      if (bool (eval c i)) then eval c t else eval c f
  | EVar n -> 
      (try List.assoc n c 
       with Not_found -> failwith ("Value"^n^" not found!"))
  | EApp (f,a) ->
      let (n,c',b) = func (eval c f) in
	eval ((n, eval c a)::c') b
  | EFun (n,f) -> VFun (n,c,f)

let _ = eval [] 
  (ELet ("double", EFun ("x", EAdd (EVar "x", EVar "x")),
	 EApp (EVar "double", 
	       EApp (EVar "double",
		     EVal (VInt 3)))))

(* Question 6 *)

type value = 
  | VInt of int
  | VBool of bool
  | VFun of string * string * (string * value) list * expr 

and expr = 
  | EVal of value
  | EAdd of expr * expr
  | ESub of expr * expr
  | EMul of expr * expr
  | EDiv of expr * expr
  | ELet of string * expr * expr
  | EVar of string
  | EEqu of expr * expr
  | EInf of expr * expr
  | ENot of expr 
  | EAnd of expr * expr
  | EIf  of expr * expr * expr
  | EFun of string * string * expr
  | ERec of string * expr * expr
  | EApp of expr * expr

let int = function VInt i -> i | _ -> failwith "Not an integer!"
let bool = function VBool b -> b | _ -> failwith "Not a boolean!"
let func = function VFun (s,n,c,b) -> (s,n,c,b) | _ -> failwith "Not a function!"

let rec eval c = function
  | EVal i -> i
  | EAdd (a,b) -> VInt (int (eval c a) + int (eval c b))
  | ESub (a,b) -> VInt (int (eval c a) - int (eval c b))
  | EMul (a,b) -> VInt (int (eval c a) * int (eval c b))
  | EDiv (a,b) -> VInt (int (eval c a) / int (eval c b))
  | ELet (n,a,b) -> eval ((n,eval c a)::c) b
  | EEqu (a,b) -> 
      VBool (match eval c a, eval c b with 
	       | VBool a, VBool b -> a = b
	       | VInt a, VInt b -> a = b
	       | _ -> failwith "Type mismatch!")
  | EInf (a,b) -> VBool (int (eval c a) < int (eval c b))
  | ENot a -> VBool (not (bool (eval c a)))
  | EAnd (a,b) -> VBool (bool (eval c a) && bool (eval c b))
  | EIf (i,t,f) -> 
      if (bool (eval c i)) then eval c t else eval c f
  | EVar n -> 
      (try List.assoc n c 
       with Not_found -> failwith ("Value"^n^" not found!"))
  | EApp (f,a) ->
      let r = eval c f in
      let (s,n,c',b) = func r in	
eval ((s,r)::(n, eval c a)::c') b
  | EFun (s,n,f) -> VFun (s,n,c,f)

let maccarthy = 
  EFun ("mc", "n", 
	EIf (EInf (EVal (VInt 100), EVar "n"),
	     ESub (EVar "n", EVal (VInt 10)),
	     EApp (EVar "mc", 
		   EApp (EVar "mc",
			 EAdd (EVar "n", EVal (VInt 11))))))

let _ = eval [] (EApp (maccarthy, EVal (VInt 23)))