1. One Simple Language
Lambda Calculus is a very small language.
It has only two main ideas:
• Making a function
• Using a function
Even with just these two ideas, we can describe very powerful programs.
2. Variables
A variable is just a name.
x, y, z, x1, y1 are variables
Variables stand for something, but what they stand for depends on the situation.
Understanding Functions in Baby Steps
Step 1: Variables
A variable is just a name.
x, y, z are variables
A variable does nothing by itself.
It is just a label.
Step 2: What the λ Symbol Means
The symbol λ (lambda) means:
“I am defining a function”
Step 3: Starting a Function
When we write:
λx
This means:
- We are creating a function
- The function will take one input
- The input will be called x
This is not a complete function yet.
Step 4: Completing the Function
When we write:
λx.x
This means:
- Take an input
- Call it x
- Return x
This is a complete function.
Step 5: Using a Function
To use a function, we give it an input.
(λx.x) 5 → 5
The function receives 5 and returns 5.
Step 6: Another Simple Function
Consider:
λx.y
This function:
- Takes an input x
- Ignores it
- Always returns y
Step 7: What to Remember
• x is just a name
• λ starts a function
• λx.x is a full function
• (λx.x) 5 means using the function
3. Lambda Expressions
There are only three kinds of expressions:
- A variable → x
- A function → λx.x
- A function use → (AB)
λx.x means “a function that returns what you give it”
4. Function Application
Applying a function means using it.
(λx.x) 3 → 3
The function takes 3 and gives back 3.
5. Functions Can Return Functions
Some functions return other functions.
λx.(λy.x)
This function:
- Takes x
- Returns a new function
- The new function always returns x
6. Parentheses Rules
To make writing easier:
- Application goes left: ABC = ((AB)C)
- λ applies to everything after it
- λxyz.t means λx.λy.λz.t
7. Meaning (Very Simple)
The meaning of an expression depends on:
λx.x → identity function
λx.y → always returns y
Quiz: Test Yourself (20 Questions)