(* An interpreter for arithmetic expressions *)

exception Error of string

datatype Token 
  = INT of int
  | ID of string
  | PLUS
  | TIMES
  | LPAREN
  | RPAREN

datatype Exp
  = Int of int
  | Plus of Exp * Exp
  | Times of Exp * Exp
  | Var of string

fun parseE (INT i :: ts) k = 
      parseE' (Int i) ts k
  | parseE (ID s :: ts) k =
      parseE' (Var s) ts k
  | parseE (LPAREN :: ts) k = 
      parseE ts (fn (E, RPAREN :: ts) => parseE' E ts k
                  | _ => raise Error ") expected")
and parseE' E (PLUS :: ts) k =
      parseE ts (fn (E', ts') => k (Plus (E, E'), ts'))
  | parseE' E (TIMES :: ts) k = 
      parseE ts (fn (E', ts') => k (Times (E, E'), ts'))
  | parseE' E ts k = 
      k (E, ts)

fun lookup nil s = 
      raise Error ("Variable " ^ s ^ "not bound")
  | lookup ((s', v) :: env) s = 
      if s = s' then v else lookup env s 

fun eval env (Int i) = i
  | eval env (Plus (E1, E2)) = eval env E1 + eval env E2
  | eval env (Times (E1, E2)) = eval env E1 + eval env E2
  | eval env (Var s) = lookup env s 


fun run env ts = 
     eval env (parseE ts
	       (fn (E, []) => E
	         | _ => raise Error "expected EOF found something else"))


val Ts1= [INT 5, PLUS, INT 10, TIMES, LPAREN, INT 199, PLUS, INT 1, RPAREN]
val Ts2= [INT 5, PLUS, ID "x"]

val R = run nil Ts1
val R' = run [("x", 42)] Ts2