CSCI 6220
Fall 2010
Exercise Set 1

Due: at the start of class on Friday, Sep. 3.

1. Add parentheses to each of the following terms to show their structure. Add enough parentheses so that no rules of precedence or associativity are required to understand them.

   1. λx.x x y
   2. λx.λy.y x
   3. λx.x λy.y

2. By carefully performing β-reductions, show that inc(2) reduces to 3, using the definitions of numbers and the inc function shown in class. Inc is defined to be λm.λf.λx.f(m f x).

3. Show that (product 2 3) reduces to 6 using the definitions of numbers and the product function shown in class. Product is defined to be λm.λn.λf.m(n f).

4. Reduce each of the following to normal form. Use the definitions of numbers and the pair function shown in class. The pair function is λx.λy.λs.s x y.

   1. 0 0
   2. 1 0
   3. pair 1 2