Homework 4a Solutions
CSc 4330 Spring 2018
---------------------

(1)

(((lambda x (lambda y (+ x y))) 10) 5)
((lambda y (+ 10 y)) 5)
(+ 10 5)
15

(((lambda f (lambda x (f x))) (lambda y (* y y))) 12)
(lambda x ((lambda y (* y y)) x) 12)
((lambda y (* y y)) 12)
(* 12 12)
144

((((lambda f (lambda x ((f x) f))) (lambda y (lambda g (g (* y y))))) 2) (lambda a a))
(( (lambda x (((lambda y (lambda g (g (* y y)))) x) (lambda y (lambda g (g (* y y)))))) 2) (lambda a a))
(( (lambda x ( (lambda g (g (* x x))) (lambda y (lambda g (g (* y y)))))) 2) (lambda a a))
(( (lambda x ((lambda y (lambda g (g (* y y)))) (* x x)) ) 2) (lambda a a))
(( (lambda x (lambda g (g (* (* x x) (* x x)))) ) 2) (lambda a a))
((lambda g (g (* (* 2 2) (* 2 2)))) (lambda a a))
((lambda g (g 16)) (lambda a a))
((lambda a a) 16)
16

(2)

t1 = x
FREE: x

t2 = (lambda y y)
FREE:
Closed

t3 = (lambda x (x x))
FREE:
Closed

t4 = ((lambda x x) x)
FREE: 3rd x

t5 = (lambda x (lambda y (x y)))
FREE:
Closed

t6 = (lambda x (x y))
FREE: y

t7 = ((lambda y x) y)
FREE: x, 2nd y

t8 = ((((lambda x x) z) x)((lambda y (z y)) y))
FREE: 1st z, 3rd x, 2nd z, 3rd y

(3)

  t1[x := t2]
= x[x := (lambda y y)]
= (lambda y y)

  t2[y:= t3]
= (lambda y y)[y := (lambda x (x x))]
= (lambda y y)

  t4[x := t3]
= ((lambda x x) x)[x := (lambda x (x x))]
= ((lambda x x)[x := (lambda x (x x))] x[x := (lambda x (x x))])
= ((lambda x x) (lambda x (x x)))

  t6[y := t5]
= (lambda x (x y))[y := (lambda x (lambda y (x y)))]
= (lambda x (x (lambda x (lambda y (x y)))))

  t8[z := t2]
= ((((lambda x x) z) x)((lambda y (z y)) y)) [z := (lambda y y)]
= ((((lambda x x) z) x)[z := (lambda y y)] ((lambda y (z y)) y)[z := (lambda y y)])
= ((((lambda x x) z)[z := (lambda y y)] x[z := (lambda y y)]) ((lambda y (z y))[z := (lambda y y)] y[z := (lambda y y)])
= ((((lambda x x) (lambda y y)) x) ((lambda y ((lambda y y) y)) y))

(4)

  t8[z := t3]
= ((((lambda x x) z) x)((lambda y (z y)) y))[z := (lambda x (x x))]
= ((((lambda x x) (lambda x (x x))) x)((lambda y ((lambda x (x x)) y)) y))
= ((   (lambda x (x x))    x) ((lambda y ((lambda x (x x)) y)) y))
= ( (x x) (  (lambda y    ((lambda x (x x)) y)   ) y)    )
= ( (x x) (  (lambda y    (y y)  ) y)    )
= ((x x)(y y))