Question 4-1

Suppose we are using an applied lambda calculus which supports the infix arithmetic operators *, +, and -. Reduce the following lambda expression, showing your intermediate steps. It should reduce to a number.

(λa.λb.a (b + 1) - a b) (λx.x * x * x) 2 Use normal (lazy) evaluation order!

Solution

(λa.λb.a (b + 1) - a b) (λx.x * x * x) 2
(λb.(λx.x * x * x) (b + 1) - * (λx.x * x * * x) b) 2
(λx.x * x * x) (2 + 1) - (λx.x * x * x) 2
(2 + 1) * (2 + 1) * (2 + 1) - (λx.x * x * x) 2
3 * 3 * 3 - (λx.x * x * x) 2
9 * 3 - (λx.x * x * x) 2
27 - (λx.x * x * x) 2
27 - 2 * 2 * 2
27 - 4 * 2
27 - 8
19

Back to Quiz 4