A lambda expression always follows this pattern:
λ input . output
✔ Whatever appears immediately after λ and before the dot is the input.
✔ Whatever appears after the dot is the output.
λx.x
Input: x
Output: x
λx.xy
Input: x
Output: xy
Some lambda expressions return another function. For example:
λx.λy.x
✔ The outer function takes x as input and returns λy.x.
✔ The inner function takes y as input and always returns x.
✔ No application happens inside; it simply returns a function.
When you apply one lambda expression to another, you substitute the input.
(λx.x)(λx.x)
✔ The first part is the identity function.
✔ Applying it to λx.x simply returns λx.x.
Many parentheses in lambda calculus are optional. Here are the simplifications you confirmed:
(λx.(xy)) → λx.xy
((λy.y)(λx.xy)) → λy.y λx.xy
((λx.xy)(λx.xy)) → λx.xy λx.xy
(λx.(λy.x)) → λx.λy.x
(λx.(λy.(λz.((xz)(yz))))) → λx.λy.λz.(xz)(yz)
✔ Parentheses around the whole expression are optional.
✔ Parentheses around the body are removed unless needed to preserve meaning.
✔ Application associates to the left, so (xz)(yz) must keep one pair of parentheses.
✔ Lambda calculus treats functions as values. ✔ This is similar to passing function pointers or callbacks in C. ✔ You can pass a function to another function exactly like a callback.