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.