[Advanced] · Twelve exercises. PL theory is the one domain here where the exercises are mostly implementations — because an interpreter you wrote cannot lie to you about the semantics.

Paper for Part A. A language with algebraic data types for B–D — Haskell, OCaml, Rust or Scala are natural; Python works with more typing.

Solutions in note 09.


Part A — Lambda calculus (note 02)

1. Reduce by hand.
Beta-reduce to normal form: (a) , (b) , (c) .
Done when: each is fully reduced with every substitution written out → note 02.

2. Get capture wrong on purpose.
Reduce naively, without renaming. Then do it correctly with alpha-conversion.
Done when: you can show the naive result means something different, and state the rule that prevents it. This is the bug every first substitution implementation has.

3. Church numerals.
Define as Church numerals. Implement succ and plus, and verify by reduction.

4. Y combinator.
Verify by reduction, where . Then explain why does not terminate under call-by-value, and what changes.
Done when: you can state why a language with strict evaluation needs a different fixpoint combinator → note 03.


Part B — Semantics (note 03)

5. Write the rules, then the interpreter.
For a language of integers, booleans, +, if, and variables: write small-step operational semantics as inference rules, then implement an evaluator that follows them exactly.
Done when: the code’s structure mirrors the rules one-to-one. If it doesn’t, one of them is wrong.

6. Make evaluation order observable.
Add a print side effect. Write a program whose output differs under call-by-value and call-by-name. Implement both.
Done when: you have two different outputs from one program, and can say which strategy Haskell, Python and Rust use → note 03.


Part C — Types (notes 04–05)

7. Implement a type checker.
Simply-typed lambda calculus: a bidirectional checker with a context . Reject .
Done when: it accepts well-typed terms and rejects ill-typed ones with a useful message → note 04.

8. Prove progress and preservation.
For your language from exercise 5, state and prove both. Preservation: if and then . Progress: if then is a value or .
Done when: you can explain, in one sentence, why the two together give “well-typed programs don’t get stuck”.

9. Implement Algorithm W.
Hindley–Milner inference with unification. Infer the type of λf.λx. f (f x) with no annotations.
Done when: you get without being told, and your unifier performs the occurs check → note 05.

10. Break inference.
Write a term that needs the occurs check to reject (), and one where let-polymorphism matters (a let id = λx.x used at two different types).
Done when: you can state why HM generalises at let but not at λ, and what that buys.


Part D — Curry–Howard and effects (notes 06–07)

11. Programs as proofs.
Give the type corresponding to each and write an inhabiting term: ; ; . Then try and fail.
Done when: you can explain why excluded middle has no inhabitant in a constructive setting → note 06.

12. Linearity by hand.
Write typing rules for a linear lambda calculus where every variable is used exactly once. Show and are both rejected.
Done when: you can connect the rules to Rust’s move semantics and say which Rust feature corresponds to weakening → note 07 · Rust.

Source: [reference] — built from this course’s own gap-closing list.

↑ Back to Programming Language Theory