type aExp =          (* arithmetical expressions *)
    | N of int           (* numbers *)
    | V of string        (* variables *)
    | Add of aExp * aExp (* addition *)
    | Mul of aExp * aExp (* multiplication *)
    | Sub of aExp * aExp (* subtraction *);;

    let unop  f a s   = f (a s);;
    let binop f a b s = f (a s) (b s);;

    let rec A =
        function
        | N n          -> fun _ -> n
        | V x          -> Map.find x
        | Add (a1, a2) -> binop ( + ) (A a1) (A a2)
        | Mul (a1, a2) -> binop ( * ) (A a1) (A a2)
        | Sub (a1, a2) -> binop ( - ) (A a1) (A a2);;

    type bExp =          (* boolean expressions *)
    | TT                 (* true *)
    | FF                 (* false *)
    | Eq of aExp * aExp  (* numeric equality *)
    | Lt of aExp * aExp  (* numeric less than *)
    | Neg of bExp        (* boolean not *)
    | Con of bExp * bExp (* boolean conjunction *);;

    (* TODO: Write a function B : bExp -> state -> bool
             to evaluate boolean expressions (note that you will need to refer to A) *)


    //let rec B _ = failwith "Not implementd"
    let rec B (xp:bExp) state =
        match xp with
        | TT -> true
        | FF -> false
        | Eq(a1,a2) -> (A a1 state) = (A a2 state)
        | Lt(a1,a2) -> (A a1 state) < (A a2 state)
        | Neg(b) -> not (B b state)
        | Con(b1, b2) -> (B b1 state) && (B b2 state);;





    type stm =                (* statements *)
    | Ass of string * aExp    (* variable assignment *)
    | Skip                    (* nop *)
    | Seq of stm * stm        (* sequential composition *)
    | ITE of bExp * stm * stm (* if-then-else statement *)
    | While of bExp * stm     (* while statement *);;

    let update = Map.add;;

    (* TODO: Write I : stm -> state -> state.
             You can rewrite the skeleton if you want, but the signature must be the same *)


    let rec I stm state =
      match stm with
      | Ass (x,a)         -> update x (A a state) state(* use update *)
      | Skip              -> state
      | Seq (stm1, stm2)  -> I stm1 state |> I stm2
      | ITE (b,stm1,stm2) -> if (B b state ) then (I stm1 state) else (I stm2 state)
      | While (b, stm)    -> if B b state then I (Seq(stm,While(b,stm))) state else state