Free variables and bound variables


In mathematics, and in other disciplines involving formal languages, including mathematical logic and computer science, a variable may be said to be either free or bound. Some older books use the terms real variable and apparent variable for free variable and bound variable, respectively. A free variable is a notation that specifies places in an expression where substitution may take place and is not a parameter of this or any container expression. The idea is related to a placeholder, 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.
An instance of a variable symbol is bound, in contrast, if the value of that variable symbol has been bound to a specific value or range of values in the domain of discourse or universe. This may be achieved through the use of logical quantifiers, variable-binding operators, or an explicit statement of allowed values for the variable A variable symbol overall is bound if at least one occurrence of it is bound. Since the same variable symbol may appear in multiple places in an expression, some occurrences of the variable symbol may be free while others are bound, hence "free" and "bound" are at first defined for occurrences and then generalized over all occurrences of said variable symbol in the expression. However it is done, the variable ceases to be an independent variable on which the value of the expression depends, whether that value be a truth value or the numerical result of a calculation, or, more generally, an element of an image set of a function.
While the domain of discourse in many contexts is understood, when an explicit range of values for the bound variable has not been given, it may be necessary to specify the domain in order to properly evaluate the expression. For example, consider the following expression in which both variables are bound by logical quantifiers:
This expression evaluates to false if the domain of and is the real numbers, but true if the domain is the complex numbers.
The term "dummy variable" is also sometimes used for a bound variable, but this should not be confused with the identically named but unrelated concept of dummy variable as used in statistics, most commonly in regression analysis.p.17

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:
  • In the expression:
  • In the expression:
  • In the expression:

    In proofs

In a broader context, bound variables are fundamental to the structure of mathematical proofs. For example, the following proof shows that the square of any positive even integer is divisible by 4:

Let be an arbitrary positive even integer. By definition, there exists an integer such that. Substituting this into the expression for the square gives. Since is an integer, is also an integer. Therefore, is divisible by 4.

In this proof, both and function as bound variables, but they are bound in different ways.
The variable is introduced as an arbitrary but particular element of a set. The statement "Let be..." implicitly functions as a universal quantifier, binding for the scope of the proof. The proof establishes a property for this single, arbitrary, which licenses the general conclusion that the property holds for all positive even integers.
The variable, on the other hand, is bound by an existential quantifier. It is introduced to represent a specific, though unnamed, integer whose existence is guaranteed by the definition of being even. The scope of is limited to the reasoning that follows its introduction.
Thus, neither variable is free; their meaning is entirely determined by their role within the logical structure of the proof.

Variable-binding operators

In mathematics and logic, a number of symbols function as variable-binding operators. These operators take a function or an open formula as an argument and bind a free variable within that expression to a specific domain or range of values, creating a new expression whose meaning does not depend on the bound variable.
Common variable-binding operators include:
  • The summation and product operators, which bind a variable over a set or range of values.
  • The integral and limit operators, which bind a variable over a continuum or as it approaches a certain value.
  • The logical quantifiers, such as the universal quantifier and the existential quantifier, which bind a variable over a domain of discourse.
In each case, the variable x is bound within the expression that follows the operator. Many of these operators act on a function of the bound variable. While standard notation is often sufficient, complex expressions with nested operators can become ambiguous, particularly if the same variable name is reused. This can lead to a problem known as variable capture, where a variable intended to be free is incorrectly bound by an operator in a different scope.
To avoid such ambiguity, it can be useful to switch to a notation that makes the binding explicit, treating the operators as higher-order functions. This approach, rooted in the principles of lambda calculus, clearly separates the function being operated on from the operator itself.
For example:
  • The summation can be written to make the functional argument explicit:
Here, the operator applies to the set S and the function f.
This notation clarifies that the operator is applied to the entire function, rather than just an expression in which happens to be a variable.

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 in-order traversal of the tree. Variable-binding operators are logical operators that occur in almost every formal language. A binding operator takes two arguments: a variable and an expression, and when applied to its arguments produces a new expression. 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, a location for that variable in an expression and a non-leaf node of the form. It worth noting that 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.
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.
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 definition and operators as binders

A clear example of a variable-binding operator from mathematics is function definition. An expression that defines a function, such as the right-hand side of:
binds the variables. The expression, which forms the body of the function, may contain some, all, or none of the variables, which are its formal parameters. Any occurrence of these variables within is bound by the function definition. The body may also contain other variables, which would be considered free variables whose values must be determined from a wider context.
The expression is directly analogous to lambda expressions in lambda calculus, where the symbol is the fundamental variable-binding operator. For instance, the function definition is equivalent to the lambda abstraction.
The same definition, binding the function being defined to the name, is more commonly written in mathematical texts in the form
Other mathematical operators can be understood as higher-order functions that bind variables. For example, the summation operator,, can be analyzed as an operator that takes a function and a set to evaluate that function over. The expression:
binds the variable x within the term. The scope of the binding is the term that follows the summation symbol. This expression can be treated as a more compact notation for:
Here, is an operator with two parameters: a one-parameter function and a set to evaluate that function over.
Other operators can be expressed in a similar manner. The universal quantifier can be understood as an operator that evaluates to the logical conjunction of the Boolean-valued function applied to each element in the set. Likewise, the product operator, the limit operator, and the integral operator all function as variable binders, binding the variables and respectively over a specified domain.