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

Homework 4a (Due: 11 March (Sunday))

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. Using the terms from above, apply alpha and beta reductions to the following lambda expression :

   t8[z := t3] 
   

   until you reach an expression which cannot be reduced any further.