rlox: A Rust Implementation of “Crafting Interpreters” – Resolving and Binding | behai-nguyen software development learnings and documentation

This post covers Chapter 11 of Crafting Interpreters: Resolving and Binding. No new syntax elements are introduced in this chapter. Instead, Chapter 11 serves as a kind of patch to Chapter 10: it ensures that variables are resolved within their correct closures. The code for this chapter is relatively straightforward, but I made a mistake that introduced a subtle bug—one that took me a long time to diagnose and finally fix.

🦀 Index of the Complete Series.


rlox: A Rust Implementation of “Crafting Interpreters” – Resolving and Binding

🚀 Note: You can download the code for this post from GitHub using:

git clone -b v0.5.1 https://github.com/behai-nguyen/rlox.git

❶ Running the CLI Application

💥 The interactive mode is still available. However, valid expressions—such as ((4.5 / 2) * 2) == 4.50;—currently produce no output. I’m not sure when interactive mode will be fully restored, and it’s not a current priority.

For now, Lox scripts can be executed via the CLI application. For example:

cargo run --release ./tests/data/closure/book_fun_in_closure.lox

Content of book_fun_in_closure.lox:

var a = "global";
{
  fun showA() {
    print a;
  }

  showA();
  var a = "block";
  showA();
}

This Lox script appears at the end of the Static Scope section. What do you think it prints?

For more details, refer to this section of the README.md.

❷ Updated Repository Layout

Legend: ★ = updated, ☆ = new.

💥 Files not modified are omitted for brevity.

.
├── docs
│   └── RLoxGuide.md ★
├── README.md ★
├── src
│   ├── ast_printer.rs ★
│   ├── environment.rs ★
│   ├── expr.rs ★
│   ├── interpreter.rs ★
│   ├── lib.rs ★
│   ├── lox_error_helper.rs ★
│   ├── lox_function.rs ★
│   ├── main.rs ★
│   ├── parser.rs ★
│   ├── resolver.rs ☆
│   ├── stmt.rs ★
│   ├── token.rs ★
│   └── token_type.rs ★
├── tests
│   ├── data/ ☆ ➜ only a few added
│   ├── README.md ★
│   ├── test_common.rs ★
│   ├── test_control_flow.rs ★
│   ├── test_functions.rs ★
│   ├── test_interpreter.rs ★
│   ├── test_parser.rs ★
│   ├── test_resolving_and_binding.rs ☆
│   ├── test_scanner.rs ★
│   └── test_statements_state.rs ★
└── tool
    └── generate_ast
        └── src
            └── main.rs ★

❸ HashMap, Pointer Identity, and Their Driven Refactorings

The code in Chapter 11 is fairly straightforward. However, the new logic in the Interpreter module deserves some discussion. For storing resolved variables, the author uses a HashMap in Java:

32
  private final Map<Expr, Integer> locals = new HashMap<>();

In the resolve() method, the visited expression is stored along with the number of scopes between the variable’s declaration and the current scope. See the reference:

87
88
89
  void resolve(Expr expr, int depth) {
    locals.put(expr, depth);
  }

Later, when accessing a resolved variable, the lookUpVariable() method uses the stored depth to retrieve the correct binding:

482
483
484
485
486
487
488
489
  private Object lookUpVariable(Token name, Expr expr) {
    Integer distance = locals.get(expr);
    if (distance != null) {
      return environment.getAt(distance, name.lexeme);
    } else {
      return globals.get(name);
    }
  }

It’s clear that both methods operate on the actual Expr enum, rather than on the variant structs associated with each enum. The Rust equivalent of Java’s HashMap is also HashMap.

⓵ The Rc<T> Pointer

I ran into some issues with the new code. After several iterations, it became clear that Rc<T> was the correct pointer type to use for the Expr and Stmt enums—rather than Box<T>.

Rc<T> implements PartialEq, Eq, and Hash by delegating to T. This means two Rc<T> instances are considered equal if their inner T values are equal. However, since variables being resolved may have the same name, comparing by value isn’t sufficient. We need pointer identity instead—that is, the HashMap should key off the pointer addresses.

For this reason, the Interpreter’s locals field uses raw pointer keys:

72
    locals: HashMap<*const Expr, usize>,

And in the Interpreter’s resolve() method, we use the pointer address via Rc::as_ptr():

137
138
139
140
    pub fn resolve(&mut self, expr: Rc<Expr>, depth: usize) {
        // Pointer identity, using pointer address: Rc::as_ptr(&expr).
        self.locals.insert(Rc::as_ptr(&expr), depth);
    }

Similarly, the Interpreter’s look_up_variable() method:

142
143
144
145
146
147
148
149
    fn look_up_variable(&self, name: &Token, expr: Rc<Expr>) -> Result<Value, LoxError> {
        // Pointer identity, using pointer address: &Rc::as_ptr(&expr).
        if let Some(&distance) = self.locals.get(&Rc::as_ptr(&expr)) {
            Environment::get_at(&self.environment, name, distance)
        } else {             
            self.globals.borrow().get(name)
        }
    }

💥 It’s essential that the Rc<Expr> instance passed to Interpreter::resolve() is the same one later passed to Interpreter::look_up_variable(). We must not create a new instance using Rc::new() in between. This was the trap I fell into—in transitional code, I created a new instance for the later method without realising it.

To arrive at the correct implementation, the existing code had to be refactored significantly. Rc<Expr> and Rc<Stmt> instances should be created only once. These refactorings are described in the next sections.

Before we move on, note that Rc::clone() increases the reference count but does not change the pointer address. This means we can safely clone an Rc<Expr> instance using either Rc::clone(&expr) or expr.clone().

⓶ The src/token_type.rs and src/token.rs Modules

● All relevant structs and enums must implement the Eq and Hash traits.

● In the src/token_type.rs module, for the TokenType enum, simply add Eq and Hash to the existing #[derive(...)] attribute.

● In the src/token.rs module:

The LiteralValue enum includes a Number(f64) variant. Since f64 does not implement Hash by default—due to NaNs and rounding behavior—you must manually implement Hash for LiteralValue. This can be done by converting the f64 to a bit pattern using to_bits(), which yields a u64 that does implement Hash: please see the implementation.
The Eq trait is a marker trait—it defines no methods or associated types. Its implementation is simple.
Once LiteralValue implements both Hash and Eq, you can then add Eq and Hash to the #[derive(...)] attribute of the Token struct: please see.
Also, all get_ prefixes were removed from getter methods to comply with idiomatic Rust naming conventions.

⓷ The src/expr.rs and src/stmt.rs Modules

● As mentioned at the outset, the Rc<T> smart pointer has replaced the Box<T> pointer. This enables shared ownership and identity preservation across the AST.

● All enums and variant structs now implement the Eq and Hash traits.

● 💡 Crucially, all Visitor<T>’s visit_* methods now receive the outer enum type directly—i.e., Rc<Expr> and Rc<Stmt>—rather than the inner variant struct.

● 💡 Equally important, the accept() and accept_ref() methods have been updated to take Rc<Expr> and Rc<Stmt> as parameters, replacing &mut self and &self. For example:

impl Expr {
    pub fn accept<T>(expr: Rc<Expr>, visitor: &mut dyn Visitor<T>) -> Result<T, LoxRuntimeError> {
	...
	}

    pub fn accept_ref<T>(expr: Rc<Expr>, visitor: &mut dyn Visitor<T>) -> Result<T, LoxRuntimeError> {
	...
    }
}

and

impl Stmt {
    pub fn accept<T>(stmt: Rc<Stmt>, visitor: &mut dyn Visitor<T>) -> Result<T, LoxRuntimeError> {
	...
    }

    pub fn accept_ref<T>(stmt: Rc<Stmt>, visitor: &mut dyn Visitor<T>) -> Result<T, LoxRuntimeError> {
	...
    }
}

This refactoring ensures that the original Rc<Expr> and Rc<Stmt> instances are passed around without altering their pointer identity.

● As discussed previously, these modules are generated by tool/generate_ast/src/main.rs. This generator has been updated accordingly, and the helper function get_constructor_overrides() was removed.

● Also, all get_ prefixes were removed from getter methods to comply with idiomatic Rust naming conventions.

⓸ The src/parser.rs Module

This is the starting point: the Parser is responsible for creating all Expr and Stmt instances. The refactoring is straightforward:

Methods that previously returned Result<Expr, LoxError> now return Result<Rc<Expr>, LoxError>.
Methods that previously returned Result<Stmt, LoxError> now return Result<Rc<Stmt>, LoxError>.
The public parse() method now returns Result<Vec<Rc<Stmt>>, LoxError>.

⓹ The src/interpreter.rs Module

The public interpret() method now takes a reference to a list of Rc<Stmt>: &Vec<Rc<Stmt>>.
This change propagates through to other helper methods and visitor implementations.

⓺ The Test Area

Changes to public methods in the main modules required minor updates across all existing test modules. These changes should be self-explanatory.

❹ The New Code: the Resolver

⓵ Some Implementation Details

The implementation closely mirrors the author’s original Java version. Here are a few noteworthy details:

The scopes field is implemented as Vec<HashMap<String, bool>>, representing a stack of lexical scopes.
Instances of Rc<Expr> and Rc<Stmt> passed to the Resolver must be the exact same ones passed to the Interpreter. Creating new Rc wrappers around existing Expr or Stmt objects will break resolution, as pointer identity is used to track bindings.

⓶ Incorporating the Resolver

As described in the book, the Parser returns a list of statements: Vec<Rc<Stmt>>. This list is first passed to the Resolver. If resolution succeeds, it is then passed to the Interpreter:

51
52
53
54
55
56
57
58
59
	match resolver.resolve(&statements) {
	  Err(err) => println!("Resolve error: {}", err),
		Ok(_) => {
			match interpreter.interpret(&statements) {
				Err(err) => println!("Evaluation error: {}", err),
				Ok(_) => (),
			}
		}
	}

See the full run() method.

❺ Test Updates

● A new module, tests/test_resolving_and_binding.rs, was added. Its structure and conventions follow those of the existing test modules.

● 💥 After incorporating the Resolver, many test scripts in the previously introduced tests/test_functions.rs module began failing. These scripts were migrated to the new tests/test_resolving_and_binding.rs module to reflect their dependency on resolution.

● 👉 What do you think is the output of the script introduced at the beginning of this article?

● Only a handful of test scripts from the author’s Crafting Interpreters test suite have been incorporated to test the code of this chapter.

❻ What’s Next

That wraps up Chapter 11: Resolving and Binding. There are still a few warnings about dead code, which I’m okay with for now. Two chapters remain in Part II, and I’m aiming to complete them during August 2025.

Thanks for reading! I hope this post helps others on the same journey. As always—stay curious, stay safe 🦊

✿✿✿

Feature image sources: