F29FA Foundations A: Lecture 5 Masterclass

Comprehensive Explanations & Practical Python for Commercial Teaching

1. Alpha Reduction (α): The Art of Renaming

λv.A →α λv'.A[v:=v'] where v' ∉ FV(A) [cite: 305-306]
Imagine you have a recipe that says "Take an apple and peel the apple." If I change it to "Take a pear and peel the pear," the instructions are exactly the same. In Lambda Calculus, we don't care about the name of the variable; we only care about where it goes. Alpha reduction is the rule that allows us to change variable names so they don't get mixed up!
The exam often asks you to reduce terms where variable names clash. You MUST use Alpha reduction to rename a variable if it's already being used nearby[cite: 309].

Python Practical: Function Equivalence

# Even though the argument names differ, the logic is identical.
def process_x(x): return x * 2
def process_y(y): return y * 2

# In Lambda Calculus, process_x and process_y are "alpha-equivalent"
print(f"Are they the same? {process_x(10) == process_y(10)}")

2. Beta Reduction (β): Execution Power

(λv.A)B →β A[v:=B] [cite: 321]
This is the "Play" button on your DVD player. The λv.A is the machine (the player), and B is the disc you put inside. When you press play (Beta-reduction), the machine swallows the disc and starts running the movie. Technically, we take the "B" and plug it into every spot where "v" used to be [cite: 321-323].

Python Practical: Applying Lambdas

# Define a machine that adds 5: λx.x + 5
add_five = lambda x: x + 5

# Perform Beta Reduction with the value 10: (λx.x + 5) 10
# Inside the computer: 10 + 5
result = add_five(10)

print(f"Beta Reduction Result: {result}")

3. Eta Reduction (η): Removing the Middleman

λv.Av →η A (if v is not in A) [cite: 340]
Imagine a worker named "Bob." Bob's only job is to take a package from you and give it to "Alice." Why do we need Bob? We don't! We can just give the package to Alice directly. If a function just takes an input and passes it straight to another function, the first function is useless and can be "Eta-reduced" away[cite: 341].

Python Practical: Wrapper vs Direct Call

import math

# This is the "A" in λv.Av
alice = math.sqrt

# This is the "Bob" (λv.Av) - he just passes x to Alice
bob = lambda x: alice(x)

# Eta Reduction says: Just use Alice!
print(f"Bob's result: {bob(16)}")
print(f"Alice's result: {alice(16)}")

4. Reduction Paths & Transitivity

If A →r B and B →r C, then A ↠r C [cite: 388]
Think of this as a set of stairs. To get to the bottom (the final answer), you have to take one step at a time. The "↠" symbol just means "I took some number of steps to get here." In your exam, you must show EVERY step, underlining the part you are changing each time[cite: 43, 60].
Question 1(h) Alert: You will be asked for "Standard" vs "Non-standard" paths. Standard means reducing the leftmost redex first[cite: 50, 64].

Python Practical: Step-by-Step Logic

# A complex term: (λx.λy.x+y) (2+3) (4+1)
step_0 = lambda x: lambda y: x + y
arg_1 = 2 + 3  # Reduction step in the argument
arg_2 = 4 + 1  # Reduction step in the argument

# The Path
step_1 = step_0(arg_1) # First Beta-reduction
final_result = step_1(arg_2) # Final Beta-reduction

print(f"The path led to: {final_result}")