type 'a tree = Node of string * 'a * 'a tree * 'a tree | Leaf;;

exception NotFound of string;;

let rec insert (t: int tree) (key: string) (value: int) =
  match t with
    Node (k,v,l,r) -> if key<k then Node(k,v, insert l key value, r)
                      else if key > k then Node (k,v,l, insert r key value)
                      else Node (key,value,l,r)
  | Leaf -> Node(key,value,Leaf,Leaf);;

let rec look (t: int tree) (key: string) : int =
  match t with
    Node(k,v,l,r) -> if key<k then look l key
                      else if key > k then look r key
                      else v
  | Leaf -> raise (NotFound key);;

type env = int tree;;
let empty_env = Leaf;;

type var = string;;

type exp = NUM of int 
         | VAR of var 
         | PLUS of exp * exp
         | LET of var * exp * exp;;

let rec interp (e: exp) (rho: env) : int =
   match e with
     NUM i -> i
   | VAR v -> look rho v
   | PLUS(e1,e2) -> interp e1 rho + interp e2 rho
   | LET(v,e1,e2) -> interp e2 (insert rho v (interp e1 rho));;

let exp1 = LET("y",PLUS(NUM 3, NUM 4), PLUS(VAR "y", VAR "y"));;
let exp2 = LET("y",PLUS(NUM 3, NUM 4), VAR "z");;

let val1 = interp exp1 empty_env;;

let rec denot (e: exp) : env -> int =
   match e with
     NUM i -> fun rho -> i
   | VAR v -> fun rho -> look rho v
   | PLUS(e1,e2) -> fun rho -> denot e1 rho + denot e2 rho
   | LET(v,e1,e2) -> fun rho -> denot e2 (insert rho v (denot e1 rho));;

let rec denot (e: exp) : env -> int =
   match e with
     NUM i -> fun rho -> i
   | VAR v -> fun rho -> look rho v
   | PLUS(e1,e2) -> let d1 = denot e1 and d2 = denot e2 
                     in fun rho -> d1 rho + d2 rho
   | LET(v,e1,e2) -> let d1 = denot e1 and d2 = denot e2 
                      in fun rho -> d2 (insert rho v (d1 rho));;

type cmd = SET of var * exp
         | SEQ of cmd * cmd
         | IF of exp * cmd * cmd
         | WHILE of exp * cmd;;

let rec cinterp c rho =
   match c with
     SET(v,e) -> insert rho v (interp e rho)
   | SEQ(c1,c2) -> cinterp c2 (cinterp c1 rho)
   | IF(e,c1,c2) -> if interp e rho <> 0 
                    then cinterp c1 rho 
                    else cinterp c2 rho
   | WHILE(e,c) -> if interp e rho <> 0 
                   then let rho1 = cinterp c rho
                         in cinterp (WHILE(e,c)) rho1
                   else rho

let cmd1 = SEQ(SET("s", NUM 0),
            SEQ(SET("i", NUM 6),
                WHILE(VAR "i", 
                   SEQ(SET("s", PLUS(VAR"s",VAR"i")),
                       SET("i", PLUS(VAR"i",NUM (-1)))))));;