(* lambda-calculus (with programming extensions) interpreter and examples. Alan Mycroft -- Lent 1999. *) datatype Expr = Name of string | Numb of int | Plus of Expr * Expr | Minus of Expr * Expr | Times of Expr * Expr | Cond of Expr * Expr * Expr | Fn of string * Expr | Apply of Expr * Expr | Let of string * Expr * Expr | Y of Expr; datatype Env = Empty | Defn of string * Val ref * Env and Val = IntVal of int | FnVal of string * Expr * Env; exception oddity of string; fun lookup(n, Defn(s, v, r)) = if s=n then !v else lookup(n, r) | lookup(n, Empty) = raise oddity("unbound name"); fun eval(Name(s), r) = lookup(s, r) | eval(Numb(n), r) = IntVal(n) | eval(Plus(e, e'), r) = let val v = eval(e,r); val v' = eval(e',r) in case (v,v') of (IntVal(i), IntVal(i')) => IntVal(i+i') | (v, v') => raise oddity("plus of non-number") end | eval(Minus(e, e'), r) = let val v = eval(e,r); val v' = eval(e',r) in case (v,v') of (IntVal(i), IntVal(i')) => IntVal(i-i') | (v, v') => raise oddity("minus of non-number") end | eval(Times(e, e'), r) = let val v = eval(e,r); val v' = eval(e',r) in case (v,v') of (IntVal(i), IntVal(i')) => IntVal(i*i') | (v, v') => raise oddity("times of non-number") end | eval(Cond(e, e', e''), r) = (case eval(e,r) of IntVal(i) => eval(if i<>0 then e' else e'', r) | v => raise oddity("cond of non-number")) | eval(Fn(s, e), r) = FnVal(s, e, r) | eval(Apply(e, e'), r) = (case eval(e, r) of IntVal(i) => raise oddity("apply of non-function") | FnVal(bv, body, r_fromdef) => let val arg = eval(e', r) in eval(body, Defn(bv, ref arg, r_fromdef)) end) | eval(Let(s, e, e'), r) = (* The next line exploits the Let=Apply-of-lambda equivalence. *) eval(Apply(Fn(s,e'),e), r) | eval(Y(Fn(f,e)), r) = (* Note that Y can only be applied to functions, indeed functions *) (* whose body 'e' is also a function -- think about it. *) (* The '999' acts as a dummy value for 'f' (later overwritten), *) (* it will not be used (provided 'e' is of the form Fn(x,e')). *) let val fv = ref (IntVal(999)); val r' = Defn(f, fv, r); val v = eval(e, r') in fv := v; v end; fun try(e) = eval(e, Empty); val exampletotry = Apply(Fn("x", Apply(Fn("n", Plus(Name("n"), Name("x"))), Numb(4))), Numb(3)); val examplewhichloops = Apply(Fn("x", Apply(Name("x"), Name("x"))), Fn("x", Apply(Name("x"), Name("x")))); val exampleFac7 = Apply(Y(Fn("f", Fn("x", Cond(Name"x", Times(Name"x", Apply(Name"f", Minus(Name"x", Numb(1)))), Numb(1))))), Numb(7));