type expr 
  = Int of int
  | Add of expr * expr 
  | Sub of expr * expr
  | Mul of expr * expr
  | Div of expr * expr
  | Let of string * expr * expr
  | Id of string
type environment = (string * int) list

let rec lookup (n:string) (env:environment) : int =
  match env with
  | [] -> raise (Failure ("Identifier " ^ n ^ " is not in scope."))
  | (x,value)::rest when x = n -> value
  | _::rest -> lookup n rest

let rec eval (env:environment) (e:expr) : int = 
  match e with
  | Int i -> i
  | Add (e1, e2) -> eval env e1 + eval env e2
  | Sub (e1, e2) -> eval env e1 - eval env e2
  | Mul (e1, e2) -> eval env e1 * eval env e2
  | Div (e1, e2) -> eval env e1 / eval env e2
  | Id n -> lookup n env
  | Let (n, dexpr, body) -> 
     let dexpr_v = eval env dexpr in
     let body_v = eval ((n,dexpr_v)::env) body in
     body_v
let e2 = Let ("x", Int 5, Add (Id "x", Int 4))