type var = string

(* form and forms are mutually recursive, 
 * because form declares Or and And with
 * forms, and forms is a form list *)
type form =
  | Var of var
  | Or of forms
  | And of forms
and forms = 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


(* eval and evals are mutually recursive, because 
 * they call each other. Warning: omitting the 
 * "rec" keyword gives the most confusing type 
 * mismatch error ever. *)
let rec eval (e:env) (f: form) : bool =
  match f with
  | Var x -> lookup e x
  | Or fs -> evals e fs false (||)
  | And fs -> evals e fs true (&&)
and evals (e:env) (fs:forms) (b:bool) (op:bool->bool->bool) : bool =
  match fs with
  | [] -> b
  | hd::tl -> op (evals e tl b op) (eval e hd)



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'