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.

Problem

$4$

$[$

$1$

$0$

$$Points

$]$

$.$

$$ Computing the exponent of a number

$($

i

$.$

e

$.$

$,$

$$nk

$)$

$$can take O

$($

n

$)$

$$time if done by simply multiplying by n

$,$

$$k number of times. A logarithmic way for computing exponents is by using the idea of successive squaring. For instance, rather than computing n

$8$

$$as: n

$*$

$$n

$*$

$$n

$*$

$$n

$*$

$$n

$*$

$$n

$*$

$$n

$*$

$$n

$,$

$$we can compute it by repeatedly squaring, beginning with n

$,$

$$computing n

$2$

$,$

$$n

$4$

$$and finally n

$8$

$.$

$$In general, the algorithm would do the following:

nk

$=$

$($

n

$($

k

$/$

$2$

$)$

$)$

$2$

$$if k is even

nk

$=$

$$n

$*$

$$n

$($

k

$-$

$1$

$)$

$$if k is odd

Write a lambda expression for this function. You may assume that the function required in Problem

$3$

$($

a

$)$

$$is already available to you, and you may use it if you like. You may also assume that if you use the function from Problem

$3$

$($

a

$)$

$,$

$$you are simply able to state the condition as a logical statement.

Because this is a recursive function, you will have to nest the lambda expression taking argument k within another lambda taking f

$$

$$the function

$$

$$which you will then recursively call within the body. Plus, you will have to precede this definition with the letter Y

$,$

$$which represents a special kind of lambda expression called the Y combinator, which actually makes the recursion happen. So

$,$

$$your solution will look something like:

Y lambda f

$.$

$[$

rest of your solution

$]$