I see that $\lambda$-calculus let's you work with anonymous functions and names are purely local. As an example

$$\lambda x.x$$

contains $x$ only as a local name. This will be replaced during reduction by another anonymous $\lambda$-term. So, I am seeing examples like

$$(\lambda x.yx)z \implies yz$$

But what is $y$ and $z$? Are these referring to other global names that we have defined before, they are not bound in any $\lambda$-term so they are free. But, to what they refer to? Did we name them in some way? What is the mechanism for naming global things and how this works with bare $\lambda$-calculus?

  • 2
    $\begingroup$ In lambda calculus everything is just a character. Nothings is defined or stands for anything. The lambda expressions can be ‘applied’ to other lambda terms, but that is just concatenation. Reduction then is just a process of substitution. Everything is syntax. $\endgroup$ – Ittay Weiss Apr 2 '18 at 17:58
  • $\begingroup$ The little you have written does not tell us what $y$ and $z$ are. They might have less than "global" scope, but it is possible that they do have that. I think it might be easier to work with a more complete example to explain scoping. See for example the previous Question "How do scoping rules work in the Lambda Calculus with nested functions". $\endgroup$ – hardmath Apr 2 '18 at 17:59
  • $\begingroup$ @IttayWeiss Is the thing I wrote, $(\lambda x.yx)z \implies yz$, also a valid $\lambda$-term? I can see that everything is a character but I understood that those should occur in a $\lambda$-abstraction, am I wrong? $\endgroup$ – meguli Apr 2 '18 at 18:11
  • $\begingroup$ @meguli these are two lambda terms. The implication arrow is not part of the lambda calculus syntax. It indicates that the term on the right is obtained from the term,on the left by the rules of manipulation of lambda terms. $\endgroup$ – Ittay Weiss Apr 2 '18 at 19:15
  • 1
    $\begingroup$ Relevant: Meaning of variables and applications in lambda calculus. $\endgroup$ – ljedrz Apr 2 '18 at 21:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.