Scope and Environments

Three concepts: lexical scope, the environment as a data structure, and globals.

This chapter contains the curriculum's clearest example of building the wrong thing on purpose. The environment you write in Lab 5 is a stack of hash maps, it is genuinely slow, and Section 3 deletes it. Building it anyway — and measuring it — is what makes the slot-based design in Lab 10 land as an insight rather than a fact.

Concept 1: Lexical Scope

1. Concept

Lexical (or static) scope means the binding a name refers to is determined by where the name appears in the source text, and can be worked out by reading the program. Dynamic scope means it is determined by the call stack at run time.

local x = "outer"
local function show() return x end     -- lexical: `x` is the one visible HERE

local function caller()
  local x = "inner"
  return show()                        -- lexical → "outer"
end                                    -- dynamic would give "inner"

2. Problem

Without a scoping rule, a name in a function body is ambiguous. Dynamic scope answers the question at run time, which sounds flexible and is in practice a catastrophe: a function's meaning depends on who called it, so no function can be understood, refactored, or optimized in isolation.

3. Mental model

Lexical scope means you can answer "which variable is this?" with your finger on the page. Nesting in the text is nesting in the scope. That is why the compiler in Section 3 can replace every name with a number: the answer is knowable before the program runs.

That last sentence is the whole reason this chapter matters. Lexical scope is what makes compilation possible.

4. Implementation

The scope rules Ember implements, each with the lab that adds it:

The initializer rule is the one to get right and the one everyone gets wrong.

local x = 10
local x = x + 1        -- reads the FIRST x (10), then creates a SECOND x = 11
print(x)               -- 11

In the interpreter that is one line of ordering:

#![allow(unused)]
fn main() {
Stmt::Local { names, exprs, .. } => {
    let values = self.eval_exprs(exprs)?;   // ← evaluate FIRST, in the current scope
    for (name, v) in names.iter().zip(values) {
        self.declare(name.clone(), v);      // ← THEN create the binding
    }
}
}

Swap those two lines and local x = x reads nil. JavaScript's let has a third behavior — the initializer is in the new scope but the binding is uninitialized, so let x = x is a ReferenceError (the "temporal dead zone"). Three languages, three answers, all defensible. Test yours.

5. Alternatives

Dynamic scope is not merely a historical mistake — it is genuinely useful for things like "the current output stream" or "the current transaction", which is why Common Lisp kept it and why thread-locals, React context, and tracing's spans are all dynamic scope wearing a hat. The lesson is that dynamic scope is a feature you opt into, not a default you tolerate.

6. Decision

Lexical scope, no dynamic-scope escape hatch.

Nothing exotic. What is worth recording is the consequence: because scope is lexical, the compiler can resolve every local to a slot number at compile time, and Section 3 depends entirely on that. Choosing dynamic scope would make a bytecode VM with slot-based locals impossible.

7. Tradeoffs

8. Production concerns

• Shadowing warnings. Lua does not warn on shadowing. luacheck exists precisely because people wanted the warning. Ember could add one; the decision to not is worth a line in docs/limitations.md rather than silence.
• A missing local is a global, silently. for i = 1, 10 do count = count + 1 end at the top of a policy file creates a global, and in Section 5 that global outlives the call and leaks state between policy evaluations. This is the single most common real bug in embedded Lua. Ember's answer is in Section 5: a fresh globals table per execution, plus an optional strict mode. Make a note now; it is a scoping decision with a production consequence.

9. References

• Lua 5.4 Reference Manual §3.5 ("Visibility Rules") — one page, and read the example, which is exactly the local x = x case.
• Structure and Interpretation of Computer Programs, chapter 3, on environments as a model of scope. The environment-diagram notation there is the one this chapter's diagrams descend from.
• The luacheck documentation on shadowing and implicit globals — a catalogue of the mistakes people actually make.

Concept 2: The Environment

1. Concept

An environment is the run-time data structure mapping names to values. In the tree walker, it is a stack of hash maps.

2. Problem

The tree walker has no compile step, so it must resolve names while executing. Given the name x, find its value.

3. Mental model

   local a = 1
   local b = 2
   do
     local c = 3
     print(a + c)          ← resolving `a`: look in {c}, miss; look in {a,b}, hit.
   end

   scopes: [ {a: 1, b: 2}, {c: 3} ]
            └─ index 0 ─┘  └ idx 1 ┘
                             ▲
                     innermost scope: searched FIRST

   globals: { print: <native>, ... }      ← searched LAST

Resolution walks inward-out: innermost scope first, then each enclosing one, then globals. That walk is the definition of shadowing.

4. Implementation

#![allow(unused)]
fn main() {
// src/interp/env.rs
pub struct Env {
    scopes: Vec<HashMap<String, Value>>,   // DELIBERATELY NAIVE. See §7.
    globals: GcRef<Table>,                 // a real Ember table; see Concept 3
}

impl Env {
    pub fn push_scope(&mut self) { self.scopes.push(HashMap::new()); }
    pub fn pop_scope(&mut self)  { self.scopes.pop(); }

    pub fn declare(&mut self, name: String, v: Value) {
        // `insert`, not `entry`: re-declaring in the SAME scope shadows, it does
        // not error. `local x = 1; local x = 2` is legal Lua.
        self.scopes.last_mut().expect("a scope is always open").insert(name, v);
    }

    pub fn get(&self, name: &str) -> Option<Value> {
        for scope in self.scopes.iter().rev() {          // ← innermost first
            if let Some(v) = scope.get(name) { return Some(*v); }
        }
        None                                              // caller falls back to globals
    }

    pub fn set(&mut self, name: &str, v: Value) -> bool {
        for scope in self.scopes.iter_mut().rev() {
            if let Some(slot) = scope.get_mut(name) { *slot = v; return true; }
        }
        false                                             // not a local → assign a global
    }
}
}

The cost, stated precisely. Reading a local costs: one hash of the name string (proportional to its length), one hash-map probe, per enclosing scope, until it hits. In a function nested three blocks deep, reading an outer variable is three hashes and three probes. In the bytecode VM it will be stack[base + 2] — one add and one load.

That is not a 10% difference. Measure it in Lab 8 and write the number down; it is the number that justifies Section 3.

5. Alternatives

6. Decision

A now, D in Section 3. Deliberately.

The reason to build A is not that it is easier — C is comparably easy. It is that A makes the cost model legible: you can see the hash and the walk in the code, so when Lab 10 replaces them with an array index, the improvement is something you understood before you measured it.

There is a second, subtler reason: the tree walker must stay obviously correct, because it is the oracle. Option D in a tree walker means implementing slot allocation twice, once in each backend, and a bug in the oracle's resolution is undetectable by differential testing — both backends would be wrong together.

7. Tradeoffs

8. Production concerns

• String keys allocate. declare(name.clone(), v) clones a String per declaration, per execution. In a loop body that declares a local, that is an allocation per iteration. It is acceptable because this is the reference implementation — and it would be unacceptable in the VM. Note the distinction explicitly; "it is fine here and not there" is a real engineering judgment, not a dodge.
• Scope leaks on early return. If pop_scope is called at the end of eval_block and the block returns early via ?, the scope is never popped and the environment is corrupted for everything after. Use a guard type with Drop, exactly as the parser does for depth — the same bug, the same fix, two labs apart. Notice the pattern; it recurs.

9. References

• Crafting Interpreters, chapters 8 and 11 — jlox's Environment (option C) and then its resolver pass, which is a partial move toward option D. The comparison is directly relevant.
• SICP §3.2, "The Environment Model of Evaluation" — the canonical treatment.
• Lua's lparser.c: new_localvar, searchvar, singlevar. Lua does option D at parse time, with no AST — see Vardesc and the FuncState struct.

Concept 3: Globals

1–3. Concept, problem, mental model

A global is a name not bound by any enclosing local. In Lua, globals are not a separate mechanism at all: x = 1 is sugar for _ENV.x = 1, where _ENV is an ordinary upvalue holding an ordinary table.

Lua has no global variables. It has one table, and a variable holding it. That is one of the most elegant designs in the language, and it is what makes sandboxing a one-line operation: give a chunk a different _ENV and it can no longer see anything you did not put in it.

   x = 1                             _ENV.x = 1
   print(x)          desugars to     _ENV.print(_ENV.x)

4. Implementation

#![allow(unused)]
fn main() {
// Ember: globals are a real Ember Table, owned by the Engine, swappable per call.
pub struct Env {
    scopes: Vec<HashMap<String, Value>>,
    globals: GcRef<Table>,        // ← a Table value, not a HashMap<String, Value>
}

// Reading a free name:
fn resolve(&mut self, name: &str, span: Span) -> Result<Value> {
    if let Some(v) = self.env.get(name) { return Ok(v); }        // local?
    // Global. A MISSING global is nil, not an error — Lua 5.4 §3.5.
    Ok(self.heap.table_get(self.env.globals, self.intern(name))?)
}
}

Making globals a Table rather than a HashMap<String, Value> costs nothing now and buys three things later:

1. The GC traces it as an ordinary object — one fewer special case in the root set (Lab 15).
2. A script can manipulate it if the host chooses to expose it, which is how _G-style reflection works.
3. The host can swap it per execution — a fresh globals table per policy evaluation means one script's accidental global cannot leak into the next one's run. That is Lab 23, and it is the single most valuable sandboxing primitive Ember has.

5–7. Alternatives, decision, tradeoffs

ADR-012: option B. It captures the sandboxing and GC benefits of C at a fraction of the complexity, and it does not force the upvalue machinery to exist before Section 4. The cost is that Ember cannot express lexically scoped globals — a nested function cannot have a different global table from its parent. No use case in Ember's stated production profile needs that; if one appears, C is the upgrade path and this ADR gets superseded.

8. Production concerns

• A typo is a nil, not an error. if artcle.score > 0 reads a missing global, gets nil, and fails at the indexing step with a message about artcle — which is at least a name. But if x == nil where x is a typo silently succeeds. This is the cost of Lua's "missing global is nil" rule, and every embedded-Lua deployment eventually wants a strict mode. Ember's is a challenge extension in Lab 5 and a real option in Section 5.
• Globals are shared mutable state across evaluations unless you swap the table. In a service that evaluates a policy per request, a script that writes a global is writing to something that outlives the request. Swap the table, or document loudly that you do not.
• Global reads are the slow path even in the VM. GET_GLOBAL is a table lookup on a string key, forever — it cannot be resolved to a slot, because the table can change between instructions. That is why Lua programmers write local sin = math.sin above a hot loop, and why inline caches exist.

9. References

• Lua 5.4 Reference Manual §2.2 ("Environments and the Global Environment") and the load function in §6.1, which takes an env argument. Read them together; the sandboxing story is right there.
• Lua's lparser.c: singlevar and luaK_indexed — watch a free name become _ENV indexing.
• The lua-users wiki page on sandboxing, for the folklore version of what §5 formalizes.

The Trace: scope, resolved

$ ember run --trace-scope -e '
local a = 1
do
  local a = 2
  local b = a + 1
end
return a'

scope push  depth=1
  declare a = 1                 scopes=[{a}]
scope push  depth=2
  declare a = 2                 scopes=[{a}, {a}]        ← shadowing
  resolve a → found at depth 2  (1 probe)
  declare b = 3                 scopes=[{a}, {a, b}]
scope pop   depth=1             scopes=[{a}]             ← b and inner a are gone
  resolve a → found at depth 1  (1 probe)
1

Now the expensive case — note the probe count, which is what Section 3 removes:

$ ember run --trace-scope -e 'local x = 1 do do do return x end end end'

  resolve x → miss at depth 4, miss at 3, miss at 2, found at depth 1  (4 probes)

Four string hashes and four hash-map probes to read a variable the compiler could have resolved to stack[base + 0]. That line is the argument for Section 3, and you should produce it on your own machine.

Things to Notice

• Lexical scope is what makes compilation possible. If the answer to "which variable is this?" needed the call stack, no compiler could precompute it.
• The initializer-before-binding rule is one line of ordering and it distinguishes three major languages.
• Ember builds the slow environment on purpose. The measurement is the deliverable.
• The scope-pop-on-early-return bug is the parser's depth-leak bug again. Any push/pop pair in a function that can ? needs an RAII guard. Once you have seen it twice, you will see it everywhere.
• Lua's _ENV is the most elegant idea in this chapter and Ember takes 80% of its value with 20% of its machinery. Knowing what you gave up is the point of writing the ADR.

Validation / Self-check

1. Define lexical and dynamic scope, and give a program that distinguishes them.
2. Why does lexical scope make a bytecode compiler possible?
3. What does local x = x do in Ember, in Lua, and in JavaScript with let? Which line of code decides it?
4. Give the exact cost of a local variable read in the tree walker, in terms of hashes and probes.
5. Give the four environment strategies and say which Lua uses and when.
6. What is _ENV, and what capability does it give a host that a plain globals map does not?
7. Why is Ember's globals table a Table rather than a HashMap? Give three consequences.
8. Why can a global read never be resolved to a slot, even in the VM? What does that motivate in Section 7?

Next: Control Flow.