module type GlobalEnv =
  sig
    type t
    val nouveau : int -> t
    val ajoute : t -> string*int -> unit
    val trouve : t -> string -> int
  end


module HashEnv : GlobalEnv = 
  struct
    type t = (string*int) list array
	
    let hash w s = 
      let h = ref 0 in
	for i = String.length s - 1 downto 0 do 
	  h := (19 * !h + Char.code s.[i]) mod w
	done;
	!h

	  
    let nouveau size = Array.make size []
	
    let trouve t s = List.assoc s t.(hash (Array.length t) s)
    let ajoute t (s,e) = let h = hash (Array.length t) s in t.(h) <- (s,e)::t.(h)
					    
  end



module AssocEnv : GlobalEnv = 
  struct
    type t = (string*int) list ref
    let nouveau _ = ref []
    let trouve t s = List.assoc s !t
    let ajoute t e =  t := e::!t
  end


module Eval ( Genv : GlobalEnv) = 
  struct

    let size = 31
    let genv = Genv.create size
	
    exception VarUndef of string
    let eval_expr = 
      let rec eval_rec env = function
	  Cst x -> x
	| Var x -> 
	    (try List.assoc x env with 
		 Not_found -> 
		   try Genv.find genv x with
		       Not_found -> raise(VarUndef x))
	| Sum(e1,e2) -> (eval_rec env e1) + (eval_rec env e2)
	| Diff(e1,e2) -> (eval_rec env e1) - (eval_rec env e2)
	| Prod(e1,e2) -> (eval_rec env e1) * (eval_rec env e2)
	| Quot(e1,e2) -> (eval_rec env e1) / (eval_rec env e2)
	| Letin(x,e1,e2) -> let t = eval_rec env e1 in eval_rec ((x,t)::env) e2
      in 
	eval_rec []
	  
	  
    let eval_instr = function
	Set(x,e) -> let t=eval_expr e in Genv.add genv (x,t)
      | Print(e) -> Printf.printf "= %d" (eval_expr e)

end