In Ocaml, implement the function

let rec eval$\_$ession env e $=(**)$

up to the designated point

You may use the included functions, the Stdlib module, the Str module, the List module, and the Re module. NO IMPERATIVES. NO REFERENCES. NO HASHMAPS.

INCLUDED FUNCTIONS

$(*$ Adds mapping $[$x:v$]$ to environment $[$env$]*)$

let extend env x v $=($x$,$ ref v$)$ :: env

$(*$ Returns $[$v$]$ if $[$x:v$]$ is a mapping in $[$env$]$; uses the

most recent if multiple mappings for $[$x$]$ are present $*)$

let rec lookup env x $=$

match env with

$|[]->$ raise $($DeclareError $("$Unbound variable $"^$ x$))$

$|($var$,$ value$)$ :: t $->$ if x $=$ var then $!$value else lookup t x

$(*$ Creates a placeholder mapping for $[$x$]$ in $[$env$]$; needed

for handling recursive definitions $*)$

let extend$\_$tmp env x $=($x$,$ ref $($Int $0))$ :: env

$(*$ Updates the $($most recent$)$ mapping in $[$env$]$ for $[$x$]$ to $[$v$]*)$

let rec update env x v $=$

match env with

$|[]->$ raise $($DeclareError $("$Unbound variable $"^$ x$))$

$|($var$,$ value$)$ :: t $->$ if x $=$ var then value :$=$ v else update t x v

PROBLEM DESCRIPTION

let rec eval$\_$ession env e $=(**)$

eval$\_$ession

Type: environment $->$ ession $->$ ession

Description: This function takes in an environment env and an expression e$,$ and returns the result of e evaluated within the environment env, which just so happens to be another expression. The returned expression can be thought of as a "reduction" of the input expression e$.$

The environment env is a $($var $*$ ession ref$)$ list, where var refers to an variable name $($a string$),$ and the ession ref refers to its corresponding expression in the environment; it's a ref because the expression could change, due to implementing recursion, as discussed for Let below. Elements earlier in the list shadow elements later in the list.

Exceptions

Here's a list of all the possible error cases and exceptions $($can also be found in types.ml$)$:

exception TypeError of string $(*$happens when an operation receives an argument of the wrong type$*)$

exception DeclareError of string $(*$appens when an ID is seen that has not been declared$*)$

exception SelectError of string $(*$happens when trying to select a nonexistent label from a record$*)$

exception DivByZeroError $(*$happens on attempted division by zero$*)$

List of each kind of ession:

type ession $=$

$|$ Int of int

$|$ Bool of bool

$|$ String of string

$|$ ID of var

$|$ Not of ession

$(*$Implement up to here; follow up questions will ask about the rest$*)$

$|$ Fun of var $*$ ession

$|$ Binop of op $*$ ession $*$ ession

$|$ If of ession $*$ ession $*$ ession

$|$ App of ession $*$ ession

$|$ Let of var $*$ bool $*$ ession $*$ ession

$|$ Closure of environment $*$ var $*$ ession

$|$ Record of $($label $*$ ession$)$ list

$|$ Select of label $*$ ession

ID

An identifier evaluates to whatever expression it is mapped to by the environment. Should raise a DeclareError if the identifier has no binding.

eval$\_$ession $[("$x$",$ ref $($Int $1))]($ID $"$x$")=$ Int $1$

eval$\_$ession $[]($ID $"$x$")(*$ DeclareError "Unbound variable x$"*)$

See the discussion of Let below for advice about managing environments.

Not

The unary not operator operates only on booleans and produces a Bool containing the negated boolean value of the contained expression. If the expression in the Not is not a boolean $($or does not evaluate to a boolean$),$ a TypeError should be raised.

eval$\_$ession $[("$x$",$ ref $($Bool true$))]($Not $($ID $"$x$"))=$ Bool false

eval$\_$ession $[("$x$",$ ref $($Bool true$))]($Not $($Not $($ID $"$x$")))=$ Bool true

eval$\_$ession $[]($Not $($Int $1))(*$ TypeError "Expected type bool" $*)$