[SOLVED] CS40032 Assignment – 2 λ-Calculus Solved       

Description

1. Reduce the following λ-expressions. Show every step of α-, β-, η– and δ [2 * 7 = 14]
   • (λz. z) (λy. y y) (λx. x a)
   • (λz. z) (λz. z z) (λz. z y)
   • (λx. λy. x y y) (λa. a) b
   • (λx. λy. x y y) (λy. y) y
   • (λx. x x) (λy. y x) z
   • (λx. (λy. (x y)) y) z
   • (((λx. (λy. (x y)) (λy. y)) w)
2. Solve the following using Y combinator [2 + 4 = 6]
   • 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

• Reduce TriProduct Show every step of β– and δ– reductions. You may skip α-reduction steps with a mention of the step.