Can you write code for this:
Part (A): AST optimization
In the first part of this project, you will implement a function optimize : expr environment -> expr -> expr, which can partially evaluate and simplify the AST, using the following optimizations:

Constant folding
Constant folding is the process of recognizing and evaluating constant expressions at compile time rather than computing them at runtime. Terms in constant expressions are typically simple literals, such as the integer literal 2, or boolean literal true, but they may also be variables whose values are known at compile time. Consider the expression:

(
3
+
4
)
∗
6

Without an optimization, the expression (3 + 4) * 6 will be calculated at run-time. We want to identify constructs such as these and substitute the computed values at compile time (in this case, 42).

Constant folding can make use of arithmetic identities. For example:

If x is numeric, the value of 0 * x is zero, even if the compiler does not know the value of x.
If x is numeric, the value of 1 * x is x.
If x is numeric, the value of x + 0 - 0 is x.
Here's a complete list of arithmetic identities that you should implement in optimize:

x + 0 = x and 0 + x = x
x * 0 = 0 and 0 * x = 0
x * 1 = x and 1 * x = x
x - 0 = x
x / 1 = x
0 / x = 0
List of boolean identities that should also be implemented:

true || x and x || true is true
false && x and x && false is false
Properties that we are NOT testing:

0 - x = -x
x / x = 1
Constant propagation
Constant propagation is the process of substituting the values of known constants in expressions. In MicroCaml such constants include the int and boolean literals. Consider the following pseudocode:

 let x = 42 in 
    let y = 14 * 3 - x in 
    if y = 0 then 1 else 2
Propagating x yields:

let x = 42 in 
    let y = 0 in 
    if y = 0 then 1 else 2
Continuing to propagate yields 1 .

You can assume all ASTs are valid OCaml expressions and will not cause an error during the optimization.

Your optimizer should evaluate as much as possible. For many programs, it will be able to optimize the AST down to just a single node containing the value returned after running the program.

Note

How is this optimization different from the evaluator in Project 4?

During evaluation, all variables are bound at some point (i.e. you can lookup the value of a variable in the environment). In the optimizer, variables may not be bound, but you'd still want to evaluate the expression as much as possible. For example, the optimizer will optimize fun x:Int -> 1+2+3+4+x to fun x:Int -> 10+x, whereas the evaluator will evaluate it a closure with the body of the function unmodified.

More examples of programs after optimization
optimize [] (parse_expr "fun x:Bool -> if x then 0 else 1") = Fun ("x", TBool, If (ID "x", Int 0, Int 1))

optimize [] (parse_expr "fun x:(Int -> Int) -> if true then (x 1) else 1") = Fun ("x", TArrow (TInt, TInt), App (ID "x", Int 1))

optimize [] (parse_expr "{a=100;b=200}.a") = Int 100

optimize [] (parse_expr "{a=100+200;b=200}") = Record [(Lab "a", Int 300); (Lab "b", Int 200)]

optimize [] (parse_expr "1 + 2 + x + 3") = Binop (Add, Binop (Add, Int 3, ID "x"), Int 3)

optimize [] (parse_expr "2 * x + 3 * x") = Binop (Add, Binop (Mult, Int 2, ID "x"), Binop (Mult, Int 3, ID "x"))

optimize [] (parse_expr "let rec f:(Int->Int) = fun a:Int -> f a in 1") = LetRec ("f", TArrow (TInt, TInt), Fun ("a", TInt, App (ID "f", ID "a")), Int 1)
(* This would infintitely recurse in evaluation, but for our optimizer, we still want it to have an output, so you do not need to worry about extending the environment of a recursive function. *)

optimize [] (parse_expr "let rec f:(Int->Int) = fun a:Int -> if a < (10 + 2) then a else f (a - 1) in (5 * 6)") =
      LetRec ("f", TArrow (TInt, TInt),
       Fun ("a", TInt,
        If (Binop (Less, ID "a", Int 12), ID "a",
         App (ID "f", Binop (Sub, ID "a", Int 1)))),
       Int 30)
(* We still optimize the sub-expressions of a LetRec *)

optimize [] (parse_expr ("0 * (1/0)")) 
(* Exception: DivByZeroError *)

ast.ml
(* The type of the abstract syntax tree (AST). *)
exception InvalidInputException of string

(* error types *)
exception TypeError of string
exception DeclareError of string
exception SelectError of string
exception DivByZeroError

type op =
  | Add
  | Sub
  | Mult
  | Div
  | Greater
  | Less
  | GreaterEqual
  | LessEqual
  | Equal
  | NotEqual
  | Or
  | And
[@@deriving show { with_path = false }]

type var = string [@@deriving show { with_path = false }]
type label = Lab of var [@@deriving show { with_path = false }]

type exptype =
  | TInt
  | TBool
  | TArrow of exptype * exptype
  | TRec of (label * exptype) list
  | TBottom
[@@deriving show { with_path = false }]

type expr =
  | Int of int
  | Bool of bool
  | ID of var
  | Binop of op * expr * expr
  | Not of expr
  | If of expr * expr * expr
  | Let of var * expr * expr
  | LetRec of var * exptype * expr * expr
  | Fun of var * exptype * expr
  | App of expr * expr
  | Record of (label * expr) list
  | Select of label * expr
[@@deriving show { with_path = false }]

type 'a environment = (var * 'a) list