Lambda Calculus - Formal Definition - Free and Bound Variables

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

  1. FV(x) = {x}, where x is a variable
  2. FV(λx.M) = FV(M) {x}
  3. 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, variables, free and/or bound:

    I am always glad to think that my education was, for the most part, informal, and had not the slightest reference to a future business career. It left me free and untrammeled to approach my business problems without the limiting influence of specific training.
    Alice Foote MacDougall (1867–1945)

    The variables are surprisingly few.... One can whip or be whipped; one can eat excrement or quaff urine; mouth and private part can be meet in this or that commerce. After which there is the gray of morning and the sour knowledge that things have remained fairly generally the same since man first met goat and woman.
    George Steiner (b. 1929)

    Bigotry is the disease of ignorance, of morbid minds; enthusiasm of the free and buoyant. Education and free discussion are the antidotes of both.
    Thomas Jefferson (1743–1826)

    ...the soul of Jonathan was bound to the soul of David, and Jonathan loved him as his own soul.
    Bible: Hebrew (RSV)