I am trying to learn Lambda calculus from here

and while trying to solve some problems, I got stuck. I was trying to solve the following problem (page 14, excercise 2.6 part (i):

Simplify $M \equiv (\lambda xyz.zyx) aa (\lambda pq. q)$.

My evaluation using the beta rule reduces it to $(\lambda z. z)$ as follows: First I replace occurences of $x$ in $M$ by $aa (\lambda pq. q)$, and then since there are no occurences of $y$ in the resulting $\lambda$ term, the expression simply evaluates to $(\lambda z. z)$.

Is my reasoning correct? (Since there were no solutions to these notes, I want to ensure my understanding is correct. Any corrections, will be much appreciated! Thanks in advance.


1 Answer 1


No, your reduction is wrong. The function $(\lambda x y z. z y x)$ is applied to three arguments: $a$, $a$ and $(\lambda p q. q)$. It is not, as you wrote, a the function $(\lambda x y z. z y x)$ applied to the term $a a (\lambda p q. q)$; that second term does not appear in $M$. Strictly speaking, functions in the lambda-calculus take three arguments, they are effectively curried, so if you add optional parentheses $M$ can be written $$ (((\lambda x. (\lambda y. (\lambda z. (z y) x))) a) a) (\lambda p. (\lambda q. q)) $$ This reduces by substituting $a$ for $x$ in $(\lambda y. (\lambda z. (z y) x)))$, then $a$ for $y$ in the result of this: $$ M \to (\lambda y z. z y a) a (\lambda p q.q) \to (\lambda z. z a a) (\lambda p q. q) $$ then substitute $(\lambda p q. q)$ for $z$, after which a new redex appears: $$ \ldots \to (\lambda p. (\lambda q. q)) a a \to (\lambda q. q) a \to a $$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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