
open Ast

exception RunTimeError
exception Unimplemented

(* notice lookup and interp are tail-recursive *)

let rec lookup (env : env) (s : variable) : valu = (* do not change this *)
  match env with
    [] -> failwith "lookup"
  | ((s2,v)::tl) -> if s2=s then v else lookup tl s

(* like the interpeter in lecture except we use S for variable (string)
   and separate out values (tagged with V)

   done for you are the cases related to functions

   other cases also need to keep around environments so that each expression
   is evaluated in the correct one -- see type context_elt in ast.ml where
   the constructors you need are defined for you

   you will need to detect other run-time errors, such as v.1 where v is not
   a pair
*)
let interp (e : exp) : valu =
  let rec loop c env e =
    match e with (* you need to add more cases *)
    | S s          -> loop c env (V (lookup env s))
    | L(s1,e1)     -> loop c env (V (C(s1,e1,env)))
    | A(e1,e2)     -> loop (LeftApp(e2,env)::c) env e1
    | V v ->
	(match c with (* you need to add more cases *)
	  []                            -> v 
	| (LeftApp  (e2,env2))::tl      -> loop (RightApp(v)::tl) env2 e2
	| (RightApp (C(s,e2,env2)))::tl -> loop tl ((s,v)::env2) e2
	| (RightApp _)::_               -> raise RunTimeError (* not a closure *)
	| _ -> raise Unimplemented)
    | _ -> raise Unimplemented
  in loop [] [] e

(* Use abstract syntax to return a program that runs e and allows e to
   apply halt to a value to halt execution *)
let allow_halt e = e  (* CHANGE this to allow halt *)

(* Do not change anything below here *)

(* expect one command-line argument, a file to parse *)
(* you do not need to understand this interaction with the system *)
let parse_file () =
  let argv = Sys.argv in
  let _ = 
    if Array.length argv != 2
    then (prerr_string ("usage: " ^ argv.(0) ^ " [file-to-parse]\n");
	  exit 1) in
  let ch = open_in argv.(1) in
  Parse.program Lex.lexer (Lexing.from_channel ch)

let _ =
  let prog = parse_file() in
  print_string (valu2string (interp (allow_halt prog)));
  print_newline ()
