HOME

TheInfoList



OR:

In mathematics, and in other disciplines involving
formal language In logic, mathematics, computer science, and linguistics, a formal language consists of words whose letters are taken from an alphabet and are well-formed according to a specific set of rules. The alphabet of a formal language consists of sy ...
s, including
mathematical logic Mathematical logic is the study of formal logic within mathematics. Major subareas include model theory, proof theory, set theory, and recursion theory. Research in mathematical logic commonly addresses the mathematical properties of formal ...
and
computer science Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to practical disciplines (includi ...
, a free variable is a
notation In linguistics and semiotics, a notation is a system of graphics or symbols, characters and abbreviated expressions, used (for example) in artistic and scientific disciplines to represent technical facts and quantities by convention. Therefore, ...
(symbol) that specifies places in an
expression Expression may refer to: Linguistics * Expression (linguistics), a word, phrase, or sentence * Fixed expression, a form of words with a specific meaning * Idiom, a type of fixed expression * Metaphorical expression, a particular word, phrase, o ...
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 In software, a wildcard character is a kind of placeholder represented by a single character, such as an asterisk (), which can be interpreted as a number of literal characters or an empty string. It is often used in file searches so the full na ...
that stands for an unspecified symbol. In
computer programming Computer programming is the process of performing a particular computation (or more generally, accomplishing a specific computing result), usually by designing and building an executable computer program. Programming involves tasks such as anal ...
, the term free variable refers to variables used in a
function Function or functionality may refer to: Computing * Function key, a type of key on computer keyboards * Function model, a structured representation of processes in a system * Function object or functor or functionoid, a concept of object-oriente ...
that are neither
local variable In computer science, a local variable is a variable that is given ''local scope''. A local variable reference in the function or block in which it is declared overrides the same variable name in the larger scope. In programming languages with o ...
s nor
parameter A parameter (), generally, is any characteristic that can help in defining or classifying a particular system (meaning an event, project, object, situation, etc.). That is, a parameter is an element of a system that is useful, or critical, when ...
s of that function. The term
non-local variable In programming language theory, a non-local variable is a variable that is not defined in the local scope. While the term can refer to global variables, it is primarily used in the context of nested and anonymous functions where some variables can ...
is often a synonym in this context. A bound variable, in contrast, is a variable that has been ''bound'' to a specific value or range of values in the domain of discourse or
universe The universe is all of space and time and their contents, including planets, stars, galaxies, and all other forms of matter and energy. The Big Bang theory is the prevailing cosmological description of the development of the 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 n is a positive integer".) Examples are given in the next section. 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. Note that 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: \forall y\,\exists x\,\left(x=\sqrt\right). This expression evaluates to ''false'' if the domain of x and y 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 as used in statistics, most commonly 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 :\sum_^ 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 :\int_0^\infty x^ e^\,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 :\lim_\frac, ''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 :\forall x\ \exists y\ \Big varphi(x,y,z)\Big ''z'' is a free variable and ''x'' and ''y'' are bound variables, associated with
logical quantifier In logic, a quantifier is an operator that specifies how many individuals in the domain of discourse satisfy an open formula. For instance, the universal quantifier \forall in the first order formula \forall x P(x) expresses that everything i ...
s; consequently the
logical value In logic and mathematics, a truth value, sometimes called a logical value, is a value indicating the relation of a proposition to truth, which in classical logic has only two possible values (''true'' or '' false''). Computing In some progra ...
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 4 :Let n be a positive even integer. Then there is an integer k such that n=2k. Since n^2=4k^2, we have n^2 divisible by 4 not only ''k'' but also ''n'' have been used as bound variables as a whole in the proof.


Variable-binding operators

The following : \sum_ \quad\quad \prod_ \quad\quad \int_0^\infty \cdots \,dx \quad\quad \lim_ \quad\quad \forall x \quad\quad \exists x are some common variable-binding operators. Each of them binds the variable x for some set S. Note that many of these are
operators Operator may refer to: Mathematics * A symbol indicating a mathematical operation * Logical operator or logical connective in mathematical logic * Operator (mathematics), mapping that acts on elements of a space to produce elements of another sp ...
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 : \sum_ \left( k \mapsto f(k,n) \right) for sums or : D \left( x \mapsto x^2 + 2x + 1 \right) 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 In botany, a tree is a perennial plant with an elongated stem, or trunk, usually supporting branches and leaves. In some usages, the definition of a tree may be narrower, including only woody plants with secondary growth, plants that are ...
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 In computer science, tree traversal (also known as tree search and walking the tree) is a form of graph traversal and refers to the process of visiting (e.g. retrieving, updating, or deleting) each node in a tree data structure, exactly once. S ...
of the tree. Variable-binding operators are
logical operator In logic, a logical connective (also called a logical operator, sentential connective, or sentential operator) is a logical constant. They can be used to connect logical formulas. For instance in the syntax of propositional logic, the binary ...
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 Semantics (from grc, σημαντικός ''sēmantikós'', "significant") is the study of reference, meaning, or truth. The term can be used to refer to subfields of several distinct disciplines, including philosophy, linguistics and comp ...
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. 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 = \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''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 In mathematics and computer science, a higher-order function (HOF) is a function that does at least one of the following: * takes one or more functions as arguments (i.e. a procedural parameter, which is a parameter of a procedure that is itse ...
applying to a function. So, for example, the expression : \sum_ could be treated as a notation for : \sum_ where \sum_ 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 \forall x \in S\ P(x) can be thought of as an operator that evaluates to the
logical conjunction In logic, mathematics and linguistics, And (\wedge) is the truth-functional operator of logical conjunction; the ''and'' of a set of operands is true if and only if ''all'' of its operands are true. The logical connective that represents thi ...
of the
boolean-valued function A Boolean-valued function (sometimes called a predicate or a proposition) is a function of the type f : X → B, where X is an arbitrary set and where B is a Boolean domain, i.e. a generic two-element set, (for example B = ), whose elements are i ...
''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 Bound or bounds may refer to: Mathematics * Bound variable * Upper and lower bounds, observed limits of mathematical functions Physics * Bound state, a particle that has a tendency to remain localized in one or more regions of space Geography *B ...
variables. In English,
personal pronoun Personal pronouns are pronouns that are associated primarily with a particular grammatical person – first person (as ''I''), second person (as ''you''), or third person (as ''he'', ''she'', ''it'', ''they''). Personal pronouns may also take dif ...
s 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 Refer or referral may refer to: *Reference, a relation of designation or linking between objects **Word-sense disambiguation, when a single term may refer to multiple meanings *Referral marketing, to personally recommend, endorse, and pass a perso ...
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 In linguistics, coreference, sometimes written co-reference, occurs when two or more expressions refer to the same person or thing; they have the same referent. For example, in ''Bill said Alice would arrive soon, and she did'', the words ''Alice'' ...
) 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 Pragmatism is a philosophical movement. Pragmatism or pragmatic may also refer to: *Pragmaticism, Charles Sanders Peirce's post-1905 branch of philosophy *Pragmatics, a subfield of linguistics and semiotics *''Pragmatics'', an academic journal in ...
) 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: : ''Lisai found heri book.'' (interpretation #1: ''her'' = of ''Lisa'') : ''Lisai found herj 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 ''heri'' and ''herj'': for example,
Norwegian Norwegian, Norwayan, or Norsk may refer to: *Something of, from, or related to Norway, a country in northwestern Europe * Norwegians, both a nation and an ethnic group native to Norway * Demographics of Norway *The Norwegian language, including ...
and
Swedish Swedish or ' may refer to: Anything from or related to Sweden, a country in Northern Europe. Or, specifically: * Swedish language, a North Germanic language spoken primarily in Sweden and Finland ** Swedish alphabet, the official alphabet used by ...
translate coreferent ''heri'' as ''sin'' and noncoreferent ''herj'' 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): : ''Lisai found heri own book.'' (interpretation #1: ''her'' = of ''Lisa'') : *''Lisai found herj own book.'' (interpretation #2: ''her'' = of a female that is not Lisa) However,
reflexive pronoun A reflexive pronoun is a pronoun that refers to another noun or pronoun (its antecedent) within the same sentence. In the English language specifically, a reflexive pronoun will end in ''-self'' or ''-selves'', and refer to a previously n ...
s, such as ''himself'', ''herself'', ''themselves'', etc., and
reciprocal pronoun A reciprocal pronoun is a pronoun that indicates a reciprocal relationship. A reciprocal pronoun can be used for one of the participants of a reciprocal construction, i.e. a clause in which two participants are in a mutual relationship. The recip ...
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, 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 In linguistics, grammaticality is determined by the conformity to language usage as derived by the grammar of a particular speech variety. The notion of grammaticality rose alongside the theory of generative grammar, the goal of which is to form ...
: : ''Janei hurt herselfi.'' (interpretation #1: ''herself'' = ''Jane'') : *''Janei hurt herselfj.'' (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: : *''Ashleyi hit heri.'' (interpretation #1: ''her'' = ''Ashley'') : ''Ashleyi hit herj.'' (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 In linguistics, anaphora () is the use of an expression whose interpretation depends upon another expression in context (its antecedent or postcedent). In a narrower sense, anaphora is the use of an expression that depends specifically upon an a ...
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 A government is the system or group of people governing an organized community, generally a state. In the case of its broad associative definition, government normally consists of legislature, executive, and judiciary. Government is a ...
(see also:
Binding (linguistics) In linguistics, binding is the phenomenon in which anaphoric elements such as pronouns are grammatically associated with their antecedents. For instance in the English sentence "Mary saw herself", the anaphor "herself" is bound by its anteceden ...
).


See also

*
Closure (computer science) In programming languages, a closure, also lexical closure or function closure, is a technique for implementing lexically scoped name binding in a language with first-class functions. Operationally, a closure is a record storing a function t ...
* Combinatory logic *
Lambda lifting Lambda lifting is a meta-process that restructures a computer program so that functions are defined independently of each other in a global scope. An individual "lift" transforms a local function into a global function. It is a two step process ...
*
Name binding In programming languages, name binding is the association of entities (data and/or code) with identifiers. An identifier bound to an object is said to reference that object. Machine languages have no built-in notion of identifiers, but name-objec ...
*
Scope (programming) In computer programming, the scope of a name binding (an association of a name to an entity, such as a variable) is the part of a program where the name binding is valid; that is, where the name can be used to refer to the entity. In other parts ...


References

* {{Calculus topics Mathematical notation Logic symbols Computer programming Predicate logic