For bound variables in computer programming, see
Name binding.
In mathematics, and in other disciplines involving formal languages, including mathematical logic and computer science, a free variable is a notation that specifies places in an expression where substitution may take place. The idea is related to a placeholder (a symbol that will later be replaced by some literal string), 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 not local variables nor parameters of that function.^{[1]} 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. 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 we use x or some other letter. 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 creates 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
- $\backslash sum\_\{k=1\}^\{10\}\; f(k,n),$
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
- $\backslash int\_0^\backslash infty\; x^\{y-1\}\; e^\{-x\}\backslash ,dx,$
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
- $\backslash lim\_\{h\backslash rightarrow\; 0\}\backslash frac\{f(x+h)-f(x)\}\{h\},$
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
- $\backslash forall\; x\backslash \; \backslash exists\; y\backslash \; \backslash varphi(x,y,z),$
z is a free variable and x and y are bound variables; 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.
Variable-binding operators
The following
- $\backslash sum\_\{x\backslash in\; S\}$
\quad\quad \prod_{x\in S}
\quad\quad \int_0^\infty\cdots\,dx
\quad\quad \lim_{x\to 0}
\quad\quad \forall x
\quad\quad \exists x
are variable-binding operators. Each of them binds the variable x.
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
- $\backslash sum\_\{1\; \backslash ,\; \backslash ldots\; \backslash ,\; 10\}\; \backslash left(\; k\; \backslash mapsto\; f(k,n)\; \backslash right)$
for sums or
- $D\; \backslash left(\; x\; \backslash mapsto\; x^2\; +\; 2x\; +\; 1\; \backslash right)\; \backslash ,$
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. 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 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 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 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
- $f\; =\; \backslash left[\; (x\_1,\; \backslash ldots\; ,\; x\_n)\; \backslash mapsto\; \backslash operatorname\{t\}\; \backslash right]$
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
- $\backslash sum\_\{x\; \backslash in\; \backslash mathbb\{A\}\}\{x^2\}$
could be treated as a notation for
- $\backslash sum\_\{\backslash mathbb\{A\}\}\{(x\; \backslash mapsto\; x^2)\}$
where $\backslash sum\_\{\backslash mathbb\{S\}\}\{f\}$ 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 $\backslash forall\; x\; \backslash in\; \backslash mathbb\{S\}\backslash \; P(x)$ 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_{i} found her_{i} book. (interpretation #1: her = Lisa)
- Lisa_{i} found her_{j} book. (interpretation #2: her = 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_{j}: for example, Norwegian translates coreferent her_{i} as sin and noncoreferent her_{j} as hennes.
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 Jane. It can never refer to a different female person. In other words, the person being hurt and the person doing the hurting are both the same person, i.e. Jane. The semantics of this sentence is abstractly: JANE hurt JANE. And it cannot be the case that this sentence could mean JANE hurt LISA. The reflexive herself must refer and can only refer to the previously mentioned Jane. In this sense, 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 (the ungrammatical interpretation is indicated with an asterisk):
- Jane_{i} hurt herself_{i}. (interpretation #1: herself = Jane)
- *Jane_{i} hurt herself_{j}. (interpretation #2: 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_{i} hit her_{i}. (interpretation #1: her = Ashley)
- Ashley_{i} hit her_{j}. (interpretation #2: 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
A small part of this article was originally based on material from the Free On-line Dictionary of Computing and is used with permission under the GFDL. Most of what now appears here is the result of later editing.
This article was sourced from Creative Commons Attribution-ShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and USA.gov, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for USA.gov and content contributors is made possible from the U.S. Congress, E-Government Act of 2002.
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a non-profit organization.