Writing Interpreters in Rust: a Guide

https://rust-hosted-langs.github.io/book/
Admin
A comprehensive guide to implementing interpreted languages in Rust, covering custom allocators,...
Tokens:86,790
Snippets:636
Trust Score:8.3
Update:9 months ago
Show doc for...
Tokens:
Raw
### Bytecode Opcode Encoding Example (Conceptual)

Source: https://rust-hosted-langs.github.io/book/print

Illustrates a conceptual 32-bit encoding scheme for a register-based virtual machine's opcodes. This example shows how an addition operation might be represented, allocating bits for the operator and operand register numbers.

```plaintext
   32.....24......16.......8.......0
    [reg a ][reg b ][reg x ][Add   ]
```

--------------------------------

### Convert Byte Arguments to Line Counts in Rust

Source: https://rust-hosted-langs.github.io/book/chapter-simple-bump

Converts byte-based arguments 'starting_at' and 'alloc_size' into line counts for memory management. It calculates the starting line and the number of lines required, using constants for line size.

```rust
let starting_line = starting_at / constants::LINE_SIZE;
let lines_required = (alloc_size + constants::LINE_SIZE - 1) / constants::LINE_SIZE;
```

--------------------------------

### Scheme 'let' Expression Example and Compilation

Source: https://rust-hosted-langs.github.io/book/chapter-interp-compiler-design

Demonstrates the 'let' expression in Scheme for variable binding and function calls. Compilation involves pushing new scopes onto a stack for bindings and evaluating expressions within these scopes.

```scheme
__
(let ((add_3 (make_adder 3)))
  (add_3 4))


```

--------------------------------

### Example Interpreter Implementation for Mutator Trait (Rust)

Source: https://rust-hosted-langs.github.io/book/chapter-interp-alloc

Provides a concrete example of an `Interpreter` struct that implements the `Mutator` trait. It demonstrates allocating a `Stack` object, creating `Roots` with a pointer to the stack, and accessing the stack pointer through `roots.stack.get(mem)`. It highlights compile-time errors when trying to access the stack pointer outside the `run` function's scope.

```rust
struct Stack {}

impl Stack {
    fn say_hello(&self) {
        println!("I'm the stack!");
    }
}

struct Roots {
    stack: CellPtr<Stack>
}

impl Roots {
    fn new(stack: ScopedPtr<'_, Stack>) -> Roots {
        Roots {
            stack: CellPtr::new_with(stack)
        }
    }
}

struct Interpreter {}

impl Mutator for Interpreter {
    type Input: ();
    type Output: Roots;

    fn run(&self, mem: &MutatorView, input: Self::Input) -> Result<Self::Output, RuntimeError> {
        let stack = mem.alloc(Stack {})?;
        stack.say_hello();

        let roots = Roots::new(stack);

        let stack_ptr = roots.stack.get(mem);
        stack_ptr.say_hello();

        Ok(roots)
    }
}

fn main() {
    ...
    let interp = Interpreter {};

    let result = memory.mutate(&interp, ());

    let roots = result.unwrap();

    // no way to do this - compile error
    let stack = roots.stack.get();
    ...
}
```

--------------------------------

### StickyImmixHeap Implementation

Source: https://rust-hosted-langs.github.io/book/print

Demonstrates the implementation of the `AllocRaw` trait for the `StickyImmixHeap` struct.

```APIDOC
## `StickyImmixHeap` Implementation of `AllocRaw`

### Description
Implements the `AllocRaw` trait for the `StickyImmixHeap` struct, allowing it to perform raw memory allocations. The associated `Header` type is determined by the generic parameter `H`.

### Method
`impl<H: AllocHeader> AllocRaw for StickyImmixHeap<H>`

### Associated Types
- **Header** (`type`): `H` - The header type is provided by the generic parameter `H`, which must implement `AllocHeader`.
```

--------------------------------

### Compile Function Implementation Excerpt (Rust)

Source: https://rust-hosted-langs.github.io/book/print

An excerpt from the `compile_function` implementation in Rust, showing validation of function name and parameters, setting up the parameter scope, and iterating through expressions for compilation.

```rust
fn compile_function<'guard>(
    mut self,
    mem: &'guard MutatorView,
    name: TaggedScopedPtr<'guard>,
    params: &[TaggedScopedPtr<'guard>],
    exprs: &[TaggedScopedPtr<'guard>],
) -> Result<ScopedPtr<'guard, Function>, RuntimeError> {
    // validate function name
    self.name = match *name {
        Value::Symbol(s) => Some(String::from(s.as_str(mem))),
        Value::Nil => None,
        _ => {
            return Err(err_eval(
                "A function name may be nil (anonymous) or a symbol (named)",
            ))
        }
    };
    let fn_name = name;

    // validate arity
    if params.len() > 254 {
        return Err(err_eval("A function cannot have more than 254 parameters"));
    }
    // put params into a list for the Function object
    let fn_params = List::from_slice(mem, params)?;

    // also assign params to the first level function scope and give each one a register
    let mut param_scope = Scope::new();
    self.next_reg = param_scope.push_bindings(params, self.next_reg)?;
    self.vars.scopes.push(param_scope);

    // validate expression list
    if exprs.len() == 0 {
        return Err(err_eval("A function must have at least one expression"));
    }

    // compile expressions
    let mut result_reg = 0;
    for expr in exprs.iter() {
        result_reg = self.compile_eval(mem, *expr)?;
    }

    // pop parameter scope

```

--------------------------------

### AllocRaw Trait - Array Allocation

Source: https://rust-hosted-langs.github.io/book/chapter-allocation-api

Details the `AllocRaw` trait and its `alloc_array` method for allocating raw byte arrays.

```APIDOC
## AllocRaw Trait - Array Allocation

### Description
Defines the interface for raw memory allocation, including a specific method for allocating byte arrays.

### Method
`alloc_array`

### Endpoint
N/A (Trait method)

### Parameters
#### Path Parameters
None

#### Query Parameters
None

#### Request Body
None

### Request Example
```rust
pub trait AllocRaw {
    ...
    fn alloc_array(&self, size_bytes: ArraySize) -> Result<RawPtr<u8>, AllocError>;
    ...
}
```

### Response
#### Success Response (200)
- **RawPtr<u8>** - A raw pointer to the allocated byte array.
- **AllocError** - An error type if allocation fails.

#### Response Example
N/A
```

--------------------------------

### AllocRaw Trait - Full Definition

Source: https://rust-hosted-langs.github.io/book/chapter-allocation-api

Presents the complete definition of the `AllocRaw` trait, outlining all its methods for object and array allocation, and pointer manipulation.

```APIDOC
## AllocRaw Trait - Full Definition

### Description
This trait provides the core interface for raw memory allocation in the Rust allocator system. It includes methods for allocating single objects, arrays, and for retrieving object headers from pointers.

### Method
- `alloc<T>`: Allocates a single object of type `T`.
- `alloc_array`: Allocates a raw byte array.
- `get_header`: Retrieves the header for a given object pointer.
- `get_object`: Retrieves the object pointer from a header pointer.

### Endpoint
N/A (Trait definition)

### Parameters
#### Path Parameters
None

#### Query Parameters
None

#### Request Body
None

### Request Example
```rust
pub trait AllocRaw {
    /// An implementation of an object header type
    type Header: AllocHeader;

    /// Allocate a single object of type T.
    fn alloc<T>(&self, object: T) -> Result<RawPtr<T>, AllocError>
    where
        T: AllocObject<<Self::Header as AllocHeader>::TypeId>;

    /// Allocating an array allows the client to put anything in the resulting data
    /// block but the type of the memory block will simply be 'Array'. No other
    /// type information will be stored in the object header.
    /// This is just a special case of alloc<T>() for T=u8 but a count > 1 of u8
    /// instances.  The caller is responsible for the content of the array.
    fn alloc_array(&self, size_bytes: ArraySize) -> Result<RawPtr<u8>, AllocError>;

    /// Given a bare pointer to an object, return the expected header address
    fn get_header(object: NonNull<()>) -> NonNull<Self::Header>;

    /// Given a bare pointer to an object's header, return the expected object address
    fn get_object(header: NonNull<Self::Header>) -> NonNull<()>;
}
```

### Response
#### Success Response (200)
- **type Header: AllocHeader** - Associated type representing the object header.
- **Result<RawPtr<T>, AllocError>** - Result of allocating a single object.
- **Result<RawPtr<u8>, AllocError>** - Result of allocating an array.
- **NonNull<Self::Header>** - Non-null pointer to the object's header.
- **NonNull<()>** - Non-null pointer to the object itself.

#### Response Example
N/A
```

--------------------------------

### Implement From<FatPtr> for TaggedPtr (Rust)

Source: https://rust-hosted-langs.github.io/book/chapter-interp-tagged-ptrs

Implements the `From<FatPtr>` trait for `TaggedPtr`. This allows converting various `FatPtr` variants (like arrays, dictionaries, numbers, symbols) into their corresponding `TaggedPtr` representations.

```rust
impl From<FatPtr> for TaggedPtr {
    fn from(ptr: FatPtr) -> TaggedPtr {
        match ptr {
            FatPtr::ArrayU8(raw) => TaggedPtr::object(raw),
            FatPtr::ArrayU16(raw) => TaggedPtr::object(raw),
            FatPtr::ArrayU32(raw) => TaggedPtr::object(raw),
            FatPtr::Dict(raw) => TaggedPtr::object(raw),
            FatPtr::Function(raw) => TaggedPtr::object(raw),
            FatPtr::List(raw) => TaggedPtr::object(raw),
            FatPtr::Nil => TaggedPtr::nil(),
            FatPtr::Number(value) => TaggedPtr::number(value),
            FatPtr::NumberObject(raw) => TaggedPtr::object(raw),
            FatPtr::Pair(raw) => TaggedPtr::pair(raw),
            FatPtr::Partial(raw) => TaggedPtr::object(raw),
            FatPtr::Text(raw) => TaggedPtr::object(raw),
            FatPtr::Symbol(raw) => TaggedPtr::symbol(raw),
            FatPtr::Upvalue(raw) => TaggedPtr::object(raw),
        }
    }
}
```

--------------------------------

### Optimize VM Instruction Dispatch with Rust `match`

Source: https://rust-hosted-langs.github.io/book/chapter-interp-vm-design

Illustrates an optimized dispatch mechanism for a Rust virtual machine. It utilizes a `match` expression within a loop to efficiently fetch, decode, and map VM instruction opcodes to their corresponding handlers, minimizing overhead.

```Rust
loop {
    let opcode = get_next_opcode();
    match opcode {
        Opcode::Add(a, x, y) => { /* handle addition */ },
        Opcode::Call(f, r, p) => { /* handle function call */ },
        // ... other opcodes
    }
}
```

--------------------------------

### Implement get method for CellPtr to obtain ScopedPtr in Rust

Source: https://rust-hosted-langs.github.io/book/chapter-interp-alloc

Implements the get method for CellPtr<T>, which takes a MutatorScope guard and returns a ScopedPtr<'guard, T>. This method utilizes the scoped_ref implementation of RawPtr to safely obtain a dereferenceable pointer within the specified guard's lifetime.

```rust
impl<T: Sized> CellPtr<T> {
    pub fn get<'guard>(&self, guard: &'guard dyn MutatorScope) -> ScopedPtr<'guard, T> {
        ScopedPtr::new(guard, self.inner.get().scoped_ref(guard))
    }
}

```

--------------------------------

### Implement Partial Functions in Rust VM

Source: https://rust-hosted-langs.github.io/book/chapter-interp-vm-design

Demonstrates the concept of partial functions in a Rust virtual machine, where functions are first-class objects. It allows for passing insufficient arguments to a function, returning a `Partial` instance that holds the arguments and a pointer to the function.

```Rust
struct Partial {
    args: Vec<Value>,
    func_ptr: FunctionPointer
}

// Example usage:
// let mul = (def mul (x y) (* x y))
// let partial_mul = (mul 3) // Creates a Partial instance holding '3' and 'mul' function pointer
// let result = (partial_mul 5) // Calls 'mul' with arguments 3 and 5
```

--------------------------------

### Rust VM Instruction Dispatch with Match Expression

Source: https://rust-hosted-langs.github.io/book/print

Illustrates the dispatch mechanism for a virtual machine in Rust. It shows a loop that fetches the next opcode and uses a `match` expression to handle different `Opcode` variants, executing corresponding logic. This approach optimizes the overhead between VM instructions.

```Rust
loop {
    let opcode = get_next_opcode();
    match opcode {
        Opcode::Add(a, x, y) => { ... },
        Opcode::Call(f, r, p) => { ... },
    }
}
```

--------------------------------

### Implement TaggedCellPtr::get() Method in Rust

Source: https://rust-hosted-langs.github.io/book/chapter-interp-tagged-ptrs

Implements the `get()` method for `TaggedCellPtr`. This method returns a `TaggedScopedPtr<'guard>`, providing a dereferenceable view of the tagged pointer. It requires a `MutatorScope` as a guard.

```rust
impl TaggedCellPtr {
    pub fn get<'guard>(&self, guard: &'guard dyn MutatorScope) -> TaggedScopedPtr<'guard> {
        TaggedScopedPtr::new(guard, self.inner.get())
    }
}

```

--------------------------------

### Scheme 'let' Expression and Compilation

Source: https://rust-hosted-langs.github.io/book/print

Demonstrates the declaration and assignment of variables using the 'let' keyword in Scheme and explains how this translates to nested scopes and register allocation in the compiler. It highlights the process of pushing and popping scopes and reserving registers for bindings.

```scheme
__
(let ((add_3 (make_adder 3))) 
  (add_3 4))

```

--------------------------------

### Get Object Header from Pointer in Rust

Source: https://rust-hosted-langs.github.io/book/chapter-allocation-api

This Rust code demonstrates a function signature for retrieving an object's header from a raw pointer. It highlights the challenge of a signature that cannot refer to the concrete object type `T` to accommodate runtime type derivation by the garbage collector or interpreter.

```rust
pub trait AllocRaw {
    ...

    // looks good but won't work in all cases
    fn get_header<T>(object: RawPtr<T>) -> NonNull<Self::Header>
    where
        T: AllocObject<<Self::Header as AllocHeader>::TypeId>;

    ...

}
```

--------------------------------

### Rust Trait for Raw Allocation - Get Object Function

Source: https://rust-hosted-langs.github.io/book/print

Includes the `get_object` function within the `AllocRaw` trait. This function performs the inverse operation of `get_header`, taking a pointer to an object's header (`NonNull<Self::Header>`) and returning a raw pointer to the object itself (`NonNull<()`).

```rust
pub trait AllocRaw {
    ...

    fn get_object(header: NonNull<Self::Header>) -> NonNull<()>;

    ...
}
```

--------------------------------

### Access Raw Pointer in Rust Block

Source: https://rust-hosted-langs.github.io/book/chapter-blocks

Provides the `as_ptr` method for the `Block` struct, returning the raw pointer to the start of the allocated memory block as a `*const u8`. This allows for direct memory access but requires careful handling to avoid invalid operations.

```rust
pub fn as_ptr(&self) -> *const u8 {
    self.ptr.as_ptr()
}
```

--------------------------------

### Helper Functions for TaggedPtr Instantiation (Rust)

Source: https://rust-hosted-langs.github.io/book/chapter-interp-tagged-ptrs

Provides helper functions to create `TaggedPtr` instances for different types like nil, numbers, and symbols. These functions handle the necessary bitwise operations for tagging pointers.

```rust
impl TaggedPtr {
    pub fn nil() -> TaggedPtr {
        TaggedPtr { tag: 0 }
    }

    pub fn number(value: isize) -> TaggedPtr {
        TaggedPtr {
            number: (((value as usize) << 2) | TAG_NUMBER) as isize,
        }
    }

    pub fn symbol(ptr: RawPtr<Symbol>) -> TaggedPtr {
        TaggedPtr {
            symbol: ptr.tag(TAG_SYMBOL),
        }
    }

    fn pair(ptr: RawPtr<Pair>) -> TaggedPtr {
        TaggedPtr {
            pair: ptr.tag(TAG_PAIR),
        }
    }
}
```

--------------------------------

### Get Object from Header Pointer in Rust

Source: https://rust-hosted-langs.github.io/book/chapter-allocation-api

This Rust code snippet defines a function `get_object` within the `AllocRaw` trait. It takes a non-null pointer to a header (`NonNull<Self::Header>`) and returns a non-null pointer to the corresponding object (`NonNull<()>`). This function allows retrieval of the object representation from its header.

```rust
pub trait AllocRaw {
    ...

    fn get_object(header: NonNull<Self::Header>) -> NonNull<()>;

    ...

}
```

--------------------------------

### Compile Function and Push Instructions in Rust

Source: https://rust-hosted-langs.github.io/book/chapter-interp-compiler-impl

Compiles a function by popping closing instructions and pushing them onto the memory. It then appends a return opcode and retrieves the function's bytecode and non-local variables. Finally, it allocates and returns a Function object.

```rust
let closing_instructions = self.vars.pop_scope();
        for opcode in &closing_instructions {
            self.push(mem, *opcode)?;
        }

        // finish with a return
        let fn_bytecode = self.bytecode.get(mem);
        fn_bytecode.push(mem, Opcode::Return { reg: result_reg })?;

        let fn_nonlocals = self.vars.get_nonlocals(mem)?;

        Ok(Function::alloc(
            mem,
            fn_name,
            fn_params,
            fn_bytecode,
            fn_nonlocals,
        )?)
    }
```

--------------------------------

### Rust: Implement ByteCode Methods for Compilation

Source: https://rust-hosted-langs.github.io/book/chapter-interp-bytecode

Provides essential methods for compiling bytecode. `push` adds an opcode to the `ArrayOpcode`. `update_jump_offset` adjusts jump instruction targets. `push_lit` adds a literal to the `Literals` list and returns its ID. `push_loadlit` adds a load instruction for a given literal ID.

```rust
fn push<'guard>(&self, mem: &'MutatorView, op: Opcode) -> Result<(), RuntimeError>;

fn update_jump_offset<'guard>(
    &self,
    mem: &'guard MutatorView,
    instruction: ArraySize,
    offset: JumpOffset,
) -> Result<(), RuntimeError>;

fn push_lit<'guard>(
    &self,
    mem: &'guard MutatorView,
    literal: TaggedScopedPtr
) -> Result<LiteralId, RuntimeError>;

fn push_loadlit<'guard>(
    &self,
    mem: &'guard MutatorView,
    dest: Register,
    literal_id: LiteralId,
) -> Result<(), RuntimeError>;
```

--------------------------------

### Allocate Aligned Memory Blocks in Rust

Source: https://rust-hosted-langs.github.io/book/chapter-blocks

Implements `Block::new` to allocate memory blocks. It requires the `size` to be a power of two for alignment, validating this condition first. If validation passes, it calls `internal::alloc_block` to get a `BlockPtr`. Returns a `Block` or a `BlockError` (BadRequest or OOM).

```rust
pub fn new(size: BlockSize) -> Result<Block, BlockError> {
    if !size.is_power_of_two() {
        return Err(BlockError::BadRequest);
    }

    Ok(Block {
        ptr: internal::alloc_block(size)?,
        size,
    })
}
```

--------------------------------

### Function to Create Adder (Lisp-like)

Source: https://rust-hosted-langs.github.io/book/chapter-interp-compiler-design

Presents a function 'make_adder' that takes an argument 'n' and returns another function (a closure). The returned function takes an argument 'x' and returns the sum of 'x' and 'n', demonstrating closure creation and nonlocal variable capture.

```lisp
(def make_adder (n)
  (lambda (x) (+ x n))
)

```

--------------------------------

### Rust Trait for Raw Allocation - Get Header Function

Source: https://rust-hosted-langs.github.io/book/print

Adds a `get_header` function to the `AllocRaw` trait. This function takes a raw pointer to an object (`NonNull<()`) and returns a non-null pointer to its corresponding header (`NonNull<Self::Header>`). This allows access to object metadata without knowing the concrete object type.

```rust
pub trait AllocRaw {
    ...

    fn get_header(object: NonNull<()>) -> NonNull<Self::Header>;

    ...
}
```

--------------------------------

### Rust find_next_available_hole Function

Source: https://rust-hosted-langs.github.io/book/chapter-simple-bump

Implements a function within BlockMeta to find the next available contiguous block of unmarked lines (a hole) within a memory block, suitable for allocating an object of a given size. It searches downwards from a starting point, considering line mark bits to identify allocatable spaces.

```rust
    /// When it comes to finding allocatable holes, we bump-allocate downward.
    pub fn find_next_available_hole(
        &self,
        starting_at: usize,
        alloc_size: usize,
    ) -> Option<(usize, usize)> {
        // The count of consecutive avaliable holes. Must take into account a conservatively marked
        // hole at the beginning of the sequence.
        let mut count = 0;
        let starting_line = starting_at / constants::LINE_SIZE;
        let lines_required = (alloc_size + constants::LINE_SIZE - 1) / constants::LINE_SIZE;
        // Counting down from the given search start index
        let mut end = starting_line;

        for index in (0..starting_line).rev() {
            let marked = unsafe { *self.lines.add(index) };

            if marked == 0 {
                // count unmarked lines
                count += 1;

                if index == 0 && count >= lines_required {
                    let limit = index * constants::LINE_SIZE;
                    let cursor = end * constants::LINE_SIZE;
                    return Some((cursor, limit));
                }
            } else {
                // This block is marked
                if count > lines_required {
                    // But at least 2 previous blocks were not marked. Return the hole, considering the
                    // immediately preceding block as conservatively marked
                    let limit = (index + 2) * constants::LINE_SIZE;
                    let cursor = end * constants::LINE_SIZE;
                    return Some((cursor, limit));
                }

                // If this line is marked and we didn't return a new cursor/limit pair by now,
                // reset the hole search state
                count = 0;
                end = index;
            }
        }

        None
    }
```

--------------------------------

### Rust Function Compilation Entrypoint

Source: https://rust-hosted-langs.github.io/book/chapter-interp-compiler-impl

The `compile_function` method serves as the main entry point for compiling a function definition. It sets up the initial variable scope with provided parameters and then iteratively calls `compile_eval` for each expression within the function body.

```rust
fn compile_function<'guard>(
    mut self,
    mem: &'guard MutatorView,
    name: TaggedScopedPtr<'guard>,
    params: &[TaggedScopedPtr<'guard>],
    exprs: &[TaggedScopedPtr<'guard>],
) -> Result<ScopedPtr<'guard, Function>, RuntimeError> {
    ...
}

```

--------------------------------

### Rust: Define Block Size Constants for Bump Allocation

Source: https://rust-hosted-langs.github.io/book/chapter-simple-bump

Defines constants for block size in bits and bytes. BLOCK_SIZE_BITS is set to 15, resulting in a BLOCK_SIZE of 32768 (32k). This fixed power-of-two block size is beneficial for garbage collection by allowing easy calculation of the block's start address.

```rust
pub const BLOCK_SIZE_BITS: usize = 15;
pub const BLOCK_SIZE: usize = 1 << BLOCK_SIZE_BITS;

```

--------------------------------

### Rust: Read Array Element Reference

Source: https://rust-hosted-langs.github.io/book/chapter-interp-arrays

This Rust function, `read_ref`, provides a reference to an array element at a given index. It uses `get_offset` to get a pointer and then converts it into a reference. This method adheres to reference semantics, returning a direct reference to the data in the backing memory. It requires a `MutatorScope` guard and returns a `Result` containing a reference to the element or a `RuntimeError`.

```rust
impl<T: Sized + Clone> Array<T> {
    pub fn read_ref<'guard>(
        &self,
        _guard: &'guard dyn MutatorScope,
        index: ArraySize,
    ) -> Result<&T, RuntimeError> {
        unsafe {
            let dest = self.get_offset(index)?;
            Ok(&*dest as &T)
        }
    }
}
```

--------------------------------

### Rust VM: MakeClosure Instruction for Creating Closures

Source: https://rust-hosted-langs.github.io/book/chapter-interp-vm-impl

This snippet details the `MakeClosure` instruction in a Rust VM. It describes how a new `Partial` object is created, an environment of `Upvalue` objects is populated by referencing nonlocal variables, and the `dest` register is updated with the new closure instance. It handles errors if the target is not a function.

```rust
Opcode::MakeClosure { dest, function } => {
    // 1. iter over function nonlocals
    //   - calculate absolute stack offset for each
    //   - find existing or create new Upvalue for each
    //   - create closure environment with list of Upvalues
    // 2. create new Partial with environment
    // 3. set dest to Partial
    let function_ptr = window[function as usize].get(mem);
    if let Value::Function(f) = *function_ptr {
        let nonlocals = f.nonlocals(mem);
        // Create an environment array for upvalues
        let env = List::alloc_with_capacity(mem, nonlocals.length())?;

        // Iter over function nonlocals, calculating absolute stack offset for each
        nonlocals.access_slice(mem, |nonlocals| -> Result<(), RuntimeError> {
            for compound in nonlocals {
                // extract 8 bit register and call frame values from 16 bit nonlocal
                // descriptors
                let frame_offset = (*compound >> 8) as ArraySize;
                let window_offset = (*compound & 0xff) as ArraySize;

                // look back frame_offset frames and add the register number to
                // calculate the absolute stack position of the value
                let frame = frames.get(mem, frames.length() - frame_offset)?;
                let location = frame.base + window_offset;

                // look up, or create, the Upvalue for the location, and add it to
                // the environment
                let (_, upvalue) = self.upvalue_lookup_or_alloc(mem, location)?;
                StackAnyContainer::push(&*env, mem, upvalue.as_tagged(mem))?;
            }

            Ok(())
        })?;

        // Instantiate a Partial function application from the closure environment
        // and set the destination register
        let partial = Partial::alloc(mem, f, Some(env), &[])?;
        window[dest as usize].set(partial.as_tagged(mem));
    } else {
        return Err(err_eval("Cannot make a closure from a non-Function type"));
    }
}

```

--------------------------------

### Rust: Get Array Element Offset with Bounds Checking

Source: https://rust-hosted-langs.github.io/book/chapter-interp-arrays

This Rust function, `get_offset`, retrieves a mutable pointer to an array element at a given index. It performs bounds checking to ensure the index is within the array's length and that the array has allocated backing memory. It returns a `Result` which is either a pointer to the element or a `RuntimeError` if bounds checks fail.

```rust
impl<T: Sized + Clone> Array<T> {
    fn get_offset(&self, index: ArraySize) -> Result<*mut T, RuntimeError> {
        if index >= self.length.get() {
            Err(RuntimeError::new(ErrorKind::BoundsError))
        } else {
            let ptr = self
                .data
                .get()
                .as_ptr()
                .ok_or_else(|| RuntimeError::new(ErrorKind::BoundsError))?;

            let dest_ptr = unsafe { ptr.offset(index as isize) as *mut T };

            Ok(dest_ptr)
        }
    }
}
```

--------------------------------

### Heap Allocation Method for Tagged Pointers in Rust

Source: https://rust-hosted-langs.github.io/book/chapter-interp-tagged-ptrs

Shows an implementation of the `alloc_tagged` method for a `Heap` struct in Rust. This method allocates an object, converts its raw pointer to a `FatPtr`, and then to a `TaggedPtr`. It demonstrates the use of `From` trait implementations for type conversions during heap allocation.

```rust
impl Heap {
    fn alloc_tagged<T>(&self, object: T) -> Result<TaggedPtr, RuntimeError>
    where
        FatPtr: From<RawPtr<T>>,
        T: AllocObject<TypeList>,
    {
        Ok(TaggedPtr::from(FatPtr::from(self.heap.alloc(object)?)))
    }
}

```

--------------------------------

### S-expression AST Parsing to Pair and Symbol

Source: https://rust-hosted-langs.github.io/book/print

Illustrates the parsing of s-expression syntax into an abstract syntax tree (AST) composed of `Pair` and `Symbol` types. This forms the basis for the compiler's understanding of code structure, with extensions for other data types like integers and strings being straightforward.

```rust
Pair(
  Symbol(function_name),
  Pair(
    Symbol(arg1),
    Pair(
      Symbol(arg2),
      nil
    )
  )
)
```

--------------------------------

### Simplified Get Header Function in Rust

Source: https://rust-hosted-langs.github.io/book/chapter-allocation-api

This Rust code presents a simplified `get_header` function signature within the `AllocRaw` trait. It takes a generic `NonNull<()>` pointer, abstracting away the concrete object type, and returns a `NonNull<Self::Header>`. This design allows the garbage collector and interpreter to access headers without knowing the specific object type at runtime.

```rust
pub trait AllocRaw {
    ...

    fn get_header(object: NonNull<()>) -> NonNull<Self::Header>;

    ...

}
```

--------------------------------

### Implement alloc method for Heap to proxy StickyImmixHeap allocation in Rust

Source: https://rust-hosted-langs.github.io/book/chapter-interp-alloc

Implements an alloc method for the Heap struct that proxies the allocation function of the wrapped StickyImmixHeap. It handles potential RuntimeError conversions from the underlying heap allocation.

```rust
impl Heap {
    fn alloc<T>(&self, object: T) -> Result<RawPtr<T>, RuntimeError>
    where
        T: AllocObject<TypeList>,
    {
        Ok(self.heap.alloc(object)?)
    }
}

```

--------------------------------

### AllocHeader Trait

Source: https://rust-hosted-langs.github.io/book/print

Defines the interface for an object header, including a method for creating new array headers.

```APIDOC
## `AllocHeader` Trait

### Description
Trait for object headers, requiring implementations to provide methods for managing object metadata and creation, including specialized array allocation.

### Method
`new_array(size: ArraySize, size_class: SizeClass, mark: Mark) -> Self`

### Parameters
- **size** (ArraySize) - Required - The size of the array to be allocated.
- **size_class** (SizeClass) - Required - The size class associated with the array.
- **mark** (Mark) - Required - The mark associated with the array.

### Response
Returns a new object header for an array of u8.
```

--------------------------------

### Rust VM MakeClosure Instruction Implementation

Source: https://rust-hosted-langs.github.io/book/print

This Rust code implements the MakeClosure instruction for a virtual machine. It handles the creation of closures by allocating Upvalues for nonlocal variables, constructing a closure environment, and instantiating a Partial function. It takes 'dest' and 'function' registers as operands and returns a Partial instance to the 'dest' register.

```rust
Opcode::MakeClosure { dest, function } => {
                    // 1. iter over function nonlocals
                    //   - calculate absolute stack offset for each
                    //   - find existing or create new Upvalue for each
                    //   - create closure environment with list of Upvalues
                    // 2. create new Partial with environment
                    // 3. set dest to Partial
                    let function_ptr = window[function as usize].get(mem);
                    if let Value::Function(f) = *function_ptr {
                        let nonlocals = f.nonlocals(mem);
                        // Create an environment array for upvalues
                        let env = List::alloc_with_capacity(mem, nonlocals.length())?;

                        // Iter over function nonlocals, calculating absolute stack offset for each
                        nonlocals.access_slice(mem, |nonlocals| -> Result<(), RuntimeError> {
                            for compound in nonlocals {
                                // extract 8 bit register and call frame values from 16 bit nonlocal
                                // descriptors
                                let frame_offset = (*compound >> 8) as ArraySize;
                                let window_offset = (*compound & 0xff) as ArraySize;

                                // look back frame_offset frames and add the register number to
                                // calculate the absolute stack position of the value
                                let frame = frames.get(mem, frames.length() - frame_offset)?;
                                let location = frame.base + window_offset;

                                // look up, or create, the Upvalue for the location, and add it to
                                // the environment
                                let (_, upvalue) = self.upvalue_lookup_or_alloc(mem, location)?;
                                StackAnyContainer::push(&*env, mem, upvalue.as_tagged(mem))?;
                            }

                            Ok(())
                        })?;

                        // Instantiate a Partial function application from the closure environment
                        // and set the destination register
                        let partial = Partial::alloc(mem, f, Some(env), &[])?;
                        window[dest as usize].set(partial.as_tagged(mem));
                    } else {
                        return Err(err_eval("Cannot make a closure from a non-Function type"));
                    }
                }
```

--------------------------------

### Iterate and Find Available Memory Holes in Rust

Source: https://rust-hosted-langs.github.io/book/chapter-simple-bump

Iterates through lines in decreasing order from 'starting_line' down to zero to find available memory holes. It fetches the 'marked' bit for each line and increments a counter if the line is unmarked. This loop contains logic to identify suitable holes and terminate early if a large enough hole is found or if no suitable hole exists.

```rust
for index in (0..starting_line).rev() {
    let marked = unsafe { *self.lines.add(index) };

    if marked == 0 {
        count += 1;

        if index == 0 && count >= lines_required {
            let limit = index * constants::LINE_SIZE;
            let cursor = end * constants::LINE_SIZE;
            return Some((cursor, limit));
        }
    } else {
        if count > lines_required {
            let limit = (index + 2) * constants::LINE_SIZE;
            let cursor = end * constants::LINE_SIZE;
            return Some((cursor, limit));
        }

        count = 0;
        end = index;
    }

}

None
}
```

--------------------------------

### AllocHeader Trait

Source: https://rust-hosted-langs.github.io/book/chapter-allocation-api

This section describes the `AllocHeader` trait, focusing on the `new_array` function used for initializing headers of dynamically allocated arrays.

```APIDOC
## AllocHeader Trait

### Description
Provides methods for managing object headers, including initialization for dynamically sized arrays.

### Method
`new_array`

### Endpoint
N/A (Trait method)

### Parameters
#### Path Parameters
None

#### Query Parameters
None

#### Request Body
None

### Request Example
```rust
pub trait AllocHeader: Sized {
    ...
    fn new_array(size: ArraySize, size_class: SizeClass, mark: Mark) -> Self;
    ...
}
```

### Response
#### Success Response (200)
N/A (Trait method)

#### Response Example
N/A
```

--------------------------------

### Token Structure

Source: https://rust-hosted-langs.github.io/book/print

Combines a TokenType with its corresponding SourcePos to represent a single token in the parsed input stream. This structure is fundamental for the parsing process.

```Rust
#[derive(Debug, PartialEq)]
pub struct Token {
    pub pos: SourcePos,
    pub token: TokenType,
}

```

--------------------------------

### Evaluate Next Instruction in VM Loop (Rust)

Source: https://rust-hosted-langs.github.io/book/chapter-interp-vm-impl

Implements the core instruction evaluation logic for a virtual machine's thread. This function fetches the next opcode, establishes a register window into the stack, and uses a `match` statement to execute different operations based on the opcode. It requires access to the memory mutator for reading thread data.

```rust
/// Execute the next instruction in the current instruction stream
fn eval_next_instr<'guard>(
    &self,
    mem: &'guard MutatorView,
) -> Result<EvalStatus<'guard>, RuntimeError> {
    // TODO not all these locals are required in every opcode - optimize and get them only
    // where needed
    let frames = self.frames.get(mem);
    let stack = self.stack.get(mem);
    let globals = self.globals.get(mem);
    let instr = self.instr.get(mem);

    // Establish a 256-register window into the stack from the stack base
    stack.access_slice(mem, |full_stack| {
        let stack_base = self.stack_base.get() as usize;
        let window = &mut full_stack[stack_base..stack_base + 256];

        // Fetch the next instruction and identify it
        let opcode = instr.get_next_opcode(mem)?;

        match opcode {
            // Do nothing.
            Opcode::NoOp => return Ok(EvalStatus::Pending),

            ...

}
```

--------------------------------

### Rust: Implement InstructionStream Get Next Opcode

Source: https://rust-hosted-langs.github.io/book/chapter-interp-bytecode

Details the `get_next_opcode` method for `InstructionStream`, responsible for fetching the next opcode during execution. It dereferences the `ByteCode` instance, accesses the `ArrayOpcode`, retrieves the opcode at the current instruction pointer, and increments the pointer. This is a core operation for the virtual machine's execution loop.

```rust
pub fn get_next_opcode<'guard>(
    &self,
    guard: &'guard dyn MutatorScope,
) -> Result<Opcode, RuntimeError> {
    let instr = self
        .instructions
        .get(guard)
        .code
        .get(guard, self.ip.get())?;
    self.ip.set(self.ip.get() + 1);
    Ok(instr)
}
```
Tokens:
Raw