Theory test — Chapter 5¶
55 questions; you pass at 80 %. This page shows the questions only: take the test in the terminal, where every answer is graded and explained.
./course quiz 5 # interactive
./course quiz template 5 -o answers/ch05.yaml # or fill in a file ...
./course quiz grade 5 # ... and grade it
static-binding-trace · mapping · 1 pt · 01-scoping-disciplinesC-like program (the notation of the drill resolve-scopes; declarations are visible from the
next statement on, Definition 5.1.2):
var y; // d1 (global)
fn h() { print(y); } // u1
fn k() {
print(y); // u2
var y; // d2
{
var y; // d3
print(y); // u3
}
print(y); // u4
h();
}
fn main() {
var y; // d4
k();
print(y); // u5
}
Under static scoping, which declaration does each use bind to?
u1, u2, u3, u4, u5shadow-candidates · set · 1 pt · 01-scoping-disciplinesSame program as the previous question. Give the candidate set \(C(u_4)\) of Definition 5.1.2
(all declarations named y that u4 follows).
dynamic-binding-trace · mapping · 1 pt · 01-scoping-disciplinesSame program, now under dynamic scoping (Definition 5.1.4), executed from main. The
global d1 is created before main starts. Which declaration does each use bind to when it
executes?
u1, u2, u3, u4, u5deep-vs-shallow · sequence · 1 pt · 01-scoping-disciplinesSame execution, implemented by shallow binding (Algorithm 5.1.8): one table \(T\) and a
save stack \(S\) of old bindings. Declaring d1 pushes \((y, \text{unbound})\). When u1
executes, list the old bindings stored in \(S\), from bottom to top (write unbound for
the first).
hoisting-tdz-js · single · 1 pt · 01-scoping-disciplinesWhat does this JavaScript program print (node 22)?
let x = 1;
function f() { console.log(x); let x = 2; }
try { f(); } catch (e) { console.log(e.constructor.name); }
- 1
- 2
- undefined
- ReferenceError
python-unbound · single · 1 pt · 01-scoping-disciplinesx = 1
def f():
print(x)
x = 2
f()
What happens, and why?
- It prints 1: the assignment comes after the print.
- It raises UnboundLocalError: the assignment makes x local to the whole function body.
- It raises NameError: x is not defined anywhere visible.
- It prints 2: Python evaluates all assignments of a function first.
scope-stack-probes · number · 1 pt · 02-symbol-tablesA stack of hash tables (Algorithm 5.2.2) holds, bottom to top: the global table {a}, a
function table {b}, a block table {c}, and an inner block table {d}. A probe is one
membership test in one table. How many probes in total do the four lookups a, c, d,
e (e is declared nowhere) make?
stack-quadratic · number · 1 pt · 02-symbol-tablesThe lab's family \(P_d\) = \x0. \x1. … \x{d-1}. x0 x1 … x{d-1}. With a stack of hash tables
(one table per binder), how many table probes do the \(d\) lookups make in total for
\(d = 100\)?
undo-log-state · mapping · 1 pt · 02-symbol-tablesAlgorithm 5.2.4 (one table, per-name chains, an undo log and scope marks). One scope is open
at the start (marks = [0], log empty). Run: declare(a, d1), enterScope(),
declare(b, d2), declare(a, d3), enterScope(), declare(b, d4), declare(c, d5),
exitScope(). Give then lookup(a), lookup(b), lookup(c) (write unbound if none)
and the length of the log.
a, b, c, logfind-clang-idresolver · text · 1 pt · 02-symbol-tablesIn clang/lib/Sema/IdentifierResolver.cpp (LLVM 23.1.2), which IdentifierResolver member
function takes a declaration off its name's chain when Sema leaves the declaration's scope?
(Give the function name.)
persistent-versions · mapping · 1 pt · 02-symbol-tablesResolve \(T\) = \x. \y. (\x. x y) (\z. x z) with a persistent map (Algorithm 5.2.7). Name
the binders λx₁ (outer), λy, λx₂ (inner), λz. Give the binder of each use — use1 = the
x in \x. x y, use2 = the y, use3 = the x in \z. x z, use4 = the z — and
the number of map versions created besides the empty map \(E_0\).
use1, use2, use3, use4, versionspath-copy-nodes · number · 1 pt · 02-symbol-tablesA persistent AVL tree with path copying (the lab's PersistentMap) holds 7 keys in a
perfectly balanced tree of height 3. You insert a key larger than all 7. How many new nodes
does the insertion allocate?
debruijn-indices · sequence · 1 pt · 02-symbol-tablesGive the de Bruijn indices (Definition 5.2.8; 0 = nearest binder) of the variable
occurrences of \x. \y. x (\z. z y x) y, in source order.
debruijn-shift · sequence · 1 pt · 02-symbol-tablesPerform one β-step on the nameless term \((\lambda.\ 1\ 0\ 2)\ 0\) using
\((\lambda.\, t)\, s \longrightarrow \uparrow^{-1}_{0}([0 \mapsto \uparrow^{1}_{0} s]\, t)\).
Give the indices of the resulting application, left to right.
one-pass-forward · set · 1 pt · 03-name-resolution-strategiesfn a() -> int { return b(); } // c1: the call b()
fn b() -> int { return c() + a(); } // c2: c(), c3: a()
fn c() -> int { return 1; }
fn main() { print(a()); } // c4: a()
A one-pass, declare-before-use resolver treats items like locals (visible from the next
item on). Which calls does it fail to resolve?
find-clang-implicit · text · 1 pt · 03-name-resolution-strategiesIn clang/lib/Sema/SemaDecl.cpp (LLVM 23.1.2), which Sema member function creates the
implicit declaration int f() for a call to an undeclared function in C89 mode (and whose
use is an error in C99 and later)?
two-pass-items · mapping · 1 pt · 03-name-resolution-strategiesfn f() -> int { return g(); } // line 1
fn g() -> int { return 1; } // line 2
fn g() -> int { return 2; } // line 3
struct S { a: T } // line 4
struct T { b: int } // line 5
fn main() { print(f()); } // line 6
With Algorithm 5.3.2, give the line of the declaration the call g() binds to (call),
the line of the E0302 redefinition error (error), and the line of the declaration the
field type T binds to (type).
call, error, typejava-forward-ref · single · 1 pt · 03-name-resolution-strategiesclass A {
int x = y + 1; // (1)
int y = 2;
int z = this.y + 1; // (2)
void m() { System.out.println(w); } // (3)
int w;
}
Which lines does javac (JDK 21) reject?
- (1) only
- (1) and (2)
- (1) and (3)
- none: class members are order-independent
glob-shadowing · single · 1 pt · 03-name-resolution-strategiesmod a { pub fn f() {} pub fn g() {} }
mod b { pub fn f() {} }
use a::*;
use b::*;
fn main() { g(); f(); }
What does rustc 1.94.1 do?
- Compiles: the later glob wins, f is b::f.
- Compiles: the earlier glob wins, f is a::f.
- Error E0659 at f(): f is ambiguous between the two globs; g() is fine.
- Error at both lines use a::; and use b::; because they conflict.
import-fixpoint-rounds · mapping · 1 pt · 03-name-resolution-strategiesAlgorithm 5.3.4 visits the pending imports in this order in every round:
mod d { use crate::a::g; } // visited first
mod a { pub use crate::b::*; }
mod b { pub use crate::c::g; }
mod c { pub fn g() {} }
In which round is each import resolved?
d, a, bscope-graph-resolve · mapping · 1 pt · 03-name-resolution-strategiesThe lab's module language (Definition 5.3.6; imports are resolved first with \(P^{*} D\);
references use \(P^{*} I^{?} D\) with \(D < I < P\); imports are not transitive):
1 def x;
2 module M {
3 def y;
4 module N { def x; }
5 }
6 module K {
7 import M;
8 def x;
9 ref x; ref y; ref N.x; ref M.y;
10 }
11 ref y;
Give the line of the declaration each reference resolves to, or unresolved. Keys:
x, y, N.x, M.y (line 9) and top-y (line 11).
x, y, N.x, M.y, top-ylabel-order · single · 1 pt · 03-name-resolution-strategiesdef x; # line 1
module A { def x; } # line 2
module C { import A; ref x; } # line 3
With the label order \(D < I < P\), what does ref x in C resolve to?
- the x of line 1: the lexical parent is searched first
- the x of line 2: at scope C, the path I D beats the path P D
- ambiguous: both paths have one D edge
- unresolved: imports are only used for qualified names
overload-ics-table · mapping · 1 pt · 04-overloading-adl-hygienevoid f(int, long); // F1
void f(long, int); // F2
void f(double, double); // F3
f(1, 2); // call1
f(1.5f, 2.5f); // call2
f(1, 2L); // call3
Apply Algorithm 5.4.3 with the C++ ranks (Exact < Promotion < Conversion). Give the result
of each call: F1, F2, F3 or ambiguous.
call1, call2, call3find-clang-bestviable · text · 1 pt · 04-overloading-adl-hygieneOverloadCandidateSet::BestViableFunction in clang/lib/Sema/SemaOverload.cpp (LLVM
23.1.2) runs a tournament and then checks the winner against every other candidate. Which
function does it call for each pairwise "is this candidate better than that one?" test?
adl-candidates · mapping · 1 pt · 04-overloading-adl-hygienenamespace lib { struct Buf {}; void dump(Buf); void dump(int); } // L1, L2
namespace app { struct Log {}; void dump(Log, lib::Buf); } // A
void dump(double); // G
void t1(app::Log l, lib::Buf b) { dump(l, b); } // call1
void t2(app::Log l, lib::Buf b) { void dump(double); dump(l, b); } // call2
Give the candidate set of each call (Algorithm 5.4.5), using the labels L1, L2, A, G. For
call2, the block-scope declaration redeclares G.
call1, call2adl-parens · multi · 1 pt · 04-overloading-adl-hygienenamespace geo { struct Point {}; int norm1(Point); } and a variable geo::Point p; in a
function at global scope with no other norm1 visible. Which calls compile?
norm1(p)(norm1)(p)geo::norm1(p)::norm1(p)
hygiene-contexts-rust · number · 1 pt · 04-overloading-adl-hygienemacro_rules! add_x { ($e:expr) => {{ let x = 10; $e + x }} }
fn main() { let x = 1; println!("{}", add_x!(x * 2)); }
What does the program print (rustc 1.94.1)?
cpp-capture · number · 1 pt · 04-overloading-adl-hygiene#define ADD_X(e) ({ int x = 10; (e) + x; }) /* GNU statement expression */
int main(void) { int x = 1; printf("%d\n", ADD_X(x * 2)); return 0; }
What does it print (clang 23.1.2)?
ag-classify · mapping · 1 pt · 05-attribute-grammarsClassify each attribute grammar as S (S-attributed), L (L-attributed, not S) or
none (neither), per Definition 5.5.4. Occurrences are written k.a (0 = left-hand side).
- G1: \(E \to E\ T\):
0.v = 1.v + 2.v; \(E \to T\):0.v = 1.v; \(T \to \texttt{n}\):0.v = n. Only synthesized attributes. - G2: \(S \to A\ B\):
1.i = 0,2.i = 1.s,0.v = 2.s; \(A \to \texttt{a}\):0.s = 0.i; \(B \to \texttt{b}\):0.s = 0.i. (\(A, B\): inh \(i\), syn \(s\).) - G3: \(S \to A\ B\):
1.i = 2.s,2.i = 0,0.v = 1.s; \(A\) and \(B\) as in G2.
G1, G2, G3ag-topo-order · sequence · 1 pt · 05-attribute-grammarsPascal-style declarations: \(D \to L\ T\) with 1.inh = 2.type, 0.n = 1.n;
\(T \to \texttt{int}\): 0.type = int; \(L \to L\ \texttt{,}\ \texttt{id}\): 1.inh = 0.inh,
0.n = 1.n + 1; \(L \to \texttt{id}\): 0.n = 1. The tree of a, b : int has nodes (preorder)
D1, L2, L3, T4. Give the order of Algorithm 5.5.5 (Kahn) when the ready instance with the
smallest node number (ties: attribute name) is always taken first.
knuth-test-cycle · multi · 1 pt · 05-attribute-grammars\(S \to A\ A\) with 1.i = 2.s, 2.i = 1.s, 0.v = 1.s; \(A \to \texttt{x}\) with 0.s = 0.i;
\(A \to \texttt{y}\) with 0.s = 0. Which trees have a cyclic dependency graph?
- S(A(x), A(x))
- S(A(x), A(y))
- S(A(y), A(x))
- S(A(y), A(y))
circularity-complexity · single · 1 pt · 05-attribute-grammarsWhich statement about deciding circularity of attribute grammars is correct?
- It is undecidable, because there are infinitely many trees.
- It is decidable in polynomial time by merging all IO graphs of each nonterminal.
- It is decidable, and every algorithm needs exponential time in the worst case; ordered AGs are a polynomially recognizable subclass.
- It is decidable in linear time with demand-driven evaluation.
rag-lookup · mapping · 1 pt · 05-attribute-grammarsA RAG resolves names with decl() = lookup(name), where a block's lookup equation for its
child \(k\) scans children \(k-1, \dots, 0\) for a declaration and otherwise asks the block's
own inherited lookup. The tree:
{ var x /*d1*/; use x /*u1*/;
{ use x /*u2*/; var x /*d2*/; use x /*u3*/; }
use y /*u4*/; }
Give decl() of each use (none if unbound).
u1, u2, u3, u4rag-circular · set · 1 pt · 05-attribute-grammarsNullability as a circular attribute (Algorithm 5.5.11, bottom = false, iterate to a fixed
point): \(A \to B\ C \mid \texttt{x}\); \(B \to C \mid \varepsilon\); \(C \to A\ B \mid \texttt{y}\).
Which nonterminals are nullable?
annotation-fields · mapping · 1 pt · 06-where-results-livefn g(a: int) -> bool { var t: bool; t = a > 0; return t; }
How many NameExpr::Decl annotations (value) and how many NamedTypeRepr annotations
(type) does resolveNames write for this function?
value, typefind-clang-declrefexpr · text · 1 pt · 06-where-results-liveIn clang/lib/Sema/SemaExpr.cpp (LLVM 23.1.2), which Sema member function (several
overloads) creates the AST node that records the declaration a name refers to — Clang's
annotation of a resolved use?
side-table-equivalence · single · 1 pt · 06-where-results-liveProposition 5.6.7 says a side table can replace AST annotations. What does the proof need
from node identities?
- They must be dense integers so that the table is an array.
- They must be injective: two different nodes never share an identity.
- They must be stable across edits, or the table is wrong.
- Nothing: any hash of the node works.
go-info-maps · text · 1 pt · 06-where-results-liveGo's types.Info (src/go/types/api.go, go1.24.7) keeps the checker's results in maps
keyed by AST nodes. Which field maps each identifier that refers to an object (as opposed
to declaring it)?
red-green-trace · set · 1 pt · 06-where-results-liveThe query graph of Lesson 5.6 §3: source → parse; parse → items, bodyF, bodyG;
resolveF reads [items, bodyF]; resolveG reads [items, bodyG]; checkF reads
[resolveF]; checkG reads [resolveG]. The user changes the type of f's parameter
(so items changes); g's body does not mention that type, so resolveG's value is
unchanged. Both checks are requested. Which queries have their function executed
(Algorithm 5.6.4)?
early-cutoff · single · 1 pt · 06-where-results-liveWhat is early cutoff in a red–green query system?
- Stopping a query when it takes too long and reporting a cycle.
- A re-executed query whose new result has the same fingerprint keeps its old changedAt revision, so the queries that read it can be marked green without running.
- Skipping the recomputation of every query whose inputs have not been read in this revision.
- Discarding the dependency graph after an edit and recomputing everything on demand.
desugar-continue · mapping · 1 pt · 06-where-results-livefor i in 0..4 { if i == 2 { continue; } print(i); } is desugared by Algorithm 5.6.6
(continue becomes k = k &+ 1; continue;). How many times is k < e evaluated (tests)?
A naive desugaring leaves continue unchanged, so it skips the increment: how many
values does it print before it loops forever (naive)?
tests, naiverust-for-mir · single · 1 pt · 06-where-results-liveWhat does rustc's AST→HIR lowering turn for pat in expr { body } into?
let mut i = 0; while i < expr.len() { let pat = expr[i]; body; i += 1; }match IntoIterator::into_iter(expr) { mut iter => loop { match Iterator::next(&mut iter) { None => break, Some(pat) => body } } }- A dedicated
Fornode that survives until MIR building. expr.for_each(|pat| body)
cc-verdicts · mapping · 1 pt · 07-control-flow-checksPebble functions with result type int (Definition 5.7.1). For each body, answer E0305
(missing return) or ok.
- A:
{ if c { return 1; } else { while true { } } } - B:
{ while c { return 1; } return 0; } - C:
{ if c { return 1; } else { return 2; } print(1); } - D:
{ { return 1; } }
A, B, C, Djava-while-true · single · 1 pt · 07-control-flow-checksstatic int f() { while (true) { } } — what do javac (JDK 21) and Pebble say?
- Both reject it: missing return.
- javac accepts it (a while with constant-true condition and no break cannot complete normally); Pebble reports E0305.
- javac rejects it; Pebble accepts it.
- Both accept it.
find-clang-fallthrough · text · 1 pt · 07-control-flow-checksIn clang/lib/Sema/AnalysisBasedWarnings.cpp (LLVM 23.1.2), CheckFallThrough returns an
enumerator of ControlFlowKind. Which one means "some paths fall off the end and some do
not" (the case of "non-void function does not return a value in all control paths")?
da-errors · set · 1 pt · 07-control-flow-checksfn f(c: bool) -> int {
var a: int;
var b: int;
if c { a = 1; } else { b = 2; }
print(a); // r1
while c { b = 3; break; }
print(b); // r2
a = 4;
return a + b; // r3 reads a, r4 reads b
}
Which reads are illegal under definite assignment (Algorithm 5.7.5)?
da-mop-mfp · single · 1 pt · 07-control-flow-checksWhy does Algorithm 5.7.5 (an iterative fixed point) compute exactly the meet over all paths?
- Because Pebble has no goto.
- Because the transfer functions are distributive (f(S ⊓ S') = f(S) ⊓ f(S')), so the fixed-point solution equals MOP (Kam–Ullman).
- Because the lattice has finite height.
- Because loops are unrolled until every path has been enumerated.
da-lattice-height · number · 1 pt · 07-control-flow-checksA function has 4 tracked variables. What is the height of the definite-assignment lattice
of Definition 5.7.3 (subsets of the 4 variables plus U), i.e. the number of steps in its
longest strictly increasing chain?
span-line-col · mapping · 1 pt · 08-diagnosticsA file's text is let a = 1;⏎let total = a + 2;⏎⏎print(totl);⏎ (⏎ = one newline byte).
Its line table is \([0, 11, 30, 31]\). The span of totl starts at byte 37. Give its line
and column as Algorithm 5.8.2 computes them (1-based, bytes).
line, colfind-clang-fixits · text · 1 pt · 08-diagnosticsWhich class in clang/include/clang/Basic/Diagnostic.h (LLVM 23.1.2) represents one
fix-it edit, with static constructors CreateInsertion, CreateRemoval and
CreateReplacement?
poison-count · number · 1 pt · 08-diagnosticsfn f() -> int {
let a = zz + 1;
let b = zz * a;
return q(b) + q(zz) + w;
}
fn g() -> int { return zz; }
fn main() { print(f() + g()); }
zz, q and w are declared nowhere. How many diagnostics does resolveNames report with
error symbols (Algorithm 5.8.4)?
gcc-error-mark · single · 1 pt · 08-diagnosticsWhat does GCC's C front end do after reporting "'x' undeclared (first use in this function)"?
- It declares x as an int so that later uses type-check.
- It binds x to error_mark_node in the function's scope, so later uses in the same function are silent; the note 'each undeclared identifier is reported only once' explains this.
- It stops compiling the function.
- It records x in a global list and reports every use at the end.
lev-osa-count · mapping · 1 pt · 08-diagnosticsFor the typo hieght and the name height, give the Levenshtein distance (lev), the OSA
distance (osa), and whether Clang's rule (unique best, \(\ell \ge 3\), \(3d \le \ell\) with
Levenshtein) suggests height when it is the only visible name (clang: yes/no).
lev, osa, clangclang-threshold · set · 1 pt · 08-diagnosticsThe visible names are count, total and index. Which of the typos cnt, totl,
idnex, countr get a suggestion under Clang's rule (Levenshtein, unique best, \(\ell \ge 3\),
\(3d \le \ell\))?
bk-visited · mapping · 1 pt · 08-diagnosticsThe BK-tree of Lesson 5.8 §3 (Levenshtein): root count with edges count —2→ counter,
count —4→ scope, count —5→ cursor, scope —1→ score, scope —5→ total,
cursor —5→ store, cursor —6→ index. Query scor with tolerance 1 (Algorithm 5.8.7).
Which words are visited (their distance computed), and which match?
visited, matches