2
$\begingroup$

Can you explain how this expression follows the grammar of the lambda calculus?

$$\lambda x.x((\lambda y.yy)x)x = λx.x(xx)x$$

I am not sure why we have the parentheses following the $.x$ (on both sides of the equation).

$\endgroup$
5
$\begingroup$

When in doubt, write down a lot of parentheses: $$\lambda x . ((x ((\lambda y . ((y y) x)) x)) x)$$ and $$\lambda x . ((x (x x)) x)$$ In $\lambda$-calculus there is the convention that $A B C$ is understood to be $(A B) C$, that is, application associates to the left. So, if somebody wants to $A (B C)$ instead, they have to put in some parentheses.

$\endgroup$
  • $\begingroup$ Thanks, after some back and forth with the lambda grammar definition, this makes perfect sense. $\endgroup$ – matanster Dec 29 '16 at 17:05

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.