Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I'm trying to work through "Elements of Functional Languages" by Martin Henson. On p. 17 he says:

$v$ occurs free in $v$, $(\lambda v.v)v$, $vw$ and $(\lambda w.v)$ but not in $\lambda v.v$ or in $\lambda v.w$. And $v$ occurs bound in $\lambda v.v$ and in $(\lambda v.v)v$ but not in $v$, $vw$ or $(\lambda w.v)$. Note that free and bound variables are not opposites. A variable may occur free and bound in the same expression.

Can someone explain what this means?

share|improve this question
    
Well, it means what it says; it gives examples for free and non-free variables, and for bound and non-bound variables. You should be more specific in saying what you don't understand. –  Florian Mar 9 '12 at 17:33
    
Okay, what does v occurs free in v mean? I do understand that λv.anything typically means v is bound. But then what is (λv.v)v trying to say? –  galaxybeing Mar 9 '12 at 17:44
    
$v$ occurs free in $v$ means that the variable $v$ occurs free in the expression $v$ (which only consists of one variable). Maybe this is what caused the confusion. –  Florian Mar 9 '12 at 18:14
    
Thanks. Got it. –  galaxybeing Mar 9 '12 at 23:45

2 Answers 2

Since you implied you're comfortable on the computer side of the house... it's talking about the scope of a variable. "$\lambda x.$" introduces a new scope which lasts for the length of the lambda expression, and $x$ is a local variable in that scope.

A free variable is one not local to the expression. e.g. in $\lambda x. xy$, $y$ is free.

Some syntaxes for lambda calculus allow a local variable to shadow a global one, just as in common programming languages. In $(\lambda x.x)x$, the lambda expression introduces a local variable $x$ which shadows the 'global' variable by the same name. I like to use colors when dealing with expressions like this, to help distinguish them: the expression is colored $(\lambda {\color{red}x}.{\color{red} x})\color{green}{x}$. The red and green $x$'s are different variables.

Note that this isn't lambda-calculus specific. Quantifiers ($\forall x:$, $\exists x:$) do the same thing. So does integral notation: $\int \ldots \, dx$ (Leibniz notation for derivatives too... sort of...). Such a thing is also usually implied when defining functions pointwise, as in

$$f(x) := x^2$$

As usually meant, $x$ is a variable local to the expression. And $f$ is a global variable! (or maybe a global constant, depending on the context and how one likes to set up the low-level details of syntax)

Do keep in mind that people aren't always consistent about distinguishing between syntactic details. Particularly on topics like whether $x^2$ is an expression that denotes a real number (the square of $x$) or an expression denoting a function in one indeterminate variable (the function that squares its input) to which $x$ is bound.

share|improve this answer
    
Thanks for the info. Q: What do you mean when you say f is a global variable? Also, (λx.x)x how did you know that the x outside the parens was a "different" variable x? Would there be a better place for a beginner to start to better understand Lambda Calc? –  galaxybeing Mar 9 '12 at 23:50

In the more normal mathematical world, we might say something like:

Let $f(x)=x^n$.

In that case, $x$ is a bound variable. If we later wrote:

Let $g(y)=y^n$

Then $g$ would be the same as $f$.

On the other hand, if we said:

Let $h(x)=x^m$

We cannot assert that $h$ is the same as $f$, because $m$ and $n$ are "free" variables.

In $\lambda$-calculus, you have to be careful about which variables are free in an expression. After a while it becomes natural.

share|improve this answer
    
Yes, this is intuitive for me. Thanks. I guess I'm spazzing a bit early. But still, I'm shaky on what v occurs free in v is really saying. I'm a newbie at the math side of computers and apt to stumble around on these sorts of things. –  galaxybeing Mar 9 '12 at 18:01

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.