What is Lambda Calculus?
Lambda calculus is a minimalistic formal system for expressing computation through function abstraction and application. Created by Alonzo Church in the 1930s, it serves as the theoretical foundation for functional programming languages and type systems.
-- Example of a simple lambda expression
-- Function that takes one parameter and returns it unchanged
λx.x
Core Concepts
Syntax
Expressions consist of variables, abstractions (λx.M), and applications (M N).
λx.λy.x y -- A function that takes two parameters and applies x to y
Beta Reduction
Applying a function to an argument and substituting variables.
(λx.x 3) ⇒ 3Alpha Conversion
Renaming bound variables without changing meaning.
λx.x ≡ λy.yExamples & Exercises
Identity
λx.xReturns its input value unchanged. The most basic combinatory function.
Booleans
True = λt.λf.t
False = λt.λf.f
Church encoding of booleans as functions that select the first or second argument.
Try It Yourself
Enter a simple lambda expression, and see the reduction steps visualized. This interactive tool helps you understand how functions are applied and simplified.
A Brief History
Formalized by Alonzo Church in 1936 as part of his research into the foundations of mathematics. Church used lambda calculus to formalize the concept of "effectively computable" functions before Turing machines were developed.
"I find it amusing that lambda calculus, which was initially proposed as a tool for analyzing foundational logic problems, has now become a practical framework for modern programming languages."
- Alonzo Church (imaginary tribute)