type exp = Int of int | Var of string | Plus of exp * exp | Times of exp * exp type stmt = Skip | Assign of string * exp | Seq of stmt * stmt | If of exp * stmt * stmt | While of exp * stmt let rec xlate_e (e:exp) = match e with Int i -> (fun h -> i) | Var str -> (fun h -> h str) | Plus(e1,e2) -> let f1 = xlate_e e1 in let f2 = xlate_e e2 in (fun h -> (f1 h) + (f2 h)) | Times(e1,e2) -> let f1 = xlate_e e1 in let f2 = xlate_e e2 in (fun h -> (f1 h) * (f2 h)) (* an example *) let e = Plus(Int 3, Times(Var "x", Int 4)) let f = xlate_e e (* the value bound to f is a function whose body does not use any IMP abstract syntax! *) let ans = f (fun s -> 0) (* string->int "is" a heap *) let rec xlate_e_WRONG (e:exp) = match e with Int i -> (fun h -> i) | Var str -> (fun h -> h str) | Plus(e1,e2) -> (fun h -> (xlate_e_WRONG e1) h + (xlate_e_WRONG e2) h) | Times(e1,e2) -> (fun h -> (xlate_e_WRONG e1) h * (xlate_e_WRONG e2) h) let rec xlate_s (s:stmt) = match s with Skip -> (fun h -> h) | Assign(str,e) -> let f = xlate_e e in (fun h -> let i = f h in (fun s -> if s=str then i else h s)) | Seq(s1,s2) -> let f2 = xlate_s s2 in (* order irrelevant *) let f1 = xlate_s s1 in (fun h -> f2 (f1 h)) (* order relevant *) | If(e,s1,s2) -> let f1 = xlate_s s1 in let f2 = xlate_s s2 in let f = xlate_e e in (fun h -> if (f h) <> 0 then f1 h else f2 h) | While(e,s1) -> let f1 = xlate_s s1 in let f = xlate_e e in let rec loop h = (* ah, recursion! *) if f h <> 0 then loop (f1 h) else h in loop let interp_prog s = ((xlate_s s) (fun str -> 0)) "ans"