Free and bounded variables

In Lambda Calculus, variables can be free or bound, which is fundamental for understanding how functions work. Let’s break down what that means.

Definition of Free Variables

A variable is free if it’s not restricted by any function (λ-abstraction). In simpler terms, a free variable is like an independent traveler — it’s not tied to any specific function.

Formal Definition

The set of free variables of a λ-term $M$, denoted as $FV(M)$, is defined inductively:

1. For a variable:

   $$FV(x)=\{x\}$$

   This means that the variable $x$ is free when it stands alone.

2. For an application:

   $$FV(MN)=FV(M)\cup FV(N)$$

   The free variables of an application are the union of the free variables in both $M$ and $N$.

3. For an abstraction:

   $$FV(\lambda x.M)=FV(M)\setminus \{x\}$$

   Here, the variable $x$ becomes bound by the λ, so it’s no longer free within $M$.

Definition of Bound Variables

A variable is bound if it falls under the scope of a λ-abstraction. It’s like a worker bound to a contract — they can’t act freely outside the company’s rules.

• A variable $x$ in $M$ is bound if it appears after $\lambda x$.
• If it’s not bound, it’s considered free.

Example:

• Bound Variable: In $\lambda x.(x+y)$, the variable $x$ is bound because it’s declared inside the λ.
• Free Variable: The variable $y$ is free because it’s not tied to any λ-abstraction.

Examples to Illustrate Free and Bound Variables

Example 1: Simple Abstraction

• Lambda Calculus: $\lambda x.x$
• Free Variables: $FV(\lambda x.x)=FV(x)\setminus \{x\}=\mathrm{\varnothing }$
• Python Equivalent:

  identity = lambda x: x
  print(identity(5))  # Output: 5
  

Here, x is bound inside the lambda function.

Example 2: Mixed Free and Bound Variables

• Lambda Calculus: $\lambda x.(x+y)$
• Free Variables: $FV(\lambda x.(x+y))=FV(x+y)\setminus \{x\}=\{y\}$
• Python Equivalent:

  y = 10  # Free variable
  add_y = lambda x: x + y  # x is bound, y is free
  print(add_y(5))  # Output: 15
  

Example 3: Nested Abstraction

• Lambda Calculus: $\lambda x.(\lambda y.(x+y+z))$

• Free Variables:

  $$FV(\lambda x.(\lambda y.(x+y+z)))=FV(\lambda y.(x+y+z))\setminus \{x\}$$

  Breaking it down:

  • $FV(\lambda y.(x+y+z))=\{x,z\}$
  • Removing $x$: $\{z\}$

• Python Equivalent:

  z = 3  # Free variable
  func = lambda x: (lambda y: x + y + z)  # x and y are bound, z is free
  print(func(2)(4))  # Output: 9
  

Closed λ-terms (Combinators)

A λ-term is closed if it has no free variables. These are also known as combinators.

Definition:

The set of all closed λ-terms is denoted by ${\mathrm{\Lambda }}_0$.

Example:

• Closed Term: $\lambda x.x$ (no free variables)

• Not Closed: $\lambda x.(x+y)$ (free variable $y$)

• Python Equivalent (Closed Term):

  identity = lambda x: x  # Closed, no external variables
  print(identity(100))  # Output: 100
  

• Python Equivalent (Not Closed):

  y = 50  # Free variable
  add_y = lambda x: x + y  # Not closed
  print(add_y(20))  # Output: 70
  

Standard Combinators

In Lambda Calculus, combinators are special λ-terms with no free variables — they’re entirely self-contained. These combinators act as the foundational "building blocks" for constructing complex expressions. The three most important combinators are:

1. Identity Combinator (I)
2. Constant Combinator (K)
3. Substitution Combinator (S)

Let’s break down each of these with detailed explanations and Python equivalents.

1. Identity Combinator (I)

Definition:

The Identity Combinator simply returns whatever you give it. It’s like holding up a mirror — the output is exactly the same as the input.

Step-by-Step:

• Applying $I$ to any value $A$:$$IA=(\lambda x.x)A\to A$$
• In other words, $I$ does nothing special — it just returns the argument unchanged.

Python Equivalent:

# Identity function
I = lambda x: x
print(I(42))       # Output: 42
print(I("Lambda")) # Output: Lambda

• Explanation: Here, I takes an input (42 or "Lambda") and simply returns it without modification.

2. Constant Combinator (K)

Definition:

or more compactly:

The Constant Combinator takes two arguments but always returns the first one, completely ignoring the second. It’s like asking someone their favorite food, and they always answer "Pizza," no matter what else you offer.

Step-by-Step:

• Applying $K$ to two arguments $A$ and $B$:$$KAB=(\lambda x.\lambda y.x)AB$$
  1. Apply $A$:$$(\lambda y.A)$$
  2. Apply $B$:$$A$$
• No matter what $B$ is, you always get $A$ back.

Python Equivalent:

# Constant combinator
K = lambda x: (lambda y: x)
print(K(10)(20))    # Output: 10
print(K("First")("Second"))  # Output: First

• Explanation: K(10) returns a function that ignores its argument (20 in this case) and always returns 10. The same applies to strings.

3. Substitution Combinator (S)

Definition:

or:

The Substitution Combinator is more complex. It:

1. Applies the same argument $z$ to both functions $x$ and $y$.
2. Then applies the result of $x(z)$ to the result of $y(z)$.

Think of it like:

• Sending the same input ($z$) to two different machines ($x$ and $y$).
• Taking the outputs of both machines and combining them.

Step-by-Step:

• Applying $S$ to $x$, $y$, and $z$:$$Sxyz=(x(z))(y(z))$$
• This means:
  • x(z) must return a function.
  • y(z) provides the input to that function.

Python Equivalent:

# Substitution combinator
S = lambda x: (lambda y: (lambda z: x(z)(y(z))))

# Example functions:
x = lambda z: (lambda w: z + w)  # Returns a function that adds z to w
y = lambda z: z * 2              # Doubles z
z = 5

# Apply the substitution combinator
result = S(x)(y)(z)
print(result)  # Output: 15

How This Works:

1. First Application:

   x(5) → lambda w: 5 + w
   

2. Second Application:

   y(5) → 10
   

3. Final Application:

   (lambda w: 5 + w)(10) → 15
   

• Summary: The input 5 is processed by both x and y, and their results are combined.

Substitution Rules

Substitution is the process of replacing a variable in a λ-term with another term. This is fundamental for reducing and evaluating λ-expressions.

Formal Substitution Notation:

• This means: “Substitute $N$ for $x$ in $M$.”

Substitution Rules:

1. Direct Substitution:

   $$[N/x]x=N$$
   • Replace $x$ with $N$ directly.

2. Irrelevant Variable:

   $$[N/x]a=a\text{(if }a\ne x\text{)}$$
   • If $a$ is not $x$, leave it unchanged.

3. Application Rule:

   $$[N/x](PQ)=([N/x]P)([N/x]Q)$$
   • Apply substitution to both $P$ and $Q$.

4. Abstraction (Bound Variable is the Same):

   $$[N/x](\lambda x.P)=\lambda x.P$$
   • No substitution occurs because $x$ is bound in $\lambda x.P$.

5. Abstraction (Bound Variable is Different):

   $$[N/x](\lambda y.P)=\lambda y.[N/x]P\text{if }y\ne x$$
   • Apply substitution inside the abstraction if it doesn’t bind $x$.

Example: Substitution in Action

Lambda Calculus Example

Substitute $y$ for $x$ in:

• Why no change?
  $x$ is bound by the λ, so the substitution does not affect it.

Python Equivalent:

# Bound variable: substitution doesn't affect 'x'
z = 5
func = lambda x: x + z  # x is bound inside the lambda
print(func(10))         # Output: 15

Substitution with Free Variables

Now, substituting outside the scope:

Python Equivalent:

# Free variable: substitution affects 'x'
x = 7  # Free variable
expr = lambda y: x + y  # 'x' is free here
print(expr(3))          # Output: 10

• Explanation: Here, x is a free variable, so changing it affects the result.

Final Thoughts

1. Identity Combinator (I): Returns its argument unchanged.

   • Python: lambda x: x

2. Constant Combinator (K): Always returns the first argument, ignoring the second.

   • Python: lambda x: (lambda y: x)

3. Substitution Combinator (S): Applies the same argument to two functions and combines the results.

   • Python: lambda x: (lambda y: (lambda z: x(z)(y(z))))

Key Concepts:

• Free Variables: Like global variables in programming — accessible anywhere.
• Bound Variables: Like local variables — limited to specific scopes (inside functions).
• Closed Terms (Combinators): Functions without free variables — completely self-contained.
• Substitution: The process of replacing variables to simplify or evaluate expressions.

This foundation prepares you for more advanced topics like α-conversion (renaming variables) and β-reduction (applying functions). 🚀