Writing Interpreters in Rust

This project provides a guide and implementation foundation for building interpreted languages in Rust. Instead of relying on standard Rust collections, the project focuses on implementing custom memory management abstractions to handle the specific challenges of interpreter implementation in a memory-safe language.

The architecture follows a layered approach:

1. Custom Allocator: A specialized allocator designed for interpreter use.
2. Safe-Rust Wrapper: A layer providing safe access to the underlying allocation logic.
3. Compiler and VM: A virtual machine and compiler that interact with the memory management layers.

The goal is to provide a solid foundation for building language features rather than delivering a complete, feature-rich language implementation.

Eval-rs is an interpreter implementation project that follows a layered approach to building a language ecosystem. The implementation progresses through the following stages:

1. Safe Abstraction Layer: Building a safe Rust layer on top of the stickyimmix API.
2. Data Structures: Implementing fundamental types from scratch using the safe layer, specifically: symbols, pairs, arrays, and dicts.
3. Syntax & Parsing: Implementing a compiler for a primitive s-expression syntax language.
4. Execution Engine: Building a bytecode-based virtual machine.

The project aims to implement a classic s-expression based meta-circular evaluator, providing the building blocks necessary to extend it into a full language implementation.

This project is a guide for building interpreters in Rust, structured into three primary technical domains:

1. Allocation: Deep dives into memory management, including alignment, obtaining memory blocks, and understanding allocation types.
2. Sticky Immix: A practical implementation of a single-threaded sticky immix allocator, covering bump allocation, block management, and API definition.
3. Eval-rs: A complete interpreter implementation covering object allocation, tagged pointers, s-expression parsing, bytecode, and virtual machine design/implementation.

The guide follows a progression from low-level memory primitives to high-level language execution.

The ByteCode structure is a composition of two main parts:

1. ArrayOpcode: A collection of the compiled Opcode instructions.
2. Literals: A list of literal values used by the instructions.

To reference literals that are larger than a standard 16-bit integer, the system uses a LiteralId (a u16), which acts as an index into the Literals list. This maintains the fixed 32-bit width for the Opcode enum while allowing support for various literal types.

When working with the low-level RawArray<T>, you can manage memory allocation and growth:

• Allocation: Use RawArray<T>::with_capacity() to allocate a backing store. This method requires a MutatorView instance because it performs allocation.
• Resizing: If the content exceeds current capacity, RawArray<T>::resize() handles allocating a new, larger backing array, copying the old content to the new location, and swapping the pointers.

The compiler uses a hierarchy of data structures to handle lexical scoping:

• Variables: Maintained for every function. It holds a stack of Scope instances and caches all Nonlocal references. It also tracks the parent nesting function to facilitate lexical lookups.
• Scope: Manages the mapping of variable names to specific register numbers within a single scope level. The outermost Scope maps function parameters to registers.
• Nonlocal: Caches the relative stack location of a variable from an outer scope to facilitate the compilation of upvalues.
• Variable: Represents a named, non-global variable. It includes a closed_over flag which defaults to false but is set to true if the compiler detects the variable must escape the stack as part of a closure.

The VM executes bytecode by iterating through instructions in a loop containing a match expression. The primary execution unit is the Thread struct, which represents a single thread of execution. The VM's core operation is performed by a method (typically Thread::eval_next_instr) that fetches the next opcode, decodes it, and executes the corresponding logic. To manage function scopes, the VM narrows the register stack to a 256-register window for the current function.

// The core execution loop pattern
loop {
    match thread.eval_next_instr() {
        // ... execute instruction
    }
}

Closures are implemented by mapping stack locations to shared variables using a Dict type.

1. Compiler Role: The compiler performs lexical scoping analysis to determine the relative stack locations of nonlocal bindings. It generates bytecode that instructs the VM to create a closure.
2. Closure Structure: A closure consists of the target function and a List<Upvalue> (the closure environment).
3. VM Role: When executing the closure creation instruction, the VM calculates the absolute stack locations for each nonlocal binding and populates the List<Upvalue>.
4. Access: Inside the function, bytecode instructions index into this environment to access nonlocal variables.