Due on Tuesday, November 6.

The Lambda Calculus

1. Do exercise 10.1 in Reynolds, but only for the first expression.
    
2. Do exercise 10.2 in Reynolds.
    
3. Do Exercise 10.5 in Reynolds.
    
4. Using the lambda calculus interpreter provided below, implement TRUE, FALSE, NUM_n (for 0 <= n <= 10), ISZERO, SUCC, ADD, and MULT as defined in Section 10.6.  Test your implementation.
    
5. Define the Y combinator using the lambda calculus interpreter, and provide alternative definitions of ADD and MULT using Y.  To do this, you will need a predecessor function:
   
   PRED = lambda n. lambda s. lambda z.
                      let s2 = lambda n. lambda f. f (n s),
                           z2 = lambda f. z
                      in n s2 z2 (lambda x.x),
    
   Test your implementation.
    
6. Define lambda calculus terms PAIR, LEFT, and RIGHT with the following properties:
    
       LEFT (PAIR X Y)  -->*  X
       RIGHT (PAIR X Y)  -->*  Y
    
   Implement these in the lambda calculus interpreter and verify that they work as described above.
    
7. Using the Y combinator, define an infinite sequence of ones called ONES that is equivalent to the following recursive definition:
    
       ONES = PAIR ONE ONES
    
   Then evaluate LEFT ONES using both normal-order and eager evaluation.

Lambda Calculus Interpreter

PS6 Solution Set

Lambda Calculus interpreter w/Solutions