Lambda Calculus Concepts in Python

1. Basic Lambda Functions

In lambda calculus, a simple function like λa. a + 10 can be written in Python as:

# λa. a + 10
def x1(a):
    return a + 10

print(x1(5))  # Output: 15

Multiple arguments:

# λa, b. a * b
def x2(a, b):
    return a * b

print(x2(5, 6))  # Output: 30

# λa, b, c. a + b + c
def x3(a, b, c):
    return a + b + c

print(x3(5, 6, 2))  # Output: 13

2. Closures and Higher-Order Functions

Lambda calculus allows functions to return other functions. In Python:

# myfunc = λn. (λa. a * n)
def myfunc(n):
    def inner(a):
        return a * n
    return inner

mydoubler = myfunc(2)
print(mydoubler(11))  # Output: 22

With debug prints to see values inside the closure:

def myfunc(n):
    def inner(a):
        print("a =", a)
        print("n =", n)
        return a * n
    return inner

mydoubler = myfunc(2)
print(mydoubler(11))  # Output: 22

3. Function Wrappers

Applying a function to another function:

def f(x):
    return x + 1

def wrapper(x):
    return f(x)

wrapper = f  # simple reference
print(wrapper(5))  # Output: 6

4. Nested Functions and Shadowing

Demonstrating variable scope and shadowing:

def outer(x):
    def inner(x):
        print(x)
        return x + 1
    return inner(x)
    
print(outer(10))
# Output:
# 10
# 11

Notice how x inside inner shadows x in outer. This is similar to variable binding in lambda calculus.

5. Beta Reduction in Python

Beta reduction (β-reduction) is the process of applying a function to an argument, replacing the bound variable with the argument.

def beta_reduce(abstraction, argument):
    """
    Simulates a beta-reduction step.
    abstraction: λv. body (Python function)
    argument: value to substitute
    """
    return abstraction(argument)

# Identity function I ≡ λx. x
I = lambda x: x
B = "Hello World"
result1 = beta_reduce(I, B)
print(result1)  # Output: Hello World

# Constant function K ≡ λx.λy. x
K = lambda x: lambda y: x
val_a = "Keep Me"
val_b = "Discard Me"
step1 = beta_reduce(K, val_a)    # returns λy. val_a
result2 = beta_reduce(step1, val_b)  # substitutes y with val_b, returns val_a
print(result2)  # Output: Keep Me

This demonstrates the exact same concept as lambda calculus: (λv. A) B → A[v := B].