# Free variables and bound variables

*https://en.wikipedia.org/wiki/Free_variable*

This article needs additional citations for
verification. (December 2008) |

In
mathematics, and in other disciplines involving
formal languages, including
mathematical logic and
computer science, a **free variable** is a
notation (symbol) that specifies places in an
expression where
substitution may take place and is not a parameter of this or any container expression. Some older books use the terms **real variable** and **apparent variable** for free variable and bound variable, respectively. The idea is related to a **placeholder** (a
symbol that will later be replaced by some value), or a
wildcard character that stands for an unspecified symbol.

In
computer programming, the term **free variable** refers to
variables used in a
function that are neither
local variables nor
parameters of that function. The term
non-local variable is often a synonym in this context.

A **bound variable** is a variable that was previously *free*, but has been *bound* to a specific value or set of values called
domain of discourse or
universe. For example, the variable x becomes a **bound variable** when we write:

For all x, (

x+ 1)^{2}=x^{2}+ 2x+ 1.

or

There exists x such that

x^{2}= 2.

In either of these propositions, it does not matter logically whether x or some other letter is used. However, it could be confusing to use the same letter again elsewhere in some compound
proposition. That is, free variables become bound, and then in a sense *retire* from being available as stand-in values for other values in the creation of formulae.

The term "dummy variable" is also sometimes used for a bound variable (more often in general mathematics than in computer science), but that use can create an ambiguity with the definition of dummy variables in regression analysis.

## Examples

Before stating a precise definition of **free variable** and **bound variable**, the following are some examples that perhaps make these two concepts clearer than the definition would:

In the expression

*n* is a free variable and *k* is a bound variable; consequently the value of this expression depends on the value of *n*, but there is nothing called *k* on which it could depend.

In the expression

*y* is a free variable and *x* is a bound variable; consequently the value of this expression depends on the value of *y*, but there is nothing called *x* on which it could depend.

In the expression

*x* is a free variable and *h* is a bound variable; consequently the value of this expression depends on the value of *x*, but there is nothing called *h* on which it could depend.

In the expression

*z* is a free variable and *x* and *y* are bound variables, associated with
logical quantifiers; consequently the
logical value of this expression depends on the value of *z*, but there is nothing called *x* or *y* on which it could depend.

More widely, in most of the proofs, we use bound variables. For example, the following proof shows that every square of even integer is divisible by

- Let be a positive even integer. Then there is an integer such that . Since , we have divisible by

not only *k* but also *n* have been used as bound variables as a whole in the proof.

### Variable-binding operators

The following

are some common **variable-binding operators**. Each of them binds the variable **x** for some set **S**.

Note that many of these are operators which act on functions of the bound variable. In more complicated contexts, such notations can become awkward and confusing. It can be useful to switch to notations which make the binding explicit, such as

for sums or

for differentiation.

## Formal explanation

Variable-binding mechanisms occur in different contexts in mathematics, logic and computer science. In all cases, however, they are purely
syntactic properties of expressions and variables in them. For this section we can summarize syntax by identifying an expression with a
tree whose leaf nodes are variables, constants, function constants or predicate constants and whose non-leaf nodes are logical operators. This expression can then be determined by doing an
inorder traversal of the tree. Variable-binding operators are
logical operators that occur in almost every formal language. A binding operator Q takes two arguments: a variable *v* and an expression *P*, and when applied to its arguments produces a new expression Q(*v*, *P*). The meaning of binding operators is supplied by the
semantics of the language and does not concern us here.

Variable binding relates three things: a variable *v*, a location *a* for that variable in an expression and a non-leaf node *n* of the form Q(*v*, *P*). Note: we define a location in an expression as a leaf node in the syntax tree. Variable binding occurs when that location is below the node *n*.

In the
lambda calculus, `x`

is a bound variable in the term `M = λx. T`

and a free variable in the term `T`

. We say `x`

is bound in `M`

and free in `T`

. If `T`

contains a subterm `λx. U`

then `x`

is rebound in this term. This nested, inner binding of `x`

is said to "shadow" the outer binding. Occurrences of `x`

in `U`

are free occurrences of the new `x`

.^{
[1]}

Variables bound at the top level of a program are technically free variables within the terms to which they are bound but are often treated specially because they can be compiled as fixed addresses. Similarly, an identifier bound to a recursive function is also technically a free variable within its own body but is treated specially.

A *closed term* is one containing no free variables.

### Function expressions

To give an example from mathematics, consider an expression which defines a function

where *t* is an expression. *t* may contain some, all or none of the *x*_{1}, …, *x*_{n} and it may contain other variables. In this case we say that function definition binds the variables *x*_{1}, …, *x*_{n}.

In this manner, function definition expressions of the kind shown above can be thought of as *the* variable binding operator, analogous to the lambda expressions of
lambda calculus. Other binding operators, like the
summation sign, can be thought of as
higher-order functions applying to a function. So, for example, the expression

could be treated as a notation for

where is an operator with two parameters—a one-parameter function, and a set to evaluate that function over. The other operators listed above can be expressed in similar ways; for example, the
universal quantifier can be thought of as an operator that evaluates to the
logical conjunction of the
boolean-valued function *P* applied over the (possibly infinite) set *S*.

## Natural language

When analyzed in
formal semantics, natural languages can be seen to have free and
bound variables. In English,
personal pronouns like *he*, *she*, *they*, etc. can act as free variables.

*Lisa found***her**book.

In the sentence above, the possessive pronoun *her* is a free variable. It may
refer to the previously mentioned *Lisa* or to any other female. In other words, *her book* could be referring to Lisa's book (an instance of
coreference) or to a book that belongs to a different female (e.g. Jane's book). Whoever the
referent of *her* is can be established according to the situational (i.e.
pragmatic) context. The identity of the referent can be shown using coindexing subscripts where *i* indicates one referent and *j* indicates a second referent (different from *i*). Thus, the sentence *Lisa found her book* has the following interpretations:

*Lisa*(interpretation #1:_{i}found her_{i}book.*her*= of*Lisa*)*Lisa*(interpretation #2:_{i}found her_{j}book.*her*= of a female that is not Lisa)

The distinction is not purely of academic interest, as some languages do actually have different forms for *her _{i}* and

*her*: for example, Norwegian and Swedish translate coreferent

_{j}*her*as

_{i}*sin*and noncoreferent

*her*as

_{j}*hennes*.

English does allow specifying coreference, but it is optional, as both interpretations of the previous example are valid (the ungrammatical interpretation is indicated with an asterisk):

*Lisa*(interpretation #1:_{i}found her_{i}own book.*her*= of*Lisa*)- *
*Lisa*(interpretation #2:_{i}found her_{j}own book.*her*= of a female that is not Lisa)

However,
reflexive pronouns, such as *himself*, *herself*, *themselves*, etc., and
reciprocal pronouns, such as *each other*, act as bound variables. In a sentence like the following:

*Jane hurt***herself**.

the reflexive *herself* can only refer to the previously mentioned
antecedent, in this case *Jane*, and can never refer to a different female person. In this example, the variable *herself* is bound to the noun *Jane* that occurs in
subject position. Indicating the coindexation, the first interpretation with *Jane* and *herself* coindexed is permissible, but the other interpretation where they are not coindexed is
ungrammatical:

*Jane*(interpretation #1:_{i}hurt herself_{i}.*herself*=*Jane*)- *
*Jane*(interpretation #2:_{i}hurt herself_{j}.*herself*= a female that is not Jane)

Note that the coreference binding can be represented using a lambda expression as mentioned in the previous Formal explanation section. The sentence with the reflexive could be represented as

- (λ
*x*.*x*hurt*x*)Jane

in which *Jane* is the subject referent argument and *λx.x hurt x* is the predicate function (a lambda abstraction) with the lambda notation and *x* indicating both the semantic subject and the semantic object of sentence as being bound. This returns the semantic interpretation *JANE hurt JANE* with *JANE* being the same person.

Pronouns can also behave in a different way. In the sentence below

*Ashley hit***her**.

the pronoun *her* can only refer to a female that is not Ashley. This means that it can never have a reflexive meaning equivalent to *Ashley hit herself*. The grammatical and ungrammatical interpretations are:

- *
*Ashley*(interpretation #1:_{i}hit her_{i}.*her*=*Ashley*) *Ashley*(interpretation #2:_{i}hit her_{j}.*her*= a female that is not Ashley)

The first interpretation is impossible. Only the second interpretation is permitted by the grammar.

Thus, it can be seen that reflexives and reciprocals are bound variables (known technically as anaphors) while true pronouns are free variables in some grammatical structures but variables that cannot be bound in other grammatical structures. The binding phenomena found in natural languages was particularly important to the syntactic government and binding theory (see also: Binding (linguistics)).

## See also

## References

**^**Thompson 1991, p. 33.

- Thompson, Simon (1991).
*Type theory and functional programming*. Wokingham, England: Addison-Wesley. ISBN 0201416670. OCLC 23287456.