Diff — Lambda calculus

{{infobox

| title = Lambda calculus

| image = lambda-anatomy.svg

| caption = The entire notation: **λx.M** — "a function that takes x and gives M" (our diagram)

| designer = [[Alonzo Church]], Princeton

| appeared = 1932–1936 · typed variant 1940

| also_called = λ-calculus

| kind = the smallest system that can compute anything

| equivalent_to = [[Alan Turing|Turing machines]] — the Church–Turing thesis

| descendants = [[LISP]] → Scheme → ML → Haskell → every `lambda`/`=>`/`fn` since

}}

The **lambda calculus** (λ-calculus) is the smallest programming language that can compute anything — and one of the largest ideas in mathematics. It has exactly **three kinds of expression** and **one rule of computation**. It contains no numbers, no strings, no loops, no `if`, no names for anything — and it is exactly as powerful as every computer ever built. [[Alan Turing]] proved his universal machine equivalent to it; [[LISP]] grew directly out of it; every anonymous function, closure, and `map` you have ever used is its grandchild.

```alb The whole language in one breath

**λx.M** means *"a function that takes x and gives M."* Applying one to an argument — `(λx.M) N` — means *"take M, and wherever it said x, put N."* That is the entire machine. Everything else on this page is what a mind did with those two facts.

```

## The story

### A mathematics in crisis

In 1900, **David Hilbert** stood before the world's mathematicians and set the program for the century: put all of mathematics on complete, consistent, *mechanical* foundations. The dream had teeth — Whitehead and Russell's *Principia Mathematica* had already shown that vast tracts of math could be derived from pure logic, famously taking hundreds of pages to prove that 1 + 1 = 2. By 1928 Hilbert had sharpened the question into the **Entscheidungsproblem**: *does there exist a procedure that can decide, in principle, whether any mathematical statement is provable?*

Then the foundations cracked. **Gödel's incompleteness theorems** (1931) proved no such system could be both consistent and complete. What remained was the sharpest question left standing: what does "a procedure" even *mean*? Nobody could answer it — because nobody had a precise definition of computation itself.

### Princeton, 1932–1936

**[[Alonzo Church]]** — a young Princeton logician of legendary precision, famous for lecturing in a monotone while erasing the blackboard with one hand and writing with the other — had been building a complete logical system of his own since 1932. At its heart was a notation for functions: where everyone else wrote "the function f(x)," Church wrote **λx.f(x)** — the function itself, unmarried from any name.

```fact Why the letter λ?

Church needed a symbol to mark "this is the bound variable." He reportedly picked the Greek letter more or less at whim — he later admitted he chose **λ** because it was easy and distinctive. The most consequential letter in programming was nearly arbitrary.

```

There was a problem. In 1935, his own graduate students — **Stephen Kleene** and **J. Barkley Rosser** — proved his grand logical system inconsistent. The logic died. But a fragment of it — the pure calculus of λ-functions — survived autopsy perfectly intact: consistent, elegant, and quietly *Turing-powerful*.

In April 1936 Church published *"An Unsolvable Problem of Elementary Number Theory"* and answered Hilbert's Entscheidungsproblem: **no**. There is no mechanical procedure that decides all mathematical truth — because he could now define "mechanical procedure" precisely, as **λ-definability**, and exhibit a problem beyond it.

### Two definitions, one machine

Months later, a young Englishman published *"On Computable Numbers"* with a completely different answer-machine: an imaginary device scanning a tape. [[Alan Turing]] then did the extraordinary thing — he **proved his machines and Church's λ-calculus exactly equivalent** in power, packed his bags, and sailed to Princeton to take his PhD under Church himself.

```quote

"Computability by a Turing machine has the advantage of making the identification with effectiveness in the ordinary sense evident immediately."

— Turing, being generous to the machine in the middle of proving the two ideas identical

```

The **Church–Turing thesis** — that "effectively calculable," "λ-definable," and "Turing-machine computable" are the same boundary, seen from three directions — remains the deepest unprovable axiom computing rests on. Every language since, [[FORTRAN]] to Haskell to [[AdaLogic BASIC]], is a costume over one of those two skeletons.

### After the war — the idea grows a body

The λ-calculus sat in logic journals for twenty years while the electronic computers were being born from [[EDVAC report|von Neumann's architecture]]. Then, in 1958, **John McCarthy** needed a notation for reasoning about programs and reached for Church's: **[[LISP]]** carried `lambda` literally into its syntax, and the idea entered living code. From there the family tree never stopped branching:

```chart From lambda to language

terminal  l   "λ-calculus\n1936"

process   lp  "LISP\n1958"

process   sc  "Scheme\n1975"

process   ml  "ML\n1973"

process   hk  "Haskell\n1990"

process   mo  "every modern\nlambda"

l -> lp -> sc

lp -> ml -> hk -> mo

sc -> mo

```

- **1958** — LISP: `lambda` becomes a working keyword; functions become data

- **1970s** — **Scheme** purifies it; **ML** marries it to a real type system

- **1970s–80s** — the **Curry–Howard correspondence** is noticed: types are propositions, programs are proofs — the bridge to modern proof assistants

- **1990** — **Haskell**: a mainstream language that is essentially typed λ-calculus wearing clothes

- **today** — `lambda` in Python, `=>` in JavaScript, closures in everything: the anonymous function is the most-borrowed idea in all of language design

## The whole language in three rules

Here it is — genuinely all of it:

1. **A variable**: `x` — a name that stands for an argument

2. **An abstraction**: `λx.M` — "a function that takes x and gives M" (the λ binds x the way a parameter name is bound in any function)

3. **An application**: `M N` — "feed N to M"

Every λ-term is one of those three. There are no numbers, no booleans, no strings, no built-in operations, no mutation, no printing. And yet: it computes everything.

```tip How to read it

`λx.x` is the identity function — "take x, give back x." `λx.λy.x` is "take x, then take y, give back x." Read the λ-list left to right like nested function headers: `λx.λy.M` is `function(x){ return function(y){ return M } }`.

```

## The one rule of computation

The engine is **β-reduction** — application is substitution:

```

(λx. M) N   →   M with every free x replaced by N

```

That's the entire interpreter:

```

(λx.x) hello      →  hello                     -- identity, applied

(λx.λy.x) a b     →  (λy.a) b  →  a            -- a two-argument selector

(λf.λx.f(f x)) g 5 →  λx.g(g x) applied to 5  →  g(g(5))   -- "twice"

```

```note Free and bound

In `λx.x y`, the `x` is **bound** by the λ (it's the parameter) and `y` is **free** (it comes from outside). Renaming bound variables never changes meaning — `λx.x` and `λq.q` are the *same* function; this renaming is called **α-conversion**. It's the rule that stops `(λx.λy.x) y` from colliding: rename first — `(λx.λz.x) y → λz.y`.

```

Two companion laws round out the system: **α-conversion** (bound names are arbitrary) and **η-conversion** (`λx.f x` *is* just `f` — a wrapper that does nothing is nothing).

### Order doesn't matter — mostly

A term can have many redexes — which do you reduce first? The **Church–Rosser theorem** answers beautifully: it doesn't matter. Reduction paths always rejoin — the calculus is **confluent**. If a term has a **normal form** (a fully-reduced answer), every road leads there.

*Mostly*, because some terms have no answer:

```warn The term that eats itself

`Ω = (λx. x x) (λx. x x)` reduces to *itself* — forever. Evaluation order decides whether you *reach* an answer, never what the answer is. **Normal order** (outermost-first) finds a normal form whenever one exists; **applicative order** (arguments-first, the way nearly every real language calls functions) can fall into Ω on a term that would have normalized. Every language's call-by-value vs. call-by-name debate is this footnote, still being argued.

```

## Building a world from nothing

The magic trick: with only functions, you can *manufacture* everything a language needs. These are the **Church encodings** — data made of pure behavior.

### Booleans — truth as choice

```

TRUE   =  λx.λy. x      -- "take two things, keep the first"

FALSE  =  λx.λy. y      -- "take two things, keep the second"

IF     =  λb.λt.λe. b t e   -- just *apply* the boolean to the branches!

```

`IF TRUE a b` reduces to `a` because TRUE *is* the function that picks its first argument. The boolean doesn't describe a choice — it **is** the choice. That's the calculus's whole aesthetic: *a value is what it does.*

### Numbers — counting as iterating

**Church numerals**: the number *n* is "the function that applies f to x, n times."

```

0  =  λf.λx. x            -- apply f zero times

1  =  λf.λx. f x          -- apply once

2  =  λf.λx. f (f x)      -- twice

3  =  λf.λx. f (f (f x))  -- three times

```

Arithmetic falls out as function composition:

```

SUCC  =  λn.λf.λx. f (n f x)        -- "one more application"

PLUS  =  λm.λn.λf.λx. m f (n f x)   -- "apply f m times, then n times"

MULT  =  λm.λn. m (PLUS n) ZERO-ish -- i.e. m composed n-fold

```

Check `PLUS 1 2` mentally: `λf.λx. 1 f (2 f x)` = apply f once after twice = three times = `3`. Arithmetic by counting applications. It works.

```fact The wisdom-tooth subtraction

**Predecessor** is famously *hard* — decrementing an iterator you can't un-run. Stephen Kleene cracked it (with pairs, counting both n and n−1 forward) — the story goes, **while his wisdom teeth were being extracted**. When Church showed the result to Gödel, Gödel reportedly found it miraculous. Kleene's own verdict: "it was just cleverness."

```

### Pairs and everything else

```

PAIR   =  λa.λb.λp. p a b     -- a pair is "a function that takes a chooser"

FIRST  =  λp. p TRUE          -- feed it the first-picker

SECOND =  λp. p FALSE         -- feed it the second-picker

```

From pairs: lists, trees, records — the entire data-type zoo, built from functions that *behave like* containers.

### Recursion without a name — the Y combinator

Nothing in λ-land can refer to itself by name — there *are* no names. Yet factorial needs recursion. The fix is the most famous one-liner in the field:

```

Y  =  λf. (λx. f (x x)) (λx. f (x x))

```

`Y g` reduces to `g (Y g)` — it hands any function its own fixpoint, recursion bootstrapped from pure self-application. Haskell **Curry** found it; Turing found a twin (`Θ`). Every `letrec`, every recursive `PROCEDURE`, every language's answer to "how does a function call itself" is Y wearing a friendlier mask.

### The cheat sheet

| You want | λ-term | What it is |

|---|---|---|

| identity | `λx.x` | return the argument |

| TRUE | `λx.λy.x` | pick first |

| FALSE | `λx.λy.y` | pick second |

| NOT | `λb.λx.λy. b y x` | pick the *other* |

| AND | `λa.λb. a b FALSE` | if a then b else false |

| pair | `λa.λb.λp. p a b` | a chooser-shaped box |

| *n* | `λf.λx. fⁿ x` | "do f n times" |

| successor | `λn.λf.λx. f (n f x)` | one more application |

| loops forever | `(λx.x x)(λx.x x)` | Ω — no normal form |

| recursion | `λf.(λx.f(x x))(λx.f(x x))` | Y — the fixpoint |

## Then types walk in

In **1940**, Church published the **simply typed λ-calculus** — every term tagged with a type, ill-typed terms forbidden. Two consequences shaped the next eighty years:

- **Strong normalization** — in the simply-typed calculus, *every* well-typed term halts. Ω can't be typed (you can't give `x x` a consistent type), so self-eating is legislated out of existence. Types as a proof of good behavior.

- **Curry–Howard** — noticed gradually (Curry 1958, Howard 1969): **types are logical propositions; programs are proofs.** `A → B` is implication; a function of that type *is* a proof that "A implies B." This isomorphism — computation *is* deduction — is the foundation of modern proof assistants (Coq, Agda, Lean) and the reason "propositions as types" sits at the deepest point where programming and mathematics touch.

From there the tower kept rising: **System F** (Girard, Reynolds — polymorphism, the ancestor of generics everywhere), **System Fω**, **dependent types** — each a λ-calculus with a more expressive type language bolted on.

## Why a working programmer should care

- Every **anonymous function** — Python `lambda`, JavaScript `=>`, C++ `[&]` — is Church's notation in street clothes.

- Every **closure** — a function carrying captured variables — is λ-abstraction plus a scope rule.

- `map`, `filter`, `reduce` — functions as arguments — is application, unabstracted from its ivory tower.

- **Functional programming** is simply the bet that β-reduction is a better programming model than assignment.

- And the languages: LISP begot Scheme and the whole symbolic tradition; the typed branch became ML → Haskell → the type systems eating modern languages (Rust's ownership, TypeScript's shapes) — all of it refinement of Church's two fragments, typed and untyped.

```alb The view from ALB

[[AdaLogic BASIC]] is a procedural language — you write `PROCEDURE`, not `λ`. But the idea underneath is the same one Church found: *a named thing that takes inputs and returns outputs is the atom of all software.* BASIC made that atom friendly; λ-calculus proved it was all you'd ever need.

```

## Try it yourself

1. Reduce `(λx.x) (λy.y)` — what do you get, and what does it mean?

2. Show `IF FALSE a b` → `b`, step by step.

3. What does `(λf.λx.f(f x)) SUCC 0` evaluate to, and why is that `2`?

4. Reduce `Ω` once — convince yourself it loops.

5. (Expert) Sketch why `NOT (NOT TRUE)` returns `TRUE` purely by substitution.

## See also

- [[Alonzo Church]] — the professor behind the λ

- [[Alan Turing]] — the other half of the thesis, and Church's PhD student

- [[LISP]] — the first language to wear the lambda openly

- [[History of Programming]] · [[FORTRAN]] · [[ALGOL]]

- [[Konrad Zuse]] · [[Plankalkül]] — the other person who invented a formal language in wartime obscurity

- [[Analytical Engine]] — computation imagined a century before it could be defined

- [[History of Mathematics]]

- [[History of Science]]

[[Category:Mathematics]]

[[Category:Theory]]

[[Category:Languages]]

[[Category:History]]