Free variables and bound variables - AbsoluteAstronomy.com

Mathematics

Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...

, and in other disciplines involving formal language

Formal language

A formal language is a set of words—that is, finite strings of letters, symbols, or tokens that are defined in the language. The set from which these letters are taken is the alphabet over which the language is defined. A formal language is often defined by means of a formal grammar...

s, including mathematical logic

Mathematical logic

Mathematical logic is a subfield of mathematics with close connections to foundations of mathematics, theoretical computer science and philosophical logic. The field includes both the mathematical study of logic and the applications of formal logic to other areas of mathematics...

and computer science

Computer science

Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...

, a free variable is a notation

Mathematical notation

Mathematical notation is a system of symbolic representations of mathematical objects and ideas. Mathematical notations are used in mathematics, the physical sciences, engineering, and economics...

that specifies places in an expression

Expression (mathematics)

In mathematics, an expression is a finite combination of symbols that is well-formed according to rules that depend on the context. Symbols can designate numbers , variables, operations, functions, and other mathematical symbols, as well as punctuation, symbols of grouping, and other syntactic...

where substitution may take place. The idea is related to a placeholder (a symbol

Symbol

A symbol is something which represents an idea, a physical entity or a process but is distinct from it. The purpose of a symbol is to communicate meaning. For example, a red octagon may be a symbol for "STOP". On a map, a picture of a tent might represent a campsite. Numerals are symbols for...

that will later be replaced by some literal string), or a wildcard character

Wildcard character

-Telecommunication:In telecommunications, a wildcard character is a character that may be substituted for any of a defined subset of all possible characters....

that stands for an unspecified symbol.

The variable x becomes a bound variable, for example, when we write

'For all x, (x + 1)² = x² + 2x + 1.'

'There exists x such that x² = 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

Proposition

In logic and philosophy, the term proposition refers to either the "content" or "meaning" of a meaningful declarative sentence or the pattern of symbols, marks, or sounds that make up a meaningful declarative sentence...

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

In computer programming

Computer programming

Computer programming is the process of designing, writing, testing, debugging, and maintaining the source code of computer programs. This source code is written in one or more programming languages. The purpose of programming is to create a program that performs specific operations or exhibits a...

, a free variable is a variable

Variable (programming)

In computer programming, a variable is a symbolic name given to some known or unknown quantity or information, for the purpose of allowing the name to be used independently of the information it represents...

referred to in a function that is not a local variable

Local variable

In computer science, a local variable is a variable that is given local scope. Such a variable is accessible only from the function or block in which it is declared. In programming languages with only two levels of visibility, local variables are contrasted with global variables...

or an argument of that function. An upvalue is a free variable that has been bound (closed over) with a closure

Closure (computer science)

In computer science, a closure is a function together with a referencing environment for the non-local variables of that function. A closure allows a function to access variables outside its typical scope. Such a function is said to be "closed over" its free variables...

. Note that variable "freeness" only applies in lexical scoping: there is no distinction, and hence no closures, when using dynamic scope.

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

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

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 logical value

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.In classical logic, with its intended semantics, the truth values are true and false; that is, classical logic is a two-valued logic...

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

are variable-binding operators. Each of them binds the variable x.

Note that many of these are operators

Operator (programming)

Programming languages typically support a set of operators: operations which differ from the language's functions in calling syntax and/or argument passing mode. Common examples that differ by syntax are mathematical arithmetic operations, e.g...

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

for sums or

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

Syntax

In linguistics, syntax is the study of the principles and rules for constructing phrases and sentences in natural languages....

properties of expressions and variables in them. For this section we can summarize syntax by identifying an expression with a tree

Abstract syntax tree

In computer science, an abstract syntax tree , or just syntax tree, is a tree representation of the abstract syntactic structure of source code written in a programming language. Each node of the tree denotes a construct occurring in the source code. The syntax is 'abstract' in the sense that it...

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

Tree traversal

In computer science, tree-traversal refers to the process of visiting each node in a tree data structure, exactly once, in a systematic way. Such traversals are classified by the order in which the nodes are visited...

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

Semantics

Semantics is the study of meaning. It focuses on the relation between signifiers, such as words, phrases, signs and symbols, and what they stand for, their denotata....

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

Lambda calculus

In mathematical logic and computer science, lambda calculus, also written as λ-calculus, is a formal system for function definition, function application and recursion. The portion of lambda calculus relevant to computation is now called the untyped 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

Computable function

Computable functions are the basic objects of study in computability theory. Computable functions are the formalized analogue of the intuitive notion of algorithm. They are used to discuss computability without referring to any concrete model of computation such as Turing machines or register...

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

where t is an expression. t may contain some, all or none of the x₁, ..., x_n and it may contain other variables. In this case we say that function definition binds the variables
x₁, ..., 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

Lambda calculus

. Other binding operators, like the summation

Summation

Summation is the operation of adding a sequence of numbers; the result is their sum or total. If numbers are added sequentially from left to right, any intermediate result is a partial sum, prefix sum, or running total of the summation. The numbers to be summed may be integers, rational numbers,...

sign, can be thought of as higher-order functions applying to a function. So, for example, the expression

could be treated as a notation for

where

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

can be thought of as an operator that evaluates to the logical conjunction

Logical conjunction

In logic and mathematics, a two-place logical operator and, also known as logical conjunction, results in true if both of its operands are true, otherwise the value of false....

of the boolean-valued function

Boolean-valued function

A boolean-valued function, in some usages is 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....

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 pronoun

Personal pronoun

Personal pronouns are pronouns used as substitutes for proper or common nouns. All known languages contain personal pronouns.- English personal pronouns :English in common use today has seven personal pronouns:*first-person singular...

s like he, she, they, etc. can act as free variables.

Lisa found her book.

In the sentence above, the possessive 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

Coreference

In linguistics, co-reference occurs when multiple expressions in a sentence or document refer to the same thing; or in linguistic jargon, they have the same "referent."...

) 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 the situational (i.e. pragmatic

Pragmatics

Pragmatics is a subfield of linguistics which studies the ways in which context contributes to meaning. Pragmatics encompasses speech act theory, conversational implicature, talk in interaction and other approaches to language behavior in philosophy, sociology, and linguistics. It studies how the...

) 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

Norwegian language

Norwegian is a North Germanic language spoken primarily in Norway, where it is the official language. Together with Swedish and Danish, Norwegian forms a continuum of more or less mutually intelligible local and regional variants .These Scandinavian languages together with the Faroese language...

translates her_i as sin and her_j as hennes.

However, reflexive pronoun

Reflexive pronoun

A reflexive pronoun is a pronoun that is preceded by the noun, adjective, adverb or pronoun to which it refers within the same clause. In generative grammar, a reflexive pronoun is an anaphor that must be bound by its antecedent...

s, such as himself, herself, themselves, etc., and reciprocal pronoun

Reciprocal pronoun

The reciprocal pronouns in English are one another and each other. Together with the reflexive pronouns — myself, yourself, ourselves, yourselves, and others — they are classified as anaphors....

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

Antecedent

An antecedent is a preceding event, condition, cause, phrase, or word. It may refer to:* Antecedent moisture, a hydrologic term describing the relative wetness condition of a sewershed.* Antecedent , the first half of a hypothetical proposition....

Jane. It can never refer to a different female person. In other words, the person being hurt yesterday 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

Subject

-Philosophy:*Hypokeimenon or subiectum, in metaphysics, the essential being of a thing**Subject , a being that has subjective experiences, subjective consciousness, or a relationship with another entity...

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

Grammaticality

In theoretical linguistics, grammaticality is the quality of a linguistic utterance of being grammatically well-formed. An * before a form is a mark that the cited form 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

Lambda expression

Lambda expression may refer to:*Anonymous function*Lambda calculus#Definition...

as mentioned in the previous Formal explanation section. The sentence with the reflexive could be represented as

((λx(x hurt x))(Jane))

Pronouns can also behave in a different way. In the sentence below

Ashley met 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 met herself. The grammatical and ungrammatical interpretations are:

*Ashley_i met her_i. (interpretation #1: her = Ashley)

Ashley_i met her_j. (interpretation #2: her = a female that is not Ashley)

The first interpretation is impossible, but the second interpretation is grammatical (and in this case, is the only interpretation).

Thus, it can be seen that reflexives and reciprocals are bound variables (known technically as anaphors) while true pronouns can be free variables in some grammatical structures or 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

Government and binding theory

Government and binding is a theory of syntax and a phrase structure grammar in the tradition of transformational grammar developed principally by Noam Chomsky in the 1980s...

(see also: Binding (linguistics)

Binding (linguistics)

In linguistics, binding theory is any of a broad class of theories dealing with the distribution of pronominal and anaphoric elements. The idea that there should be a specialised, coherent theory dealing with this particular set of phenomena originated in work in transformational grammar in the 1970s...

Examples

Variable-binding operators

Formal explanation

Function expressions

Natural language

See also