# 3.3. Free and Bound Variables¶

## 3.3.1. Free and Bound Variables¶

In the lambda calculus, like in other programming languages, there are two kinds of variable occurrences: variable declaration and variable use. In the following JavaScript code fragment, for example:

```
function (x) {
return x + y;
}
```

there are two occurrences of the variable \(x\). The first
occurrence of \(x\) (between parentheses) is the *declaration* of
the parameter \(x\), that is, the place where the variable is
first introduced into the program. In contrast, the second occurrence
of \(x\) is a *use* of the variable \(x\) (more precisely,
\(x\) is being used as an operand for an addition operation). Is
the occurrence of \(y\) in this program a variable declaration or a
variable use?

Each variable declaration defines a *scope* for that variable,
that is, the section(s) of the program in which this variable is
defined and usable. In the example above, the scope of the variable
\(x\) is the body of the function. When the use of a variable, say
\(x\), appears within the scope of a declaration of \(x\), we
say that the former is *bound* to the latter, and the latter is
the *binding occurrence* of the variable. So, in the example
above, the declaration of \(x\) in parentheses is the binding
occurrence of this variable and the use \(x\) on the next line is
bound to this binding occurrence. A variable that is not bound is said
to be *free*. In the example above, the occurrence of \(y\)
is free in the body of the function, since this function does not
contain any binding occurrence (i.e., declaration) of \(y\).

Since there may be several declarations of a variable \(x\) inside a given program, there cannot be any ambiguity about which declaration of the variable each use of it is bound to. This is why each programming language must define a binding scheme. The lambda calculus, like JavaScript and most other modern programming languages, uses static binding (also known as "static scoping" or "lexical binding"; see <some section in previous chapter>), which means that each variable use is bound to the variable declaration by the same name in the smallest lambda abstraction that contains the variable use.

We are now ready to discuss the concepts of declaration/use of variables, binding occurrence, free and bound variables, and lexical scoping in the context of the lambda calculus. Consider the following example:

This lambda expression is a lambda abstraction whose parameter is \(y\) and whose body is the application of the identity function to the expression \((y\ x)\). Therefore, the \(y\) after the \(\lambda\) is the binding occurrence of the variable \(y\). The scope of this declaration is \((\lambda x.x\ (y\ x))\), which implies that the rightmost occurrence of \(y\) is bound to the leftmost binding occurrence. In contrast, the scope of the binding occurrence of \(x\) in \(\lambda x.x\) is just the second \(x\) in it (that is, as always, the body of the lambda abstraction). As a result, the third, rightmost occurrence of \(x\) in the expression above is free: it is a use of \(x\) that does not belong to the scope of any declarations of \(x\).

To summarize this example, going from left to right, the first
occurrence of \(x\) is its binding occurrence, the second one is
bound to the first one, and the third one is free. This example
illustrates the fact that it is possible for any variable to occur
both free and bound within the same expression. Therefore, it can be
confusing to ask whether a variable is free or bound in a lambda
expression. It is preferable to ask this question about each
particular *occurrence* of a variable, keeping in mind that a binding
occurrence is never free since its role is to define a new variable.

## 3.3.2. Identifying Free Variables¶

This exercise will be good practice for identifying free variables in lambda expressions. To get credit for this randomized problem, you must solve it correctly three times in a row.

## 3.3.3. Identifying Bound Variables¶

This exercise will be good practice for identifying bound variables in lambda expressions. To get credit for this randomized problem, you must solve it correctly three times in a row.

## 3.3.4. Formal Definition of Free Variables¶

Throughout this section, we have attempted to be as intuitive and
informal as possible. However, it is possible to define the notions of
free and bound variables systematically. For any precise definition
pertaining to lambda calculus, we need only consider the three types of
lambda expressions defined in the lambda calculus grammar (see
*BNF grammar*).
For example, we say that any variable
\(x\) occurs *free* in any lambda expression
\(E\) if and only if:

- \(E\) is a variable and \(E\) is identical to \(x\), or
- \(E\) is of the form \((E_1\ E_2)\) and \(x\) occurs free in either \(E_1\) or \(E_2\) (or both), or
- \(E\) is of the form \(\lambda y.E'\) where \(y\) is different from \(x\) and \(x\) occurs free in \(E'\).

Notice that the recursion in cases 2 and 3 above mirrors the recursion in the lambda calculus grammar. The following table illustrates all cases of this definition.

\(E\) | Case | Does \(x\) occur free in \(E\)? | Explanation |
---|---|---|---|

\(x\) | 1 | yes, because ... | ... \(x\) appears in (is equal to) \(E\) and \(E\) does not contain any binding occurrences (no \(\lambda\)). |

\(y\) | 1 | no, because ... | ... \(x\) does not occur in \(E\) and thus cannot occur free in it. |

\((x\ y)\) | 2 | yes, because ... | ... \(x\) occurs free in the first component of the function application (recursive application of case 1). |

\((y\ x)\) | 2 | yes, because ... | ... \(x\) occurs free in the second component of the function application (recursive application of case 1). |

\((y\ z)\) | 2 | no, because ... | ... \(x\) occurs free in neither the first nor the second component of the function application (doubly recursive application of case 1). |

\(\lambda z.x\) | 3 | yes, because ... | ... \(x\) is different from \(z\) (the parameter of the lambda abstraction) and \(x\) occurs free in the body of the lambda abstraction (recursive application of case 1). Note that the body is what is left of the lambda abstraction after the binding occurrence (i.e., \(\lambda z.\)) is removed. |

\(\lambda z.z\) | 3 | no, because ... | ... \(x\) is different from \(z\) (the parameter of the lambda abstraction) and \(x\) does not occur (at all, and thus not free either) in the body of the lambda abstraction. |

\(\lambda z.\lambda x.x\) | 3 | no, because ... | ... \(x\) is different from \(z\) (the parameter of the lambda abstraction) but \(x\) does not occur free in the body of the lambda abstraction (recursive application of case 3). Note that the body in this case is the lambda abstraction \(\lambda x.x\). |

\(\lambda x.y\) or \(\lambda x.x\) | 3 | no, because ... | ... \(x\) is identical to the parameter of the lambda abstraction \(E\). \(x\) cannot be free in \(E\) since any free occurrences of \(x\) in the body of \(E\) would become bound in \(E\) by the leading binding occurrence of \(x\). |

The reason we devoted a whole section to the notions of free and bound variables is because we will invoke them repeatedly throughout this chapter, starting in the next section.