G6021: Comparative Programming
Exercises on the λ-calculus
1. Insert all the missing parentheses and λ’s into the following abbreviated
λ-terms.
(i) xx(xxx)x (ii) vw(λxy.vx)
(iii) (λxy.x)xy (iv) w(λxyz.xz(yz))uv
2. Mark all the occurrences of xy in the following terms:
(i) (λxy.xy)xy (ii) (λxy.xy)(xy)
(iii) λxy.xy(xy) (iv) (λxy.x)yxy
3. Do any of the terms in (1) or (2) contain any of the following terms as
subterms? If so, which contains which?
(i) λy.xy (ii) y(xy)
(iii) λxy.x (iv) (λzyz.xz)yz 4. Evaluate the following substitutions:
(i) (x(λy.yx)){x → vw} (ii) (x(λx.yx)){x → vw} (iii) (x(λy.yx)){x → ux} (iv) (x(λy.yx)){x → uy}
5. Reduce the following terms to normal forms:
(i) (λxy.xyy)uv (ii) (λxy.yx)(uv)zw
(iii) (λxy.x)(λx.x) (iv) (λxyz.xz(yz))(λuv.v)
6. Let I = λx.x and W = λxy.xyy. Reduce the following to normal form using any strategy.
(i) WWW (ii) WII (iii) W (II)I (iv) W (W I)
1