In a tree-walking interpreter, a function is called with a local variable `x = 5`. Later in the function body, `x` is referenced. Where does the interpreter find the value of `x`, and what happens when the function returns?
AIt looks up `x` in a global symbol table that persists across all function calls
BIt finds `x` in a new environment created for this function call; when the function returns, that environment is discarded and the enclosing scope is restored
CIt compiles the function to bytecode and stores `x` in a stack frame before executing
DIt searches the AST node for the function definition and reads the parameter value from the parse tree
A tree-walking interpreter implements lexical scoping via a chain of environments. Each function call creates a new environment that binds parameter names (and local variable assignments) to their values, and this environment points to the enclosing scope. Variable lookup walks inward-to-outward: first check the current call's environment, then its enclosing scope, and so on. When the function returns, the local environment is simply abandoned — no explicit cleanup of a stack frame is needed, because environments are ordinary data structures, not memory stacks.
Question 2 Multiple Choice
Why is a tree-walking interpreter slower than a compiler that generates native machine code, even when both correctly execute the same program?
ATree-walking interpreters are written in slower programming languages than compilers
BTree-walking requires reading the source file on every execution, while compilers cache the output
CEvery operation requires navigating pointer-based tree nodes, dispatching on node types, and environment chain lookups — overhead that a compiler eliminates by generating direct machine instructions
DTree-walking interpreters cannot perform arithmetic operations directly; they must call external library functions for every computation
The performance cost of tree-walking is structural: even a simple `3 + 4` requires allocating AST node objects, making recursive `eval` function calls, dispatching on the 'BinaryOp' node type to find the right handler, recursively evaluating both operands, then applying the operator. A compiler emits a single machine `ADD` instruction for the same operation. These overheads multiply across every operation in a program. Tree-walking interpreters are not slow because of language choice or I/O — the overhead is intrinsic to walking pointer-based structures at runtime.
Question 3 True / False
A tree-walking interpreter compiles the AST into bytecode and then executes the bytecode, which is why it requires no separate compilation step.
TTrue
FFalse
Answer: False
This describes a bytecode interpreter (like CPython or the JVM), not a tree-walking interpreter. A tree-walking interpreter executes the AST *directly* — the AST itself is the executable representation. The eval function traverses the tree nodes and performs operations on the spot, with no intermediate representation. The key characteristic is that the AST is walked at execution time, node by node, without any lowering to bytecode or machine code.
Question 4 True / False
A tree-walking interpreter and a compiled language implementation can have identical observable behavior for a given program, even though their internal execution strategies differ entirely.
TTrue
FFalse
Answer: True
Both approaches implement the same language semantics — the observable output of a correct program must be identical regardless of implementation strategy. Compilation to machine code is an optimization that changes the *how* (execution speed, memory layout) but not the *what* (program behavior). This is why tree-walking interpreters are valuable for prototyping and verifying language semantics: if a tree-walker and a compiler disagree on a program's output, one of them has a bug. The behavior is defined by the semantics, not the implementation.
Question 5 Short Answer
How does a tree-walking interpreter implement lexical scoping for nested function calls, and why is a chain of environments the natural solution?
Think about your answer, then reveal below.
Model answer: Each function call creates a new environment (a name-to-value mapping) that binds the function's parameters and any local variables. This environment stores a pointer to its enclosing scope — the environment that was active when the function was defined. Variable lookup starts in the innermost environment and walks outward through the chain until a binding is found. If a nested function references a variable from an outer scope, the lookup naturally traverses the chain. A chain of environments is natural because lexical scope is itself a nested structure: functions are defined inside other scopes, and the environment chain mirrors that nesting relationship directly.
A flat global dictionary would work for a language without nested scopes, but lexical scoping requires tracking which scope a name belongs to. The environment chain solution is elegant because it directly maps the structure of the language (nesting of scopes) to the structure of the runtime (chaining of environment dictionaries). It also automatically handles closures: if a function is returned and called later, its closure captures the enclosing environment pointer, preserving access to outer variables even after the enclosing function has returned.