In your view, which are the best and worst reduction strategies for a functional programming language? Give examples to support your claims. In this chapter, we have shown how to define arithmetic...

In your view, which are the best and worst reduction strategies for a functional programming language? Give examples to support your claims.

In this chapter, we have shown how to define arithmetic operations using

Church numerals.

a) Check that the term ADD = λxyab.(xa)(yab) behaves like the addition function; that is, show that when we apply ADD to two Church

numerals, we obtain the Church numeral representing their sum.

Hint: Reduce the term (λx.λy.λa.λb.(xa)(yab))n m.

b) Show that the λ-term MULT = λx.λy.λz.x(yz) applied to two Church

numerals m and n computes their product m × n.

c) Which arithmetic operation does the term λn.λm.m (MULT n) 1 compute?