Separate Namespaces and Overload Sets in a Symbol Table

A symbol table that maps one string to one binding is a simplification that holds for a subset of languages and fails for all the rest. C keeps a struct tag and a variable of the same spelling in separate spaces. C++ allows one spelling to name dozens of functions and chooses between them by argument types. Java and Haskell both separate the type namespace from the term namespace, but for different reasons and with different consequences for the resolver. Each of these is a design decision about what a name denotes, and each changes the data structure.

Four namespaces and why each exists

The C rule is the most concrete. Identifiers fall into four disjoint name spaces: ordinary identifiers (variables, functions, typedef names, enumeration constants), tags (struct, union, and enum tags), members of each struct or union, and labels. The same spelling may appear in all four in one scope without conflict, and the compiler resolves each by context. struct s and s as a variable are different entities, and goto s names a label unrelated to either.

The reason is historical and practical. Tags are introduced by a keyword that already announces the namespace, so the grammar disambiguates without lookahead: after struct, only a tag can follow. Labels appear only after goto and before :. Making them separate let the grammar stay simple and let programmers reuse short names. The cost is a rule that beginners trip over: typedef struct node node; works because the typedef name is in the ordinary namespace and the tag is not, and the two nodes never collide.

C++ keeps a version of the split rather than removing it. A class or enumeration name may be declared in the same scope as a variable, function, or enumerator with the same spelling, and in that case the class name is hidden wherever the other name is visible; an elaborated specifier such as struct s still reaches the class. That is why struct stat and a function stat coexist in C++ headers. Java and C# separate types from values more cleanly: a variable named Foo is legal alongside a class Foo, and the resolver knows which table to consult because the syntactic position says so — a type annotation consults the type namespace, an expression the value namespace.

Haskell separates data constructors from type constructors, so Maybe and Just never collide, and the module system adds a further qualification layer on top. Class names and type constructor names share one namespace at the level of the module’s declarations, which is why the same identifier cannot be declared as both in one module, even though a class name in an instance declaration and a type name in a type expression are distinguishable by syntax.

One spelling, many candidates

Overloading breaks the assumption that lookup returns a binding. In C++ a call to print may match any of several functions declared across several headers, and the resolver’s job is not to pick one but to produce a candidate set from which the type checker selects.

The mechanism is a two-stage process that must be kept strictly separate. Name lookup collects the set of declarations visible under the ordinary scoping rules, and only then does overload resolution choose among them using argument types. Keeping the stages apart matters because a candidate that cannot match the arguments still takes part in lookup: it hides an outer declaration of the same name and it is present for the diagnostics that list near misses, which a lookup that pruned by arity would not reproduce.

Collecting candidates requires the symbol table to store a list per name rather than one binding. Insertion appends to the list; same-scope redefinition rules then differ by kind — two variables with the same name in one scope is an error, two functions with different parameter types is not. The table needs to know which it is holding.

Argument-dependent lookup complicates the collection further: for a call with an argument of class type, functions declared in the namespace of that type’s class join the candidate set even if not otherwise visible. The resolver cannot compute that set without knowing argument types, so candidate collection for a call is interleaved with type checking rather than done in a pure name-resolution pass.

The selection rule is not part of resolution

Choosing among candidates is a ranking procedure. C++ builds a set of viable functions — those whose parameters can be initialized from the arguments — and then ranks the implicit conversion sequences for each argument. An exact match beats a promotion, a promotion beats a conversion, and a user-defined conversion is worse than any standard one. Ambiguity is an error, not a preference for the first declaration.

The ranking requires types, so it belongs in the checker. The symbol table’s contribution is limited to producing an ordered candidate list with enough information to know each candidate’s scope, its declaration order, and whether it was found by ordinary lookup or by argument-dependent lookup. Ordering matters because a member function hides a namespace-scope function of the same name rather than competing with it, and a declaration in an inner scope hides one in an outer scope entirely.

The Haskell approach is different in kind. A class declaration introduces a name whose type is a constrained polymorphic type, and uses of the overloaded name are resolved by inferring which instance satisfies the constraints. There is no candidate ranking at the call site; the compiler emits a constraint and solves it, which makes overload resolution part of type inference rather than a separate step. The practical consequence is that a Haskell program can fail to compile because a constraint is unsatisfiable even though every individual use looks well typed.

Representing the split in one table

Two implementation strategies exist and both are used.

The first keeps genuinely separate tables, one per namespace, each with its own scope stack. The resolver selects the table by syntactic context before looking anything up, which means the scope stack described in Symbol Table Layouts and the Cost of Leaving a Scope must be maintained once per table or once for all of them. This is simple and fast: the C compiler’s tag table and ordinary table share nothing, and a lookup is a hash probe in one of them. The drawback is duplication — entering a scope must push a frame in each table, and the tables must stay in step or a lookup in one will see a scope that the other does not.

The second uses one table keyed by a pair of namespace tag and string, hashing the concatenation or a combined hash. This keeps one scope stack and one bucket array, and a lookup is a probe with a different key. The cost is a wider key and a hash function that must not produce collisions between namespaces; the benefit is a single structure to enter, leave, and snapshot. A common refinement stores the namespace as a small integer and packs it into the key’s high bits when names are interned with a per-namespace offset.

A third option appears when a name can hold a set of candidates: the table maps to a small vector, with the common case of length one stored inline and the overflow case in a side allocation. That avoids an allocation per declaration, which matters because most names are declared once.

Diagnostics depend on the split

The split is visible to users, and the diagnostics should reflect it. If a program declares a variable s and then writes struct s { int a; };, a compiler that reports a redefinition is wrong; a compiler that reports nothing is right, and a compiler that reports a shadowing warning would be inventing a rule the language does not have. Conversely, in C++ declaring a class Foo and then a variable Foo in the same scope is legal but hides the class name, so a later use of Foo as a type resolves to the variable and fails; the diagnostic should say the name was hidden by a non-type declaration, not that the two collide.

The same principle applies to overload diagnostics. “No matching function” is the correct message when the candidate set is non-empty and all candidates fail; “undeclared identifier” is correct when the set is empty. Merging the two produces the classic unhelpful message about an undeclared function that is in fact declared with the wrong argument types.

Cascading errors are the other trap. A call whose argument expression is ill-typed produces an error binding; if the checker then reports that no overload matches, the user sees two errors for one mistake. The fix is to propagate an unknown type through overload resolution without committing to an error, which requires the checker to distinguish a genuine no-match from a poisoned argument.

Interaction with the rest of the front end

Namespaces affect every pass that follows. Definite-assignment analysis, described in Definite Assignment as a Flow-Sensitive Dataflow Problem, operates on value bindings and must not confuse a type name with a variable of the same spelling. Capture analysis for closures needs to know whether an identifier refers to a value, a type, or a namespace-level entity, because only values are captured. Code generation needs the storage class of the resolved entity, which is recorded at declaration time in the ordinary namespace and has no meaning for a tag.

The layering that keeps this manageable is a resolution pass that produces, for each identifier occurrence, a reference to a binding with an explicit kind tag and namespace. Every later pass switches on that tag rather than on the spelling. A pass that re-derives meaning from the string has reintroduced the ambiguity the resolver existed to remove.

Where the split breaks down

Languages that partially unify namespaces pay for it in resolution rules. In C++, a name can denote a type in one context and a value in another, and the rules for when a name is treated as a type are elaborate enough to occupy their own standard clause. Templates make it worse: a dependent name is one whose namespace cannot be determined until instantiation, so the parser must record both possibilities and the checker must resolve later. That is why typename and template disambiguators exist.

The failure mode to watch for in a compiler under construction is a table that silently permits two bindings in one namespace because insertion did not check. It compiles the program and binds the second occurrence to the first declaration, producing wrong code with no diagnostic. An assertion at insertion time, plus a test that declares a variable and a tag with one spelling and checks that both resolve correctly, catches it before it reaches users.