The width-and-depth contract: checklist and review rubric¶

This file turns PROPOSAL §6.0 into something you can check off. It's binding for every chapter. A chapter can't be marked status: available in tools/course/chapters.yaml until every technique in its technique map passes the rubric at the end of this file.

Related documents: - STYLE.md covers how to write: voice, formatting, math, real-world boxes, diagrams, trace tables, citations and code. - NOTATION.md is the house notation and the numbered-statement conventions. - REFERENCES.md is the bibliography format (references.yaml) and how to cite. - LABS.md is the lab rule: specs and a minimal test contract, not scaffolding. - REVIEW_CHECKLIST.md is the procedure the independent reviewer follows. - QUIZ_FORMAT.md covers quiz sources. - DRILLS.md covers drill plugins. - CHAPTER_TEMPLATE/ has files you copy.

Process. Every chapter is written by an author subagent and then audited by a separate reviewer subagent following REVIEW_CHECKLIST.md. The author self-audits against this file first; the reviewer re-derives everything independently.

1. Width: the technique map¶

Every chapter answers one problem: "turn characters into tokens", "compute dominators", "assign registers". It surveys the family of techniques that solve that problem. Never teach just one.

The chapter's README.md is the technique map. It must contain all of the following.

#	Requirement	Minimum
W1	The problem stated precisely, with its inputs and outputs.	one paragraph
W2	Every technique family from the chapter's syllabus entry in PROPOSAL §6. List each technique in each family by name with its origin (authors, year).	all of them. Adding more is fine, dropping any is not.
W3	How they relate: a Mermaid diagram of lineage and refinement ("CHK simplifies iterative; Semi-NCA simplifies LT") or of the design space.	1 diagram
W4	Who uses what: production compilers and tools, with the technique each uses.	≥ 4 systems, where the domain has that many
W5	The comparison table, with one row per technique and fixed columns (see §3, item 8).	every technique
W6	The route through the chapter: lessons in order, which techniques Pebble implements, which live in the comparison lab, and which are theory + drills only.	a table
W7	Prerequisites and outcomes: what you need from earlier chapters, and 4–8 concrete "you will be able to…" outcomes.	yes
W8	Notation: a `## Notation` section listing every symbol the chapter uses, pointing to NOTATION.md for shared ones and defining new ones precisely.	yes
W9	References: `references.yaml` (+ generated `references.md`), a curated, annotated bibliography per REFERENCES.md, linked from the README.	≥ 12 entries: ≥ 1 paper, book (with sections), source, docs

Implementation must also span the width: - At least two competing techniques are implemented in the comparison lab (labs/chNN-*). The tests check that each is correct, and the lab measures how they differ (speed, precision, table size, spills…). - The technique Pebble uses is implemented in full. - ★ marks optional extra labs. - Labs ship a spec, not scaffolding (LABS.md): a SPEC.md with requirements, formats, performance targets, what the tests check, milestones and hidden hints; the only code provided for the learning objective is the minimal test contract (one header, or a CLI contract), with a single stub file. Learners design their own data structures and files. Solutions stay complete under solutions/.

2. Depth: lessons and technique families¶

Each lesson file (lessons/NN-topic.md) covers one technique family. Example: "Dominator algorithms: iterative, Cooper–Harvey–Kennedy, Lengauer–Tarjan, Semi-NCA".
A lesson has exactly the nine numbered ## sections below, in this order. ./course validate checks the headings (prefix match, so plurals are fine).
Inside each section, give every technique of the family its own ### subsection. The exceptions are sections 5 and 8, where one table covering all of them is usually clearer.

## 1. Problem and motivation
## 2. Definitions and algorithms
## 3. Worked example            (or "Worked examples")
## 4. Invariants and correctness
## 5. Complexity
## 6. Variants and refinements
## 7. In real compilers
## 8. Comparison
## 9. Assessment

A technique that is "only theory" still gets the full treatment. The only thing it skips is the C++ implementation.

2a. Rigor and real examples (binding for every lesson)¶

Theory is written in LaTeX inside Markdown ( $…$ , $$…$$, \begin{aligned}), in the notation of NOTATION.md, and structured as numbered boxes (STYLE.md §5):

Requirement	Minimum per lesson
R1 Definitions	Every term the algorithms and proofs use is a `!!! definition "Definition N.k.m (Name)"` box, before its first use.
R2 Results	Every correctness, termination and optimality claim is a numbered `theorem` / `proposition` / `lemma` / `corollary`. At least one per technique that has a correctness argument.
R3 Proofs	Each result is followed by a `!!! proof` box. A full proof, or a labelled sketch — `"Proof sketch (full proof: [LT79, §3])"` — that names where the full proof is. "It is easy to see" is never a step.
R4 Algorithms	Each algorithm is an `!!! algorithm "Algorithm N.k.m (Name)"` box with Input, Output, Precondition(s), Postcondition(s), Invariant(s), then the pseudo-code. The invariants are the ones the proof uses.
R5 Complexity	Every bound defines its variables and is justified: a counting argument, a recurrence, a potential function, or a citation to where it is proved. Pathological families are constructed explicitly and their cost derived.
R6 Real-world examples	Every technique (every `###` of §7) has at least one `!!! real-world` box placed under that technique's `###` in any section — best right next to the theory it illustrates (§2–§4) — showing the concept in an actual system with the exact command, tool versions and captured output (STYLE.md §5a): `clang -S -emit-llvm` output, `opt -passes='print<domtree>'`, Bison/ANTLR conflict reports, rustc/Swift diagnostics or MIR/SIL dumps.
R7 Examples of definitions	Non-trivial definitions and theorems are followed by a small `!!! example` on the running example.

./course validate checks R1–R4 and R6 syntactically (presence, numbering N.k.m in order, proof after each result, algorithm fields, real-world box per technique with a sh command, versions, Reproduce and Output). Today these are warnings; --strict (required for status: available) makes them errors. A lesson that is genuinely not theory-bearing (a survey of tools) opts out of R1–R4 with ; the reviewer must agree.

3. The nine items, per technique¶

For each item you get: - what it must contain - the minimum that passes review - the failure modes reviewers look for

1. Problem and motivation¶

Contains: - What question the technique answers, and where in the compiler pipeline it runs. - Why the previous approach wasn't good enough: the historical step. - The origin paper.

Minimum: - 1–3 paragraphs. - The original paper cited inline ([KEY]) and present in the chapter's references.yaml with an annotation (REFERENCES.md). - One sentence tying it to Pebble or LLVM ("pebblec runs this before SSA construction because…").

Failure modes: - A history lesson with no problem statement. - No citation, or citing a blog post instead of the paper.

2. Precise definitions and the algorithm¶

Contains: - Formal definitions of every term the algorithm uses. - Inputs, outputs and preconditions. - Complete pseudo-code.

Minimum: - Definitions are numbered !!! definition boxes in LaTeX, in the notation of NOTATION.md (§2a R1). - The algorithm is an !!! algorithm box stating input, output, preconditions, postconditions and invariants (§2a R4). - Pseudo-code sits in a text fenced block inside that box, follows STYLE.md §6, and defines every helper it calls. - No ..., "details omitted" or "standard" steps left out. - A reader can implement it from the lesson alone. - If the course implements it, link the skeleton file (pebble/lib/... or labs/...).

Failure modes: - Prose instead of pseudo-code. - Helper functions used but never given (intersect, closure, eval/link). - Pseudo-code that differs from the implementation without saying so.

3. A worked example, traced step by step¶

Contains: - A concrete input. - A trace showing every state change of every data structure: tables, sets, stacks, worklists, union-find forests. - The final answer.

Minimum: - The input has 5–12 nodes, productions or instructions. It exercises every branch of the algorithm: a loop and a join for CFG algorithms; ε and a FIRST/FOLLOW conflict for grammars; a spill for register allocators. - Draw the input as Mermaid. - Trace in tables, one row per iteration or step, following STYLE.md §4. - Use the same running example for every technique in the lesson (and preferably the chapter), so the reader can compare the traces directly. - End with a "Try it yourself" line that points to a drill and seed that reproduce a similar problem, e.g. ./course drill dominators --seed 12 --difficulty hard --solution.

Failure modes: - "After a few iterations we get…". - Traces that skip the final no-change pass. - An example so small that half the algorithm never runs.

4. Invariants and a correctness argument¶

Contains: - Why it terminates. - Why the result is right. - The loop invariant or the fixed-point characterization.

Minimum: - State the invariant(s) as numbered lemmas (or in the algorithm box) and prove initialization, maintenance and what they give at termination. - State correctness as a numbered theorem: termination (with a well-founded measure: lattice height, a strictly decreasing set, a finite number of items), soundness, and completeness or optimality where it applies. - Each result has a !!! proof box: a full proof, or a proof sketch that names where the full proof is (§2a R3). 10–30 lines of LaTeX is typical. - Say which precondition breaks the argument: irreducible CFGs, ambiguous grammars, non-distributive frameworks, and so on — ideally with a counterexample.

Failure modes: - "It's easy to see that…". - A proof of a different algorithm than the pseudo-code. - Missing termination. - A "proof sketch" with no pointer to a full proof.

5. Complexity¶

Contains: - Best, worst and typical time and space, with the variables defined. - Pathological inputs. - What goes wrong at scale.

Minimum: - A table row per technique with time (worst), time (typical), space, and the variables used (n = nodes, e = edges, d = loop connectedness, and so on). - Each bound is justified (§2a R5): a counting argument, a recurrence, or a citation to the proof. - One explicitly constructed pathological family, e.g. "the ladder graph makes iterative dominators take Θ(n) passes in postorder", with the cost derived. - One sentence of real-world scale with a number and its source, e.g. "CHK beats Lengauer–Tarjan below ~30 000 nodes [CHK01]".

Failure modes: - Big-O without variables. - Worst case only. - Claims about practice with no source.

Contains: the known improvements and the trade-off each one makes.

Minimum: - ≥ 2 variants or refinements per technique, each with a citation and a one-line trade-off ("sophisticated linking: better bound, slower in practice"). - If a variant is itself in the technique map, cross-link it rather than repeat it.

Failure modes: a list of names with no trade-offs.

7. Where it lives in real compilers¶

Contains: - Which production systems use the technique. - Where in their source. - How the production version differs from the textbook.

Minimum: - ≥ 2 systems where they exist: LLVM, GCC, Clang, rustc, swiftc, V8, HotSpot, Cranelift, tree-sitter, ANTLR, Bison… - Each has a source pointer: a repository path plus a symbol, pinned to a version (STYLE.md §8), also listed as a source entry in references.yaml. Example: llvm/include/llvm/Support/GenericDomTreeConstruction.h, SemiNCAInfo::runSemiNCA (LLVM 23.1.2). - At least one !!! real-world box per technique (§2a R6) that the learner can reproduce. - If nothing in production uses it, say so and why. - The LLVM pointer should lead into a "Find where LLVM does X" reading task that has a quiz question.

Failure modes: - "LLVM uses this" with no path. - Paths from an old LLVM version. - Pointers into files that don't exist.

8. Comparison¶

Contains: the technique against the others in the chapter.

Minimum: - A row in the lesson's comparison table, and the same row in the chapter README's table. - The columns are always Power / precision, Speed (asymptotic + practical), Output or error quality, Implementation effort, Typical use. - Add chapter-specific columns if useful, such as "handles irreducible CFGs" or "table size". - Follow the table with a "Choose it when…" paragraph per technique. - Where the comparison lab measures something, quote its numbers here and say how to reproduce them.

Failure modes: - Adjectives only ("fast", "simple") with no basis. - A table that doesn't match the README.

9. Assessment¶

Contains: how the learner practices and proves they know it.

Minimum per technique:

Artifact	Minimum
Quiz questions (in `solutions/quizzes/chNN.yaml`)	≥ 2 that are tagged with the technique's tag. At least one must require computation or tracing (mapping, set, sequence or number), not recall.
Drills	A registered drill that generates this technique's problems (an existing one or a new one per DRILLS.md), or a written justification in the lesson for why a drill doesn't fit (rare; e.g. purely historical techniques).
Flashcards	≥ 3 cards tagged with the technique's tag: definition, key invariant, complexity.
Exercises	If implemented: the steps in `exercises.md` with hints, and the matching `PEBBLE_TODO("chNN", …)` sites.

The section itself lists these: quiz ids, ./course drill <name>, flashcard tags and exercise numbers. That way a reviewer can check them one by one.

4. Chapter-level checklist¶

Copy this list into the pull request or review notes for the chapter.

5. Review rubric¶

Score each technique on each of the nine items:

Score	Meaning
2	Meets the minimum above. A motivated learner could implement, trace, prove and place the technique from this material alone.
1	Present but shallow: a missing trace row, a vague complexity claim, a pointer without a path, a single quiz question.
0	Missing or wrong.

Pass: every technique scores 2 on all nine items. A chapter with any 1 or 0 stays planned.

Automatic 0 (red flags): - Pseudo-code containing ... or "etc." in place of steps. - A trace that skips iterations or the final confirming pass. - A complexity claim with undefined variables. - "Used in LLVM/GCC" without a source path. - A comparison row that is adjectives only. - A worked example whose answer disagrees with the course oracle. When a drill exists, check the lesson's example by feeding it through the oracle functions in tools/course/lib/. - A theorem without a proof box, or a proof sketch that doesn't say where the full proof is. - A real-world box whose command doesn't reproduce its output with the stated versions. - An over-scaffolded lab (internal helpers or per-step stubs for the learning objective). - A quiz answer that disagrees with the lesson.

Review procedure. The independent reviewer follows REVIEW_CHECKLIST.md in full (it includes the steps below). For the author's self-audit: 1. Run ./course validate --strict, ./course quiz verify --all and ./course site build. 2. For each lesson, fill in one row per technique:

Technique	1	2	3	4	5	6	7	8	9	Notes
Cooper–Harvey–Kennedy	2	2	2	2	2	2	2	2	2

Re-derive each worked example independently, with a drill oracle or by hand, and compare it with the lesson's traces.
Open two source pointers per lesson at the pinned version and confirm that they exist.
Take the quiz cold with ./course quiz NN and flag questions that can be answered without reading the chapter, or that the chapter doesn't answer.