Lambda Calculus
Lambda calculus is the mathematical foundation of functional programming: only function definition (λx.M) and application (MN), yet Turing-complete.
Purpose
Understand the theoretical foundation and computation model of functional programming.
Mechanism
Three rules: variable x, abstraction λx.M (defining a function), and application MN (calling a function). β-reduction ((λx.M)N → M[x:=N]) is computation. α-conversion renames bound variables. Church encoding represents data with lambdas.
Use cases
- Functional programming
- Theory of computation
- Language foundations