Free and Bound Variables
The abstraction operator, λ, is said to bind its variable wherever it occurs in the body of the abstraction. Variables that fall within the scope of a lambda are said to be bound. All other variables are called free. For example in the following expression y is a bound variable and x is free: λy.x x y. Also note that a variable binds to its "nearest" lambda. In the following expression one single occurrence of x is bound by the second lambda: λx.y (λx.z x)
The set of free variables of a lambda expression, M, is denoted as FV(M) and is defined by recursion on the structure of the terms, as follows:
- FV(x) = {x}, where x is a variable
- FV(λx.M) = FV(M) \ {x}
- FV(M N) = FV(M) ∪ FV(N)
An expression that contains no free variables is said to be closed. Closed lambda expressions are also known as combinators and are equivalent to terms in combinatory logic.
Read more about this topic: Lambda Calculus, Formal Definition
Famous quotes containing the words free and, free, bound and/or variables:
“Without free, self-respecting, and autonomous citizens there can be no free and independent nations. Without internal peace, that is, peace among citizens and between the citizens and the state, there can be no guarantee of external peace.”
—Václav Havel (b. 1936)
“Man is a masterpiece of creation if for no other reason than that, all the weight of evidence for determinism notwithstanding, he believes he has free will.”
—G.C. (Georg Christoph)
“Nature in darkness groans
And men are bound to sullen contemplation in the night:
Restless they turn on beds of sorrow; in their inmost brain
Feeling the crushing wheels, they rise, they write the bitter words
Of stern philosophy & knead the bread of knowledge with tears & groans.”
—William Blake (1757–1827)
“The variables of quantification, ‘something,’ ‘nothing,’ ‘everything,’ range over our whole ontology, whatever it may be; and we are convicted of a particular ontological presupposition if, and only if, the alleged presuppositum has to be reckoned among the entities over which our variables range in order to render one of our affirmations true.”
—Willard Van Orman Quine (b. 1908)