Editing Free variables and bound variables

{{Short description|Concept in mathematics or computer science}}
{{For|bound variables in computer programming|Name binding}}
{{For|free variables in systems of linear equations|Free variables (system of linear equations)}}
{{Redirect-distinguish|Free variable|Free parameter|Dummy variable (statistics)|}}
{{Refimprove|date=December 2008}}

In [[mathematics]], and in other disciplines involving [[formal language]]s, 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 [[Mathematical notation|notation]] (symbol) that specifies places in an [[expression (mathematics)|expression]] where [[Substitution (logic)|substitution]] may take place and is not a parameter of this or any container expression. 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 [[variable (programming)|variables]] used in a [[function (computer science)|function]] that are neither [[local variable]]s nor [[parameter (computer programming)|parameter]]s 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 (mathematics)|universe]]. This may be achieved through the use of logical quantifiers, variable-binding operators, or an explicit statement of allowed values for the variable (such as, "...where <math>n</math> is a positive integer".) A variable symbol overall is '''bound''' if at least one occurrence of it is bound.<ref name="Quine81">[[W. V. O. Quine]] (1981) ''Mathematical Logic'', Harvard University Press {{ISBN|0-674-55451-5}}</ref><sup>pp.142--143</sup> 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,<ref name="Quine81" /><sup>p.78</sup> 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:

:<math>\forall y\,\exists x\,\left(x=\sqrt{y}\right).</math>

This expression evaluates to ''false'' if the domain of <math>x</math> and <math>y</math> 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 (more commonly in general mathematics than in computer science), but this should not be confused with the identically named but unrelated concept of [[dummy variable (statistics)|dummy variable]] as used in statistics, most commonly in regression analysis.<ref>Robert S. Wolf (2005) ''A Tour through Mathematical Logic'' {{ISBN|978-0-88385-036-7}}</ref><sup>p.17</sup>

==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

:<math>\sum_{k=1}^{10} f(k,n),</math>

''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 

:<math>\int_0^\infty x^{y-1} e^{-x}\,dx,</math>

''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

:<math>\lim_{h\rightarrow 0}\frac{f(x+h)-f(x)}{h},</math>

''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

:<math>\forall x\ \exists y\ \Big[\varphi(x,y,z)\Big],</math>

''z'' is a free variable and ''x'' and ''y'' are bound variables, associated with [[logical quantifier]]s; 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 proofs, bound variables are used. For example, the following proof shows that all squares of positive even integers are divisible by <math>4</math>

:Let <math>n</math> be a positive even integer. Then there is an integer <math>k</math> such that <math>n=2k</math>. Since <math>n^2=4k^2</math>, we have <math>n^2</math> divisible by <math>4</math>

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

===Variable-binding operators===
The following

: <math>\sum_{x\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</math>

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

Many of these are [[Operator (mathematics)|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

: <math>\sum_{1, \ldots, 10} \left( k \mapsto f(k,n) \right)</math>

for sums or

: <math>D \left( x \mapsto x^2 + 2x + 1 \right) </math>

for differentiation.

==Formal explanation==
[[File:Binary math expression tree.svg|thumb|Tree summarizing the syntax of the expression <math>\forall x\, ((\exists y\, A(x)) \vee B(z)) </math>]]

Variable-binding mechanisms occur in different contexts in mathematics, logic and computer science. In all cases, however, they are purely [[syntax|syntactic]] properties of expressions and variables in them. For this section we can summarize syntax by identifying an expression with a [[Abstract syntax tree|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 [[Tree traversal|inorder traversal]] of the tree. Variable-binding operators are [[logical operator]]s 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]], <code>x</code> is a bound variable in the term <code>M = λx. T</code> and a free variable in the term <code>T</code>. We say <code>x</code> is bound in <code>M</code> and free in <code>T</code>. If <code>T</code> contains a subterm <code>λx. U</code> then <code>x</code> is rebound in this term. This nested, inner binding of <code>x</code> is said to "shadow" the outer binding. Occurrences of <code>x</code> in <code>U</code> are free occurrences of the new <code>x</code>.{{sfn|Thompson|1991|p=33}}

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 [[computable function|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

: <math>f = \left[ (x_1, \ldots , x_n) \mapsto t \right]</math>

where ''t'' is an expression. ''t'' may contain some, all or none of the ''x''<sub>1</sub>, …, ''x''<sub>''n''</sub> and it may contain other variables. In this case we say that function definition binds the variables ''x''<sub>1</sub>, …, ''x''<sub>''n''</sub>.

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 function]]s applying to a function. So, for example, the expression

: <math>\sum_{x \in S}{x^2}</math>

could be treated as a notation for

: <math>\sum_{S}{(x \mapsto x^2)}</math>

where <math>\sum_{S}{f}</math> 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]] <math>\forall x \in S\ P(x)</math> 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==
{{Multiple issues|section=yes|
{{Unsourced section|date=March 2023}}
{{Expand section|date=December 2008}}
}}

When analyzed in [[Formal semantics (logic)|formal semantics]], natural languages can be seen to have free and [[Bound variable pronoun|bound]] variables. In English, [[personal pronoun]]s like ''he'', ''she'', ''they'', etc. can act as free variables.<ref>{{Cite book |title=Papers in Computational Linguistics: Proceedings of the 3rd International Meeting on Computational Linguistics held at Debrecen, Hungary |date=2020 |publisher=De Gruyter Mouton |isbn=978-3-11-080670-0 |editor-last=Papp |editor-first=Ferenc |edition=Reprint 2017 |series=Janua Linguarum. Series Maior |location=Berlin Boston |pages=88-90 |editor-last2=Szépe |editor-first2=György}}</ref>

: ''Lisa found '''her''' book.''

In the sentence above, the possessive pronoun ''her'' is a free variable. It may [[Reference#Semantics|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. [[Pragmatics|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<sub>'''i'''</sub> found her<sub>'''i'''</sub> book.'' (interpretation #1: ''her'' = of ''Lisa'')
: ''Lisa<sub>'''i'''</sub> found her<sub>'''j'''</sub> book.'' (interpretation #2: ''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<sub>'''i'''</sub>'' and ''her<sub>'''j'''</sub>'': for example, [[Norwegian language|Norwegian]] and [[Swedish language|Swedish]] translate coreferent ''her<sub>'''i'''</sub>'' as ''sin'' and noncoreferent ''her<sub>'''j'''</sub>'' as ''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<sub>'''i'''</sub> found her<sub>'''i'''</sub> own book.'' (interpretation #1: ''her'' = of ''Lisa'')
: *''Lisa<sub>'''i'''</sub> found her<sub>'''j'''</sub> own book.'' (interpretation #2: ''her'' = of a female that is not Lisa)

However, [[reflexive pronoun]]s, such as ''himself'', ''herself'', ''themselves'', etc., and [[reciprocal pronoun]]s, 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 (grammar)|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 (grammar)|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 [[Grammaticality|ungrammatical]]:

: ''Jane<sub>'''i'''</sub> hurt herself<sub>'''i'''</sub>.'' (interpretation #1: ''herself'' = ''Jane'')
: *''Jane<sub>'''i'''</sub> hurt herself<sub>'''j'''</sub>.'' (interpretation #2: ''herself'' = a female that is not Jane)

The coreference binding can be represented using a [[Lambda calculus|lambda expression]] as mentioned in the previous [[#Formal explanation|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<sub>'''i'''</sub> hit her<sub>'''i'''</sub>.'' (interpretation #1: ''her'' = ''Ashley'')
: ''Ashley<sub>'''i'''</sub> hit her<sub>'''j'''</sub>.'' (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 [[anaphor]]s) 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==
* [[Closure (computer science)]]
* [[Combinatory logic]]
* [[Lambda lifting]]
* [[Name binding]]<!-- that article is a bit better but still fails to explain the notion of an environment (which is used in both logic and programming!) -->
* [[Scope (programming)]]
* [[Scope (logic)]]

==References==
{{Reflist}}
* {{Cite book|title=Type theory and functional programming|first=Simon|last=Thompson|date=1991|publisher=Addison-Wesley|isbn=0201416670|location=Wokingham, England|oclc=23287456}}
*{{cite book |jstor=10.4169/j.ctt5hh94h |title=A Tour through Mathematical Logic |last1=Wolf |first1=Robert S. |date=2005 |volume=30 |publisher=Mathematical Association of America |isbn=978-0-88385-042-8 }}

==Further reading==
* {{Princeton Companion to Mathematics|pages=15–16}}

{{Calculus topics}}

[[Category:Mathematical notation]]
[[Category:Logic symbols]]
[[Category:Computer programming]]
[[Category:Predicate logic]]