FACTOID # 26: Delaware is the latchkey kid capital of America, with 71.8% of households having both parents in the labor force.
 
 Home   Encyclopedia   Statistics   States A-Z   Flags   Maps   FAQ   About 
   
 
WHAT'S NEW
 

SEARCH ALL

FACTS & STATISTICS    Advanced view

Search encyclopedia, statistics and forums:

 

 

(* = Graphable)

 

 


Encyclopedia > Free variables and bound variables

In computer programming, a free variable is a variable referred to in a function that is not a local variable or an argument of that function. Programming redirects here. ... In computer science, a local variable is a variable that is given local scope. ...


In mathematics, and in other disciplines involving formal languages, including mathematical logic and computer science, a free variable is a notation for a place or places in an expression, into which some definite substitution may take place, or with respect to which some operation (summation or quantification, to give two examples) may take place. The idea is related to, but somewhat deeper and more complex than, that of a placeholder (a symbol that will later be replaced by some literal string), or a wildcard character that stands for an unspecified symbol. Euclid, Greek mathematician, 3rd century BC, as imagined by by Raphael in this detail from The School of Athens. ... In mathematics, logic, and computer science, a formal language is a set of finite-length words (i. ... To meet Wikipedias quality standards, this article or section may require cleanup. ... Computer science, or computing science, is the study of the theoretical foundations of information and computation and their implementation and application in computer systems. ... The term notation can be used in several contexts. ... An expression in the very basic sense is the noun form of the verb express. ... In general, substitution is the replacement of one thing with another. ... Summation is the addition of a set of numbers; the result is their sum. ... In language and logic, quantification is a construct that specifies the extent of validity of a predicate, that is the extent to which a predicate holds over a range of things. ... In various branches of mathematics and computer science, strings are sequences of various simple objects (symbols, tokens, characters, etc. ... The term wildcard character has the following meanings: // Telecommunication In telecommunications, a wildcard character is a character that may be substituted for any of a defined subset of all possible characters. ...


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

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

or

'There exists x such that x2 = 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 further work supporting the formation of formulae. Proposition is a term used in logic to describe the content of assertions. ...

Contents

Examples

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 mathematical subfield of set theory, the indicator function is a function defined on a set X which is used to indicate membership of an element in a subset A of X. Remark. ...


In the expression

sum_{k=1}^{10} f(k,n),

n is a free variable and k is a bound variable (or dummy 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

sum_{n=1}^{10} f(k,n),

k is a free variable and n is a bound variable; consequently the value of this expression depends on the value of k, but there is nothing called n on which it could depend.


In the expression

int_0^infty x^{y-1} e^{-x},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_{hrightarrow 0}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

forall x exists y 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. In logic and mathematics, a logical value, also called a truth value, is a value indicating to what extent a proposition is true. ...


Variable-binding operators

The following

sum_{xin S}qquadqquad int_0^inftycdots,dxqquadqquad lim_{xto 0}qquadqquad forall x

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


Formal explanation

Variable-binding mechanisms occur in different contexts in mathematics, logic and computer science but in all cases 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. 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. For other uses, see Syntax (disambiguation). ... The coniferous Coast Redwood, the tallest tree species on earth. ... In logical calculus, logical operators or logical connectors serve to connect statements into more complicated compound statements. ... Semantics (Greek semantikos, giving signs, significant, symptomatic, from sema, sign) refers to the aspects of meaning that are expressed in a language, code, or other form of representation. ...

Image:IMG_binding.jpg
forall x, (exists y, A(x) vee B(z)) this is a parse tree File history Legend: (cur) = this is the current file, (del) = delete this old version, (rev) = revert to this old version. ...

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


To give an example from mathematics, consider an expression which defines a function

(x_1, ldots , x_n) mapsto operatorname{t}

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 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. The lambda calculus is a formal system designed to investigate function definition, function application, and recursion. ...


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. It has been suggested that recursive function be merged into this article or section. ...


A closed term is one containing no free variables.


See also

In programming languages, a closure is a function that refers to free variables in its lexical context. ... In mathematics, the closure C(X) of an object X is defined to be the smallest object that both includes X as a subset and possesses some given property. ... Lambda lifting is the process of eliminating free variables and local function definitions from a computer program. ... In computer programming in general, a scope is an enclosing context. ... Combinatory logic is a notation introduced by Moses Schönfinkel and Haskell Curry to eliminate the need for variables in mathematical logic. ... The article is about assignment in mathematical logic; for other uses, see Assignment Assignment can be regarded as an auxiliary notion, an important step in a specific way for defining the concept of truth formally (e. ...

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.


  Results from FactBites:
 
Free variables and bound variables: Definition and Links by Encyclopedian.com - All about Free variables and bound ... (417 words)
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.
A free variable is a variable referred to in a function, which is not an argument of the function.
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.
Variable - Wikipedia, the free encyclopedia (2090 words)
Variables are useful in mathematics and computer programming because they allow instructions to be specified in a general way.
In general, a variable binds an object to a name so that the object could be accessed later, much like a person has a name and people could refer to him by that name.
Usually, a variable is set to reside in some scope in program code, and entrance and leave of the scope coincides with the beginning and ending of a variable life, respectively.
  More results at FactBites »

 
 

COMMENTARY     


Share your thoughts, questions and commentary here
Your name
Your comments

Want to know more?
Search encyclopedia, statistics and forums:

 


Press Releases |  Feeds | Contact
The Wikipedia article included on this page is licensed under the GFDL.
Images may be subject to relevant owners' copyright.
All other elements are (c) copyright NationMaster.com 2003-5. All Rights Reserved.
Usage implies agreement with terms, 1022, m