module SS $=$ Set.Make$($String$)$module SMap $=$ Map.Make$($String$)$module IMap $=$ Map.Make$($Int$)$open Listopen Charopen Formatexception Not$\_$implementedexception Parse$\_$exnexception NotAbs of stringexception NotFound of stringexception DuplicateVar of string$(*$ Data Definitions $*)$type label $=$ stringtype typ $=$ TUnit$|$ TBool$|$ TNat$|$ TFun of typ $*$ typ$|$ TRef of typ$|$ TVariant of $($label $*$ typ$)$ list $|$ TBottype term$=$ TmVar of string$|$ TmAbs of string $*$ typ $*$ term$|$ TmApp of term $*$ term$|$ TmUnit$|$ TmTrue $|$ TmFalse $|$ TmIf of term $*$ term $*$ term$|$ TmZero$|$ TmSucc of term$|$ TmPred of term$|$ TmIsZero of term$|$ TmVariant of label $*$ term $*$ typ $(*$ eg$.$ red $=6$ as $[$red:Nat; blue:Nat$]*)|$ TmCase of term $*($label $*$ string $*$ term$)$ list $(*$ eg$.$ case red $2$ of $[$red x $=>5|$ blue y $=>9]*)|$ TmRef of term $|$ TmLoc of int $|$ TmBang of term $(*!$t $*)|$ TmAssn of term $*$ term $|$ TmRaise of term$|$ TmTry of term $*$ term$|$ TmNull$|$ TmIsNull of typ $*$ term$(*$ Variants $*)(*$ Implement an option type, some and none as variants $*)$let tp$\_$opt $($tp : typ$)$ : typ $=$ raise Not$\_$implemented let tm$\_$some $($t : term$)($tp : typ$)$ : term $=$ raise Not$\_$implementedlet tm$\_$none $($tp : typ$)$ : term $=$ raise Not$\_$implemented$(*$ Implement an exception type as a variant. There are at least three possible exceptions that you should be able to handle. $($These should become clear as you progress through the homework, but feel free to start with some obvious candidates. No points will be deducted for having extra exceptions.$)*)$let tp$\_$exn : typ $=$ raise Not$\_$implemented$(*$ Small$-$step evaluation $*)(*$ Implement the small$-$step evaluation relations from class. Note the presence of a store and the possibility of encountering raise and null. $*)$type store $=$ term IMap.tlet rec cbv $($t : term$)($mu : store$)$ : $($term$*$store$)$ option $=$ raise Not$\_$implementedlet rec multistep $($t : term$)($mu : store$)$ : term$*$store $=$ raise Not$\_$implemented$(*$ Typechecking utilities $*)$type ctx $=$ typ SMap.ttype typ$\_$store $=$ typ IMap.t let empty$\_$ctx : ctx $=$ SMap.emptylet empty$\_$store : typ$\_$store $=$ IMap.empty$(*$ look up a given variable's typ$,$ throw a NotFound exception if the variable is not found $*)$let lookup $($g : ctx$)($x : string$)$ : typ $=$ match SMap.find$\_$opt x g with$|$ Some t $->$ t$|$ None $->$ raise $($NotFound x$)(*$ extend a context with a new variable$-$typ association $*)$let extend $($g : ctx$)($x : string$)($t : typ$)$: ctx $=$ if SMap.mem x g then raise $($DuplicateVar x$)$ else SMap.add x t g$(*$ Typechecking $*)(*$ check if a term has the given type. $*)(*$ Takes in a context and a store, as well as a term t and type T $*)(*$ Returns true iff gamma $|$ sigma $|-$ t : T $*)$let type$\_$check $($g : ctx$)($s : typ$\_$store$)($t : term$)($tp : typ$)=$ raise Not$\_$implemented$(*$ This should infer the type of a term in the given context $*)(*$ return None if the term is ill$-$typed $*)$and type$\_$infer $($g : ctx$)($s : typ$\_$store$)($t : term$)$ : typ option $=$ raise Not$\_$implemented$(*$ Checks if the given store is well typed with respect to the given type$\_$store and typing context. $*)(*$ Returns true iff gamma $|$ sigma $|-$ mu $*)$let store$\_$well$\_$typed $($g : ctx$)($s : typ$\_$store$)($mu : store$)=$ raise Not$\_$implemented