datatype Expr = Num of int
              | Var of string
              | Add of Expr * Expr
              | Times of Expr * Expr
              | Apply of string * (Expr list)
              | Cond of Expr * Expr * Expr
              | Let of string * Expr * Expr;

type function = (string list * Expr);
type env = ((string * int) list) * ((string * function) list)

fun env_vars (a,_) = a
fun env_funs (_,a) = a

exception LookupEx;

fun lookup(s:string,[] : (string * 'a) list) = raise LookupEx
  | lookup(s, (t,v)::rest) = if s=t then v else lookup(s,rest);

fun lookupVar (s,r) = lookup (s, env_vars r);
fun lookupFun (s,r) = lookup (s, env_funs r);
fun envAppendVal (s,v,(rv,rf)) = ((s,v)::rv, rf);
fun zipNamesToVals (sl,vl,(rv,rf)) = (zip (sl,vl), rf);

fun zip (_,[]) = []
  | zip ([],_) = []
  | zip (a::al, b::bl) = (a,b) :: (zip (al,bl));

fun eval (Num n, r) = n
  | eval (Var s, r) = lookupVar (s, r)
  | eval (Add (e,e'), r) = (eval (e,r)) + (eval (e',r))
  | eval (Times (e,e'), r) = (eval (e,r)) * (eval (e',r))
  | eval (Cond (e,e',e''), r) = if eval (e,r) = 0 
                                then eval (e',r)
                                else eval (e'',r)
  | eval (Let (s,e,e'), r) = let val v = eval(e,r) in
                                 eval (e', envAppendVal(s,v,r))
                             end
  | eval (Apply (s,el), r) = let val vl = map (fn e => eval (e,r)) el 
                                 val (param_names, funbody) = lookupFun (s,r) in
                                 eval (funbody, zipNamesToVals (param_names, vl, r))
                             end;

(*some tests*)
val e1 = Let ("a", Num 3, Let ("b", Num 4, Times (Var "a", Var "b")));
val eval_e1 = eval (e1, ([],[]));

(*function that calculates the nth fibonacci number*)
val fibBody = Cond (Var "n", 
                    Num 1,
                    Cond (Add (Var "n", Num (~1)), Num 1,
                          Add (Apply ("fib", [Add (Var "n",Num (~1))]), Apply ("fib", [Add (Var "n",Num (~2))]))
                   ));

val fibFun = (["n"],fibBody);
fun fib n = eval (fibBody, ([("n",n)], [("fib", fibFun)]));