# Give a computation of the expression to normal form (Lambda calculus)

Past exam question:

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


Example:

(λx.xy)z

= (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)$$.