Due Sunday by $11$:$59$ p$.$m$.$ Points $50$ Submitting a text entry box or a file upload File Types pdf Available Jan $15$ at $3$ p$.$m$.-$ Jan $28$ at $11$:$59$ p$.$m$.$

Lambda Calculus

$2x,y,$ came as saying $f(x)=x$

Total: $50$ Points. This assignment is worth half the marks that the programming assignment $2$ through $5$ will be worth.

Problem $1[5+5$ Points$].$ Simply the following lambda expressions, if possible. Always evaluate the "outer" applications first $($i$.$e$.,$ use lazy evaluation$).$

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

b$)$ y$)y*(yy)$

$2$ Problem $2[10$ Points$].$ Using the definitions of boolean constants and operators presented in class, show that the following evaluates to true. Show all your steps for a perfect mark. Always evaluate the "outer" applications first $($i$.$e$.,$ use lazy evaluation$),$ but continue to evaluate further until you obtain true.

and true $($or false $($not $($not true$)))$

$3$ Problem $3[5+5$ Points$].$ Consider a function ite $($for if then else$)$ which takes three arguments: a boolean, an expression to evaluate if the boolean is true, and a second expression to evaluate if the boolean is false.

a$)$ Given the lambda expressions for boolean constants and operators presented in class, write the lambda expression for this ite function.

b$)$ Write the lambda expression for a function iteite $($for if then elseif then else$)$ which takes five arguments: a boolean, an expression to evaluate if the boolean is true, another boolean, an expression to evaluate if the second boolean is true, and a third expression to evaluate if both booleans are false. You may assume that a correct implementation of function ite from $($a$)$ is available to you, and use it if you like.

$4$ Problem $4[10$ Points$].$ Computing the exponent of a number $($i$.$e$.,n^k)$ can take $O(n)$ time if done by