leave free variables as is$.$

$>($lex $\text{'}($lambda $($x$)$ x$)$

$\text{'}())$

$($lambda $($var $0))$

$>($lex $\text{'}($lambda $($y$)($lambda $($x$)$ y$))$

$\text{'}())$

$($lambda $($lambda $($var $1)))$

$>($lex $\text{'}($lambda $($y$)($lambda $($x$)($x y$)))$

$\text{'}())$

$($lambda $($lambda $(($var $0)($var $1))))$

$>($lex $\text{'}($lambda $($x$)($lambda $($x$)($x x$)))$

$\text{'}())$

$($lambda $($lambda $(($var $0)($var $0))))$

$>($lex $\text{'}($lambda $($x$)($lambda $($x$)($y x$)))$

$\text{'}())$

$($lambda $($lambda $($y $($var $0))))$

$>($lex $\text{'}($lambda $($y$)(($lambda $($x$)($x y$))($lambda $($c$)($lambda $($d$)($y c$)))))$

$\text{'}())$

$($lambda $(($lambda $(($var $0)($var $1)))($lambda $($lambda $(($var $2)($var $1))))))$

$>($lex $\text{'}($lambda $($a$)$

$($lambda $($b$)$

$($lambda $($c$)$

$($lambda $($a$)$

$($lambda $($b$)$

$($lambda $($d$)$

$($lambda $($a$)$

$($lambda $($e$)$

$((((($a b$)$ c$)$ d$)$ e$)$ a$)))))))))$

$\text{'}())$

$($lambda

$($lambda

$($lambda

$($lambda

$($lambda

$($lambda

$($lambda

$($lambda

$(((((($var $1)($var $3))($var $5))($var $2))($var $0))($var $1))))))))))$

$>($lex $\text{'}($lambda $($a$)$

$($lambda $($b$)$

$($lambda $($c$)$

$($lambda $($w$)$

$($lambda $($x$)$

$($lambda $($y$)$

$(($lambda $($a$)$

$($lambda $($b$)$

$($lambda $($c$)$

$((((($a b$)$ c$)$ w$)$ x$)$ y$))))$

$($lambda $($w$)$

$($lambda $($x$)$

$($lambda $($y$)$

$((((($a b$)$ c$)$ w$)$ x$)$ y$)))))))))))$

$\text{'}())$

$($lambda

$($lambda

$($lambda

$($lambda

$($lambda

$($lambda

$(($lambda

$($lambda

$($lambda

$(((((($var $2)($var $1))($var $0))($var $5))($var $4))($var $3)))))$

$($lambda

$($lambda

$($lambda

$(((((($var $8)($var $7))($var $6))($var $2))($var $1))($var $0))))))))))))$

$>($lex $\text{'}($lambda $($a$)$

$($lambda $($b$)$

$($lambda $($c$)$

$($lambda $($w$)$

$($lambda $($x$)$

$($lambda $($y$)$

$(($lambda $($a$)$

$($lambda $($b$)$

$($lambda $($c$)$

$((((($a b$)$ c$)$ w$)$ x$)$ y$))))$

$($lambda $($w$)$

$($lambda $($x$)$

$($lambda $($y$)$

$((((($a b$)$ c$)$ w$)$ h$)$ y$)))))))))))$

$\text{'}())$

$\text{'}($lambda

$($lambda

$($lambda

$($lambda

$($lambda

$($lambda

$(($lambda

$($lambda

$($lambda $(((((($var $2)($var $1))($var $0))($var $5))($var $4))($var $3)))))$

$($lambda

$($lambda

$($lambda $(((((($var $8)($var $7))($var $6))($var $2))$ h$)($var $0))))))))))))$

There are a number of ways you can approach this problem. Our suggestion is to build some lambda expressions with pen and paper, and then by hand find the lexical addresses of some variables that occur in them. Try and do it almost mechanically, starting from the body of the innermost lambda of the expression and working your way out. If there is more than one innermost lambda, pick one, resolve it and repeat. Then think about what it is you$$re doing, and figure out how to do it without having to go back up the tree. That is$,$ ensure that when you get to a variable position in the expression where you need to fill in the lexical address, that you already have all the information you need to figure it out.

Part $2$: Interpreters and Higher Order Function Representation

In recent lectures, we$$ve learned how to write an interpreter that takes a Racket expression and returns the result of evaluating that expression. We have also learned to make it representation independent with respect to environments and closures. We have written helper functions that manipulate the representations of environments and closures: extend$-$env, apply$-$env, empty$-$env, apply$-$clos and make$-$clos. In Part $2,$ we will implement two interpreters in total: the basic representation dependent $($RD$)$ interpreter, and the representation independent $($RI$)$ interpreter, along with helper functions for the RI interpreter.

You must define a set of environment helpers: that uses functional $($higher$-$order$)$ representation of environments. Call the representation$-$dependent version value$-$of$,$ and the representation independent version value$-$of$-$fn$.$

Notice these names may be different from those presented in lecture. This is a framework for how you should name your procedures and helpers:

$($define value$-$of $...)$

$($define value$-$of$-$fn $...)$

$($define empty$-$env$-$fn $...)$

$($define extend$-$env$-$fn $...)$

$($define apply$-$env$-$fn $...)$

$($define apply$-$clos$-$fn $...)$

$($define make$-$clos$-$fn $...)$

Your interpreter must handle the following forms: numbers, booleans, variables, lambda$-$abstraction$,$ application, zero?, sub$1,*,$ if$,$ and let

Unlike in Racket, here let can bind only one variable.

Remember, your solutions should be compositional.

You may have seen the expansion of $($let $(($x e$))$ body$)$ as $(($lambda $($x$)$ body$)$ e$).$ When you are comfortable with the environment, however, you can implement let without using