Summary of ""Propositions as Types" by Philip Wadler"
High-level summary
- This talk (Philip Wadler) explains the Curry–Howard correspondence: “propositions as types, proofs as programs, normalization as evaluation.”
- Wadler gives historical background (Hilbert’s decision problem, Gödel’s incompleteness, Church’s lambda calculus, Kleene/recursive functions, Turing machines) to motivate the need for formal definitions of “algorithm.” The fact that multiple independent definitions coincide is strong evidence the concept was discovered, not invented.
- Gentzen’s natural deduction (introduction and elimination rules for connectives), the subformula property and normalization (proof simplification) map exactly to constructs and evaluation rules in the simply‑typed lambda calculus.
- Consequences and applications:
- Simply‑typed lambda calculus guarantees termination (no general recursion).
- Dependent types correspond to quantifiers (∀/∃).
- Polymorphism/System F corresponds to generics.
- Modern proof assistants and dependently typed languages (Coq, Agda, etc.) exploit this correspondence.
- Ongoing research connections include linear logic ↔ session types for concurrency.
- Philosophical and practical notes:
- Lambda calculus is a natural, “discovered” foundation for computation and is a better candidate than ad‑hoc programming languages for cross‑civilizational communication, though it’s not literally universal in a metaphysical sense.
- Deep ideas from logic and PL often take decades to be adopted in industry.
Detailed concepts and lessons
Historical motivation
- Historically, an “algorithm” meant a person carrying out instructions; a formal mathematical definition only appeared in the 1930s.
- Hilbert’s Entscheidungsproblem (decision problem): seek an algorithm to decide provability of arbitrary formal statements.
- Gödel (1930s): incompleteness—any sufficiently powerful logic can encode a self‑referential “this is not provable” statement, undermining Hilbert’s program.
- Church (λ‑calculus), Kleene (general recursive functions), and Turing (Turing machines) independently formalized effective computability; these definitions are equivalent in the Church–Turing thesis sense.
- Turing’s model provided a convincing philosophical account: a person following mechanical rules can be modeled by a Turing machine.
Natural deduction (Gentzen) — structure of rules
- Rules come in introduction (I) and elimination (E) pairs for each connective.
- Examples (informal):
- Implication (A → B)
- →I: assume A, derive B, then discharge the assumption to conclude A → B.
- →E (modus ponens): from A → B and A infer B.
- Conjunction (A ∧ B)
- ∧I: from A and B derive A ∧ B.
- ∧E: from A ∧ B derive A (or B).
- Implication (A → B)
- Gentzen’s subformula property and normalization:
- Proofs can be simplified by canceling an introduction immediately followed by an elimination of the same connective.
- Normalization yields proofs containing only subformulas of the hypotheses and conclusion.
- This gives a simple argument for consistency: a proof of false would normalize to a proof made only of subformulas of false, which is impossible.
Lambda calculus and types (Church)
- Simply‑typed lambda calculus:
- Terms: variables, λ‑abstractions, application; types: function types A → B, pair types A × B, etc.
- Evaluation rules correspond to proof simplification:
- Beta reduction: (λx. N) M → N[x := M].
- Pair projections: fst (M, N) → M; snd (M, N) → N.
- Subject reduction: typed terms remain well‑typed during evaluation.
- Strong normalization: in the simply‑typed setting without general recursion/fix, all evaluation sequences terminate.
Curry–Howard correspondence (key mapping)
- Core mapping:
- Proposition ↔ Type
- Proof ↔ Program (term)
- Proof normalization ↔ Program evaluation (reduction)
Extensions: - Quantifiers ↔ Dependent types (∀, ∃ ↔ dependent product and sum types) - Polymorphism/System F ↔ generics / polymorphic types - Linear logic ↔ session types / models for concurrency and resource usage
- Practical consequences:
- Proof assistants and dependently typed languages (Coq, Agda) let you write proofs as programs and extract verified programs from proofs.
- The correspondence’s independent rediscovery across communities strengthens the view that these structures are discovered rather than arbitrary inventions.
Examples and pedagogical points
- Wadler walks through a small natural‑deduction proof using ∧I, ∧E, →I, →E and shows the corresponding lambda term and reduction steps (for example, a pair swap function).
- Normalization (replacing introduced connectives that are immediately eliminated) corresponds exactly to β‑reduction simplifying lambda terms.
Broader implications & open directions
- Curry–Howard recurs across logic, type theory, programming languages, and proof systems—many language features were discovered independently in logic and CS.
- Industrial adoption can be slow; good ideas (e.g., garbage collection, generics) often take decades to reach mainstream industry.
- Current research: relating concurrency/distribution to logic. Linear logic and session types are promising for principled models of concurrency.
- Philosophical/outreach notes: lambda calculus abstracts computation in a way that makes it a strong candidate for universal communication of computation, but asserting absolute universality requires philosophical caveats.
Methodology — rules and stepwise procedures
Natural deduction rules (usage and simplification)
- Implication (A → B)
- →I: to prove A → B, temporarily assume A, derive B, then discharge the assumption to form A → B.
- →E: from A → B and A derive B (modus ponens).
- Simplification: when →I is immediately followed by →E for the same assumption, substitute the proof of A for occurrences of that assumption in the B‑derivation to remove the intermediate A → B step.
- Conjunction (A ∧ B)
- ∧I: from proofs of A and B derive A ∧ B.
- ∧E: from A ∧ B derive A (or B).
- Simplification: forming A ∧ B and immediately extracting a component can be replaced by the direct proof of that component.
- Generic normalization process:
- Identify adjacent introduction/elimination pairs for the same connective.
- Replace the eliminated introduction by substitution of the concrete proof/term for the discharged assumption (cut elimination idea).
- Repeat until no such pairs remain — the result satisfies the subformula property.
Corresponding lambda‑calculus evaluation steps
- Beta reduction: (λx. N) M → N[x := M].
- Pair projection: fst (M, N) → M ; snd (M, N) → N.
- Subject reduction: evaluation preserves types.
- Termination (simply‑typed, no general recursion): all evaluation sequences terminate (strong normalization).
Applications and takeaways
- Use types to get guarantees: typing disciplines, especially dependent types, let you encode specifications so properties (termination, correctness) hold by construction.
- Curry–Howard offers a principled route to executable, certified programs—foundational for proof assistants and verified software.
- Many language features (polymorphism, algebraic data types, dependent types) have logical counterparts; understanding the correspondence clarifies language design and verification.
- Research frontier: mapping concurrency/distributed computation to logic (e.g., linear logic ↔ session types) could reveal “discovered” models for distributed systems.
Speakers and sources mentioned
- Speaker: Philip Wadler
- Historical/logical/mathematical figures:
- David Hilbert
- Kurt Gödel
- Alonzo Church
- Alan Turing
- Gerhard Gentzen
- Stephen Kleene
- Haskell Curry
- William A. Howard
- Brouwer / Heyting / Kolmogorov (BHK interpretation referenced)
- Computer scientists, PL and logic researchers:
- Luca Cardelli
- J. Roger Hindley
- Robin Milner
- John C. Reynolds
- Nicolaas G. de Bruijn
- Systems, languages, tools referenced:
- Lambda calculus (Church)
- Simply‑typed lambda calculus
- System F / polymorphic lambda calculus
- Standard ML, Haskell, Java (generics), C, C++, Python
- Proof assistants / dependently typed languages: Coq, Agda
- Cultural references:
- The Voyager plaque (NASA)
- The movie Independence Day
- The play Constellations (analogy about multiverses)
Category
Educational
Share this summary
Is the summary off?
If you think the summary is inaccurate, you can reprocess it with the latest model.
Preparing reprocess...