Precedencia

Ahora que hemos visto la gramática completa de cálculo lambda, podemos preguntarnos cómo interpretar la expresión $\lam{x}{\app{x}{\lam{y}{y}}}$.

Si agregamos paréntesis, ¿cuáles serían expresiones válidas? $\app{(\lam{x}{x})}{(\lam{y}{y})}$ 👍 👎 $\lam{x}{x}$ y $\lam{y}{y}$ son términos válidos. También con $(\ldots)$, y son una aplicación válida. $(\lam{x}{\app{x}{\lam{y}{)y}}}$ 👍 $\lam{y}{}$ no es un término válido. 👎 $(\lam{x}{\app{x}{\lam{y)}{y}}}$ 👍 $\lambda y$ no es un término válido. 👎 $\lam{x}{(\app{x}{\lam{y)}{y}}}$ 👍 $\app{x}{\lambda y}$ no es un término válido. 👎 $\lam{x}{(\app{x}{\lam{y}{y}})}$ 👍 👎 $\app{x}{\lam{y}{y}}$ es una aplicación de $x$ con $\lam{y}{y}$.

En estos casos se usa la convención de precedencia para interpretar la expresión. La convención es que la abstracción tiene menor precedencia que la aplicación. Esto significa que $\lam{x}{\app{M}{N}}$ se interpreta como $\lam{x}{(\app{M}{N})}$. Notar que esto no depende de si $x$ aparece o no en $M$ o $N$.

Según la regla de precedencia, ¿cómo se interpreta el término $\lam{x}{\app{x}{\lam{y}{y}}}$? $\app{(\lam{x}{x})}{(\lam{y}{y})}$ El cuerpo de la abstracción de $x$ es $\app{x}{\lam{y}{y}}$, no $x$. $\lam{x}{(\app{x}{\lam{y}{y}})}$ Creemos un árbol sintáctico para la expresión $\lam{x}{\app{x}{\lam{y}{y}}}$ según la convención de precedencia. Creemos un árbol sintáctico para la expresión $\app{(\lam{x}{x})}{(\lam{y}{y})}$.