# Compiler & Metaprogramming Resources

Curated for the `pydantic-codegen` mission. Every entry says when to reach for it.

## Knowledge — pass structure & IR design

- [Paper: "A Nanopass Infrastructure for Compiler Education" — Sarkar, Waddell & Dybvig (ICFP '04)](https://www.cs.tufts.edu/comp/150FP/archive/kent-dybvig/nanopass.pdf)
  The single most relevant paper to this project. Argues for many tiny passes over a few
  monolithic ones, with the IR *declared* per pass so each pass only mentions what it
  changes. `transformers.py` is already a nanopass pipeline; this is the theory of it.
  Use for: how small a pass should be, and how to keep N IRs from becoming N boilerplates.

- [Book chapter: Crafting Interpreters — "Representing Code" — Bob Nystrom](https://craftinginterpreters.com/representing-code.html)
  Free online. The clearest existing explanation of why an AST is shaped the way it is,
  and of the expression-problem tension between adding node types and adding passes.
  Use for: vocabulary (grammar, production, node), and the visitor-vs-match tradeoff.

- [Docs: Nanopass Framework](https://nanopass.org/documentation.html)
  The Scheme implementation. Skim the `define-language` / `define-pass` forms even
  without reading Scheme — the *shape* is the lesson: an IR defined as a grammar, and a
  pass that only names the productions it rewrites.
  Use for: what "IR as declared grammar" looks like in practice.

## Knowledge — this project is a macro system

- [Docs: `syn` — Rust source parser](https://docs.rs/syn) and [`quote` — Rust quasi-quoter](https://docs.rs/quote/latest/quote/macro.quote.html)
  Rust `#[derive(...)]` is the closest widely-used analogue to `pydantic-codegen`:
  read a type definition, emit derived code. `syn` = the loader, `quote` = the renderer.
  Use for: how a mature derive ecosystem structures the read → transform → emit split,
  and for the argument that emitting *structured* output beats emitting strings.

- [Paper: "Macros That Work" — Clinger & Rees (POPL '91)](https://xivilization.net/~marek/tex/hellprog/papers/p155-clinger.pdf)
  Where hygiene comes from: a macro must not be able to capture names it did not
  introduce. `gates.py`'s `ImportCollisionError` and `ShadowedImportError` are hygiene
  violations caught by hand instead of prevented by construction. Read for the split
  between *hygiene* and *referential transparency* — two obligations, not one.
  Use for: deciding whether to keep detecting collisions or to start renaming.

- [Paper: "Syntactic Abstraction in Scheme" — Dybvig, Hieb & Bruggeman (LaSC 1993)](https://legacy.cs.indiana.edu/~dyb/pubs/LaSC-5-4-pp295-326.pdf)
  The `syntax-case` design: identifiers carry the scope they were written in, so hygiene
  is a property of the representation rather than a renaming pass.
  Use for: the principled alternative to gensym, and for why a syntax object is not a string.

- [Paper: "Binding as Sets of Scopes" — Flatt (POPL '16)](https://users.cs.utah.edu/plt/scope-sets/)
  Racket's current model, and the clearest modern statement of what a "name" is: name plus
  set of scopes. Landing page has the paper, the executable model, and the artifact.
  Use for: understanding what you are giving up by renaming instead — and for the one idea
  worth stealing, that `bindings.py` is already a scope table.

- [Paper: "Template Meta-programming for Haskell" — Sheard & Peyton Jones (Haskell Workshop '02)](https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/meta-haskell.pdf)
  Quasiquotation in a statically-typed language: `[| ... |]` to quote, `$( )` to splice,
  and a careful account of what must be checked when. Section 2 is the readable part.
  Use for: the design of a `Template` type, and for why templates are parsed once.

## Knowledge — diagnostics

- [Docs: "Errors and lints" — Rust Compiler Development Guide](https://rustc-dev-guide.rust-lang.org/diagnostics.html)
  How a production compiler structures diagnostics: `DiagCtxt` as the sink, severity levels,
  stable error codes (`E0308`), structured suggestions, and the `Diagnostic` trait that keeps
  reporting logic out of the main code paths.
  Use for: the shape of a `Diagnostic` type, and for what "fatal" means as distinct from "error".

- [Docs: "ErrorGuaranteed" — Rust Compiler Development Guide](https://rustc-dev-guide.rust-lang.org/diagnostics/error-guaranteed.html)
  Two screens, and the best single idea in compiler diagnostics: a zero-sized token that cannot be
  constructed outside the diagnostics crate, so an error node *carrying* one is a static proof that a
  diagnostic was already emitted. Note the direction it insists on — *has been* emitted, not *will be*.
  Use for: making silent recovery unrepresentable rather than merely discouraged, and for the
  delayed-bug assertion that covers what the type system can't.

- [Paper: "Applicative programming with effects" — McBride & Paterson (JFP 2008)](https://www.staff.city.ac.uk/~ross/papers/Applicative.pdf)
  The origin of the applicative interface. Section 2's `Validation`-style example is the
  precise reason error accumulation needs `<*>` and cannot be done with `>>=`.
  Use for: being able to say in one sentence why the return type has to change.

- [Article: "Compiler Errors for Humans" — Evan Czaplicki (Elm, 2015)](https://elm-lang.org/news/compiler-errors-for-humans)
  Short, and the reference point for treating error output as a designed artifact. Directly
  influenced rustc's diagnostics.
  Use for: judging your `rejections.py` messages — which are already good — against a standard.

## Knowledge — spans, provenance, diagnostic rendering

- [Docs: `rustc_span::Span`](https://doc.rust-lang.org/nightly/nightly-rustc/rustc_span/struct.Span.html)
  A production span type: interned into a machine word, with the file, the byte range, and the
  expansion context that produced it. Skim the field list rather than the API.
  Use for: what a span has to carry, and the fact that provenance lives in the same value as location.

- [Docs: `proc_macro::Span`](https://doc.rust-lang.org/proc_macro/struct.Span.html)
  The macro-author's view, and the one that connects this to hygiene: `call_site()` versus
  `mixed_site()` decide where errors point *and* what identifiers resolve to, from one field.
  Use for: the argument that location and resolution are the same question asked of the same fact.

- [Library: codespan-reporting](https://docs.rs/codespan-reporting)
  A standalone renderer for rustc-style caret diagnostics — multiple labels, severities, notes.
  Read the `Diagnostic`/`Label` types, not the renderer.
  Use for: the shape of a diagnostic type that can hold more than one location, which is the diff to
  make before building any rendering at all.

- [Spec: Source Map, revision 3](https://tc39.es/source-map/)
  The *reverse* mapping — generated position back to source position. The standard is dry; what matters
  is the direction and the cost.
  Use for: knowing precisely what you are declining to build, and why a generated-file provenance
  header is the cheap 90%.

## Knowledge — normalisation and rewriting

- [Book: _Term Rewriting and All That_ — Baader & Nipkow (CUP 1998)](https://www.cambridge.org/core/books/term-rewriting-and-all-that/71768055278D0DEF4FFC74722DE0D707)
  The reference for termination, confluence, critical pairs and Newman's lemma. Chapters 2 and 6 are
  the relevant ones; the rest is Knuth–Bendix completion, which you do not need.
  Use for: the precise definitions behind "pass order doesn't matter", and the critical-pair argument
  that keeps the obligation to pairs of rules instead of sequences of passes.

- [Docs: MLIR — Canonicalization](https://mlir.llvm.org/docs/Canonicalization/)
  Two screens, and the best practitioner statement of the rules a canonicaliser must obey — including
  the one people skip: a canonical form is chosen for the *passes*, and it is allowed to be uglier than
  what the user wrote.
  Use for: the obligations list, and for permission to normalise aggressively.

- [Docs: LLVM — InstCombine contributor guide](https://llvm.org/docs/InstCombineContributorGuide.html)
  Distinguishes canonicalisation from optimisation, and is explicit about why two rules that undo each
  other are a bug in the rule set rather than in the driver.
  Use for: the termination argument, stated as a real project's policy.

## Knowledge — the relational target, and mapping onto it

- [Catalog: _Patterns of Enterprise Application Architecture_ — Martin Fowler](https://martinfowler.com/eaaCatalog/)
  The naming authority for everything this backend does. Three entries carry most of it:
  [Foreign Key Mapping](https://martinfowler.com/eaaCatalog/foreignKeyMapping.html) (an association
  becomes a foreign key), [Identity Field](https://martinfowler.com/eaaCatalog/identityField.html) (who
  owns the id), and [Embedded Value](https://martinfowler.com/eaaCatalog/embeddedValue.html) (a value
  object with no table flattens into the owner's).
  Use for: the term to reach for before inventing one, and — for the sum-type question —
  [Single Table Inheritance](https://martinfowler.com/eaaCatalog/singleTableInheritance.html) vs
  [Class Table Inheritance](https://martinfowler.com/eaaCatalog/classTableInheritance.html), which is the
  same three-way choice Django exposes as abstract / multi-table / proxy.

- [Docs: Django — `ForeignKey` and the related-field arguments](https://docs.djangoproject.com/en/stable/ref/models/fields/#foreignkey)
  Reference for `on_delete` (and the explicit warning that `DO_NOTHING` yields an `IntegrityError` unless
  you add the SQL constraint yourself), `related_name` including `'+'` to suppress the reverse relation,
  `related_query_name`, and lazy relationships — `"app_label.ModelName"` and `"self"` as forward
  references resolved by the app registry.
  Use for: the elaboration defaults, and for the escape hatch that makes emission order irrelevant.

- [Docs: Django — System check framework reference](https://docs.djangoproject.com/en/stable/ref/checks/)
  The `fields.E302`–`E305` block is the taxonomy of reverse-name collisions on two axes: which name
  (accessor or query name) against what (a field, or another reverse name). Read it as a specification of
  what a generator must not emit.
  Use for: knowing exactly which hygiene violations the target catches for you — and the argument against
  relying on that, since it catches them at application startup in code the user did not write.

- [Docs: Django — System check framework (writing your own)](https://docs.djangoproject.com/en/stable/topics/checks/)
  How the checks above are registered and run. The relevant design fact is that they are a *separate pass
  over the finished model registry*, not validation inside field construction — a verifier in lesson 1's
  sense, in a framework that had the same problem you do.
  Use for: prior art on where a whole-program check lives.

- [Docs: Django — Lazy relationships and `ForeignKey("app.Model")`](https://docs.djangoproject.com/en/stable/ref/models/fields/#lazy-relationships)
  The forward-reference mechanism the target hands you for free: a string resolved against the app registry
  after every model is imported, plus `"self"` for self-relations. Two paragraphs.
  Use for: the argument that a topological sort of models is dead code, and that a per-model module layout
  does not need imports between models at all.

- [Docs: PostgreSQL — `SET CONSTRAINTS`](https://www.postgresql.org/docs/current/sql-set-constraints.html)
  and [`CREATE TABLE` … `DEFERRABLE`](https://www.postgresql.org/docs/current/sql-createtable.html)
  The database-level escape for a cycle of required foreign keys: mark the constraint deferrable and check
  it at commit instead of per statement. Django does not create foreign keys as deferrable, so this means a
  hand-written migration plus a standing obligation that every write happens in a transaction.
  Use for: knowing the escape exists, and for the argument that a generator should reject and mention it
  rather than silently take it.

- [Docs: pydantic — Fields, and `FieldInfo.metadata`](https://pydantic.dev/docs/validation/latest/concepts/fields/)
  with [annotated-types](https://github.com/annotated-types/annotated-types)
  Where constraints actually live in pydantic v2: `MaxLen`, `Gt` and friends in `FieldInfo.metadata`, not as
  attributes, and `Field(max_length=3)` converges on the same metadata as
  `Annotated[str, StringConstraints(max_length=3)]`.
  Use for: reading constraints correctly — `getattr(field, "max_length", None)` returns `None` for every
  field forever, and the symptom is valid output that silently drops the constraint.

- [Article: "The Vietnam of Computer Science" — Ted Neward (2006)](https://blogs.newardassociates.com/blog/2006/the-vietnam-of-computer-science.html)
  The canonical statement of the object-relational impedance mismatch, and deliberately polemical. The
  useful part is the enumeration of the mismatches that have no clean resolution — identity, inheritance,
  partial loading — rather than the conclusion.
  Use for: knowing which of your mapping problems are hard *in general* and should be pushed back to the
  domain author rather than solved.

## Knowledge — elaboration

- [Paper: "Elaboration in Dependent Type Theory" — de Moura, Avigad, Kong & Roux (2015)](https://leodemoura.github.io/files/elaboration.pdf)
  The closest thing to a written-up account of *filling in what the source did not say*: coercion
  insertion, overload resolution, implicit arguments. Section 1 and the framing are the readable part; the
  unification machinery is not the point.
  Use for: the vocabulary — that inserting `on_delete` is coercion-shaped elaboration, and that an
  elaborator's obligation is to make its inserted choices *inspectable*.

## Knowledge — Python's own semantics (the substrate)

- [PEP 649 — Deferred Evaluation of Annotations Using Descriptors](https://peps.python.org/pep-0649/)
  and [PEP 749 — Implementing PEP 649](https://peps.python.org/pep-0749/)
  As of 3.14 annotations are lazily computed via `__annotate__`, and `annotationlib`
  exposes `VALUE` / `FORWARDREF` / `STRING` formats. This directly affects the comment in
  `loader.py:_declaring_class` about `inspect.get_annotations` being unsafe.
  Use for: deciding what the loader should read, and what it can stop working around.

- [PEP 657 — Fine-grained error locations in tracebacks](https://peps.python.org/pep-0657/)
  Why CPython stores column offsets and end positions, what it costs, and the exact semantics of the
  four position attributes on an `ast` node. Note the stated fact that columns are UTF-8 byte offsets.
  Use for: the position hazards — 1-based lines against 0-based columns, and bytes against characters.

- [Docs: `ast` — Abstract Syntax Trees (CPython)](https://docs.python.org/3/library/ast.html)
  Reference for `ast.parse`, `ast.walk`, `ast.get_source_segment`, and `ast.unparse`.
  Use for: checking whether a hand-rolled string operation has a node-level equivalent.

- [Library: LibCST — Instagram](https://github.com/Instagram/LibCST)
  A *concrete* syntax tree for Python: keeps comments, whitespace, and formatting that
  `ast` throws away. The canonical CST-vs-AST reference point.
  Use for: understanding what `ast` discards, and when losing it matters (it mostly
  doesn't here — this project generates files rather than editing them).

## Knowledge — generating values from types

- [Docs: Hypothesis — "What you can generate and how"](https://hypothesis.readthedocs.io/en/latest/data.html)
  and [`hypothesis.strategies.builds` / `from_type`](https://hypothesis.readthedocs.io/en/latest/reference/strategies.html)
  A production type-directed value generator for Python, including how it resolves
  recursive types and how `register_type_strategy` handles types it can't derive.
  Use for: prior art on the `fake()` constructor — especially the recursion problem.

- [Paper: "QuickCheck: A Lightweight Tool for Random Testing of Haskell Programs" — Claessen & Hughes (ICFP '00)](https://www.cs.tufts.edu/~nr/cs257/archive/john-hughes/quick.pdf)
  Where `Arbitrary` comes from. Its `sized`/depth-budget mechanism is the standard answer
  to "how do I generate a value of a recursive type without diverging".
  Use for: the design of the depth budget, and the deterministic-vs-random split.

## Knowledge — properties and metamorphic testing

- [Paper: "How to Specify It! A Guide to Writing Properties of Pure Functions" — John Hughes (2019)](https://research.chalmers.se/publication/517894/file/517894_Fulltext.pdf)
  The single best practitioner text on *choosing* properties: five styles (postconditions,
  metamorphic, inductive, model-based, algebraic), each measured against one function with
  eight seeded bugs. The mutation-testing discipline in it is the part to copy.
  Use for: deciding which properties to write, and for proving a property has power.

- [Survey: "Metamorphic Testing: A Review of Challenges and Opportunities" — Chen et al. (ACM CSUR 2018)](https://www.cs.hku.hk/data/techreps/document/TR-2017-04.pdf)
  Where the term is defined properly: a metamorphic relation is a pair of an input
  transformation and an output relation. Skim §2–3; the rest is a literature map.
  Use for: the vocabulary, and for the catalogue of relation shapes to steal from.

- [Paper: "Compiler Validation via Equivalence Modulo Inputs" — Le, Afshari & Su (PLDI '14)](https://web.cs.ucdavis.edu/~su/emi-project/)
  Metamorphic testing applied to compilers, and the most successful instance of it: perturb a
  program in ways that cannot change its behaviour, then require the compiled results to agree.
  Hundreds of real GCC and LLVM bugs. Project page has the paper and the tooling.
  Use for: the argument that equivariance-style relations beat golden files for a compiler,
  and for how to pick perturbations that are guaranteed meaning-preserving.

- [Docs: Hypothesis — settings, statistics and the example database](https://hypothesis.readthedocs.io/en/latest/settings.html)
  Reference for `@example`, `event()`, `target()`, `--hypothesis-show-statistics`,
  `derandomize`, and where failing examples are cached.
  Use for: keeping generated tests reproducible under moon's caching and `--testmon`.

## Gaps

- No high-trust source found yet on **derive-macro design in Python specifically**
  (attrs, dataclasses, and pydantic all do it, but as source, not as written-up design).
  Reading `dataclasses.py` in the stdlib is currently the best substitute — it builds
  `__init__` by generating source text and `exec`-ing it, and its `default_factory`
  handling is exactly the mutable-default problem, solved in production.
- No good survey of **elaboration** (filling in implicit code) aimed at practitioners rather than
  dependent-type theorists. The Lean paper above is the best available and is still a theorem-prover
  paper; the practitioner half is currently supplied by Django's own defaults, read as a worked example of
  what an elaborator owes its user.
- No high-trust source on **cycle diagnostics** — every treatment of strongly connected components is
  algorithmic (Tarjan, Kosaraju) and none discusses what a *good error message* for a dependency cycle
  looks like. The best available models are practitioner artifacts rather than writing: Go's import-cycle
  error and Rust's `E0391`, both of which print the whole cycle rather than one member.
- No high-trust source on **generating ORM models from a schema** as a design problem. The nearest prior
  art is `sqlacodegen` and Django's own `inspectdb`, both of which run in the opposite direction
  (database → models) and neither of which is written up. Reading `inspectdb`'s handling of
  self-references and duplicate foreign keys is the substitute.