[Advanced] · Worked answers to note 08.
Part A — Lambda calculus
1. Reduce by hand
(a) — the identity.
(b) — this is const / K, and Church-encoded true.
(c) .
Write every substitution out. The discipline is the exercise — reduction errors come from skipping steps, not from misunderstanding.
2. Capture
. Naively substituting for gives — the identity function.
That’s wrong. The being passed in is a free variable that has been captured by the binder , changing its meaning entirely.
Correctly: alpha-convert first, , then substitute → — a constant function returning the outer .
The rule: when substituting into a term with a binder, rename the bound variable if it would capture a free variable of what you’re substituting.
Every first implementation of substitution has this bug, and it’s why real implementations use De Bruijn indices (bound variables as numbers, so there are no names to collide) or a locally-nameless representation. It’s also the same phenomenon as unhygienic macros capturing user variables → compilers.
3. Church numerals
is “apply to , times”:
: apply once, then once more — . ✓
The point of the exercise is that data is unnecessary. Numbers, booleans, pairs and lists are all encodable as functions. The lambda calculus has only abstraction and application and is still Turing-complete → Turing machines.
4. Y combinator
. ✓
reproduces itself with a in front — which is recursion without any named self-reference. That’s the trick: a language with no def and no recursion still gets recursion.
Under call-by-value it diverges. CBV evaluates arguments before applying, so must fully evaluate — which reduces to itself, forever. No is ever reached.
fixes it by eta-expansion: . Wrapping the self-application in makes it a value, so CBV stops early and unfolds only on demand.
This is why strict languages need and lazy ones can use , and it’s the cleanest demonstration that evaluation strategy is not a mere implementation detail — it changes which programs terminate → note 03.
Part B — Semantics
5. Rules, then interpreter
The first two are congruence rules (evaluate inside), the third is the computation rule. Note they encode left-to-right order: the second requires to already be a value.
The interpreter should mirror them one-to-one — one case per rule. When it doesn’t, you’ve either implemented a rule you didn’t write down, or written a rule you don’t implement, and both are bugs you can only see by keeping the two side by side. That is the entire pedagogical point of operational semantics.
6. Evaluation order
let f = λx. 42 in f (print "hi")
- Call-by-value: prints
hi, returns 42 - Call-by-name / lazy: returns 42, prints nothing — the argument is never used, so never evaluated
Haskell is lazy (call-by-need — call-by-name plus memoisation). Python, Rust, Java, Go, OCaml are call-by-value.
The consequences are real: laziness lets you define infinite structures (take 5 [1..]) and gives short-circuiting for free, at the cost of unpredictable space behaviour and space leaks from unevaluated thunks. Strict evaluation is predictable and needs explicit laziness (generators, Iterator, thunks) for the same tricks → generators.
Part C — Types
7. Type checker
Bidirectional checking splits into two mutually recursive functions: infer(Γ, e) → τ (synthesise) and check(Γ, e, τ) (verify against an expectation). Lambdas are checked against an expected function type; applications infer the function then check the argument.
fails: the function infers , so true is checked against Int and fails.
Bidirectional is the practical approach because it produces good error messages — you know what was expected at the failure point, so you can say “expected Int, found Bool” rather than “unification failed”. It also needs far fewer annotations than naive checking → compilers.
8. Progress and preservation
Preservation: if and then . By induction on the typing derivation; the substitution lemma does the work in the beta case.
Progress: if then is a value or . By induction on typing, using a canonical forms lemma (a value of type is a lambda).
The one-sentence version: progress says a well-typed term is never stuck right now; preservation says evaluating it keeps it well-typed — so by induction it is never stuck, ever.
“Stuck” means a non-value that cannot step — true + 1, or calling a non-function. That is what type safety actually guarantees, and it is narrower than people assume: it says nothing about termination, correctness, or the absence of exceptions and infinite loops.
9. Algorithm W
λf.λx. f (f x):
Assign , . From f x: . From f (f x): . Unifying gives . Result: , generalised to . ✓
The occurs check rejects unifying with a type containing , which would build an infinite type. Omit it and your unifier loops forever on exercise 10’s first term.
This is why ML-family languages need almost no annotations while remaining fully statically typed, and it is the machinery behind type inference in Haskell, OCaml, Rust and (partially) TypeScript.
10. Break inference
requires — occurs in its own definition. Rejected by the occurs check. Untyped it is perfectly fine (it is half the Y combinator), which shows the type system rejects some terminating, meaningful programs. Every type system is conservative — that is the trade.
Let-polymorphism:
let id = λx.x in (id 1, id true) -- ✓ id : ∀α. α → α
(λid. (id 1, id true)) (λx.x) -- ✗ ill-typed
HM generalises at let but not at λ. At let, the definition is complete, so free type variables can be quantified. A lambda-bound variable must have one monomorphic type across the body, because the function might be applied to anything.
Generalising at λ is System F, and its inference is undecidable. HM’s restriction is exactly the compromise that keeps inference decidable and complete — which is why it is the design nearly every practical inferring language adopted.
Part D — Curry–Howard and effects
11. Programs as proofs
| Type | Proposition | Inhabitant |
|---|---|---|
| (K) | ||
| transitivity | (composition) | |
| conjunction elimination |
Types are propositions; programs are proofs; evaluation is proof simplification. Product = ∧, sum = ∨, function = ⇒, Void = ⊥.
has no inhabitant. To construct a value of Either A (A → Void) you must supply either an or a refutation of — and for an arbitrary, unknown you can do neither. A constructive proof must produce a witness, and excluded middle asserts a disjunction without saying which side holds.
That is why Coq, Agda and Lean are constructive by default, and why classical reasoning must be added as an axiom — which then blocks extracting a running program from the proof → note 06.
12. Linearity
Linear rules use context splitting:
Each variable goes to exactly one subterm, and there is no rule permitting duplication or discarding.
- rejected — used twice (no contraction)
- rejected — used zero times (no weakening)
The Rust mapping is direct:
| Structural rule | Rust |
|---|---|
| Contraction (use twice) | Forbidden for non-Copy — that is move semantics |
| Weakening (never use) | Allowed — Rust is affine, not linear. Drop runs |
| Both allowed | Copy types |
Rust is affine (at most once), not linear (exactly once) — which is why an unused String is fine but using it after a move is not, and why the compiler inserts drop.
This is the vault’s clearest case of theory arriving in industry: substructural type systems from the 1980s became the borrow checker, and “the type system tracks how many times you use a value” is the whole idea → Rust.
Related
Source: [reference] — from Pierce’s Types and Programming Languages and the course’s primary sources.
Software engineering
Infrastructure & security
Computer science
Hardware & engineering