$[25$ points$]$ Lambda Calculus

This first two sets of problems will require you to correctly interpret the precedence and associativity

rules for Lambda calculus and also properly identify free and bound variables. For each of the fol$-$

lowing expressions, rewrite the expression using parentheses to make the structure of the expression

explicit $($make sure it is equivalent to the original expression$).$ Remember the "application over ab$-$

straction" precedence rule together with the left$-$associativity of application and right$-$associativity

of abstraction$.$ Make sure your solution covers both precedence and associativity.

Now, the expressions:

a$.(x.x)$ y $z$

Example: $)z)($Only associativity is necessary in this example since parentheses

are already present to force abstraction$)$

b$.x,y,z,zx$

c$.x,xyz,ww,wxz$

d$.xyz,xwzw,wz$

e$.z.((s.sq)(q.qz))z.zz$

Circle all of the free variables $($if any$)$ for each of the following lambda expressions $($You may have

to rewrite the expression using parentheses as you did in the above question in order to identify

the free variables$)$:

a$.z,zxy,yz$

b$.(x*x)(x*x(y*y))y$

c$.p.(z.fx.zy)px$

d$.yx,xyy,yx$

e$.x*x(xy,y)$

These next two sets of questions is intended to help you understand more fully why $-$conversions

are needed: namely, to avoid having a free variable in an actual parameter captured by a formal

parameter of the same name. This would result in a different $($incorrect$)$ solution. Remember that

when performing an $-$conversion, we always change the name of the formal parameter$-$never the

free variable. Consider the following lambda expressions. For each of the expressions below, state

whether the expression can be legally $-$reduced without any $-$conversion at any of the steps,

according to the rule we learned in class. For any expression below requiring an $-$conversion,

perform the $-$reduction twice: once after performing the $-$conversion $($the correct way$)$ and once

after not performing it $($the incorrect way$).$ Do the two methods reduce to the same expression?

a$.(x,xy)(y.yx)$

b$.(x,yz,xyz)(z,zy)$

c$.(x,xz)(xz,xy)$

d$.(xy,xyz)(z,zx)$

Note: All the variables are single letters $\{x,y,z\},$ i$.$e$,$ expression $(x,yz,xyz)$ is equivalent to

$(x,y,z,(xyz)).$

For each of the expressions below, $-$reduce each to normal form $($provided a normal form exists$)$

using applicative order reduction. For each, perform $$ conversions where required. For clarity,

please show each step individually $-$ do not combine multiple reductions on a single line.

a$.(x,xy)(x,xy)$

b$.(x*x)(x*x)$

c$.(x*x)(y*xy)(z*xyz)$

d$.$ ISZERO $1?$

e$.$ EXP ${?}^{\text{u}\text{l}\text{c}\text{o}\text{r}\text{n}\text{e}\text{r}}$

If the tools you are using to submit your solution supports the $$ character, please use it in your solution.

If not, you may write $\backslash$lam as a substitute for $.$