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

type bExp =
 | TT
 | FF
 | Eq of aExp * aExp
 | Lt of aExp * aExp (*less than*)
 | Neg of bExp
 | Con of bExp * bExp;; (*conjunction*)

type stm =
 | Ass of string * aExp
 | Skip
 | Seq of stm * stm
 | ITE of bExp * stm * stm
 | While of bExp * stm
 | IT of bExp * stm
 | RepeatUntil of bExp * stm
 | Inc of string;;

let rec A a s =
 match a with
 | N i -> i
 | V x -> Map.find x s
 | Add(a1, a2) -> A a1 s + A a2 s
 | Mul(a1, a2) -> A a1 s * A a2 s
 | Sub(a1, a2) -> A a1 s - A a2 s;;

let rec B b s =
 match b with
 | TT -> true
 | FF -> false
 | Eq(a1, a2) -> A a1 s = A a2 s
 | Lt(a1, a2) -> A a1 s < A a2 s
 | Neg(b) -> not(B b s)
 | Con(a1, a2) -> B a1 s && B a2 s;;

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)
 | 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 stm (I stm' s) else s;;