Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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)$.
