open System.Collections

(* Exercise 3.4 *)
//    type state =
//    | State of Map 'a 'b

    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 b state =
        match b with
        | TT -> true
        | FF -> false
        | Eq(x,y) -> (A x state) = (A y state)
        | Lt(x,y) -> (A x state) < (A y state)
        | Neg(x) -> not (B x state)
        | Con(x,y) -> (B(x) state && B(y) state)

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

    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 s =
      match stm with
      | Ass (x,a)         -> update x (A a s) s
      | Skip              -> s
      | Seq (stm1, stm2)  -> I stm2 (I stm1 s)
      | IT (b, stm)       -> if (B b s) then I stm s else s
      | ITE (b,stm1,stm2) -> if (B b s) then I stm1 s else I stm2 s
      | While (b, stm)    -> if (B b s) then I (Seq(stm,While(b, stm))) s else s
      | Repeat (b, stm)  -> if not (B b s) then I stm s else I (Seq(stm,Repeat (b, stm))) s