Skip to content

References — Chapter 5 · Names, Scopes & Semantic Analysis

Every source this chapter cites, grouped by kind. Lessons cite entries inline as [KEY]; each entry says why and when to read it. Core reading marks the entries the chapter assumes you will open.

Foundational and research papers

  • [ACPPW08] Brian Aydemir, Arthur Charguéraud, Benjamin C. Pierce, Randy Pollack, and Stephanie Weirich. Engineering formal metatheory. POPL 2008, 3–15, 2008. doi:10.1145/1328438.1328443
    Why and when: Locally nameless plus cofinite quantification, the recipe that the side condition of Lemma 5.2.13 alludes to. Read §2–3 after Lesson 5.2 §6.
    Cited in: 02-symbol-tables

  • [Bak78] Henry G. Baker Jr.. Shallow binding in Lisp 1.5. Communications of the ACM 21(7), 565–569, 1978. doi:10.1145/359545.359566
    Why and when: Rerooting: one global value cell per name, moved lazily between contexts, which reconciles deep and shallow binding (Lesson 5.1 §6). Short; read after Algorithm 5.1.8.
    Cited in: 01-scoping-disciplines

  • [BK73] Walter A. Burkhard and Robert M. Keller. Some approaches to best-match file searching. Communications of the ACM 16(4), 230–236, 1973. doi:10.1145/362003.362025
    Why and when: BK-trees (Algorithm 5.8.7): metric-space indexing with the triangle inequality, and why the distance must be a metric (Theorem 5.8.12, Lemma 5.8.11). Read §2 after Lesson 5.8 §2.
    Cited in: 08-diagnostics

  • [Cha12] Arthur Charguéraud. The locally nameless representation. Journal of Automated Reasoning 49(3), 363–408, 2012. doi:10.1007/s10817-011-9225-2
    Why and when: The reference treatment of locally nameless syntax: opening, closing, local closure and the lemmas that make proofs go through. Read §2–4 after Lesson 5.2 §6 if you want to see why Lean and Coq developments use it.
    Cited in: 02-symbol-tables

  • [Dam64] Fred J. Damerau. A technique for computer detection and correction of spelling errors. Communications of the ACM 7(3), 171–176, 1964. doi:10.1145/363958.363994
    Why and when: The observation that most misspellings are one insertion, deletion, substitution or transposition of adjacent letters: why GCC and rustc use OSA. Read after Lesson 5.8 §2.
    Cited in: 08-diagnostics

  • [dB72] Nicolaas G. de Bruijn. Lambda calculus notation with nameless dummies, a tool for automatic formula manipulation, with application to the Church–Rosser theorem. Indagationes Mathematicae 75(5), 381–392, 1972. doi:10.1016/1385-7258(72)90034-0
    Why and when: Core reading. The origin of de Bruijn indices (Definition 5.2.8) and the shifting of free indices under substitution (Lemma 5.2.13). Read §1–3 after Lesson 5.2 §4; the notation differs but the counting rule is the same.
    Cited in: overview, 02-symbol-tables

  • [DHB92] R. Kent Dybvig, Robert Hieb, and Carl Bruggeman. Syntactic abstraction in Scheme. Lisp and Symbolic Computation 5(4), 295–326, 1992. doi:10.1007/BF01806308
    Why and when: syntax-case with marks and substitutions: how a resolver compares identifiers by name and marks (Lesson 5.4 §2). Read §3.
    Cited in: 04-overloading-adl-hygiene

  • [DSST89] James R. Driscoll, Neil Sarnak, Daniel D. Sleator, and Robert E. Tarjan. Making data structures persistent. Journal of Computer and System Sciences 38(1), 86–124, 1989. doi:10.1016/0022-0000(89)90034-2
    Why and when: Core reading. The theory of persistence behind Algorithm 5.2.7: path copying (§2) and the node-copying technique that makes updates amortized \(O(1)\) space. Read §1–2 after Lesson 5.2 §3.
    Cited in: 02-symbol-tables

  • [EH07] Torbjörn Ekman and Görel Hedin. The JastAdd extensible Java compiler. OOPSLA 2007, 1–18, 2007. doi:10.1145/1297027.1297029
    Why and when: A full Java 1.⅘ front end written as a reference attribute grammar, with name analysis, type analysis and definite assignment as modules. Read §3–4 after the JastAdd box of Lesson 5.5; the performance numbers are in §6.
    Cited in: 05-attribute-grammars

  • [Fla16] Matthew Flatt. Binding as sets of scopes. POPL 2016, 705–717, 2016. doi:10.1145/2837614.2837620
    Why and when: Racket's hygiene as a lookup rule: a reference resolves to the binding whose scope set is the largest subset of its own, a direct generalization of Definition 5.1.2. Read §2–3 after Lesson 5.4 §2.
    Cited in: 04-overloading-adl-hygiene

  • [Hed00] Görel Hedin. Reference attributed grammars. Informatica (Slovenia) 24(3), 301–317, 2000.
    Why and when: Attributes whose values are references to other tree nodes, so that decl() can point at a declaration (Lesson 5.5 §6). Read §2–4 before the JastAdd box of Lesson 5.5.
    Note: No DOI; the journal's archive and the author's Lund University page host the PDF.
    Cited in: 05-attribute-grammars

  • [HPHF14] Matthew A. Hammer, Khoo Yit Phang, Michael Hicks, and Jeffrey S. Foster. Adapton: Composable, Demand-Driven Incremental Computation. PLDI 2014, 2014. doi:10.1145/2594291.2594324
    Why and when: Demand-driven incremental computation with a dependency graph that is dirtied eagerly and cleaned lazily; compare it with Algorithm 5.6.4 after Lesson 5.6 §4.
    Cited in: 06-where-results-live

  • [JOR75] Mehdi Jazayeri, William F. Ogden, and William C. Rounds. The intrinsically exponential complexity of the circularity problem for attribute grammars. Communications of the ACM 18(12), 697–706, 1975. doi:10.1145/361227.361231
    Why and when: The lower bound behind Theorem 5.5.16: deciding circularity takes exponential time. Read §1–2 for the statement and skim the encoding in §3–5 after Lesson 5.5 §5.
    Cited in: 05-attribute-grammars

  • [Kas80] Uwe Kastens. Ordered attributed grammars. Acta Informatica 13(3), 229–256, 1980. doi:10.1007/BF00288644
    Why and when: Ordered AGs: a polynomial-time test and visit sequences computed at generation time (Definition 5.5.9, Proposition 5.5.17). Read §3–4 after Lesson 5.5 §5; the evaluator generators LIGA and Eli use it.
    Cited in: 05-attribute-grammars

  • [KFFD86] Eugene Kohlbecker, Daniel P. Friedman, Matthias Felleisen, and Bruce Duba. Hygienic macro expansion. LFP 1986, 151–161, 1986. doi:10.1145/319838.319859
    Why and when: The origin of hygiene. For Chapter 5 read §2 (the hygiene condition) after Lesson 5.4 §2: hygiene is a name-resolution property, resolution by (name, context) pairs.
    Cited in: 04-overloading-adl-hygiene

  • [Knu68] Donald E. Knuth. Semantics of context-free languages. Mathematical Systems Theory 2(2), 127–145, 1968. doi:10.1007/BF01692511
    Why and when: Core reading. The origin of attribute grammars: synthesized and inherited attributes, dependency graphs, and a circularity test (Definitions 5.5.1–5.5.4 and 5.5.7). Read §1–3 after Lesson 5.5 §2; the binary numerals example is the classic first AG.
    Cited in: overview, 05-attribute-grammars

  • [Knu71c] Donald E. Knuth. Semantics of context-free languages: correction. Mathematical Systems Theory 5(1), 95–96, 1971. doi:10.1007/BF01702865
    Why and when: Two pages that fix the 1968 circularity test: keep a set of IO graphs per nonterminal, not their union — exactly the point of Algorithm 5.5.8 and Theorem 5.5.15. Read right after the proof sketch of Theorem 5.5.15.
    Cited in: 05-attribute-grammars

  • [KU77] John B. Kam and Jeffrey D. Ullman. Monotone Data Flow Analysis Frameworks. Acta Informatica 7(3), pp. 305-317, 1977. doi:10.1007/BF00290339
    Why and when: MFP versus MOP in monotone frameworks; definite assignment is distributive, so its MFP solution equals the all-paths meaning (Theorem 5.7.8). Read after Lesson 5.7 §4; Chapter 14 covers the full theory.
    Cited in: 07-control-flow-checks

  • [KW76] Ken Kennedy and Scott K. Warren. Automatic generation of efficient evaluators for attribute grammars. POPL 1976, 32–49, 1976. doi:10.1145/800168.811538
    Why and when: Strongly (absolutely) non-circular grammars: one merged IO graph per nonterminal, a polynomial test and static evaluation plans. Read after Lesson 5.5 §6.
    Cited in: 05-attribute-grammars

  • [Lev66] Vladimir I. Levenshtein. Binary codes capable of correcting deletions, insertions, and reversals. Soviet Physics Doklady 10(8), 707–710, 1966.
    Why and when: Core reading. The origin of the edit distance of Definition 5.8.5 (insertions, deletions, substitutions). Read the definitions on the first two pages after Lesson 5.8 §2.
    Note: English translation of the 1965 Russian paper (Doklady Akademii Nauk SSSR 163(4)); no DOI.
    Cited in: 08-diagnostics

  • [LRS74] Philip M. Lewis, Daniel J. Rosenkrantz, and Richard E. Stearns. Attributed translations. Journal of Computer and System Sciences 9(3), 279–307, 1974. doi:10.1016/S0022-0000(74)80045-0
    Why and when: L-attributed translations, evaluable during a single left-to-right parse (Definition 5.5.4, Theorem 5.5.13). Read §2 after Lesson 5.5 §3 for the formal definition behind one-pass compilers.
    Cited in: 05-attribute-grammars

  • [MH07] Eva Magnusson and Görel Hedin. Circular reference attributed grammars — their evaluation and applications. Science of Computer Programming 68(1), 21–37, 2007. doi:10.1016/j.scico.2005.06.005
    Why and when: Circular attributes evaluated to a fixed point over a finite-height lattice (Algorithm 5.5.11), with nullability and definite assignment as examples. Read §3 after Lesson 5.5 §6.
    Cited in: 05-attribute-grammars

  • [MM04] Conor McBride and James McKinna. Functional pearl: I am not a number—I am a free variable. Haskell Workshop 2004, 1–9, 2004. doi:10.1145/1017472.1017477
    Why and when: Locally nameless terms in practice: bound variables as indices, free ones as names, with abstract and instantiate as the only operations that cross the boundary. Read after Lesson 5.2 §6.
    Cited in: 02-symbol-tables

  • [Mos70] Joel Moses. The function of FUNCTION in LISP, or why the FUNARG problem should be called the environment problem. ACM SIGSAM Bulletin 15, 13–27 (also MIT AI Memo 199), 1970. doi:10.1145/1093410.1093411
    Why and when: Names the funarg problem that Lesson 5.1 §3 reproduces: a function passed as an argument sees the wrong binding under dynamic scope. Read §1–3 after Theorem 5.1.10.
    Cited in: 01-scoping-disciplines

  • [Nau63] Peter Naur (ed.), John W. Backus, and et al.. Revised report on the algorithmic language ALGOL 60. Communications of the ACM 6(1), 1–17, 1963. doi:10.1145/366193.366201
    Why and when: The origin of block structure and static scoping: §4.1.3 (blocks and the locality of identifiers) and §5 (declarations). Read those two pages after Lesson 5.1 §1; Definition 5.1.2 is their modern form.
    Cited in: 01-scoping-disciplines

  • [NTVW15] Pierre Néron, Andrew Tolmach, Eelco Visser, and Guido Wachsmuth. A theory of name resolution. ESOP 2015, LNCS 9032, 205–231, 2015. doi:10.1007/978-3-662-46669-8_9
    Why and when: Core reading. Scope graphs: declarations, references, scopes and labeled P/I edges, resolution as well-formed minimal paths (Definitions 5.3.5–5.3.6). Read §2–3 before the ★ part of the lab and §4 for the resolution calculus behind Algorithm 5.3.7.
    Cited in: overview, 03-name-resolution-strategies

  • [RTD83] Thomas Reps, Tim Teitelbaum, and Alan Demers. Incremental context-dependent analysis for language-based editors. ACM TOPLAS 5(3), 449–477, 1983. doi:10.1145/2166.357218
    Why and when: Optimal incremental attribute evaluation after a subtree replacement: the ancestor of red–green marking and early cutoff (Lesson 5.6 §4). Read §1–3 after Lesson 5.6.
    Cited in: 05-attribute-grammars, 06-where-results-live

  • [RvAPKV20] Arjen Rouvoet, Hendrik van Antwerpen, Casper Bach Poulsen, Robbert Krebbers, and Eelco Visser. Knowing when to ask: sound scheduling of name resolution in type checkers derived from declarative specifications. Proc. ACM Program. Lang. 4 (OOPSLA), Article 180, 2020. doi:10.1145/3428248
    Why and when: When is a scope-graph query's answer final while the graph is still being built? Critical edges answer it, the principled version of the "undetermined import" of Algorithm 5.3.4. Read §2–3 after Lesson 5.3 §6.
    Cited in: 03-name-resolution-strategies

  • [vAPRV18] Hendrik van Antwerpen, Casper Bach Poulsen, Arjen Rouvoet, and Eelco Visser. Scopes as types. Proc. ACM Program. Lang. 2 (OOPSLA), Article 114, 2018. doi:10.1145/3276484
    Why and when: Statix: type checkers specified as constraints over scope graphs, with regular path expressions and label orders as query parameters. Read §2–4 after Lesson 5.3 §6.
    Cited in: 03-name-resolution-strategies

  • [WF74] Robert A. Wagner and Michael J. Fischer. The string-to-string correction problem. Journal of the ACM 21(1), 168–173, 1974. doi:10.1145/321796.321811
    Why and when: The dynamic program for edit distance (Algorithm 5.8.6) with its correctness proof. Six pages; read after Lesson 5.8 §2 and compare with llvm::ComputeEditDistance.
    Cited in: 08-diagnostics

Textbooks and monographs

  • [ALSU07] Alfred V. Aho, Monica S. Lam, Ravi Sethi, and Jeffrey D. Ullman. Compilers: Principles, Techniques, and Tools, 2nd ed.. Addison-Wesley, 2007. Read: §1.6.3 (static and dynamic scope), §2.7 (symbol tables per scope), §4.1.4 (error recovery), §5.1–5.4 (syntax-directed definitions, S- and L-attributed), §6.3 (types and declarations), §9.2 (data-flow analysis).
    Why and when: Core reading. The textbook companion for most of the chapter: read §2.7 with Lesson 5.2, §5.1–5.4 with Lesson 5.5, and §9.2 with Lesson 5.7.
    Cited in: overview, 02-symbol-tables, 03-name-resolution-strategies, 05-attribute-grammars, 07-control-flow-checks, 08-diagnostics

  • [EaC3] Keith D. Cooper and Linda Torczon. Engineering a Compiler, 3rd ed.. Morgan Kaufmann, 2022. Read: Ch. 3 (parsers: error recovery), Ch. 4 (intermediate representations: symbol tables and scoped tables), Ch. 5 (syntax-driven translation: declarations, scopes and attribute evaluation), Ch. 9 (data-flow analysis).
    Why and when: An engineering-first view of scoped symbol tables and syntax-driven translation; read the symbol-table sections as an alternative to Lesson 5.2 and Ch. 9 before Lesson 5.7.
    Cited in: 02-symbol-tables, 03-name-resolution-strategies, 07-control-flow-checks, 08-diagnostics

  • [ES90] Margaret A. Ellis and Bjarne Stroustrup. The Annotated C++ Reference Manual. Addison-Wesley, 1990. Read: §13.2 (argument matching), with the annotations on ambiguity.
    Why and when: Where the C++ overload-resolution rules (Algorithm 5.4.3, the ranks of Definition 5.4.1) were first written down with the rationale. Read §13.2 after Lesson 5.4 §2.
    Cited in: 04-overloading-adl-hygiene

  • [Knu98] Donald E. Knuth. The Art of Computer Programming, Volume 3: Sorting and Searching, 2nd ed.. Addison-Wesley, 1998. Read: §6.2.3 (balanced trees: the AVL height bound), §6.4 (hashing).
    Why and when: The height bound \(1.44 \log_2(n+2)\) used in Proposition 5.2.10 and the analysis of chained hashing behind the scope stack. Read §6.2.3 if the AVL rotations of the lab are new.
    Cited in: 02-symbol-tables

  • [McC62] John McCarthy, Paul W. Abrahams, Daniel J. Edwards, Timothy P. Hart, and Michael I. Levin. LISP 1.5 Programmer's Manual. MIT Press, 1962. Read: Ch. 1 (the LISP language), Appendix B (the LISP interpreter: eval, apply and the association list).
    Why and when: Dynamic scoping as it was first implemented: eval looks names up in the association list of the calling context. Read the interpreter in Appendix B after Lesson 5.1 §2 and find where deep binding (Algorithm 5.1.7) happens.
    Cited in: 01-scoping-disciplines

  • [Oka98] Chris Okasaki. Purely Functional Data Structures. Cambridge University Press, 1998. Read: Ch. 2 (persistence: lists and binary search trees with path copying), §3.3 (red-black trees).
    Why and when: Persistent trees the functional way: Ch. 2 is Algorithm 5.2.7 in twenty lines of ML. Read it before the L2 milestone of the lab.
    Cited in: 02-symbol-tables

  • [TAPL] Benjamin C. Pierce. Types and Programming Languages. MIT Press, 2002. Read: Ch. 5 (the untyped lambda calculus: free variables, substitution), Ch. 6 (nameless representation of terms: shifting and substitution), Ch. 7 (an ML implementation).
    Why and when: The standard textbook account of de Bruijn indices, shifting and substitution (Lemma 5.2.13). Read Ch. 6 after Lesson 5.2 §4; Ch. 7 is a working implementation.
    Cited in: 02-symbol-tables

Theses and technical reports

  • [Bag01] Phil Bagwell. Ideal hash trees. EPFL, Technical Report (LAMP), 2001. link
    Why and when: Hash array mapped tries: a persistent map with one popcount per level, used by Clojure, Scala and rust-analyzer-era persistent collections. Read §2–3 for the stretch goal of the lab (a HAMT environment) after Lesson 5.2 §6.
    Cited in: 02-symbol-tables

  • [SS75] Gerald Jay Sussman and Guy L. Steele Jr.. Scheme: an interpreter for extended lambda calculus. MIT Artificial Intelligence Laboratory, AI Memo 349, 1975. link
    Why and when: The memo that brought static scoping and closures to Lisp. Read the interpreter's treatment of environments after Lesson 5.1 §1; it is the static counterpart of [McC62]'s a-list.
    Cited in: 01-scoping-disciplines

Source code (pinned versions)

  • [CLANG-ABW] Clang's CFG-based warnings (falling off the end of a function) — clang/lib/Sema/AnalysisBasedWarnings.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: CheckFallThroughForBody, CheckFallThrough.
    Why and when: -Wreturn-type from a CFG instead of the syntax-directed rules of Definition 5.7.1. Read after Lesson 5.7 §7 and compare with pebblec's E0305.
    Cited in: 07-control-flow-checks

  • [CLANG-DiagSema] Clang's table of semantic diagnostics — clang/include/clang/Basic/DiagnosticSemaKinds.td in llvm/llvm-project at llvmorg-23.1.2. Symbols: err_undeclared_var_use_suggest, warn_decl_shadow.
    Why and when: The TableGen counterpart of Pebble's DiagnosticKinds.def: every message, its severity and its warning group. Skim after Lesson 5.8.
    Cited in: 08-diagnostics

  • [CLANG-Expr] Clang's expression nodes, including RecoveryExpr — clang/include/clang/AST/Expr.h in llvm/llvm-project at llvmorg-23.1.2. Symbols: RecoveryExpr, DeclRefExpr.
    Why and when: RecoveryExpr is the error symbol of Algorithm 5.8.4: it keeps the broken subexpressions and marks the expression as containing errors so later checks stay quiet. Read after Lesson 5.8 §2.
    Cited in: 08-diagnostics

  • [CLANG-IdResolver] Clang's per-identifier chains of visible declarations — clang/lib/Sema/IdentifierResolver.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: IdentifierResolver::AddDecl, IdentifierResolver::RemoveDecl, IdentifierResolver::begin.
    Why and when: A single table with shadowing chains (Algorithm 5.2.4): each identifier points to its innermost declaration; leaving a scope removes the scope's declarations. Read after Lesson 5.2 §7.
    Cited in: 02-symbol-tables

  • [CLANG-Scope] Clang's parser-time scope objects — clang/include/clang/Sema/Scope.h in llvm/llvm-project at llvmorg-23.1.2. Symbols: Scope, Scope::AddDecl, Scope::ScopeFlags.
    Why and when: The scope marks of Algorithm 5.2.4: each Scope remembers the declarations made in it so that ActOnPopScope can remove them. Read with [CLANG-IdResolver] after Lesson 5.2.
    Cited in: 01-scoping-disciplines

  • [CLANG-SemaDecl] Clang's semantic analysis of declarations — clang/lib/Sema/SemaDecl.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: Sema::CheckShadow, Sema::ImplicitlyDefineFunction, Sema::ActOnPopScope.
    Why and when: -Wshadow (Lesson 5.1), implicit function declarations as a declare-before-use failure (Lesson 5.3) and the scope pop that ends lifetimes of names. Search for the symbols; the file is huge.
    Cited in: 01-scoping-disciplines, 03-name-resolution-strategies

  • [CLANG-SemaExpr] Clang's semantic analysis of expressions (name uses become DeclRefExprs) — clang/lib/Sema/SemaExpr.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: Sema::BuildDeclRefExpr, Sema::ActOnIdExpression, Sema::DiagnoseEmptyLookup.
    Why and when: AST annotation (Lesson 5.6 §2): a resolved name becomes a DeclRefExpr pointing at its declaration; DiagnoseEmptyLookup starts typo correction. Read after Lesson 5.6.
    Cited in: 06-where-results-live

  • [CLANG-SemaLookup] Clang's name lookup, ADL and typo correction — clang/lib/Sema/SemaLookup.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: Sema::LookupName, Sema::ArgumentDependentLookup, TypoCorrectionConsumer::addName, Sema::CorrectTypo.
    Why and when: Core reading. Unqualified lookup through scopes, ADL's associated namespaces (Algorithm 5.4.5) and the typo-correction rule of Lesson 5.8 (a unique best candidate with \(3d \le\) the typo's length) (addName rejects when TypoLen / ED < 3). Read after Lessons 5.4 and 5.8.
    Cited in: overview, 04-overloading-adl-hygiene, 08-diagnostics

  • [CLANG-SemaOverload] Clang's overload resolution — clang/lib/Sema/SemaOverload.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: OverloadCandidateSet::BestViableFunction, isBetterOverloadCandidate, CompareImplicitConversionSequences.
    Why and when: The tournament of Algorithm 5.4.3 with the C++ tie-breakers: find BestViableFunction's two loops (pick a winner, then check it beats everyone). Read after Lesson 5.4 §2.
    Cited in: 04-overloading-adl-hygiene

  • [CLANG-SemaStmt] Clang's semantic analysis of statements (range-based for) — clang/lib/Sema/SemaStmt.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: Sema::BuildCXXForRangeStmt.
    Why and when: A range-based for keeps its own AST node but gets implicit __range, __begin, __end variables — partial desugaring (Lesson 5.6 §5).
    Cited in: 06-where-results-live

  • [CLANG-TextDiag] Clang's textual diagnostic printer (carets, ranges, fix-its) — clang/lib/Frontend/TextDiagnostic.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: TextDiagnostic::emitParseableFixits, TextDiagnostic::emitSnippetAndCaret.
    Why and when: How spans become carets and fix-its become fix-it: lines (Definition 5.8.1). Read after Lesson 5.8 §2 and run clang -fdiagnostics-parseable-fixits.
    Cited in: 08-diagnostics

  • [CLANG-Uninit] Clang's uninitialized-variables analysis (-Wuninitialized, -Wsometimes-uninitialized) — clang/lib/Analysis/UninitializedValues.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: runUninitializedVariablesAnalysis, TransferFunctions.
    Why and when: A may/must uninitialized analysis over Clang's CFG, a warning rather than definite assignment's error. Read after Lesson 5.7 §4.
    Cited in: 07-control-flow-checks

  • [CPY-Symtable] CPython's symbol-table pass (local, global, free and cell variables) — Python/symtable.c in python/cpython at v3.13.0. Symbols: analyze_name, symtable_analyze, PySymtable_Build.
    Why and when: A separate pass that classifies every name per scope before code generation (LEGB, PEP 227): why assignment anywhere in a function makes a name local. Read after Lesson 5.1 §2.
    Cited in: 01-scoping-disciplines, 06-where-results-live

  • [GCC-CDecl] GCC's C front end scopes and bindings — gcc/c/c-decl.cc in gcc-mirror/gcc at releases/gcc-15.1.0. Symbols: bind, pop_scope, warn_if_shadowing, c_binding.
    Why and when: A single table with per-name binding chains plus a per-scope list, restored by pop_scope: Algorithm 5.2.4 with an intrusive undo log. Read after Lesson 5.2 §7.
    Cited in: 01-scoping-disciplines, 02-symbol-tables, 08-diagnostics

  • [GCC-CPCall] GCC's C++ overload resolution — gcc/cp/call.cc in gcc-mirror/gcc at releases/gcc-15.1.0. Symbols: joust, tourney, build_new_function_call, compare_ics.
    Why and when: tourney and joust are the tournament of Algorithm 5.4.3 by name; compare_ics ranks conversion sequences. Read after Lesson 5.4 §2.
    Cited in: 04-overloading-adl-hygiene

  • [GCC-NameLookup] GCC's C++ name lookup, including ADL — gcc/cp/name-lookup.cc in gcc-mirror/gcc at releases/gcc-15.1.0. Symbols: lookup_arg_dependent, name_lookup::adl_expr.
    Why and when: GCC's version of Algorithm 5.4.5: the associated namespaces and classes of each argument type. Read after Lesson 5.4 §3, next to [CLANG-SemaLookup].
    Cited in: 04-overloading-adl-hygiene

  • [GCC-Spellcheck] GCC's spelling suggestions — gcc/spellcheck.cc in gcc-mirror/gcc at releases/gcc-15.1.0. Symbols: get_edit_distance, get_edit_distance_cutoff, best_match.
    Why and when: OSA distance with cheaper case changes and a length-dependent cutoff: compare with Clang's rule (Lesson 5.8, Algorithm 5.8.6) after Lesson 5.8 §2.
    Cited in: 08-diagnostics

  • [GCC-Uninit] GCC's uninitialized-use warnings on SSA form — gcc/tree-ssa-uninit.cc in gcc-mirror/gcc at releases/gcc-15.1.0. Symbols: warn_uninitialized_vars, warn_uninit.
    Why and when: Uninitialized uses found on SSA after optimization, so the result depends on -O: the opposite design choice to definite assignment (Lesson 5.7 §6).
    Cited in: 07-control-flow-checks

  • [GHC-RdrEnv] GHC's renamer environments (persistent maps of local names) — compiler/GHC/Types/Name/Reader.hs in ghc/ghc at ghc-9.4.7-release. Symbols: LocalRdrEnv, extendLocalRdrEnv, lookupLocalRdrEnv.
    Why and when: A persistent environment (Algorithm 5.2.7) passed down the renamer's recursion; every binder gets a fresh Unique. Read after Lesson 5.2 §7.
    Cited in: 02-symbol-tables

  • [GO-Info] go/types Info (side tables of the type checker's results) — src/go/types/api.go in golang/go at go1.24.7. Symbols: Info, Info.Types, Info.Defs, Info.Uses, Info.Scopes.
    Why and when: Side tables in their purest form (Lesson 5.6 §3): maps from AST nodes to objects and types, filled only if the caller asks for them. Read after Lesson 5.6.
    Cited in: 06-where-results-live

  • [GO-Scope] go/types scopes (a map per scope with a parent pointer) — src/go/types/scope.go in golang/go at go1.24.7. Symbols: Scope, Scope.Insert, Scope.Lookup, Scope.LookupParent (in scope2.go).
    Why and when: The stack of tables of Algorithm 5.2.2 written as a tree of scopes that stays alive after checking, so tools can query it. Read after Lesson 5.2 §7.
    Cited in: 02-symbol-tables

  • [JAVAC-Attr] javac's attribution (name and type analysis) including illegal forward references — src/jdk.compiler/share/classes/com/sun/tools/javac/comp/Attr.java in openjdk/jdk at jdk-21+35. Symbols: Attr.checkInit, Attr.visitIdent.
    Why and when: JLS §8.3.3 in code: a field initializer may not read a later field by simple name (Lesson 5.3 §2). Read checkInit after Lesson 5.3.
    Cited in: 03-name-resolution-strategies

  • [JAVAC-Flow] javac's flow analysis (reachability and definite assignment) — src/jdk.compiler/share/classes/com/sun/tools/javac/comp/Flow.java in openjdk/jdk at jdk-21+35. Symbols: Flow.AliveAnalyzer, Flow.AssignAnalyzer.
    Why and when: JLS chapters 14.22 and 16 in code: AliveAnalyzer is Definition 5.7.1 and AssignAnalyzer Algorithm 5.7.5 with when-true/when-false sets. Read after Lesson 5.7.
    Cited in: 07-control-flow-checks

  • [LEAN-Expr] Lean 4 expressions (locally nameless terms) — src/Lean/Expr.lean in leanprover/lean4 at v4.19.0. Symbols: Expr.bvar, Expr.fvar, Expr.instantiate1, Expr.abstract.
    Why and when: bvar holds a de Bruijn index and fvar a free variable: the locally nameless design of [Cha12] in a production prover. Read after Lesson 5.2 §6.
    Cited in: 02-symbol-tables

  • [LLVM-EditDistance] LLVM's Levenshtein distance with an upper bound — llvm/include/llvm/ADT/edit_distance.h in llvm/llvm-project at llvmorg-23.1.2. Symbols: ComputeEditDistance, ComputeMappedEditDistance.
    Why and when: Algorithm 5.8.6 with one row of memory and an early exit when every cell exceeds the bound. Read after Lesson 5.8 §2; StringRef::edit_distance calls it.
    Cited in: 08-diagnostics

  • [LLVM-ImmutableMap] LLVM's persistent AVL-tree map (ImmutableMap / ImmutableSet.h) — llvm/include/llvm/ADT/ImmutableMap.h in llvm/llvm-project at llvmorg-23.1.2. Symbols: ImmutableMap, ImmutableMap::Factory::add, ImutAVLTree.
    Why and when: A production persistent map with path copying and hash-consed nodes (Algorithm 5.2.7), used by the Clang Static Analyzer's program states. Read ImmutableSet.h's ImutAVLFactory::add_internal after the L2 milestone.
    Cited in: 02-symbol-tables

  • [ROSLYN-DA] Roslyn's definite-assignment pass for C# — src/Compilers/CSharp/Portable/FlowAnalysis/DefiniteAssignment.cs in dotnet/roslyn at Visual-Studio-2022-Version-17.8. Symbols: DefiniteAssignmentPass.
    Why and when: C#'s definite assignment on bound trees, with the state as a bit vector per variable slot. Read after Lesson 5.7 §7 next to [JAVAC-Flow].
    Cited in: 07-control-flow-checks

  • [RUSTC-Borrowck] rustc's report of uses of possibly-uninitialized variables (E0381) — compiler/rustc_borrowck/src/diagnostics/conflict_errors.rs in rust-lang/rust at 1.94.1. Symbols: MirBorrowckCtxt::report_use_of_moved_or_uninitialized.
    Why and when: Definite assignment done on MIR by the borrow checker's maybe-uninitialized dataflow, reported as E0381. Read after Lesson 5.7 §7.
    Cited in: 07-control-flow-checks

  • [RUSTC-BRG] rustc's collection pass (the module tree before resolution) — compiler/rustc_resolve/src/build_reduced_graph.rs in rust-lang/rust at 1.94.1. Symbols: build_reduced_graph, BuildReducedGraphVisitor.
    Why and when: The collect pass of Algorithm 5.3.2: every item enters its module before any body is resolved, which makes items order-independent. Read after Lesson 5.3 §2.
    Cited in: 03-name-resolution-strategies

  • [RUSTC-DepGraph] rustc's dependency graph and red–green marking — compiler/rustc_query_system/src/dep_graph/graph.rs in rust-lang/rust at 1.94.1. Symbols: DepGraph, DepGraphData::try_mark_green, DepGraphData::try_mark_previous_green.
    Why and when: Algorithm 5.6.4 in production: a node is green if all its dependencies are green, re-executed otherwise, and early cutoff when the new result's fingerprint is unchanged. Read after Lesson 5.6 §4.
    Cited in: 06-where-results-live

  • [RUSTC-EditDistance] rustc's edit distance and "a similar name exists" suggestions — compiler/rustc_span/src/edit_distance.rs in rust-lang/rust at 1.94.1. Symbols: edit_distance, find_best_match_for_name.
    Why and when: OSA distance with a length-based cutoff and case-insensitive tie-breaking: compare with Clang's rule after Lesson 5.8 §2.
    Cited in: 08-diagnostics

  • [RUSTC-Hygiene] rustc's hygiene (syntax contexts and expansion marks) — compiler/rustc_span/src/hygiene.rs in rust-lang/rust at 1.94.1. Symbols: SyntaxContext, ExpnData, Transparency.
    Why and when: Identifiers compare by (name, syntax context), the resolution rule of Lesson 5.4 §2. Read after the rustc hygiene box of Lesson 5.4.
    Cited in: 04-overloading-adl-hygiene

  • [RUSTC-Imports] rustc's import resolution fixed point — compiler/rustc_resolve/src/imports.rs in rust-lang/rust at 1.94.1. Symbols: ImportResolver::resolve_imports, ImportResolver::finalize_imports.
    Why and when: Algorithm 5.3.4: rounds of import resolution while the number of undetermined imports decreases, then error reporting for the rest. Read after Lesson 5.3 §3.
    Cited in: 03-name-resolution-strategies

  • [RUSTC-Late] rustc's late resolution of local names (ribs) — compiler/rustc_resolve/src/late.rs in rust-lang/rust at 1.94.1. Symbols: Rib, RibKind, LateResolutionVisitor, LateResolutionVisitor::resolve_ident_in_lexical_scope.
    Why and when: A stack of ribs, each a map from identifiers to resolutions, searched from the innermost: Algorithm 5.2.2 in production. Read after Lesson 5.2 §7.
    Cited in: 01-scoping-disciplines, 02-symbol-tables

  • [RUSTC-Lowering] rustc's AST-to-HIR lowering of for loops and ? — compiler/rustc_ast_lowering/src/expr.rs in rust-lang/rust at 1.94.1. Symbols: LoweringContext::lower_expr_for, LoweringContext::lower_expr_try.
    Why and when: Desugaring (Definition 5.6.5, Algorithm 5.6.6): for becomes loop + match on Iterator::next before type checking. Read after Lesson 5.6 §5.
    Cited in: 06-where-results-live

  • [RUSTC-MBE] rustc's macros by example (matching in macro_parser.rs/macro_rules.rs, transcription here) — compiler/rustc_expand/src/mbe/transcribe.rs in rust-lang/rust at 1.94.1. Symbols: transcribe_pnr, macro_rules.rs expand_macro, macro_rules.rs try_match_macro, macro_parser.rs.
    Why and when: Where transcription applies a fresh mark to the tokens a macro introduces, so that its let x cannot capture the caller's x (Lesson 5.4 §2).
    Cited in: 04-overloading-adl-hygiene

  • [RUSTC-TypeckErrors] rustc's type-checking diagnostics (break/continue outside a loop, E0268) — compiler/rustc_hir_typeck/src/errors.rs in rust-lang/rust at 1.94.1. Symbols: BreakNonLoop, OutsideLoop.
    Why and when: The diagnostic structs behind E0268, the rustc analogue of Pebble's E0304. Read after Lesson 5.7 §7.
    Cited in: 07-control-flow-checks

  • [RUSTC-TypeckResults] rustc's per-body side tables of type-checking results — compiler/rustc_middle/src/ty/typeck_results.rs in rust-lang/rust at 1.94.1. Symbols: TypeckResults, TypeckResults::node_type, TypeckResults::type_dependent_defs.
    Why and when: Side tables keyed by HirId instead of AST fields (Lesson 5.6 §3). Read after Lesson 5.6 and compare with [GO-Info].
    Cited in: 06-where-results-live

  • [RUSTC-TypeIR] rustc's de Bruijn indices for bound regions and types — compiler/rustc_type_ir/src/lib.rs in rust-lang/rust at 1.94.1. Symbols: DebruijnIndex, DebruijnIndex::shifted_in.
    Why and when: De Bruijn indices outside the lambda calculus: late-bound regions under for<'a> binders use DebruijnIndex with shifted_in/shifted_out (Lemma 5.2.13). Read after Lesson 5.2 §7.
    Cited in: 02-symbol-tables

  • [SG-Crate] The scopegraphs Rust crate (scope graphs as a library) — scopegraphs/src/lib.rs in metaborg/rust-scopegraphs at v0.3.3. Symbols: ScopeGraph, query.
    Why and when: Scope graphs with regular path queries and label orders as a Rust library, from the Statix group. Read its documentation after the ★ part of the lab.
    Cited in: 03-name-resolution-strategies

  • [SWIFT-CSRanking] Swift's ranking of constraint-system solutions — lib/Sema/CSRanking.cpp in swiftlang/swift at swift-6.1-RELEASE. Symbols: ConstraintSystem::compareSolutions, isDeclAsSpecializedAs.
    Why and when: Overloading resolved by comparing whole solutions by score, then declarations by "more specialized": a different architecture from Algorithm 5.4.3 (Lesson 5.4 §6).
    Cited in: 04-overloading-adl-hygiene

  • [SWIFT-DIsrc] Swift's definite-initialization pass on SIL — lib/SILOptimizer/Mandatory/DefiniteInitialization.cpp in swiftlang/swift at swift-6.1-RELEASE. Symbols: LifetimeChecker, LifetimeChecker::doIt.
    Why and when: Definite initialization done on an IR instead of the AST, including the stored properties of self in initializers. Read after Lesson 5.7 §7.
    Cited in: 07-control-flow-checks

  • [SWIFT-Evaluator] Swift's request evaluator (memoization and cycle detection) — lib/AST/Evaluator.cpp in swiftlang/swift at swift-6.1-RELEASE. Symbols: Evaluator, Evaluator::checkDependency, Evaluator::diagnoseCycle.
    Why and when: Queries (Lesson 5.6 §4) with cycle diagnostics: a request that depends on itself is reported rather than overflowing the stack. Read with [SWIFT-RequestEvaluator].
    Cited in: 06-where-results-live

  • [V8-TDZ] V8's bytecode generator (temporal-dead-zone hole checks) — src/interpreter/bytecode-generator.cc in v8/v8 at 13.4.1. Symbols: BytecodeGenerator::BuildThrowIfHole, HoleCheckElisionScope.
    Why and when: How let/const hoisting is implemented: the slot holds a "hole" and accesses check it, eliding redundant checks per basic block (Lesson 5.1 §2).
    Cited in: 01-scoping-disciplines

  • [Z3-Ast] Z3's term representation (quantified variables as de Bruijn indices) — src/ast/ast.h in Z3Prover/z3 at z3-4.15.3. Symbols: var, quantifier.
    Why and when: De Bruijn indices in an SMT solver: bound variables of quantifiers are var nodes with an index. Read after Lesson 5.2 §7.
    Cited in: 02-symbol-tables

Official documentation and specifications

  • [BASH-Manual] GNU Bash Reference Manual: Shell Functions. Bash 5.2. link
    Why and when: Dynamic scoping still in daily use: a function sees its caller's local variables. Read the section, then run the Bash box of Lesson 5.1.
    Cited in: 01-scoping-disciplines

  • [BISON-Manual] GNU Bison manual: semantic values, actions and mid-rule actions. Bison 3.8.2. link
    Why and when: $$, $n and mid-rule actions are S-attributed evaluation during an LR parse; $0 and $<type>0 read the value below the rule on the stack (an inherited attribute). Read "Actions" and "Mid-Rule Actions" after Lesson 5.5 §3.
    Cited in: 05-attribute-grammars

  • [CLANG-Internals] Clang internals manual (diagnostics, fix-it hints). LLVM 23.1.2. link
    Why and when: The section "The Diagnostics Subsystem" and "Fix-It Hints": what makes a good fix-it and how ranges and notes are attached. Read after Lesson 5.8 §2.
    Cited in: 08-diagnostics

  • [CPP-Draft] Working Draft, Programming Languages — C++ (eel.is HTML rendering). link
    Why and when: [basic.scope.pdecl] (point of declaration), [basic.lookup.argdep] (ADL) and [over.match] (overload resolution). Look up the stable names cited in Lessons 5.1 and 5.4.
    Cited in: 04-overloading-adl-hygiene

  • [CSHARP-DA] C# language specification: Variables, §9.4 Definite assignment. link
    Why and when: C#'s version of the JLS rules, with the definite-assignment state per statement and expression kind. Read after Lesson 5.7 §4 and compare with [JLS21-16].
    Cited in: 07-control-flow-checks

  • [ECMA24] ECMA-262, 15th edition: ECMAScript 2024 Language Specification. ES2024. link
    Why and when: §14.3.1 (let and const: the temporal dead zone), §14.3.2 (var hoisting) and §14.7.4 (per- iteration bindings of for (let …)). Read after Lesson 5.1 §2.
    Cited in: 01-scoping-disciplines

  • [JASTADD] JastAdd reference manual (reference attribute grammars in Java). JastAdd2 2.3.6. link
    Why and when: Syntax of syn, inh, eq and circular attributes as used in the JastAdd box of Lesson 5.5. Read before running the box.
    Cited in: 05-attribute-grammars

  • [JLS21-14] The Java Language Specification, SE 21: Chapter 14, Blocks, Statements, and Patterns. link
    Why and when: §14.22 (unreachable statements): the syntax-directed "can complete normally" rules that Definition 5.7.1 adapts, including the if (false) exception. Read after Lesson 5.7 §2.
    Cited in: 07-control-flow-checks

  • [JLS21-16] The Java Language Specification, SE 21: Chapter 16, Definite Assignment. link
    Why and when: Core reading. The most precise specification of definite assignment in any mainstream language, with when-true/when-false rules for conditions. Read §16.2.10–16.2.12 (loops) after Lesson 5.7 §4.
    Cited in: overview, 07-control-flow-checks

  • [JLS21-6] The Java Language Specification, SE 21: Chapter 6, Names. link
    Why and when: §6.3 (scope of a declaration) and §6.4 (shadowing and obscuring, and the rule that a local may not redeclare a local). Read after Lesson 5.1 §6.
    Cited in: 01-scoping-disciplines

  • [JLS21-8] The Java Language Specification, SE 21: Chapter 8, Classes. link
    Why and when: §8.3.3 (restrictions on field references in initializers): order-independent members with one declare-before-use exception. Read after Lesson 5.3 §2.
    Cited in: 03-name-resolution-strategies

  • [PEP227] PEP 227 – Statically Nested Scopes. link
    Why and when: The design document of Python's LEGB rule and of why a name assigned anywhere in a function is local throughout it (UnboundLocalError). Read after Lesson 5.1 §2.
    Cited in: 01-scoping-disciplines

  • [RFC1560] Rust RFC 1560: Name resolution changes (globs, shadowing, item-like imports). link
    Why and when: The rules Lesson 5.3 §2 summarizes: explicit imports shadow globs and two globs conflict only when the name is used. Read after Lesson 5.3.
    Cited in: 03-name-resolution-strategies

  • [ROSLYN-Overview] Roslyn: Understand the .NET Compiler Platform SDK model. link
    Why and when: Immutable syntax trees, compilations and semantic models computed on demand: the query architecture of Lesson 5.6 as an API. Read after Lesson 5.6 §4.
    Cited in: 06-where-results-live

  • [RUSTC-DevDiag] rustc dev guide: Errors and lints (diagnostic structure, suggestions, applicability). link
    Why and when: Multi-span labels, notes and machine-applicable suggestions as rustc defines them. Read after Lesson 5.8 §2 and compare with Definition 5.8.1.
    Cited in: 08-diagnostics

  • [RUSTC-DevIncr] rustc dev guide: Incremental compilation in detail. link
    Why and when: The red–green algorithm, try_mark_green and fingerprint-based early cutoff described by the rustc team. Read after Lesson 5.6 §4.
    Cited in: 06-where-results-live

  • [RUSTC-DevQueries] rustc dev guide: Queries — demand-driven compilation. link
    Why and when: How rustc is organized as queries with memoized results and providers. Read before Algorithm 5.6.4 in Lesson 5.6.
    Cited in: 06-where-results-live

  • [SALSA] The salsa book (incremental recomputation for rust-analyzer). salsa 0.23. link
    Why and when: Inputs, tracked functions, revisions and durability: the red–green algorithm as a library. Read "Overview" and "The red-green algorithm" after Lesson 5.6 §4.
    Cited in: 06-where-results-live

  • [SWIFT-DI] The Swift Programming Language: Initialization (two-phase initialization and safety checks). link
    Why and when: The user-facing rules that Swift's definite-initialization pass enforces: every stored property set before self is used. Read after Lesson 5.7 §1; the implementation is [SWIFT-DIsrc].
    Cited in: 07-control-flow-checks

  • [SWIFT-RequestEvaluator] Swift's request evaluator design. swift-6.1-RELEASE. link
    Why and when: Requests as memoized, cycle-checked queries: the architecture of Lesson 5.6 §4 in Swift. Read before [SWIFT-Evaluator].
    Cited in: 06-where-results-live

  • [SWIFT-TypeChecker] Swift's type checker design (constraints, overload sets, solution ranking). swift-6.1-RELEASE. link
    Why and when: How Swift resolves overloads inside a constraint solver and ranks complete solutions. Read the overview and "Comparing Solutions" after Lesson 5.4 §6.
    Cited in: 04-overloading-adl-hygiene