| • Science | • People | • Locations | • Timeline |
In elementary algebra, for example, the symbol x is used to construct formulae, under the assumptions (i) later we may assign x a value such as 2, and (ii) each occurrence of x stands for the same unknown value. The variable x becomes a bound variable, for example, when we write
In this proposition it no longer much matters whether we use x or some other letter; but it would be confusing notationally to use the letter again elsewhere in some compound proposition. That is, free variables become bound, and then in a sense retire from further work supporting the formation of formulae.
Free and bound variables also are meaningful in natural languages. For example, without further context, in the phrase She was at home., the pronoun she could be regarded as a free variable. However, in this article we only consider free variables in formal languages.
Before stating a precise definition of free variable and bound variable (or dummy variable), we present some examples that perhaps make these two concepts clearer than the definition would (unfortunately the term dummy variable is used by many statisticians to mean an indicator variable or some variant thereof; the name is really not apt for that purpose, but magnificently conveys the intuition behind the definition of this concept):
In the expression
y is a free variable and x is a bound variable (or dummy 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 y is a bound variable; consequently the value of this expression depends on the value of x, but there is nothing called y 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; consequently the truth-value of this expression depends on the value of z, but there is nothing called x or y on which it could depend.
The expressions
are variable-binding operators. The variables that they bind are x (in the first, second, and fourth examples) and h (in the third example).
Variable-binding mechanisms occur in different contexts in mathematics, logic and computer science but in all cases they are purely syntacticThe first meaning of the term syntax originating from the Greek words (sun, meaning ‘together’) and (taxis, meaning sequence/order), can be described as the study of the rules, or "patterned relations" that govern the way the words in a sentence come toge properties of expressions and variables in them. For this section we can summarize syntax by identifying expressions with treeThis article is about the biological organisms known as trees. For other meanings of the word see tree (disambiguation). oak tree in Denmark A tree can be defined as a large perennial woody plant. Though there is no set definition of size, it is generallys whose leaf nodes are variables, function constants or predicate constants and whose nodes are logical operators. Variable-binding operators are logical operators that occur in almost every formal language. Indeed languages which do not have them are either extremely inexpressive or extremely difficult to use. 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 semanticsIn general, semantics (from the Greek semantikos or "significant meaning," derived from sema sign) is the study of meaning, in some sense of that term. Semantics is often opposed to syntax, in which case the former pertains to what something means while t 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 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
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 x1, ..., xn and it may contain other variables. In this case we say that function definition binds the variables x1, ..., xn.
In the lambda calculusThe lambda calculus is a formal system designed to investigate function definition, function application, and recursion. It was introduced by Alonzo Church and Stephen Cole Kleene in the 1930s; Church used the lambda calculus in 1936 to give a negative an, x is a bound variable in the term M = λ x . T, and a free variable of 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 functionIn mathematical logic and computer science, the recursive functions are a class of functions from natural numbers to natural numbers which are "computable" in some intuitive sense. In fact, in computability theory it is shown that the recursive functions is also technically a free variable within its own body but is treated specially.
A closed term is one containing no free variables.