type var = string

type form =
  | Var of var
  | Or of form list
  | And of form list


type env = (var*bool) list

(* return the value of variable x in environment e*)
let rec lookup (e:env) (x:var) : bool =
  match e with
  | [] -> failwith (x^" is not in environment")
  | (hd_v,hd_b)::tl_e -> 
     if x=hd_v then hd_b
     else lookup tl_e x


  
let rec eval (e:env) (f:form) : bool =
  let op f acc x =
    f acc (eval e x)
  in
  let or' = op (||) in
  let and' = op (&&) in
  match f with
  | Var x -> lookup e x
  | Or fs -> List.fold_left or' false fs
  | And fs -> List.fold_left and' true fs


let sample_env = [("x", true); ("y", false); ("z", true)]

(* (x || y) && z *)
let true_form = And [Or [Var "x"; Var "y"] ; Var "z"]

(* (x && y) && z ... this is silly, because && is associative *)
let false_form = And [ And [Var "x"; Var "y"] ; Var "z"]

(* x && y && z *)
let false_form' = And [ Var "x" ; Var "y" ; Var "z" ]

let tf = eval sample_env true_form
let ff = eval sample_env false_form
let ff' = eval sample_env false_form'