1. Reduce the following λ-expressions. Show every step of α-, β-, η- and δreductions. [2 * 7 = 14]
(a) (λz. z) (λy. y y) (λx. x a)
(b) (λz. z) (λz. z z) (λz. z y)
(c) (λx. λy. x y y) (λa. a) b
(d) (λx. λy. x y y) (λy. y) y
(e) (λx. x x) (λy. y x) z
(f) (λx. (λy. (x y)) y) z
(g) (((λx. (λy. (x y)) (λy. y)) w)
2. Solve the following using Y combinator [2 + 4 = 6]
(a) Write the recursive definition for TriProduct where TriProduct(n) can be defined as
TriProduct(n) = n* (TriProduct(n − 1) if n 3
+ TriProduct(n − 2)+
TriProduct(n − 3)),
= 5, if n = 3
= 2, if n = 2
= 1 if n = 1
Using Y combinator, encode the above recursive definition of TriProduct as λ-expressions
(b) Reduce TriProduct 4. Show every step of β- and δ- reductions. You may skip α-reduction steps with a mention of the step.
