Using only DrRacket

In this part you will implement your own limited version of eval. Your version will only understand a very limited subset of Racket, with expressions of the following kind:

expr ::$=($lambda $($var$)$ expr$)$ ; lambda $($function$)$ definition

$|($expr expr$)$ ; function application

$|$ var ; variable reference

Note that a lambda may only have one parameter.

Your evaluation function will be passed s$-$expressions of the above form $($the base form will always be a lambda$),$ and should return corresponding Racket values. Because your evaluator will use Racket features to represent and implement this subset of the Racket language, it is a so$-$called meta$-$circular evaluator.

To implement this, you will need to take apart the input to your evaluator and determine which form it is before building the corresponding Racket form. In order to implement variables $($which are just symbols in the input$),$ you will also need to keep track of their bindings in an environment $--$ we recommend using the associative list which you implemented above.

Here's the evaluator in action:

$>(($my$-$eval $\text{'}($lambda $($x$)$ x$))10)$

$10$

$>((($my$-$eval $\text{'}($lambda $($f$)($lambda $($x$)($f $($f x$)))))$ sqr$)5)$

$625$

We've stubbed out portions of the evaluator for you as a guide. Feel free to delete$/$keep what you wish.

$($define $($my$-$eval rexp$)$

$($let my$-$eval$-$env $([$rexp rexp$]$

$[$env $\text{'}()])$ ; environment $($assoc list$)$

$($cond $[($symbol$?$ rexp$)$ ; variable

void$]$

$[($eq$?($first rexp$)$ 'lambda$)$ ; lambda expression

void$]$

$[$else ; function application

void$])))$

Here are the test cases $($DO NOT CHANGE THESE, and please make sure they pass$)$:

$($test$-$case "test$-$my$-$eval$-1"$

$($define rexp $\text{'}($lambda $($x$)$ x$))$

$($define val $($my$-$eval rexp$))$

$($define res $($val $42))$

$($check$-$equal? res $42))$

$($test$-$case "test$-$my$-$eval$-2"$

$($define rexp $\text{'}(($lambda $($x$)$ x$)($lambda $($y$)$ y$)))$

$($define val $($my$-$eval rexp$))$

$($define res $($val $42))$

$($check$-$equal? res $42))$

$($test$-$case "test$-$my$-$eval$-3"$

$($define exp $\text{'}($lambda $($f$)$

$($lambda $($x$)$

$($f $($f x$)))))$

$($define val $($my$-$eval exp$))$

$($define res $(($val $($lambda $($x$)(*$ x x$)))8))$

$($check$-$equal? res $4096))$