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 =&gt; output [param := input] =&gt; 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)$.