Csc 4330/6330, Programming Language Concepts (Spring 2020)

Homework 5 (Due: 31 March (Tuesday))

HW5 Hints

NOTE: I have used the notation for the Lambda Interpreter for problems 1, 2, and 3 and the formal mathematical notation for problems 4, 5, and 6.

1. Reduce the following expressions to values:

   (((lambda x (lambda y (+ x y))) 10) 5)
   (((lambda f (lambda x (f x))) (lambda y (* y y))) 12)
   ((((lambda f (lambda x ((f x) f))) (lambda y (lambda g (g (* y y))))) 2) (lambda a a))
   

2. For each of the following terms, identify the free variables in each term and identify which terms are closed:

   t1 = x
   t2 = (lambda y y)
   t3 = (lambda x (x x))
   t4 = ((lambda x x) x)
   t5 = (lambda x (lambda y (x y)))
   t6 = (lambda x (x y))
   t7 = ((lambda y x) y)
   t8 = ((((lambda x x) z) x)((lambda y (z y)) y))
   

3. Using the terms from above, apply the following substitutions and show the resulting expression:

   t1[x := t2]
   t2[y := t3]
   t4[x := t3]
   t6[y := t5]
   t8[z := t2]
   

4. Make all parentheses explicit in the following expressions:

   λx.xz λy.xy
   (λx.xz) λy.w λw.wyzx 
   λx.xy λx.yx
   

5. Apply β-reductions to the folowing λ expressions as much as possible:

   (λz.z) (λy.y y)(λx.x a)
   (λz.z)(λz.z z)(λz.z y)
   ((λf.λa.(f a) λs.(s s)) λx.x)
   

6. Consider the following definitions for the numerals 0,1,2,...

   zero = λs.λz.z
   one = λs.λz.(s z)
   two = λs.λz.(s (s z))
   three = λs.λz.(s (s (s z)))
   four = λs.λz.(s (s (s (s z))))
   five = λs.λz.(s (s (s (s (s z)))))
   ...
   ...
   

   and the definition of addition:

   plus = λm.λn.λs.λz.(m s (n s z))
   

   Show that

   (plus two three)
   

   reduces to

   five