Chapter 5 · Names, Scopes & Semantic Analysis¶
Part 1 · Front End · about 2–3 weeks · Previous: Ch 4 · Next: Ch 6
The problem¶
A parser (Chapter 4) turns text into a tree, but the tree does not yet say what any name means. Semantic analysis starts by answering, for every identifier occurrence, which declaration it denotes — under the language's scoping discipline, across blocks, functions and modules, with overloading, argument-dependent lookup and macros where the language has them — and by rejecting programs whose control flow is wrong in ways the grammar cannot see: a function that can fall off its end, a break outside a loop, a variable read before it was assigned. The input is a syntax tree; the output is the same tree with every use bound to a declaration (as annotations, side tables or queries), plus diagnostics with precise spans, notes and suggestions, and no cascades. In pebblec this is resolveNames and checkFlow (pebble/include/pebble/Sema/Sema.h), which the type checker (Ch 6), definite-initialization-dependent lowering (Ch 11) and every later chapter rely on.
What you will be able to do¶
- Resolve every name of a program under static and dynamic scoping by hand, with the "visible from the next statement", hoisting and temporal-dead-zone rules, and prove that static bindings survive renaming (Theorem 5.1.10).
- Implement and compare four symbol tables — a stack of hash tables, one table with scope marks, a persistent map, de Bruijn indices — and explain their costs (quadratic, linear, \(n \log n\)) on the lab's pathological inputs.
- Resolve order-independent items, imports with globs and cycles, and module references in a scope graph, and prove the two-pass and fixed-point algorithms correct.
- Rank C++ overload candidates, compute an ADL candidate set, and explain hygiene as binding by (name, syntax context).
- Classify an attribute grammar as S-, L-attributed or neither, order its attribute instances, run Knuth's circularity test, and explain why the problem is exponential.
- Implement
pebblec's resolver and flow checks (resolveNames,checkFlow) with error symbols and Clang-style typo correction, and pass./course test 5. - State definite assignment as a monotone dataflow problem, trace it to a fixed point, and prove it sound.
- Find where Clang (
IdentifierResolver,BestViableFunction,CorrectTypo), GCC, rustc, javac and Swift implement each technique.
Prerequisites: Ch 2 (grammars and parse trees, for attribute grammars), Ch 4 (the Pebble AST and its dumper, hygiene in Lesson 4.8). Chapter 14 generalizes Lesson 5.7's dataflow analysis; you do not need it first.
Notation¶
Shared notation follows the house notation (§1 sets and functions, §2 lattices, §3 graphs, §5 grammars, §7 dataflow, §8 complexity). In this chapter:
| Symbol | Meaning |
|---|---|
| \(d\), \(u\), \(\mathrm{name}(\cdot)\) | a declaration (binding occurrence), a use (applied occurrence), their spelling (Lesson 5.1) |
| \(\mathrm{blk}(n)\), \(B_1 \sqsupseteq B_2\) | the innermost block containing \(n\); block \(B_1\) encloses (or is) \(B_2\) (Lesson 5.1) |
| \(d \prec u\) | \(u\) follows \(d\) in \(d\)'s region (Definition 5.1.1) |
| \(C(u)\), \(\mathrm{res}_s(u)\), \(\mathrm{res}_d(u)\), \(\mathrm{res}_h(u)\) | candidates of \(u\); its static, dynamic and hoisted binding (Definitions 5.1.2–5.1.5) |
| \(\mathrm{scope}(d)\) | the uses bound to \(d\) (Definition 5.1.3) |
| \(\delta\), \(h\) | nesting depth of blocks; height of the dynamic environment stack |
| \(\sigma = \langle m_0, \dots, m_k \rangle\) | the abstract symbol table: a list of finite maps, innermost last (Definition 5.2.1) |
| \(\uparrow^{d}_{c}\), \([j \mapsto s]\), \(\mathrm{FV}(t)\) | de Bruijn shift by \(d\) above cutoff \(c\), substitution of index \(j\), free indices (Lesson 5.2 §2) |
| \(P\), \(I\), \(D\), \(\mathit{WF}\), \(<\) | scope-graph edge labels (parent, import, declaration), a well-formedness regex, a label order (Definition 5.3.5) |
| \(\mathrm{ICS}_i(F)\), \(F \succ G\) | the implicit conversion sequence of argument \(i\) for candidate \(F\); \(F\) is better than \(G\) (Definitions 5.4.1–5.4.2) |
| \(\mathrm{assoc}(T)\) | the namespaces associated with type \(T\) for ADL (Definition 5.4.4) |
| \(\mathrm{Syn}(X)\), \(\mathrm{Inh}(X)\), \(X_k.a\), \(D(t)\) | synthesized and inherited attributes of \(X\); an attribute occurrence; the dependency graph of tree \(t\) (Definitions 5.5.1–5.5.2) |
| \(\mathrm{IO}(X)\), \(\mathrm{IDS}(X)\), \(\mathrm{IDP}(p)\) | Knuth's sets of IO graphs; Kastens' induced dependencies (Definitions 5.5.7, 5.5.9) |
| \(\mathrm{cc}(s)\) | "statement \(s\) can complete normally" (Definition 5.7.1) |
| \(S \subseteq V\), \(\mathsf{U}\), \(\sqcap\) | a definite-assignment state, "unreachable" (top), the meet (intersection with \(\mathsf{U}\) as identity) (Definition 5.7.3) |
| \(\mathrm{MOP}(p)\), \(\mathrm{MFP}\) | meet over all paths, maximal fixed point (Definition 5.7.4; NOTATION §7) |
| \(\mathrm{lev}\), \(\mathrm{osa}\), \(\mathrm{dam}\) | Levenshtein, optimal string alignment, Damerau–Levenshtein distances (Definition 5.8.5) |
| \(\ell\) | the length of a typo; a suggestion needs distance \(d\) with \(3d \le \ell\) |
The definite-assignment lattice is ordered with \(\mathsf{U}\) ("unreachable") at the top and \(\emptyset\) at the bottom; the analysis computes a greatest fixed point starting from the entry state — the dual orientation of NOTATION §2's default, as in dominators.
Technique map¶
| Family | Techniques (origin) | Lesson |
|---|---|---|
| Scoping disciplines | static (lexical) scoping with block, function and module scope and shadowing (ALGOL 60, Naur et al. 1960/63; Scheme, Sussman & Steele 1975); dynamic scoping with deep and shallow binding (LISP 1.5, McCarthy 1962; the funarg problem, Moses 1970; Baker 1978); hoisting and the temporal dead zone (JavaScript var; ES2015 let; Python function locals, PEP 227) |
5.1 |
| Symbol tables | stack of hash tables (Dragon book §2.7); one hash table with scope marks and an undo log (Aho et al.; Clang, GCC); persistent maps — path-copying balanced trees (Driscoll, Sarnak, Sleator & Tarjan 1989) and HAMTs (Bagwell 2001); de Bruijn indices and levels (de Bruijn 1972) and the locally nameless representation (McBride & McKinna 2004; Charguéraud 2012) | 5.2 |
| Name-resolution strategies | declare-before-use in one pass (C, Pascal); order-independent multi-pass resolution (Java members, Rust/Swift items); module and import resolution with globs, shadowing and cyclic imports by fixed point (rustc, RFC 1560); scope graphs (Néron, Tolmach, Visser & Wachsmuth 2015; Statix, van Antwerpen et al. 2018) | 5.3 |
| Overloading, ADL and hygiene | overload resolution with candidate sets, viable functions and conversion ranking (C++ ARM, Ellis & Stroustrup 1990; ISO C++ [over.match]; Swift's solution ranking); argument-dependent (Koenig) lookup (ISO C++ [basic.lookup.argdep]); macro hygiene as binding by syntax context (Kohlbecker et al. 1986; Dybvig et al. 1992; Flatt 2016) | 5.4 |
| Attribute grammars | synthesized/inherited attributes, dependency graphs, S- and L-attributed definitions and one-pass evaluation (Knuth 1968; Lewis, Rosenkrantz & Stearns 1974); the circularity test (Knuth 1968/1971) and its EXPTIME-completeness (Jazayeri, Ogden & Rounds 1975); ordered AGs (Kastens 1980); reference and circular AGs (Hedin 2000; Magnusson & Hedin 2007; JastAdd, Ekman & Hedin 2007) | 5.5 |
| Where results live | AST annotation (Clang); side tables (Go types.Info, rustc TypeckResults); query-based incremental analysis with red–green re-validation (rustc queries, salsa, Swift's request evaluator, Roslyn; Adapton, Hammer et al. 2014); desugaring and HIR lowering (rustc lower_expr_for; Pebble's for scheme) |
5.6 |
| Control-flow-sensitive checks | structural reachability, missing returns, loop context (JLS §14.22); definite assignment as a monotone dataflow problem (JLS ch. 16; C#; Swift DI; Rust E0381; Kam & Ullman 1977) | 5.7 |
| Diagnostics | spans, notes and fix-its (Clang, rustc); error recovery and poisoning with error symbols and error types (GCC error_mark_node, Clang RecoveryExpr); typo correction by edit distance (Levenshtein 1966; Damerau 1964; Wagner & Fischer 1974) and BK-trees (Burkhard & Keller 1973) |
5.8 |
flowchart LR
subgraph SCOPE[Scoping]
ST[Static scope<br/>ALGOL 60] ---|vs| DY[Dynamic scope<br/>LISP 1.5]
ST -->|where in the block| HO[Hoisting / TDZ<br/>JS, Python]
end
subgraph TABLES[Symbol tables]
SS[Stack of tables] -->|one probe| SM[Scope marks + undo log]
SS -->|never undo| PM[Persistent maps<br/>1989, HAMT 2001]
PM -->|drop names| DB[de Bruijn / locally nameless<br/>1972, 2012]
end
subgraph STRAT[Resolution strategies]
DBU[Declare-before-use] -->|collect first| OI[Order-independent]
OI -->|modules, globs| IMP[Import fixed point]
IMP -->|one model| SG[Scope graphs<br/>2015, Statix 2018]
end
subgraph MULTI[Many meanings]
OV[Overloading] --> ADL[ADL]
HY[Hygiene<br/>1986]
end
subgraph AGS[Attribute grammars]
SL[S/L-attributed<br/>Knuth 1968] --> CI[Circularity, OAG<br/>1971, 1975, 1980]
CI -->|references, demand| RAG[RAGs, JastAdd<br/>2000]
end
subgraph RES[Results and checks]
ANN[Annotation] --> SIDE[Side tables] --> Q[Queries<br/>red-green]
DES[Desugaring / HIR]
REACH[Reachability] --> DA[Definite assignment<br/>JLS 16, dataflow]
DIAG[Spans, fix-its] --- POI[Poisoning] --- TYPO[Typo correction<br/>edit distance, BK-trees]
end
SM --> OI
SL -. the resolver is an L-attributed walk .-> SM
RAG -. demand-driven, cached .-> Q
HY -. binding by context .-> SG
DA -. generalized in Ch 14 .-> QWho uses what¶
| System | Technique | Notes |
|---|---|---|
| Clang/LLVM 23 | block scopes with one identifier chain per name (IdentifierResolver); declare-before-use at file scope in C; overload resolution and ADL (SemaOverload.cpp, SemaLookup.cpp); AST annotation with implicit nodes; RecoveryExpr poisoning; Levenshtein typo correction; CFG-based -Wsometimes-uninitialized |
Lessons 5.2, 5.4, 5.6, 5.8 |
| GCC 15 | binding chains with shadowed links (c-decl.cc); joust overload ranking; error_mark_node error symbols; OSA typo correction (spellcheck.cc); optimizer-based -Wmaybe-uninitialized |
Lessons 5.2, 5.4, 5.7, 5.8 |
| rustc 1.94 | ribs (stack of tables) for locals; order-independent items; import fixed point with determinacy; hygiene by SyntaxContext; HIR lowering of for; side tables keyed by HirId; queries with red–green; E0381 from the MIR borrow checker; OSA suggestions |
Lessons 5.2, 5.3, 5.6, 5.7, 5.8 |
| javac 21 | order-independent members, illegal forward references for fields; JLS §14.22 reachability and ch. 16 definite assignment (Flow.java) |
Lessons 5.3, 5.7 |
| Swift 6 | order-independent types and functions; overloads ranked in the constraint solver; request evaluator; DI on SIL | Lessons 5.4, 5.6, 5.7 |
Go 1.24 (go/types) |
a scope tree with parent pointers; results in types.Info side tables |
Lessons 5.2, 5.6 |
| GHC 9.4 | persistent environments in the renamer, a unique per binder | Lesson 5.2 |
| CPython 3.11 | function/class/module scopes computed by symtable; UnboundLocalError as a dead zone |
Lesson 5.1 |
| Z3 4.15, Lean 4 | de Bruijn indices for bound variables (locally nameless in Lean) | Lesson 5.2 |
| JastAdd 2.3 / ExtendJ | reference attribute grammars, demand-driven and circular attributes | Lesson 5.5 |
Spoofax/Statix, scopegraphs crate |
scope graphs with regular path well-formedness and label orders | Lesson 5.3 |
pebblec |
two-pass resolution, one table with scope marks, error symbols, OSA suggestions with Clang's threshold, AST annotation, structural reachability and dataflow definite assignment | Exercises |
Comparison¶
The rows are the lessons' comparison tables (§8), verbatim, in lesson order.
| Technique | Power / precision | Speed (asymptotic · practical) | Output / error quality | Implementation effort | Typical use |
|---|---|---|---|---|---|
| Static scoping | Meaning fixed by the text; bindings survive renaming (Theorem 5.1.10); closures well defined | \(O(1)\) per use with a table (Lesson 5.2) · resolved once at compile time | Errors at compile time, at the use; shadowing warnings possible | Low: one walk with a scope table | C, C++, Java, Rust, Swift, Python, JavaScript, Pebble |
| Dynamic scoping | Meaning depends on the call path; renaming a caller's local changes a callee (funarg problem) | \(O(h)\) deep, \(O(1)\) shallow · per execution, never ahead of time | Errors only at run time, far from the cause | Lowest in an interpreter; no compile-time resolution possible | Shells, Perl local, special variables, parameterize |
| Hoisting and the temporal dead zone | Same bindings as static scoping inside whole-block regions; dead-zone uses detected (TDZ) or silently default (var) |
As static, plus a run-time check per possibly-dead use (removable when dominated) | TDZ: a precise run-time error; var: none at all |
Low; the check is a flag per binding | JavaScript, Python function locals, Swift locals (at compile time) |
| Stack of hash tables | Exact static bindings (Theorem 5.2.3); scopes can be kept as objects | \(O(\delta)\) lookup · 196 ms at depth 8000 in the lab, \(\Theta(d^2)\) on \(P_d\) | Easy to list "names visible here" for suggestions | Lowest | Go, rustc ribs, Roslyn binders, teaching compilers |
| One table + scope marks | Exact (Lemma 5.2.5); state is destroyed as the walk moves on | \(O(1)\) lookup and amortized exit | Visible names = non-empty chains; suggestions need a scan | Low | Clang, GCC, pebblec |
| Persistent maps | Exact (Proposition 5.2.10); every version survives for free | \(O(\log s)\) (AVL) or near \(O(1)\) (HAMT) · 8.2 ms at depth 8000 in the lab | Environments can be stored in closures, IDE caches, error messages | Medium: a persistent tree or a HAMT library | GHC renamer, functional-language compilers, static analyzers (LLVM ImmutableMap), IDEs |
| De Bruijn indices / locally nameless | Alpha-equivalence is syntactic equality (Theorem 5.2.11); capture-free substitution (Lemma 5.2.13) | \(O(n)\) conversion · 2.6 ms at depth 8000 in the lab | Unreadable without names: keep names on binders for printing | Medium; shifting bugs are subtle | Proof assistants (Lean, Coq), SMT solvers, core IRs, type-level binders (rustc) |
| Declare-before-use | Correct only if every binding precedes its use (Proposition 5.3.8); mutual recursion needs forward declarations | \(O(n)\), one pass · the fastest | Clear "undeclared" errors, but also for names declared later in the file | Lowest | C, Pascal, locals in most languages, Pebble function bodies |
| Order-independent resolution | Any order within the region (Theorem 5.3.9); redefinitions must be errors | \(O(n + m)\), two passes | Errors can point to both definitions; "used before declared" is impossible | Low: a collect pass | Java members, Rust/Swift/Haskell items, Pebble items |
| Module and import resolution | Qualified names, globs, re-exports and cycles (Theorem 5.3.10) | \(O(I^2 c)\) worst case, a few rounds in practice | Ambiguity and "unresolved import" errors with notes for each candidate (E0659 box) | High: determinacy, globs, visibility | Rust, Java, Haskell, Python (at run time), C++20 modules |
| Scope graphs | Language-independent; lexical, import, inheritance and record lookups in one model (Theorem 5.3.11) | \(O(\delta)\) per query for \(P^{*} I^{?} D\); product-graph search in general | Resolution paths explain why a name resolved | Medium for the engine, low per language | Language workbenches (Spoofax/Statix), the scopegraphs crate, stack graphs, the lab |
| Overload resolution | One name, many functions, chosen by argument types; unique best or an ambiguity error (Theorem 5.4.8) | \(O(c\,k)\) per call · templates and Swift's joint solving can be expensive | Ambiguity errors list the tied candidates; "no viable function" lists why each failed | High (conversion ranking, templates, tie-breakers) | C++, Swift, Java, C#, Ada |
| Argument-dependent lookup | Adds functions from the arguments' namespaces (Proposition 5.4.9); makes operators and customization points work | \(O(\sum t_i)\) namespace lookups per unqualified call | Surprising candidates ("ADL hijacking"); errors mention functions the reader cannot see nearby | Medium | C++ only (other languages attach operators to types) |
| Macro hygiene | Binding by (name, context): no accidental capture (Theorem 5.4.10) | \(O(N)\) with lazy marks | Errors point into expansions with a backtrace | Medium–high (contexts on every identifier) | Rust, Scheme, Racket; not C or C++ |
| S- and L-attributed evaluation | S: bottom-up only; L: plus left-to-right inherited information (Theorem 5.5.13) — enough for declarations, types and name resolution in declare-before-use languages | \(\Theta(N + E)\), one pass, no graph · runs inside the parser | Errors at the node whose equation fails, in source order | Lowest: parser actions or recursive-descent parameters | yacc/Bison actions, recursive-descent front ends, pebblec |
| Circularity test and ordered attribute grammars | Any non-circular AG (Theorem 5.5.12); OAG: a polynomially testable subclass with static visit sequences (Proposition 5.5.17) | Test: exponential in general (Theorem 5.5.16), polynomial for OAG · evaluation \(\Theta(N + E)\) | The generator reports circular or unordered grammars before any program is compiled | High (a generator) | AG-based compiler generators (Eli/LIGA, LRC, Silver) |
| Reference attribute grammars | Remote attribute access and references: name and type analysis without copying environments; circular attributes for fixed points (Proposition 5.5.18) | Demand-driven, cached · only demanded instances | Cycles detected at run time on the demanded path | Medium (JastAdd generates the evaluator) | JastAdd/ExtendJ, Modelica compilers (JModelica), language workbenches |
| AST annotation | Any fact, stored where it is used; one version of the tree at a time | \(O(1)\) field access · the fastest | Diagnostics read facts directly from nodes | Lowest | Clang, GCC, pebblec, most batch compilers |
| Side tables | Same facts (Proposition 5.6.7), several analyses side by side, immutable tree | \(O(1)\) expected hash lookup | Same | Low; needs stable node ids | Go types.Info, rustc TypeckResults, CPython symtable, analyzers |
| Query-based incremental analysis | Same facts, computed on demand, re-validated after edits (Theorem 5.6.8) | Proportional to what an edit affects; overhead of recording dependencies | Cycles become diagnostics (Swift); consistent results across edits | High: every phase must be a pure query | rustc, rust-analyzer (salsa), Swift, Roslyn |
| Desugaring and HIR lowering | Fewer constructs for later phases; meaning preserved (Theorem 5.6.9) | \(O(n)\) per lowering | Needs desugaring-aware spans, or errors mention generated code | Medium per construct | rustc HIR, Kotlin, Swift SIL generation, Pebble's for (Ch 11) |
| Reachability, missing returns and loop context | Conservative (Theorem 5.7.6): never misses a fall-off; rejects some infinite loops without return (Pebble) or decides constant conditions (Java) |
\(\Theta(n)\), one structural pass | Precise locations; predictable because specified per construct | Lowest | Every statically checked language; E0304/E0305/W0314 in pebblec |
| Definite assignment (dataflow) | Exactly MOP for gen/kill rules (Theorem 5.7.8); sound (Corollary 5.7.9); conditions uninterpreted | \(O(n \lceil \lvert V \rvert / w \rceil)\) per pass, 2 passes per loop in Pebble (Lemma 5.7.10) | One error per variable at the first bad read, with a note at the declaration; Clang/rustc explain the missing branch | Low–medium (bit vectors, loop fixed points, jump states) | Java, C#, Swift DI, Rust (E0381), Pebble (E0306); C compilers as warnings |
| Spans, notes and fix-its | Exact byte ranges, related locations, machine-applicable edits | \(O(\log L)\) per rendered location; zero cost when there are no errors | Best-in-class when every diagnostic carries a span and a code; fix-its let tools repair code | Medium: every diagnostic site must supply spans and notes | Clang, rustc, Swift, pebblec |
| Error recovery and poisoning | One report per mistake (Theorem 5.8.9); later phases keep working around errors | \(O(1)\) per failed lookup | Removes cascades; a missed poisoning shows up as a wall of errors | Low for error symbols; pervasive for error types (every check must accept them) | GCC error_mark_node, Clang RecoveryExpr, rustc {type error}, pebblec |
| Typo correction | Suggestions within \(\lfloor \ell / 3 \rfloor\) edits; OSA catches transpositions, Levenshtein does not; BK-trees exact only for metrics (Theorem 5.8.12) | \(O(N \ell \bar{\ell})\) per failed lookup by scan; BK-tree sublinear in practice | "Did you mean" with a fix-it; a wrong suggestion is worse than none (hence the thresholds and the uniqueness rule) | Low (a DP and a threshold); higher with ranking and indexes | Clang, GCC, rustc, Swift, pebblec |
Comparison-lab results (reproduce with build/<preset>/bin/ch05-bindbench; reference solutions, RelWithDebInfo, this course's Linux container): on the nesting-depth family \(P_d\) at \(d = 2000, 4000, 8000\), the stack of hash tables takes 8.1, 40.0 and 196.0 ms (quadratic), the persistent AVL map 1.6, 3.6 and 8.2 ms, and the de Bruijn level map 0.45, 0.98 and 2.6 ms; on a random program of about 860 000 nodes the three take 98, 108 and 53 ms.
Route through this chapter¶
| Step | What | Techniques | How it is exercised |
|---|---|---|---|
| 1 | Lesson 5.1 | static and dynamic scoping, hoisting/TDZ | drill resolve-scopes; quiz; flashcards |
| 2 | Lesson 5.2 | four symbol-table designs | quiz; lab L1–L4 |
| 3 | Lesson 5.3 | declare-before-use, order independence, imports, scope graphs | quiz; lab L6 ★ |
| 4 | Exercises E1–E4 | pebblec uses two passes, one table with scope marks, error symbols and OSA suggestions (full implementation) |
./course test 5 (ch05.Names.E1_*–E4_*, lit goldens) |
| 5 | Comparison lab labs/ch05-binders/ L1–L5 |
scope stack vs persistent map vs de Bruijn indices; alpha-equivalence | lab tests + ch05-bindbench measurements |
| 6 | Lesson 5.4 | overloading, ADL, hygiene (theory + real compiler runs) | quiz; flashcards |
| 7 | Lesson 5.5 | attribute grammars | drill attr-eval-order; quiz |
| 8 | Lesson 5.6 | annotation, side tables, queries, desugaring | quiz |
| 9 | Lesson 5.7 and Exercises E5–E6 | reachability, definite assignment | drill definite-assignment; ch05.Names.E5_*, E6_* |
| 10 | Lesson 5.8 | spans, poisoning, typo correction | drill edit-distance; E4 |
| 11 | Theory test | all | ./course quiz 5 (≥ 80 % to finish) |
Practice and check¶
./course drill resolve-scopes --difficulty easy # warm up; --solution shows every step
./course drill attr-eval-order
./course drill definite-assignment
./course drill edit-distance
./course flash 5 # daily, a few minutes
./course quiz 5 # after the lessons
./course test 5 # after the exercises and the lab
./course status # done = quiz ≥ 80 % and tests pass
References¶
The chapter's annotated bibliography — papers, textbook sections, pinned source files, docs — is in references.md. Start with: [ALSU07] (the Dragon book's symbol tables and syntax-directed definitions), [Knu68] (attribute grammars), [dB72] (de Bruijn indices), [NTVW15] (scope graphs), [JLS21-16] (definite assignment, precisely specified) and [CLANG-SemaLookup] (Clang's lookup and typo correction).