Chapter 5 exercises¶

You implement pebblec's name resolution and control-flow checks: every use of a name bound to its declaration, the three namespaces, loops and mutability, diagnostics with notes, error symbols and "did you mean" suggestions, then missing returns, unreachable code and definite assignment. In the comparison lab you resolve one small language with three symbol-table designs, compare them on correctness and cost, and decide alpha-equivalence with de Bruijn indices; the ★ milestone resolves a module language with a scope graph.

The contract is two functions of pebble/include/pebble/Sema/Sema.h: resolveNames(ModuleDecl*, ASTContext&, DiagnosticEngine&) and checkFlow(…). What they must record in the AST is listed in that header and in ResolutionDump.h: NameExpr::setDecl, CallExpr::setCalleeDecl/setBuiltin, StructLiteralExpr::setStructDecl, TypeRepr::setResolvedType (every type repr, nested ones included), BreakStmt/ContinueStmt::setTarget. The rules are §6, §12 and §13 of the Pebble specification (positions and notes: §13.2); the dump the golden tests compare is §14.3.
Your code goes anywhere under pebble/lib/Sema/Names/src/ (switch names). It starts with a Stub.cpp whose two functions stop with TODO(ch05): …; replace it and add files as you like. Semantic types come from the ASTContext (getIntType(), getStructType(S), getArrayType(T, N), getRefType(T, mut), getErrorType()).
Provided: the lexer and parser (Chapters 1 and 4; build with -DPEBBLE_USE_SOLUTION=lexer,parser if you skipped them), the AST, the diagnostics engine with codes E0301–E0315 and the notes note_previous_definition, note_declared_here, note_did_you_mean, note_declared_later, note_struct_contains, the tool ch05-resolve, and the corpus tests/ch05/Inputs/ with golden .resolved files.
The lab is specified in labs/ch05-binders/SPEC.md (requirements R1–R8, contracts include/binders/Binders.h and ★ include/binders/ScopeGraphs.h, milestones L1–L6); this page only orders it.

./course test 5                                                  # builds, then runs every test labelled ch05
ctest --preset linux -L '^ch05$' -R 'Names.E1'                   # one group while iterating (macOS: --preset macos)
build/linux/bin/ch05-resolve tests/ch05/Inputs/scopes.pbl        # your bindings and diagnostics on any file
build/linux/bin/ch05-resolve --names-only tests/ch05/Inputs/err-flow.pbl   # skip checkFlow

Before you start, every ch05.Names.* test and ch05.lit fail with TODO(ch05): E1-E4: implement name resolution (resolveNames), and every ch05.Binders.* test except Provided_* with TODO(ch05): L1…. The golden dumps were produced by the reference resolver and cross-checked against an independent Python resolver that threads persistent environments through the tree of the independent Python parser (tools/course/lib/pebble_names.py, run by tests/ch05/update_goldens.py): two symbol-table designs, one answer (Theorem 5.2.3). Diagnostics in the lit tests were written by hand from the spec.

Why ch05-resolve and not pebblec? pebblec runs resolveNames, then the type checker (Chapter 6), then checkFlow; until Chapter 6 is done, compiling stops at TODO(ch06). ch05-resolve runs your two phases on their own (pebble-spec §14.3).

Stuck? Work through the hints in order. The reference solution is in solutions/pebble/lib/Sema/Names/src/ (one possible design); look at it only after you pass the tests, or after an honest hour.

E1 · Block scopes, shadowing and "visible from the next statement"¶

Contract: resolveNames, locals and parameters · Spec: pebble-spec §6.3 · Tests: ch05.Names.E1_*, lit scopes.test · Lessons: 5.1, 5.2 (Algorithm 5.2.4)

Bind every NameExpr to its VarDecl or ParamDecl. A let/var is visible from the next statement to the end of its block; its initializer does not see it (let x = x + 1 reads the outer x); any binding may shadow any earlier one, in the same block or an outer one; a for variable is visible only in the loop body, and the bounds are resolved outside it. A use with no visible binding is E0301 at the name.

Hint 1 — where to start

Walk each function body recursively in source order with a symbol table for the value namespace. Declare a VarDecl only after resolving its initializer. Push a scope for every block; decide whether the function body shares the parameters' scope (either works, because shadowing is allowed).

Hint 2 — the key idea

Lesson 5.2's single table with scope marks gives \(O(1)\) lookups: a hash map from a name to the stack of its visible bindings, plus an undo log of declared names and one mark per open scope. A stack of llvm::StringMaps is also fine for this exercise (the lab measures the difference).

Hint 3 — a design sketch

A Resolver class with resolveFunction, resolveBlock, resolveStmt, resolveExpr (one switch on the node kind each) and a ScopedTable member. Every expression kind must be walked, including interpolated strings, struct-literal field values, casts and reference arguments — E1_NamesInEveryExpressionForm checks that no NameExpr is left unbound.

Done when: E1_* pass and ch05-resolve tests/ch05/Inputs/scopes.pbl equals scopes.resolved (the lit test diffs it).

E2 · Namespaces, order-independent items, builtins and types¶

Contract: resolveNames · Spec: pebble-spec §6.1–6.2, §5 (types) · Tests: E2_*, lit items.test, spec-examples.test · Lessons: 5.3 (Algorithm 5.3.2)

Resolve in two passes: collect every struct and function first, then resolve everything else, so that items can be used before their definition. Keep three namespaces: types (structs), functions (fn, extern fn, and the builtins print/write, recorded with setBuiltin), values. Resolve every TypeRepr — including the element of an array type and the pointee of a reference type, and the target of as — to a semantic type from the ASTContext; an unknown type name is E0303 and resolves to the error type.

Hint 1 — where to start

Pass 1 fills two maps, name → FunctionDecl* and name → StructDecl*. A call looks in the function map, a name expression in the value table, a type repr and a struct literal in the struct map.

Hint 2 — the key idea

let fib = fib(3); is legal: the call's fib is looked up among functions, the initializer's result is then bound to a value fib. print in a value position is not a value (E0309, E4), but let print = 3; print(print); is fine.

Hint 3 — a design sketch

const Type *resolveType(TypeRepr *T): builtin names → Ctx.getIntType() etc.; a struct → Ctx.getStructType(S); [T; N] → Ctx.getArrayType(resolveType(elem), N); &mut T → Ctx.getRefType(…, true); then T->setResolvedType(result) for every repr, even when the result is the error type.

Done when: E2_* pass and the lit tests items.test, spec-examples.test match.

E3 · Loops and mutability¶

Contract: resolveNames · Spec: pebble-spec §7 (break/continue), §6.4 · Tests: E3_*, lit err-loops.test, err-immutable.test · Lessons: 5.6 (annotation), 5.7 (loop context)

Set the target of every break and continue to the innermost enclosing while or for; outside a loop they are E0304 at the statement. Report an assignment (= or op=) whose target's root binding (strip parentheses, fields and indices) is a let, a for variable, a by-value parameter or a &T parameter as E0307 at the root name, with the note "declared here".

Hint 1 — where to start

A stack of the loops you are inside, pushed when you enter a loop body and popped when you leave it.

Hint 2 — the key idea

A parameter is assignable only if its type repr is &mut T; VarDecl::isMutable() distinguishes var from let and for variables. Resolve the target expression first, then look at the declaration its root name was bound to.

Done when: E3_* and the two lit tests pass.

E4 · Declaration errors, notes, error symbols and suggestions¶

Contract: resolveNames · Spec: pebble-spec §6.2–6.3, §13.2 · Tests: E4_*, lit err-duplicates.test, err-namespaces.test, err-structs.test, err-undeclared.test, err-recovery.test, err-nomain.test · Lessons: 5.8, 5.3

Report redefinitions (E0302: functions, structs, fields of one struct, parameters of one function) with a "previous definition" note; E0313 for a function named print/write; E0315 for pebble_ names; E0309/E0308 for a name found only in another namespace, with a "declared here" note; E0310 once per cycle of structs that contain each other (through arrays too), at the first struct of the cycle, with a note per field on the cycle; E0311 if there is no function main. For E0301/E0303 add a note: "declared here, after its use" if the name is declared later in the same function, otherwise "did you mean …?" by the rule of §13.2. No cascades: report each unresolved name once per item and namespace.

Hint 1 — where to start

Duplicates are found in pass 1. Error symbols: a set of already-reported names per namespace, cleared at the start of each function and each struct; a failed lookup of a name in the set stays silent.

Hint 2 — the key idea

Recursive structs are cycles in the graph "struct → struct of a field type (looking through arrays)". Find the strongly connected components (Tarjan's algorithm, or a DFS with colors if you prefer); a component with more than one struct, or one struct with a self-edge, is one E0310. The distance for suggestions is the optimal string alignment distance (Algorithm 5.8.6 with the transposition case); only a unique closest candidate with \(3d \le \ell\), \(\ell \ge 3\), is suggested.

Hint 3 — a design sketch

A TypoCorrector object that is given the typo and fed candidate names one by one (consider(name)), remembering the best distance and whether it is tied; for value names, feed it every name that is currently visible in your symbol table. For "declared later", collect the function's local declarations before resolving its body and look for one with the same name positioned after the use.

Done when: E4_* pass and all the err-* lit tests of this exercise match, notes included.

E5 · Missing returns and unreachable code¶

Contract: checkFlow · Spec: pebble-spec §12.3–12.4 · Tests: E5_*, lit err-flow.test (E0305 and W0314 lines) · Lesson: 5.7 (Definition 5.7.1, Algorithm 5.7.2)

checkFlow runs only if resolveNames succeeded. Report E0305 at the name of every function with a result type whose body can complete normally, and W0314 at the first statement that directly follows a return, break or continue in each block (once per block, in every nested block).

Hint 1 — where to start

One recursive predicate canComplete(Stmt*), written straight from Definition 5.7.1; loops always complete.

Done when: E5_* pass.

E6 · Definite assignment¶

Contract: checkFlow · Spec: pebble-spec §12.2 · Tests: E6_* (including 400 random programs checked against brute-force path enumeration, and 40 nested loops that must finish quickly), lit flow-ok.test, err-flow.test · Lesson: 5.7 (Definition 5.7.3, Algorithm 5.7.5)

Track scalar (int, float, bool, str) vars declared without an initializer. Report E0306 once per variable, at its first read in source order that is not definitely assigned, with a note at the declaration. Reads include x += e, &x, &mut x arguments and interpolations; an if without else assigns nothing definitely; loops may run zero times; after return/break/continue everything counts as assigned. The analysis must take time roughly linear in the function for Pebble programs (E6_DeeplyNestedLoopsStayFast).

Hint 1 — where to start

Number the tracked variables and use an llvm::BitVector per state, plus a flag for "unreachable". Write State exec(Stmt*, State in) returning the state after the statement.

Hint 2 — the key idea

Joins intersect, with "unreachable" as the identity. A loop's head state starts at the entry state and is recomputed as entry ⊓ body-exit ⊓ continue-states until it stops changing; break states flow to after the loop. Record bad reads during the iterations — the head states only shrink, so the last iteration's bad reads include the earlier ones.

Hint 3 — a design sketch

Keep a stack of {breaks, continues} states for the loops you are in. To avoid re-analyzing an inner loop on every iteration of the loops around it (2^depth work), remember each loop's exit state by its entry state and reuse it when the loop is entered with the same state again.

Done when: every ch05.Names.* test and ch05.lit pass.

Lab · One resolver, three symbol tables (and ★ scope graphs)¶

Specified in labs/ch05-binders/SPEC.md. Order of attack:

L1 — resolveWithScopeStack: a stack of hash tables (ch05.Binders.L1_*).
L2 — resolveWithPersistentMap: an immutable map with structural sharing (L2_*).
L3 — toDeBruijn (L3_*).
L4 — alphaEquivalent via L3 (L4_*).
L5 — large and pathological inputs (L5_*), then measure with build/<preset>/bin/ch05-bindbench and fill in the table of SPEC §4.
L6 ★ — resolveScopeGraph for the module language (L6_*).