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
Answer:
(i) (((xx)((xx)x))x) (ii) ((vw)(λx.(λy.(vx))))
(iii) (((λx.(λy.x))x)y) (iv) (((w(λx.(λy.(λz.((xz)(yz))))))u)v)
2. Mark all the occurrences of xy in the following terms:
(i) (λxy.xy)xy (ii) (λxy.xy)(xy)
Answer:
(iii) λxy.xy(xy) (iv) (λxy.x)yxy
(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
Answer: λy.xy is a subterm of (λxy.xy)xy (2(i) and 2(ii)) λxy.x is a subterm of (λxy.x)xy (1(iii))
4. Evaluate the following substitutions: (i) (x(λy.yx)){x → vw}
(iii) (x(λy.yx)){x → ux} Answer:
(i) ((vw)(λy.y(vw))) (iii) ((ux)(λy.y(ux)))
1
(ii) (iv)
(x(λx.yx)){x → vw} (x(λy.yx)){x → uy}
(ii)
(iv) ((uy)(λz.z(uy)))
((vw)(λx.yx))
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) Answer:
(i) uvv (ii) z(uv)w (iii) (λyx.x) (iv) λyz.yz
6. Let I = λx.x and W = λxy.xyy. Reduce the following to normal form using any strategy.
Answer:
(i) WWW (ii) WII
(iii) W (II)I
(iv) W (W I)
(ii) WII → III →∗ I
(iv) W (W I) → λy.W Iyy → λy.Iyyy → λy.yyy
(i) Does not terminate (iii) W (II)I → (II)II →∗ I
2