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).
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
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.
answered Dec 29, 2016 at 15:10
-
$\begingroup$ Thanks, after some back and forth with the lambda grammar definition, this makes perfect sense. $\endgroup$– matanoxCommented Dec 29, 2016 at 17:05