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:
“You want to be free and break new ground, speak your mind, fear no man, have the neighbours acknowledge that you’re a good man; and at the same time you want to be a success, make money, join the country club, get the votes and kick the other man in the teeth and off the ladder.”
—Christina Stead (1902–1983)
“The angels yawning in an empty heaven;
Alternate shows of dynamite and rain;
And choosing forced on free will: fire or ice.”
—Philip Larkin (1922–1986)
“When I received this [coronation] ring I solemnly bound myself in marriage to the realm; and it will be quite sufficient for the memorial of my name and for my glory, if, when I die, an inscription be engraved on a marble tomb, saying, “Here lieth Elizabeth, which reigned a virgin, and died a virgin.””
—Elizabeth I (1533–1603)
“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)