Past exam question:

enter image description here

What my understanding of B-reduction is : Find all occurrences of the parameter in the output, and replace them with the input and that is what it reduces to

(λ param . output)input => output [param := input] => result



= (xy)[x:=z]

= (zy)

= zy

But I do not know how to use B-reduction on the expression above. What is the input, output and the parameter.


Usually, a series of applications $f\,x_1\,x_2 \dots$ means $\big(\big((f\,x_1)\,x_2\big)\,\ldots\big)$. We say that application is left associative.

According to this convention, there is an extra set of parentheses that is implied in the expression you write. Here I've made it explicit: $$\big((\lambda f.\lambda g.\lambda x. f \,(g\,x))\,(\lambda u.u)\big)\,(\lambda v.v)$$

The expression $(\lambda f.\lambda g.\lambda x. f \,(g\,x))$ is a function and it is applied on input $(\lambda u.u)$. Reducing this will result to a function of the form $(\lambda g. \lambda x. \langle\text{body}\rangle)$, which in turn gets applied to $(\lambda v.v)$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.