Can you apply a free variable to something in lambda calculus? It is my understanding that an unbound variable equals itself, for example, $(\lambda x . y) a = y$. So, if a free variable just equals itself, then would the fully reduced form of $(\lambda x . (y x)) a$ be literally $(y a)$?
Asked
Active
Viewed 182 times
1 Answers
0
Yes. The terms of the lambda-calculus are given by the formation rules
- $x$ is a term for any variable $x$
- If $e_1$ and $e_2$ are terms, then so is $e_1 e_2$
- If $x$ is a variable and $e$ is a term, then $\lambda x.e$ is a term
- If $e$ is a term, then $(e)$ is a term
- Nothing else is a term
So $(\lambda x.y)a$ is a valid term, and it $\beta$-reduces to $y$.
Hans Hüttel
- 4,271
-
-
All variables are terms; the notions of free and bound variables are separate from the formation rules. – Hans Hüttel May 26 '17 at 20:48