Functional Programming

topics to cover
Imperative
Functional
Pure function, impure function
Recursive function
Higher order function
Currying
Free and bound variable
Name and value
Applicative order Normal order
Call by name - call by value - call by need
Session and script
Combination function
Advantages of functional programming
Alpha and Beta reduction

Functional Programming 1
 ✅ What is Functional Programming?
Functional Programming (FP) is a programming paradigm where:
Programs are built using pure functions, avoiding shared state and side
effects, and treating functions as first-class citizens.

📌 Simple Definition (2–3 marks answer)

Functional Programming is a style of programming in which:
Computation is done using functions
Functions are pure
Data is immutable
No side effects occur

🧠 Core Characteristics
1️⃣ Pure Functions
A function is pure if:
Same input → Same output
No side effects (no changing global variables, no printing, no file writing)
Example:

f(x) = x + 2

2️⃣ Immutability
Variables do not change after creation.
Imperative:

x = 5
x = 10 ❌ (state changed)
Functional:

Functional Programming 2
 x = 5
y = 10 ✅ (new value)
3️⃣ First-Class Functions
Functions can:
Be assigned to variables
Be passed as arguments
Be returned from other functions

4️⃣ Higher Order Functions

A function that:
Takes another function as input OR
Returns a function
Examples:
map()
filter()
reduce()

⚔ Imperative vs Functional (5 Mark

Question)
Imperative Programming Functional Programming
Uses statements Uses expressions
Mutable variables Immutable variables
Uses loops Uses recursion
State changes No side effects
Focus on "how" Focus on "what"

🎯 Why Functional Programming Matters?

Functional Programming 3
 Easier reasoning about code
Better for parallel programming
Fewer bugs due to no side effects
Cleaner and modular code

📝 5 Mark Exam Answer (Ready to Write)

Functional Programming is a programming paradigm in which computation is
treated as evaluation of mathematical functions. It avoids changing state and
mutable data. In functional programming, functions are pure, meaning they
produce the same output for the same input and do not cause side effects.
Functions are first-class citizens and higher-order functions are commonly
used. It promotes immutability, recursion instead of loops, and declarative style
of programming.

✅ Pure vs Impure Functions

🔹 1️⃣ Pure Function
A function is pure if:
1. ✅ Same input → Same output
2. ✅ No side effects
3. ✅ Does NOT modify external state

📌 Example of Pure Function

def add(a, b):
return a + b

Why is this pure?

If you call add(2,3) → always returns 5

It does not change any global variable

It does not print, read files, or modify anything outside

🔹2️⃣
Functional Programming 4
 🔹 2️⃣ Impure Function
A function is impure if:
1. ❌ Output depends on external state
2. ❌ It modifies something outside
3. ❌ It has side effects

📌 Example 1: Uses Global Variable

x = 10

def add_to_x(y):
return x + y

Why impure?
If x changes, output changes.
Depends on external variable.

📌 Example 2: Side Effect

def greet(name):
print("Hello", name)

Why impure?
It prints (side effect)
Does not just compute and return

🔥 What are Side Effects?

A side effect is:
Modifying global variable
Writing to file
Printing to console

Functional Programming 5
 Updating database
Changing input data

⚔ Pure vs Impure (Comparison Table)

Pure Function Impure Function
Same input → Same output Output may change
No side effects Has side effects
No global state used Uses or modifies external state
Easy to test Harder to test
Safe for parallel execution Risky in parallel programs

🧠 Why Pure Functions Are Important in

FP?
Because they:
Make programs predictable
Easier debugging
Support parallelism
Improve code reliability

📝 5 Mark Exam Answer (Ready to Write)

A pure function is a function that always produces the same output for the
same input and does not cause any side effects. It does not modify global
variables or external data. An impure function, on the other hand, may depend
on external state or modify data outside the function. Pure functions are easier
to test and reason about, whereas impure functions may produce unpredictable
behavior due to side effects.

✅ 1️⃣ First-Class Functions

Functional Programming 6
 A language supports first-class functions if functions are treated like normal
values.
That means functions can:
1. ✅ Be assigned to variables
2. ✅ Be passed as arguments
3. ✅ Be returned from other functions
4. ✅ Be stored in data structures

📌 Example (Python)
✔ Assigned to Variable
def greet(name):
return "Hello " + name

x = greet
print(x("Harsh"))

Here, greet is stored in variable x .

✔ Passed as Argument
def square(x):
return x * x

def apply_function(f, value):

return f(value)

print(apply_function(square, 5))

We passed function square as parameter.

✔ Returned from Function

def outer():
def inner():

Functional Programming 7
 return "Inside"
return inner

📌 Definition (Exam Ready)

A function is called a first-class function if it can be treated as a value, meaning
it can be assigned to variables, passed as arguments, and returned from other
functions.

✅ 2️⃣ Higher-Order Functions (HOF)

A Higher-Order Function is a function that:
Takes another function as input
OR
Returns a function

📌 Example 1: Takes Function as Argument

def square(x):
return x * x

def apply(f, x):

return f(x)

apply() is higher-order because it takes function f .

📌 Example 2: Returns a Function

def multiplier(n):
def multiply(x):
return x * n
return multiply

📌
Functional Programming 8
 📌 Built-in HOFs in Python
map()

filter()

reduce()

Example:

numbers = [1,2,3,4]
result = list(map(lambda x: x*2, numbers))

🔥 Important Difference
First-Class Function Higher-Order Function
Property of language Type of function
Functions treated as values Function that takes/returns function
👉 First-class is a feature
👉 Higher-order is a result of that feature
🧠 Why Important in Functional
Programming?
Because FP relies heavily on:
Abstraction
Code reuse
Composition
Currying

📝 5 Mark Exam Answer (Perfect to Write)

A language supports first-class functions if functions are treated as values.
They can be assigned to variables, passed as arguments, and returned from
other functions. A higher-order function is a function that either takes another

Functional Programming 9
 function as an argument or returns a function. Higher-order functions are
possible because functions are first-class citizens in functional programming
languages.

✅ What is a Recursive Function?

A recursive function is a function that calls itself to solve a smaller part of the
same problem.

📌 Simple Definition (2–3 Marks)

A recursive function is a function that calls itself during its execution until a
base condition is satisfied.

🧠 Two Important Parts of Recursion

Every recursive function must have:

1️⃣ Base Case

Stops the recursion.

2️⃣ Recursive Case

Function calls itself with smaller input.
Without base case → infinite recursion ❌
📌 Example: Factorial
[
n! = n × (n-1)!
]

Python Example:
def factorial(n):
if n == 0: # Base case
return 1

Functional Programming 10
 else:
return n * factorial(n-1) # Recursive call

How It Works:
If we call:

factorial(3)

It becomes:

3 * factorial(2)
2 * factorial(1)
1 * factorial(0)

Base case:

factorial(0) = 1

Then result:

3 × 2 × 1 × 1 = 6

🔥 Why Recursion is Important in

Functional Programming?
Because:
Functional programming avoids loops.
Uses recursion instead of iteration.
Works naturally with mathematical definitions.
Supports immutable data.

⚔ Recursion vs Iteration
Functional Programming 11
 Recursion Iteration
Function calls itself Uses loops
Needs base case Needs loop condition
Common in FP Common in imperative programming

📝 5 Mark Exam Answer (Ready to Write)

A recursive function is a function that calls itself to solve a smaller instance of
the same problem. It consists of a base case that terminates the recursion and
a recursive case that reduces the problem size. Recursion is widely used in
functional programming because it replaces loops and follows mathematical
definitions of computation.

✅ What is Currying?
Currying is the process of converting a function that takes multiple arguments
into a sequence of functions, each taking one argument.

📌 Simple Definition (2–3 Marks)

Currying is a technique in functional programming where a function with
multiple arguments is transformed into a chain of functions, each taking a
single argument.

🔹 Normal Function (Uncurried)

Example:

f (x, y) = x + y

This function takes two arguments at once.

🔹 Curried Version
f (x)(y) = x + y

Functional Programming 12
 Here:
First function takes x

Returns another function that takes y

🧠 Step-by-Step Understanding
Instead of:

add(2,3)

We do:

add(2)(3)

First:

add(2)

returns a new function:

λy. 2 + y

Then:

(λy. 2 + y)(3) = 5

📌 Example in Python
def add(x):
def add_y(y):
return x + y
return add_y

result = add(2)(3)
print(result)

Functional Programming 13
 🔥 Why Currying is Important?
Helps in partial application
Increases modularity
Makes function composition easier
Very common in Lambda Calculus

📌 Partial Application
Example:

add5 = add(5)

Now:

add5(3) = 8
add5(10) = 15

We fixed one argument in advance.

⚠ Currying vs Normal Function

Normal Function Curried Function
f(x, y) f(x)(y)
Takes all arguments together Takes one argument at a time
Less flexible More reusable

📝 5 Mark Exam Answer (Ready to Write)

Currying is a technique in functional programming where a function that takes
multiple arguments is transformed into a sequence of functions, each taking a
single argument. For example, a function f(x, y) can be written in curried form
as f(x)(y). Currying allows partial application and improves modularity of

Functional Programming 14
 programs. It is widely used in lambda calculus and functional programming
languages.

✅ Free and Bound Variables (Lambda

Calculus)
In Lambda Calculus, variables inside expressions can be:
🔒 Bound Variables
🔓 Free Variables
🔒 1️⃣ Bound Variable
A variable is bound if it is declared inside a lambda abstraction.
👉 It is controlled by a λ .

📌 Example 1
λx.x + 1

Here:
x is bound
Because it is declared after λ

📌 Example 2
λx.λy.x + y

Here:
x is bound (by first λ)
y is bound (by second λ)
No free variables here.

Functional Programming 15
 🔓 2️⃣ Free Variable
A variable is free if it is NOT declared inside a lambda abstraction.
It has no λ binding it.

📌 Example 3
λx.x + y

Here:
x → Bound

y → Free (because no λy exists)

🧠
👉
Important Rule
A variable is bound if it appears inside its corresponding λ scope.
👉 If no λ binds it → it is free.
🔍 Example with Nested Scope
λx.(λy.x + y + z)

Now identify:
x → Bound (by outer λ)

y → Bound (by inner λ)

z → Free

📌 What is Scope?
The scope of a bound variable extends to the body of its lambda expression.
Example:

λx.(x + (λy.y + x))

Functional Programming 16
 x is bound in entire body
y is bound only inside (λy. y + x)

🔥 Why This Is Important?

Because:
Needed for beta reduction
Needed to avoid variable capture
Important for alpha renaming

🔄 Alpha Conversion Reminder

We can rename bound variables.

λx.x → λy.y

This is allowed because x is bound.

But you cannot rename free variables randomly.

📝 5 Mark Exam Answer (Perfect to Write)

In lambda calculus, a bound variable is a variable that is declared within a
lambda abstraction and whose scope is limited to the body of that abstraction.
A free variable is a variable that appears in an expression but is not bound by
any lambda abstraction. For example, in the expression λx. x + y, x is a bound
variable while y is a free variable.

✅ What is “Value”?
A value is a final evaluated result.
Examples:
5

True

Functional Programming 17
 "Hello"

λx. x+1 (a lambda expression is also a value in FP)

👉 A value does NOT need further evaluation.
✅ What is “Name”?
In evaluation strategies, Name refers to passing an expression without
evaluating it first.
This comes from:
Call by Name
Call by Value

🔥
👉
Call by Value (CBV)
Argument is evaluated first
👉 Then passed to function
Example
(λx.x + 1)(2 + 3)

Step 1:
Evaluate argument first:

2+3=5

Step 2:
(\lambda x. x + 1) 5
Result:

✔ This is Call by Value

Functional Programming 18
 🔥
👉
Call by Name (CBN)
Argument is NOT evaluated first
👉 Expression is substituted directly
Same example:

(λx.x + 1)(2 + 3)

Step:
Substitute directly:

(2 + 3) + 1

Then evaluate:

🧠 Key Difference
Call by Value Call by Name
Evaluate argument first Do not evaluate first
Faster May recompute
Used in Python, Java Used in lazy languages
Strict evaluation Non-strict evaluation

🔥 Important Exam Concept

Consider:

(λx.5)(inf initel oop)​

Call by Value:
First evaluate infinite_loop

Program never finishes ❌

Functional Programming 19
 Call by Name:
Substitute directly
Since x is never used
Result = 5 ✅
This shows:
👉 Call by Name can terminate even when Call by Value does not.
📌 In Short (Exam Ready Answer)
Call by Value is an evaluation strategy where the argument to a function is
evaluated before being passed to the function. Call by Name is a strategy
where the argument is not evaluated before substitution; instead, the
expression is directly substituted into the function body and evaluated only
when needed.

✅ Normal Order vs Applicative Order

These are two evaluation strategies used to reduce lambda expressions.

🔹
👉
1️⃣ Normal Order Evaluation
Also called Call by Name
👉 Evaluate the leftmost outermost expression first
👉 Do NOT evaluate arguments unless necessary
📌 Rule:
Reduce the outer function first, before evaluating arguments.

Example
(λx.5) ((λy.y + 1) 3)

Normal Order Steps:

Step 1: Apply outer function first

Functional Programming 20
 =5

✔ Argument is ignored because x is not used.

🔹
👉
2️⃣ Applicative Order Evaluation
Also called Call by Value
👉 Evaluate the innermost arguments first
👉 Then apply function
Same Example
(λx.5) ((λy.y + 1) 3)

Applicative Order Steps:

Step 1: Evaluate argument first

(λy.y + 1) 3 = 4

Step 2:

(λx.5) 4 = 5

Result = 5

🔥 The Big Difference (Important)

Consider:

(λx.5) (∞)

Where ∞ means infinite loop.

Applicative Order:
Try to evaluate infinite loop first ❌
Never terminates

Functional Programming 21
 Normal Order:
Apply outer function first
Result = 5 ✅
Terminates
👉 Normal order always finds a result if one exists.
This is a very important exam line.

⚔ Comparison Table
Normal Order Applicative Order
Leftmost outermost reduction Innermost first
Arguments evaluated only if needed Arguments evaluated first
Corresponds to Call by Name Corresponds to Call by Value
May be slower Usually faster
Guaranteed to find normal form if exists May not terminate

🧠 Memory Trick
Normal → "Outer first"
Applicative → "Argument first"

📝 5 Mark Exam Answer (Ready to Write)

Normal order evaluation reduces the leftmost outermost lambda expression
first and evaluates arguments only when necessary. Applicative order
evaluation reduces the innermost expressions first by evaluating arguments
before applying the function. Normal order is guaranteed to find a normal form
if one exists, whereas applicative order may not terminate if the argument does
not evaluate.

✅
👉
1️⃣ Call by Value (CBV)
Argument is evaluated first

Functional Programming 22
 👉 Then passed to the function
Evaluation Style:
Strict / Eager evaluation

📌 Example
(λx.x + 1) (2 + 3)

Step 1:
Evaluate argument:

2+3=5

Step 2:

(λx.x + 1) 5 = 6

✔ Used in:
Python
Java
C
Most imperative languages

✅
👉
2️⃣ Call by Name (CBN)
Argument is NOT evaluated first
👉 Expression is substituted directly
👉 Evaluated only when needed
Same Example
(λx.x + 1) (2 + 3)

Step 1:
Substitute directly:

Functional Programming 23
 (2 + 3) + 1

Step 2:

⚠ Important
If argument is used multiple times → it is recomputed multiple times.
Example:

(λx.x + x) (2 + 3)

Call by Name:

(2 + 3) + (2 + 3)

Computed twice.

✅
👉
3️⃣ Call by Need (Lazy Evaluation)
Like Call by Name
BUT
👉 Argument is evaluated only once
👉 Result is stored (memoized)
This avoids repeated computation.

Same Example
(λx.x + x) (2 + 3)

Call by Need:
Step 1:
Store result of (2+3) = 5
Step 2:

5 + 5 = 10

Functional Programming 24
 ✔ Computed only once.
🔥 Infinite Loop Example (Very Important
for Exam)
(λx.5) (∞)

Call by Value:
Evaluate ∞ first ❌
Never terminates

Call by Name:
Substitute directly
Since x not used → result = 5 ✅
Call by Need:
Same as Call by Name
Also returns 5 ✅
⚔ Comparison Table (Very Important)
Feature Call by Value Call by Name Call by Need
Argument evaluated first? Yes No No
Re-computation possible? No Yes No
Stores result? Yes No Yes
Efficient? Usually Can be slow More efficient
Used in Python, Java Theoretical model Haskell

🧠 Simple Memory Trick

Value → Evaluate first
Name → Substitute expression

Functional Programming 25
 Need → Lazy + remember result

📝 10 Mark Exam Answer (Ready to Write)

Call by Value is an evaluation strategy in which function arguments are
evaluated before the function is applied. Call by Name substitutes the argument
expression directly into the function body without evaluating it first, and it is
evaluated only when required. Call by Need is an optimized version of Call by
Name where the argument is evaluated only once and the result is stored to
avoid repeated computation. Call by Value is strict evaluation, while Call by
Name and Call by Need are non-strict evaluation strategies.

✅ 1️⃣ Session (Interactive Mode)

A session means running code interactively, one command at a time.
👉 You type a statement
👉 It executes immediately
👉 You see output instantly
📌 Example (Python Interactive Mode)
>>> 2 + 3
5
>>> x = 10
>>> x * 2
20

This is called a REPL session

(REPL = Read → Evaluate → Print → Loop)

🔹 Characteristics of Session
Executes line by line
Immediate output
Good for testing

Functional Programming 26
 Temporary (variables lost when session ends)

✅ 2️⃣ Script (Program File Mode)

A script is a file containing multiple lines of code that is executed all at once.
Example file: [Link]

x = 10
y = 20
print(x + y)

When you run:

python [Link]

Entire file executes.

🔹 Characteristics of Script
Written in file
Executed as a whole
Permanent storage
Used for real applications

⚔ Session vs Script (Comparison Table)

Session Script
Interactive File-based
One command at a time Full program
Temporary Saved permanently
Used for testing Used for development
REPL .py file execution

Functional Programming 27
 🧠 Why This Matters in Functional
Programming?
In FP learning:
Session is used to test lambda expressions
Script is used to implement functional programs

📝 5 Mark Exam Answer (Ready to Write)

A session refers to interactive execution of code where statements are
executed line by line and results are displayed immediately. It is commonly
used for testing and experimentation. A script refers to a file containing multiple
lines of code that are executed together as a program. Scripts are used for
developing complete applications, while sessions are mainly used for quick
testing and debugging.

✅ What is a Combination Function

(Combinator)?
A combinator is:
A lambda expression with no free variables.
That means:
Every variable inside it is bound
It depends only on its arguments

📌 Simple Definition (2–3 Marks)

A combinator is a lambda expression that contains no free variables. All
variables in the expression are bound by lambda abstraction.

🔹 Example of a Combinator
λx.x

Functional Programming 28
 ✔ is bound
x

✔ No free variables
👉 This is a combinator
🔹 Example NOT a Combinator
λx.x + y

Here:
x is bound
y is free ❌
👉 So this is NOT a combinator.
🔥 Important Combinators (Very Common
in Exam)
1️⃣ Identity Combinator (I)
I = λx.x

It returns whatever is given.

2️⃣ K Combinator
K = λx.λy.x

It ignores second argument.

Example:

K 5 10 = 5

3️⃣ S Combinator
Functional Programming 29
 S = λx.λy.λ[Link](yz)

Used in combinatory logic.

🔥 Why Combinators Are Important?

Because:
They remove the need for named variables
Basis of combinatory logic
Used to build computation without free variables

🧠
👉
Important Fact
A program written only using combinators has:
No free variables
No external dependency

⚔ Combinator vs Normal Lambda

Expression
Combinator Normal Lambda Expression
No free variables May have free variables
Self-contained May depend on outside values
Fully bound Not fully bound

📝 5 Mark Exam Answer (Ready to Write)

A combinator is a lambda expression that contains no free variables. All
variables in the expression are bound by lambda abstraction. Examples of
combinators include the identity combinator I = λx.x and the K combinator K =
λx.λy.x. Combinators are important in functional programming because they
allow computation without free variables.

Functional Programming 30
 ✅ Advantages of Functional
Programming
Functional Programming (FP) has several advantages due to pure functions and
immutability.

1️⃣ Predictability
Because of pure functions:
Same input → Same output
No hidden state
No side effects
👉 Makes programs easy to understand and debug.
2️⃣ Easier Testing
Pure functions:
Do not depend on global variables
Do not modify external data
So testing becomes simple.
Example:
If f(5) always gives 10 , testing is straightforward.

3️⃣ Better Parallelism

Since there is:
No shared mutable state
No side effects
Functions can run in parallel safely.
👉 Very important advantage in modern multi-core systems.
4️⃣ Code Reusability
Functional Programming 31
 Higher-order functions and small pure functions:
Encourage modular design
Promote reusable components
Support function composition

5️⃣ Reduced Bugs

Immutability prevents:
Accidental data modification
Unexpected state changes
This reduces runtime errors.

6️⃣ Mathematical Foundation

Functional programming is based on:
Lambda Calculus
Mathematical functions
So reasoning about programs becomes easier.

7️⃣ Supports Lazy Evaluation

In some FP languages:
Computation happens only when needed
Improves performance

⚔ Summary Table
Feature Advantage
Pure functions Predictable behavior
Immutability No unexpected state change
Higher-order functions Reusable and modular code
No side effects Easy debugging

Functional Programming 32
 Feature Advantage
Stateless design Safe parallel execution

📝 5 Mark Exam Answer (Ready to Write)

Functional programming offers several advantages such as predictability due to
pure functions, easier testing because there are no side effects, better support
for parallel execution due to immutability, improved modularity through higher-
order functions, and reduced bugs caused by avoiding shared mutable state. It
is based on mathematical principles, which makes reasoning about programs
simpler and more reliable.

✅ Disadvantages of Functional
Programming
Although functional programming has many benefits, it also has some
limitations.

1️⃣ Difficult to Learn

Concepts like lambda calculus, currying, higher-order functions, and lazy
evaluation are abstract.
Beginners from imperative background may find it hard.

2️⃣ Performance Overhead

Excessive recursion can lead to stack overflow.
Creating many small functions may increase memory usage.
Lazy evaluation may consume extra memory.

3️⃣ Hard Debugging in Some Cases

Deep function composition can make stack traces complex.
Understanding flow of execution can be difficult.

4️⃣
Functional Programming 33
 4️⃣ Not Always Efficient for I/O
Functional programming avoids side effects, but:
Real-world applications require input/output.
Managing I/O purely can be complicated.

5️⃣ Limited Library Support (Compared to Imperative)

Some domains (like system programming) are easier in imperative
languages.
Not all problems are naturally functional.

6️⃣ State Management is Tricky

Since:
Variables are immutable
State cannot be changed directly
Modeling changing systems may require extra abstraction.

⚔ Comparison Idea (If Asked in 10 Marks)

You can write:
Functional programming emphasizes immutability and pure functions, which
improves reliability but may increase complexity in handling state and I/O
operations. It may also introduce performance overhead due to recursion and
abstraction.

📝 5 Mark Exam Answer (Ready to Write)

Functional programming has some disadvantages such as difficulty in learning
due to abstract concepts like lambda calculus and currying. It may lead to
performance overhead because of excessive recursion and memory usage.
Debugging complex function compositions can be challenging. Handling
input/output and state management can also be complicated since functional
programming avoids side effects and mutable data.

Functional Programming 34
 ✅ What is Alpha (α) Reduction?
Alpha reduction means:
Renaming a bound variable in a lambda expression.
It does NOT change the meaning of the function.

📌 Simple Definition (2–3 Marks)

Alpha reduction is the process of renaming bound variables in a lambda
expression without changing its meaning.

🧠 Why Do We Need Alpha Reduction?

To:
Avoid variable capture
Prevent confusion between variables
Prepare for safe beta reduction

🔹 Example 1
λx.x

We can rename x to y :

λy.y

✔ Same meaning
✔ Only variable name changed
🔹 Example 2
λx.λy.x + y

Rename outer x to a :

Functional Programming 35
 λa.λy.a + y

Still same function.

⚠ Important Rule
You can rename only bound variables.
You cannot rename free variables randomly.

🔥 Example of Wrong Renaming

λx.x + y

Here:
x is bound → can rename
y is free → cannot rename
Correct alpha reduction:

λz.z + y

Wrong:

λx.x + z

(You changed free variable ❌)

🔥 Why Alpha Reduction is Important
Before Beta Reduction?
Consider:

(λx.λy.x) y

If we directly substitute:

λy.y

Functional Programming 36
 This changes meaning due to variable capture.
Correct method:
Step 1: Alpha convert inner y

λx.λz.x

Step 2: Now apply beta reduction:

λz.y

✔ Correct result
⚔ Alpha vs Beta
Alpha Reduction Beta Reduction
Renames bound variables Applies function
No computation Substitution happens
Avoids variable capture Performs actual evaluation

📝 5 Mark Exam Answer (Ready to Write)

Alpha reduction is the process of renaming bound variables in a lambda
expression without changing its meaning. It is used to avoid variable capture
during beta reduction. For example, λx.x can be renamed to λy.y. Only bound
variables can be renamed, while free variables must remain unchanged.

✅ What is Beta (β) Reduction?

Beta reduction is the process of applying a lambda function to an argument.
👉 It means:
Substitute the argument into the function body.

📌 Formal Definition (Exam Ready)

Functional Programming 37
 Beta reduction is the process of replacing the bound variable in a lambda
abstraction with the given argument.

🧠 General Rule
(λx.E) A

After β-reduction:

E[x := A]

Meaning: Replace every occurrence of x in E with A .

🔹 Simple Example
(λx.x + 1) 5

Substitute x = 5 :

5+1=6

🔹 Example 2
(λx.x × x) 3

Substitute:

3×3=9

🔥 Example 3 (Important)
(λx.x + x) (2 + 3)

After substitution:

Functional Programming 38
 (2 + 3) + (2 + 3)

Then evaluate:

5 + 5 = 10

🔥 Example 4 (Nested Lambda)

(λx.λy.x + y) 5

Substitute x = 5 :

λy.5 + y

This is the result.

🔥 Example 5 (Very Important)

(λx.x x) (λy.y)

Substitute:

(λy.y) (λy.y)

Then reduce again:

λy.y

⚠ Important Concept: Variable Capture

Before substituting, ensure you do not accidentally bind a free variable.
Sometimes alpha conversion (renaming variables) is needed before beta
reduction.

⚔ Beta vs Alpha vs Eta

Functional Programming 39
 Reduction Meaning
Alpha (α) Renaming bound variables
Beta (β) Function application (substitution)
Eta (η) Removing unnecessary abstraction

📝 5 Mark Exam Answer (Ready to Write)

Beta reduction is the process in lambda calculus where a lambda abstraction is
applied to an argument. It involves substituting the argument for the bound
variable in the function body. For example, (λx. x+1) 5 reduces to 6 by replacing
x with 5. Beta reduction represents function application in lambda calculus.

Functional Programming 40