Here we restrict our lambdas to have only one argument. The lexical address of a

variable is the number of lambdas between the place where the variable is bound $($also

known as the formal$)$ and the place where it occurs. For example, in the following

expression:

$($ lambda $(0)$

$($ lambda $(r)$

$($ lambda $($s$)$

$($ lambda $(p)$

$($ lambda $($g$)$

o$)))))$

The o at the very bottom is a bound occurrence. It has a lexical address of $4,$ because

there are four lambda expressions between the formal o at the top and the occurrence

of $o$ at the bottom.

Define and test a procedure lex that takes a lambda$-$calculus expression and an

accumulator $($which starts as the empty list$),$ and returns the same expression with all

bound variable references replaced by lists of two elements whose first member is the

symbol var and whose second member is the lexical address of the referenced variable.

You should leave free variables as is$.$

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

$\text{'}())$

$($lambda $(var0))$

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

$\text{'}())$

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

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

$\text{'}())$

$($lambda $($lambda $((var0)(var1))$

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

$\text{'}())$

$($ lambda $($lambda $((var0)(var0))$

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

$\text{'}())$

$($lambda $($lambda $(y(var0))\text{'}())$

lambda lambda $((var0)(var1))$ lambda $(((var2)(var1)))$