Flashcards — Chapter 5¶
86 cards. Review them with spaced repetition in the terminal (./course flash 5) or export them to Anki (./course flash export 5). Here, click a card to reveal its back.
static-scope¶
Static scoping: how is the binding of a use chosen (Definition 5.1.2)?
Among the candidates (same name, declared before the use in an enclosing block), take the one in the innermost block, and in that block the last one in source order. It depends only on the program text.
Invariant of Algorithm 5.1.6 (walking outwards)?
Before examining block B, no block strictly inside B on the path from the use contains a candidate; so the first hit is the innermost, latest candidate (Lemma 5.1.9).
Cost of resolving one use by walking outwards, and with a table?
O(δ·b) for δ nesting levels and b statements per block; O(1) expected with a symbol table (Lesson 5.2), O(n) for the whole program.
Why do static bindings survive consistent renaming (Theorem 5.1.10)?
Renaming a declaration and its scope to a fresh name gives those uses a single candidate (the same declaration), and removing a non-winning candidate from other uses cannot change the innermost-latest choice.
dynamic-scope¶
Dynamic scoping: what is the binding of a use (Definition 5.1.4)?
The most recently created live binding of that name at the moment the use executes; it depends on the call chain, so one use can bind differently on different executions.
Deep vs shallow binding (Algorithms 5.1.7, 5.1.8)?
Deep: a stack of (name, binding) pairs scanned from the top at each use — O(h) lookup, free context switch. Shallow: one table of current bindings plus a save stack of old ones — O(1) lookup, a context switch must swap the table.
What is the funarg problem?
Under dynamic scoping a function's free names are bound in its caller's environment, so passing or calling a function from a different context changes the meaning of its body (Moses 1970); renaming a caller's local can change a callee.
Where does dynamic scoping survive today?
Bash functions see callers' locals; Common Lisp/Emacs Lisp special variables; Perl local; typed forms: Racket parameterize, Scala implicits/givens.
hoisting-tdz¶
Hoisting (Definition 5.1.5)?
A declaration's region is its whole block regardless of position: uses earlier in the block resolve to it (JavaScript var/let/function, Python locals).
Temporal dead zone?
The time between entering a block and executing a hoisted declaration; a use that runs there is an error (JS let/const: ReferenceError; Python: UnboundLocalError) instead of reading an outer binding.
When do hoisting and declaration-point visibility disagree (Proposition 5.1.12)?
Exactly when some enclosing block, at least as inner as the static binding's block, declares the name at or after the use's statement; without an intervening function body, every execution of such a use is in the dead zone.
Cost of TDZ checks at run time?
One flag ("hole") per binding and a check per possibly-dead access; V8 elides repeated checks of the same binding within a basic block (HoleCheckElisionScope).
scope-stack¶
Stack of hash tables (Algorithm 5.2.2): the operations?
enterScope pushes an empty table, exitScope pops it, declare writes the top table, lookup searches tables from top to bottom.
Complexity of the stack of hash tables?
enter/exit/declare O(1); lookup O(δ) expected, δ = number of open scopes. On \x0.…\x{d-1}. x0 … x{d-1} it probes d(d+1)/2 tables in total: quadratic.
Which compilers use a stack of per-scope tables?
Go's go/types (a map per Scope with a parent pointer), rustc's late resolution (ribs), CPython's symtable; Clang and GCC use a single table with chains instead.
scope-marks¶
Single table with scope marks (Algorithm 5.2.4)?
Per-name chains of declarations, an undo log of declared names, and a mark (log length) per open scope; exitScope pops the log down to the mark, popping each name's chain.
Invariant of the undo-log table (Lemma 5.2.5)?
chain[n] lists the declarations of n in open scopes, oldest first; the log entries above mark i are exactly the declarations of scope i; so top(chain[n]) = lookup(n).
Cost of the undo-log table?
lookup O(1) expected (one probe); exitScope O(k) for k declarations in the scope — amortized O(1) per declaration.
Clang's and GCC's single-table symbol tables?
Clang: IdentifierResolver chains per identifier plus Scope objects listing their decls (AddDecl/RemoveDecl). GCC C: c_binding chains per identifier (I_SYMBOL_BINDING), restored by pop_scope.
persistent-map¶
Persistent map?
Every update returns a new version and leaves all old versions unchanged and usable; a scope's environment is just a version, so nothing is popped.
Path copying in a balanced tree?
An insertion copies only the nodes on the root-to-leaf search path (and rotated nodes) and shares every other subtree: O(log n) new nodes per insert.
Resolution with a persistent map (Algorithm 5.2.7): invariant?
The environment passed to a statement maps each name to its static binding at the start of that statement; a binder calls insert and passes the new version down.
When is a persistent environment worth it?
When old environments must be kept: closures, incremental or parallel analysis, backtracking, functional compilers (GHC LocalRdrEnv, LLVM ImmutableMap in the static analyzer). It makes deep nesting O(log n) per lookup.
de-bruijn¶
De Bruijn index of a bound variable?
The number of binders strictly between the use and its binder (0 = the nearest): depth(use) − level(binder) − 1.
Why do de Bruijn indices decide alpha-equivalence (Theorem 5.2.11)?
Two terms are alpha-equivalent iff their nameless forms (indices for bound variables, names for free ones) are identical: binder names disappear.
Shift operation ↑^d_c?
Adds d to every free index ≥ c (indices below the cutoff c are bound inside); needed when a term moves under or out of binders during substitution.
Locally nameless representation?
Bound variables as de Bruijn indices, free variables as names; used by Lean 4 (Expr.bvar/fvar) and mechanized metatheory.
declare-before-use¶
Declare-before-use?
A name is visible only after its declaration (from the next statement on): one pass over the text resolves everything; C, Pascal and Pebble locals.
Why does one pass suffice for declare-before-use (Proposition 5.3.8)?
Every candidate of a use precedes it, so by the time the pass reaches the use, all candidates are in the table.
How does C cope with mutual recursion under declare-before-use?
Prototypes: a declaration before the definition, i.e. a manual pass 1. Clang still recognizes calls to undeclared functions via ImplicitlyDefineFunction (an error since C99).
order-independent¶
Two-pass resolution (Algorithm 5.3.2)?
Pass 1 collects every item of the order-independent region into a table (reporting redefinitions); pass 2 resolves all uses against it. Items may be used before they appear.
Order-independent region: what error replaces shadowing?
Two declarations of one name in one namespace are a redefinition error (Pebble E0302, with a note at the first).
Java's exception to order-independent members?
JLS §8.3.3: a field initializer may not read a later field by simple name (illegal forward reference); this.y and method bodies are fine.
module-imports¶
Import resolution by fixed point (Algorithm 5.3.4)?
Repeat rounds over the pending imports; each resolves (found/not found) or is undetermined (a pending import might still supply the name); stop when a round makes no progress.
Why does the import fixed point terminate (Theorem 5.3.10)?
Bindings are only added, never removed; each productive round removes at least one import from the finite pending set.
Rust glob imports: shadowing and conflicts?
An explicit import or item shadows a glob; two globs providing the same name conflict only if the name is used (E0659 ambiguous) — RFC 1560.
scope-graphs¶
Scope graph (Néron et al. 2015)?
Nodes are scopes and declarations; labeled edges P (to lexical parent), I (to an imported module's body), D (to a declaration). A reference resolves along well-formed paths, e.g. P* I? D, choosing by a label order.
Label order D < I < P means?
At each scope, its own declarations win; otherwise declarations of imported bodies; only then the parent scope.
Scope graph resolution vs environments (Theorem 5.3.11)?
With WF = P* I? D and D < I < P, the result equals env(s) = D(s) shadowing Imp(s) shadowing env(parent(s)).
overload-resolution¶
Viable function?
A candidate with the right number of parameters and an implicit conversion sequence from every argument to its parameter.
F better than G (Definition 5.4.2)?
No argument's conversion sequence is worse for F than for G, and at least one is strictly better (ranks Exact < Promotion < Conversion), then C++ tie-breakers.
Best viable function in two passes (Algorithm 5.4.3)?
Tournament: keep the winner of each comparison; then verify the winner beats every other viable function, else ambiguous. O(r·k) comparisons.
adl¶
Argument-dependent lookup?
For an unqualified call, also search the associated namespaces (and classes) of the argument types for functions of that name.
When is ADL suppressed?
When the callee is parenthesized, qualified, or ordinary lookup finds a class member, a block-scope function declaration or a non-function.
What can ADL add, and what not (Proposition 5.4.9)?
It only adds candidates, and only functions (and function templates): it never removes the ordinary lookup result.
hygiene¶
Macro hygiene?
Names introduced by a macro cannot capture or be captured by the user's names: identifiers compare by (name, syntax context), and each expansion adds a fresh mark.
Why does the C preprocessor capture names?
It pastes tokens without contexts, so a macro's local (e.g. int x) binds the argument's x after expansion.
rustc's hygiene data structure?
Every span carries a SyntaxContext (rustc_span/src/hygiene.rs); macro_rules! transcription applies a fresh mark to tokens the macro introduces.
ag-s-l¶
S-attributed vs L-attributed?
S: only synthesized attributes. L: every inherited attribute of X_k reads only the parent's inherited attributes and attributes of left siblings X_1…X_{k−1}.
One-pass evaluation (Algorithm 5.5.6)?
Visit children left to right; before visiting a child compute its inherited attributes; after all children, compute the node's synthesized ones — the order of a recursive-descent parser.
Evaluation for any non-circular AG (Algorithm 5.5.5)?
Build the tree's dependency graph and evaluate in a topological order (Kahn), O(size of the graph).
ag-circularity¶
When is an attribute grammar circular?
If the dependency graph of some parse tree has a cycle (Definition 5.5.3).
Knuth's circularity test?
Compute, per nonterminal, the set of IO graphs (inherited→synthesized dependencies) of all its trees by fixed point; check every production with every combination of child graphs for a cycle. Keep sets, not unions (1971 correction).
Complexity of circularity testing?
Decidable but intrinsically exponential (Jazayeri–Ogden–Rounds 1975); strong non-circularity and Kastens' ordered AGs are polynomial subclasses.
rag¶
Reference attribute grammar?
Attributes may be references to tree nodes (decl() points at a declaration) and may take parameters (lookup(name)); rules may read attributes through references.
Demand-driven evaluation (Algorithm 5.5.11)?
Evaluate an attribute when requested, recursively, caching final values; an attribute requested while in progress is an error unless declared circular.
Circular attributes?
Start from bottom and iterate the equations to a fixed point over a finite-height lattice (nullability, reachability, definite assignment).
ast-annotation¶
AST annotation?
Semantic results written into fields of the tree's nodes (NameExpr::Decl, Clang's DeclRefExpr pointer); O(1) access, but the tree is mutable and one field per fact.
What does pebblec's resolveNames annotate?
NameExpr → its Decl, call callees, NamedTypeRepr → the resolved type, struct literals → struct decl, break/continue → the target loop.
Clang's annotation of a resolved name?
Sema::BuildDeclRefExpr creates a DeclRefExpr that points to the ValueDecl and carries the type.
side-tables¶
Side table?
A map from stable node identities to facts, kept outside an immutable tree (Go types.Info, rustc TypeckResults).
Side tables vs annotations (Proposition 5.6.7)?
Equivalent for later phases if node identities are injective; side tables keep the tree immutable and let several analyses coexist, at the cost of a hash lookup.
go/types Info fields?
Types (expr → type and value), Defs (declaring idents), Uses (referring idents), Implicits, Selections, Scopes, Instances, FileVersions.
query-incremental¶
Query system?
Inputs plus pure derived queries that call each other; each execution records its dependencies; results are memoized per revision.
Red–green re-validation (try_mark_green)?
Walk a memo's dependencies in order: an input changed after the memo was verified → red; a derived dependency is re-validated or recomputed, and if it changed → red; if all are green, reuse the memo.
Early cutoff?
A recomputed query whose result fingerprint is unchanged keeps its changedAt revision, so its readers stay green.
desugaring¶
Desugaring?
A meaning-preserving translation of surface constructs into a smaller core language, construct by construct, so later phases handle fewer constructs.
Pebble for → while desugaring: the continue pitfall?
continue must jump to the increment: the desugaring rewrites it to k = k &+ 1; continue; otherwise the loop never advances.
Why must desugaring temporaries be fresh?
So they cannot capture or be captured by user names — the hygiene condition (rustc's iter in lowered for loops is unnameable).
reachability¶
Pebble's cc(s) for if/else and while?
cc(if c B1 else B2) = cc(B1) ∨ cc(B2); cc(if c B) = true; cc(while) = true (conditions are not interpreted); return/break/continue are false.
When does pebblec report E0305 and W0314?
E0305 at the function name if the body can complete normally and the function has a result type; W0314 at a statement directly after return/break/continue, once per block.
Why is structural reachability conservative (Theorem 5.7.6)?
If some execution completes a statement normally, cc says true; it may say true for code that never completes (while true), never the reverse.
definite-assignment¶
Definite-assignment lattice?
Sets of definitely-assigned variables ordered by ⊆, plus U (unreachable) on top; meet is ∩ with U as identity; height |V| + 1.
Legal read under definite assignment?
A read of tracked x is legal iff the state is U or x ∈ S; pebblec reports the first illegal read of each variable (E0306) with a note at its declaration.
Why does the dataflow answer equal the all-paths answer?
The transfer functions (add x, remove x, identity) distribute over ∩, so MFP = MOP (Kam–Ullman); finite height gives termination.
Loop rule in Algorithm 5.7.5?
The head state is In ⊓ out ⊓ continues, iterated until stable; the exit state is head ⊓ breaks (zero iterations are possible).
spans-fixits¶
Diagnostic as data?
Severity, stable code, message, primary span, notes (span, message) and fix-its (span, replacement) — renderable as text, JSON or IDE actions.
From byte offset to line:column?
Binary-search the sorted line-start table for the last start ≤ b: line = its index, col = b − start + 1. O(log L) after one O(n) scan.
Fix-it kinds?
Insertion (empty span), removal (empty text), replacement; a set is applicable when the spans do not overlap. Clang: FixItHint::CreateInsertion/Removal/Replacement.
recovery-poisoning¶
Cascading error?
A diagnostic that disappears once the first error is fixed as suggested; reporting it only adds noise.
Error symbol (Algorithm 5.8.4)?
After reporting an undeclared name, record it as poisoned in its namespace for the current item; later lookups fail silently. Each (name, namespace) is reported once per item (Theorem 5.8.9).
Error types in production compilers?
GCC error_mark_node, Clang RecoveryExpr and the contains-errors bit, rustc's {type error}: every check accepts them silently.
typo-correction¶
Levenshtein vs OSA vs Damerau–Levenshtein?
Levenshtein: insert/delete/substitute. OSA: also swap two adjacent characters, but no substring edited twice. Damerau–Levenshtein: transpositions without that restriction (a metric).
Clang's typo-correction acceptance rule?
Levenshtein distance d to the best visible name; suggest only if that name is unique at distance d, the typo has length ℓ ≥ 3 and 3d ≤ ℓ (TypoLen / ED < 3 rejects).
BK-tree query?
At a node at distance d from the query, search only children whose edge label k satisfies d − t ≤ k ≤ d + t; exact for a metric by the triangle inequality.
Why can OSA not be used in a BK-tree?
It violates the triangle inequality: osa(ca, abc) = 3 > osa(ca, ac) + osa(ac, abc) = 1 + 1, so pruning could miss matches (Lemma 5.8.11).