type expr = Var of int
          | Fun of (int * expr)
          | App of (expr * expr)
          | Cl of (int * expr * env)
and env = (int * expr) list

exception LookupFailed

let rec lookup m x = match m with
	[] -> (* raise LookupFailed *) Var x
	| (y, v)::m2 -> if (x = y) then v else lookup m2 x

let rec eval m e = match e with
(*
	Note: => used in place of \Downarrow

	v = lookup(m, x)
	----------------
	(m, x) => v
*)
	Var x -> lookup m x
(*
	----------------------------
	(m, ,\ x . e) => Cl(x, e, m)
*)
	| Fun (x, e) -> Cl (x, e, m)
(*
	(m, e1) => Cl(x, e, m')  (m, e2) => v  (m'', e) => v'
	-----------------------------------------------------
	(m, e1 e2) => v'

	where m'' = (x, v)::m'
*)
	| App (e1, e2) ->
		let v1 = eval m e1
		and v2 = eval m e2
		in
			(match v1 with
			Cl (x, e, m1) ->
				let m2 = (x, v2)::m1 in
					eval m2 e
			| _ -> App (v1, v2))
	| e -> e