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, bound and/or variables:
“In the deserts of the heart
Let the healing fountain start,
In the prison of his days
Teach the free man how to praise.”
—W.H. (Wystan Hugh)
“Without being bound to the fulfillment of promises, we would never be able to keep our identities; we would be condemned to wander helplessly and without direction in the darkness of each man’s lonely heart, caught in its contradictions and equivocalities—a darkness which only the light shed over the public realm through the presence of others, who confirm the identity between the one who promises and the one who fulfills, can dispel.”
—Hannah Arendt (1906–1975)
“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)