G6021: Comparative Programming
Some more exercises on the λ-calculus
1. Insert all the missing parentheses and λ’s into the following abbreviated λ-terms, where
I = λx.x.
• λxy.x
• λxy.xyy
• λxyz.xz(yz)
• λxyz.x(yz)
• λxyz.xzy
• λxy.x(xy)
• λx.xI
• λx.xII
• λx.xIII
• (λxy.y(xxy))(λxy.y(xxy)) • λf.(λx.f(xx))(λx.f(xx))
2. Let I = λx.x, B = λxyz.x(yz), C = λxyz.xzy, T = λxy.x(xy) and Y = (λxy.y(xxy))(λxy.y(xxy)). Reduce the following terms to normal form, if they have one. You do not need to draw a
reduction graph.
• CI
• C(λx.xII)I
•Y
• TBCI
•TI
•TT
• TTT (Just joking – this takes 42 beta reductions…)
1