Question 3-4

Simplify the following lambda expression to normal form. Show your intermediate steps.

(((\f.\g.g f) (\x.10 - x)) (\y.\x.y (y x))) 4

Solution

(((\f.\g.g f) (\x.10 - x)) (\y.\x.y (y x))) 4
        = ((\g.g (\x.10 - x)) (\y.\x.y (y x))) 4
        = ((\y.\x.y (y x)) (\x.10 - x)) 4
        = (\x.(\x.10 - x) ((\x.10 - x) x)) 4
        = (\x.10 - x) ((\x.10 - x) 4)
        = 10 - ((\x.10 - x) 4)
        = 10 - (10 - 4)
        = 10 - 6
        = 4

Back to Review for Quiz 3