AtlasLangimplementation

AtlasLang: Scopes, Shadowing and a Real Bug

An inner `let x` must not disturb an outer one. Our lowering keys storage slots by the resolved symbol rather than by the source name — because an earlier version keyed them by name, and the outer `x` was silently overwritten.

The question

What actually goes wrong if a compiler tracks variables by their names?

Source→Lexing→Tokens→Parsing→AST→Semantics→Typed→IR→Optimize→Codegen→Machine code→Link→Execute
What the program is here

A scope tree with a symbol table at each node, and a typed AST whose every identifier carries a symbol id rather than only a name. The symbol is the point: a name is a string that several different variables may share, and a symbol is a unique identity that exactly one declaration owns. Every later phase — type checking, lowering, storage allocation — is written against symbols, and the moment any of them falls back to the name, this lesson's bug reappears.

What this phase may assume or do

Lowering may assign two variables to the same storage slot only if they are the same variable — the same resolved symbol — and never merely because they share a source name. It may also assume, from the resolver, that every identifier in the tree already has a symbol, so it does not need to and must not re-resolve by name. The subtler ordering condition is that a let initializer must be lowered *before* its own slot is created, because let x = x + 1; in an inner scope reads the outer x, and creating the new binding first would make the initializer read the variable it is defining.

Key points

  • A name is a string that many variables may share; a symbol is an identity exactly one declaration owns. Every phase after resolution must use the symbol.
  • Lexical scoping is one loop from the innermost scope outward, and shadowing falls out of it rather than being special-cased.
  • Keying storage slots by name merges two distinct variables onto one slot, so an inner let silently overwrites an outer one.
  • That failure produces no diagnostic and no crash — just a wrong value read some distance from the block that caused it.
  • The fix is a map keyed by symbol id; the display name is derived separately, so the IR shows x and x.1 rather than local#0 and local#1.
  • A let initializer must be lowered before its own slot is created, or let x = x + 1; reads the variable it is defining.
  • Parameters and compiler temporaries go through the same symbol-keyed allocator, which is what stops either from colliding with a user variable.

Lookup is one loop outward

AtlasLang has block scope. A let is visible from its declaration to the end of the enclosing block, and blocks nest — a function body, an if arm, a while body, or a bare { ... } all push a scope. The checker keeps a stack of scopes, pushing on entry and popping on exit.

Resolution is a loop from the innermost scope outward, returning the first match. That single loop is the whole of lexical scoping, and it is where shadowing comes from: an inner let x is found before an outer one, so it wins, and when the block ends and its scope is popped the outer one is visible again. Nothing special-cases shadowing; it falls out.

Redeclaring in the *same* scope is a different matter and is an error: "x is already declared in this scope", with the help line "Shadowing an outer scope is allowed; redeclaring in the same scope is not." That distinction is the language taking a position — shadowing across scopes is a useful idiom, and two let x in one block is almost always a mistake.

Function declarations are collected before any body is checked, so a function may call one declared later in the file. That one ordering decision is the whole of [[declaration-order]]: without it AtlasLang would need forward declarations the way C does, and the language would be worse for a reason nobody would enjoy explaining.

The bug

Lowering turns local variables into named storage slots and emits load and store against them. The obvious implementation keys those slots by the variable's name: see x, use the slot called x.

That is what an earlier version of this compiler did, and it is wrong. Consider let x = 1; { let x = 2; print(x); } print(x);. There are two variables here. Keyed by name, there is one slot. The inner let x = 2 stores 2 into the slot named x — the same slot the outer x lives in — and after the block ends, the outer x has been overwritten. The program prints 2 and then 2, and the second 2 is a value the source never assigned to that variable.

The failure has every property that makes a compiler bug expensive. There is no diagnostic, because both scopes are perfectly legal. There is no crash. The program compiles and runs and produces a wrong number, and the wrongness only appears at the point where the outer variable is read again, which may be a long way from the block that clobbered it. Shadowing is common enough in real code that this would be hit constantly and diagnosed as a mystery.

A test caught it: shadowing binds to the inner declaration and restores the outer one in scripts/compilers-sim.test.ts, which asserts that the program above prints ["2", "1"]. The test is one line. The bug it catches is one that reading the code will not reliably reveal, because the code that has it looks entirely reasonable.

The same source, lowered two ways
Before
; keyed by NAME — one slot, two variables
store @x, 1
store @x, 2      ; clobbers the outer x
%0 = load @x
print %0         ; 2  — correct by luck
%1 = load @x
print %1         ; 2  — WRONG, should be 1
After
; keyed by SYMBOL — two slots, two variables
store @x, 1
store @x.1, 2    ; a different slot entirely
%0 = load @x.1
print %0         ; 2
%1 = load @x
print %1         ; 1
Legal only when

Two variables may share a storage slot only when they are the same variable — the same resolved symbol — or when the compiler has proved their live ranges do not overlap, which is a register allocator's job and requires liveness information that does not exist at lowering time. Keying by symbol satisfies the first condition unconditionally, which is why it is the right rule here rather than an optimization.

Illegal when

Two distinct declarations share a name. Then a name-keyed slot merges storage for variables the language says are different, and a write through one is observable through the other. It is a miscompilation with no diagnostic: the program is well-formed, compiles cleanly, and prints a value nothing in the source produced.

The fix, and the readable-names problem it creates

The fix is one map. slotBySymbol in src/compilers/sim/ir.ts is keyed by the symbol id the checker produced — local#0, local#1 — and never by the source text. Every place lowering needs a slot for a variable, it goes through slotNameFor(symbol, name), which looks up by symbol.

That immediately creates a presentation problem. Symbol ids are correct and unreadable: an IR listing full of store @local#7 teaches nothing. So the display name is derived separately from the identity: the first binding of a name keeps it, and later ones get a numeric suffix. Two variables named x become slots x and x.1, which are distinct where it matters and legible where it matters.

That split — identity by symbol, display by name — is worth naming as a general rule, because compilers get it wrong in both directions. Use the name as the identity and you get this bug. Use the symbol for display and you get diagnostics and dumps that nobody can read. Real compilers do exactly the same thing under different vocabulary: [[name-mangling]] is this problem at the linker's scale, where a unique identity has to be encoded into a flat namespace while remaining demanglable back into something a human recognises.

One ordering detail comes with the fix. In let x = x + 1;, the initializer must be lowered before the new slot is created, so the x on the right resolves to the outer binding. The checker already resolves it that way; the lowering has to match, and getting the order wrong there is the other half of the same bug.

Real IR for let x = 1; { let x = 2; print(x); } print(x);
Lowered — two slots
▸fn main(): void {
▸b0: ; entry
▸  store @x, 1
▸  store @x.1, 2
▸  %0 = load @x.1
▸  print %0
▸  %1 = load @x
▸  print %1
▸  ret
▸}

Read it asTwo slots for two variables that share a name. The .1 suffix is display only — the identity is the symbol local#1, which is what the map is keyed by. Run this program on the playground and the output is 2 then 1; the optimizer folds both loads away and leaves print 2; print 1;, which is a satisfying confirmation that the two values never met.

Parameters, functions and where scopes come from

Parameters are treated as locals for exactly this reason. A parameter gets a symbol like any other declaration, and lowering gives it a slot keyed the same way, so a parameter shadowed by an inner let of the same name behaves correctly with no extra machinery. It also means assigning to a parameter works, and that SSA construction promotes parameters and locals uniformly rather than needing two paths.

Scopes are pushed at five places, and the list is short enough to memorise: the global scope, a function body, an if arm, an else arm, a while body, and a bare block. Each gets a labelled node in the scope tree that the scope viewer renders, so you can see the nesting and which symbols each level holds.

The short-circuit lowering quietly uses the same machinery. a && b needs a temporary written on two paths and read at the join, and that temporary is allocated through slotNameFor with a synthetic symbol. Using the same mechanism for compiler-introduced temporaries as for user variables means a temporary can never collide with a user variable named the same thing — which is the third form of this same bug, and the one that bites compilers whose temporaries are named by string concatenation.

  • Scopes are pushed for: the global scope, each function body, each if and else arm, each while body, and each bare { ... } block.
  • Lookup walks outward from the innermost and returns the first hit — that loop is lexical scoping in its entirety.
  • Redeclaring in the same scope is an error; shadowing an outer scope is not, and the diagnostic says so explicitly.
  • Functions are declared before any body is checked, so call order in the file does not matter.
  • Parameters are ordinary symbols with ordinary slots, so shadowing a parameter and assigning to one both work without special cases.
  • Compiler-generated temporaries go through the same symbol-keyed allocator, so they cannot collide with a user variable of the same name.

How it works

The steps, in the order the compiler takes them.

  • The checker pushes a scope on entering the global scope, a function body, an if or else arm, a while body or a bare block, and pops on leaving.
  • Each declaration creates a SymbolInfo with a unique id, a kind, a type, a declaration offset and the depth it was declared at, and records it in the innermost scope.
  • Declaring a name that already exists in the *same* scope reports an error; a name that exists only in an outer scope shadows it silently and legally.
  • Resolution walks the scope stack outward and returns the first match, then writes the symbol id onto the identifier node.
  • Lowering asks slotNameFor(symbol, name) for storage; the map is keyed by symbol id, so two declarations never share a slot.
  • The display name is chosen separately — first binding keeps the name, later ones get a numeric suffix — so the IR stays readable without the identity depending on it.
  • A let lowers its initializer before creating its own slot, so the initializer sees the outer binding of the same name.
  • Parameters are declared as symbols and stored to slots at function entry, so SSA construction treats them uniformly with locals.

How it breaks

What the engineer observes when it goes wrong — not what goes wrong internally.

  • An inner let x overwrites an outer x and the program prints a value nothing assigned to it, with no diagnostic anywhere — the exact bug this lesson is about.
  • A let x = x + 1; in an inner scope reads the variable being declared instead of the outer one, because the slot was created before the initializer was lowered.
  • A compiler-generated temporary named by string concatenation collides with a user variable of the same name, and a value is corrupted in a program the user cannot see anything wrong with.
  • A phase that re-resolves by name rather than using the symbol reintroduces the bug locally, so shadowing works everywhere except in that one pass.
  • A scope popped on the wrong path — an early return, an error path — leaves the symbol table describing a nesting that no longer matches the tree, and later lookups find the wrong declaration.
  • Redeclaration in the same scope accepted silently, so a typo that reuses a name compiles and one of the two assignments quietly does nothing.

When it helps

  • Reading or writing any resolver, where "resolve once, then use the symbol everywhere" is the single rule that prevents a whole family of silent bugs.
  • Debugging a language implementation where a variable holds a value nothing assigned to it — shadowing and slot identity are the first two things to check.
  • Designing a language's scoping rules, where the choice to allow shadowing across scopes and forbid it within one is a real decision with real ergonomic consequences.
  • Understanding why IR dumps and mangled symbols look the way they do: they are identity and readability being served by two different mechanisms.

When it hurts

  • For languages with dynamic scoping, eval, or names resolvable only at run time, where a static symbol cannot be assigned at all and the whole approach needs replacing.
  • For languages with hoisting or complex temporal dead zones, where "declared before use" is not the rule and resolution has to model a more intricate lifetime.
  • As a substitute for liveness analysis: symbol identity says two variables are different, and only a register allocator can say when different variables may share storage anyway.

What it costs

Every one of these is paid by something.

  • Keying storage by symbol buys correct shadowing unconditionally and pays with a map and an indirection at every variable reference in the lowering.
  • Deriving display names separately buys readable IR and pays with a second naming scheme to maintain and a suffix convention that can itself collide if it is not checked.
  • Allowing shadowing across scopes buys a genuinely useful idiom and pays with a class of reader confusion — and with this bug, for any implementation that gets identity wrong.
  • Forbidding redeclaration within one scope buys a diagnostic for a common typo and pays by rejecting a pattern that a few languages permit deliberately.
  • Treating parameters as ordinary locals buys uniform SSA promotion and assignable parameters, and pays two extra instructions per parameter in the unoptimized IR.

What else you could do

What a different compiler or language does instead, and when that is better.

  • Alpha-renaming: rewrite the tree so every variable has a globally unique name, then key by name safely. Equivalent in effect, and it destroys the source names the diagnostics need.
  • De Bruijn indices, which replace names with a depth-and-position pair. Elegant, immune to capture, and unreadable in any dump a human has to look at.
  • A persistent immutable environment per scope, as functional-language implementations often use, which makes scope exit free and allocation per binding the cost.
  • Forbidding shadowing entirely, which removes the problem by removing the feature and irritates every user who wanted to reuse an obvious name in a small block.
  • Resolving names lazily at each use rather than once — the approach dynamically scoped languages take, which is more flexible and gives up every static guarantee this design provides.

See it for yourself

The flag, dump or tool that shows you this directly.

  • Type let x = 1; { let x = 2; print(x); } print(x); on /compilers/atlaslang. The IR panel shows @x and @x.1, and the output is 2 then 1.
  • The scope viewer renders the scope tree with each level's symbols, so the nesting and the two distinct x symbols are both visible.
  • Try let x = 1; { let x = x + 1; print(x); } print(x); — the inner initializer reads the outer x, so the output is 2 then 1.
  • Try let a = 1; let a = 2; in one scope and read the diagnostic, which names the rule rather than just refusing.
  • scripts/compilers-sim.test.ts — the test shadowing binds to the inner declaration and restores the outer one is the regression test for this bug.
  • src/compilers/sim/ir.ts — slotBySymbol and slotNameFor are a dozen lines under a comment that tells this story.

Plausible wrong readings

Stated the way a confident engineer states them.

  • "Shadowing is a language feature, so the compiler must implement it." Nothing implements it. It falls out of resolving from the innermost scope outward. What has to be implemented is not undoing it later.
  • "The bug was a typo." It was a design decision — keying storage by name — that looked correct and is correct for every program without shadowing, which is most of the programs you would test by hand.
  • "Symbol ids are an internal detail." They are the identity the entire back half of the compiler is written against. Any phase that falls back to the name reintroduces the bug in its own corner.
  • "Two variables with the same name should share storage since only one is live." Only if that has been proved. Deciding when distinct values may share a location is register allocation, and it needs liveness that does not exist at lowering time.

Misconceptions

The claim, and what is actually true.

Name resolution is a lookup, so any map will do.
The map's *key* is the whole design. Keyed by name it merges distinct variables; keyed by symbol it cannot. The bug in this lesson is entirely a choice of key.
A shadowing bug would show up immediately in testing.
Only in a test that shadows and then reads the outer variable afterwards. Every program without shadowing behaves identically under both implementations.
The IR should use symbol ids, since those are the identity.
It should be keyed by them and display names. A dump nobody can read is a dump nobody uses, and readability is why the display-name scheme exists.

Go deeper

The same idea at increasing depth. Stop wherever it stops being useful.

overview

Two variables can have the same name if they are in different blocks — the inner one shadows the outer one, and when the block ends the outer one is visible again. That works because the compiler looks names up from the innermost scope outward. The trap is what happens next: if the compiler then stores variables by name, the two share one location and the inner one overwrites the outer one, with no error and a wrong answer.

practical

Resolve every name once, attach the resulting symbol to the node, and make every later phase use the symbol. If any pass looks a variable up by string, that pass has the bug even if the rest of the compiler does not. Write the regression test the same day: declare, shadow, print inside, print outside, assert both values. And keep display names separate from identity, or your own IR dumps become unreadable exactly when you need them.

advanced

This bug is the small version of a problem that recurs at every scale of a toolchain, and recognising the shape is worth more than the fix. The general form is: a human-facing name is not unique, an implementation needs a unique key, and merging on the name silently unifies things the language says are distinct. It is name-keyed slots in a lowering; it is [[name-mangling]] at the linker, where two static functions in different translation units must not collide; it is an ODR violation, where two differing definitions of one inline function link cleanly and one is silently chosen; it is a monomorphized generic whose mangled name loses a lifetime or an argument. In every case the failure is quiet, well-formed and far from its cause, and in every case the fix is the same: derive identity from something the language guarantees is unique, and derive the readable name separately.

How much this depends on

Nothing in this domain is true of every compiler. These say how much.

implementationThe x / x.1 display convention and the local#N symbol ids are AtlasLang's, in src/compilers/sim/check.ts and ir.ts. Other compilers solve the identical problem with alpha-renaming, De Bruijn indices, or mangled unique names, and their dumps look correspondingly different. The rule — identity by symbol, never by name — is what transfers.
simplifiedAtlasLang has no closures, no captured variables, no modules and no eval, so a symbol's scope is always a syntactic region and resolution always succeeds statically. Closures make this substantially harder: a captured variable outlives the scope that declared it, so identity has to survive into a heap-allocated environment — which is [[closure-conversion]], and it is a different problem wearing the same clothes.
specWhether shadowing is permitted at all is a language decision, not an implementation one. Rust and most ML-family languages allow it freely and idiomatically; Java forbids shadowing a local by a local within a method; JavaScript's var has function scope with hoisting, which makes the same source text mean something different again. AtlasLang allows it across scopes and forbids redeclaration within one, and that choice is what its resolver implements.

If you were asked this in an interview

  • What exactly goes wrong if a compiler keys local storage by variable name, and why is it hard to notice?
  • Why must a let initializer be lowered before the variable's own slot is created?
  • How does an IR dump stay readable if slots are keyed by symbol ids?

Connections

DSAhash-tablestackbinary-tree
Domains that do not exist yet
  • Testing & Reliability Engineering — Regression tests for bugs that produce a wrong value rather than an error
    This defect emits no diagnostic and does not crash, so it can only be caught by a test that asserts an observed value. The general discipline — turning each silent miscompilation into a permanent one-line assertion — belongs there; the reason this compiler needed one is here.