Chapter 5: Storage Allocation & Garbage Collection

Relevant source files

The following files were used as context for generating this wiki page:

• rust-examples/chapter5/src/section_5_3.rs
• rust-examples/chapter5/src/lib.rs
• rust-examples/chapter5/Cargo.toml
• rust-examples/chapter3/SECTION_3_3_SUMMARY.md
• rust-examples/chapter3/src/lib.rs

Introduction

Chapter 5 of the sicp-rust project focuses on the low-level representation of data structures and the management of memory within a register machine environment. Specifically, Section 5.3 demonstrates how high-level list structures, typically found in Lisp-like languages, are mapped onto vector-based memory systems. This involves representing pairs using parallel vectors and implementing mechanisms for automatic memory reclamation.

The implementation contrasts traditional runtime Garbage Collection (GC) algorithms, such as Stop-and-Copy and Mark-Sweep, with Rust's native ownership system. While the former are simulated to demonstrate classical computer science concepts, the project highlights that Rust's ownership, borrowing, and RAII (Resource Acquisition Is Initialization) function as a form of "compile-time garbage collection," eliminating the need for a runtime collector in most idiomatic Rust code.
Sources: rust-examples/chapter5/src/section_5_3.rs:1-15, rust-examples/chapter5/src/lib.rs:1-12

Memory Representation as Vectors

In this model, Lisp memory is simulated using two parallel vectors, the_cars and the_cdrs. These vectors store "typed pointers" represented by the Value enum. A pair is represented by a shared index into both vectors.

Data Structures

The primary data structures used to simulate this memory model include:

Structure	Description
Value	An enum representing tagged pointers (Number, Symbol, Pair, Nil, BrokenHeart).
PairIndex	A type alias for usize, representing an index into the memory vectors.
Memory	A struct containing parallel Vec<Value> (the_cars, the_cdrs) and a free pointer.

Sources: rust-examples/chapter5/src/section_5_3.rs:25-50, rust-examples/chapter5/src/section_5_3.rs:75-87

Pointer Tagging

The Value enum implements SICP's "typed pointers," which distinguish between data types at the pointer level.

pub enum Value {
    Number(i64),
    Symbol(String),
    Pair(PairIndex),
    Nil,
    BrokenHeart(usize),
}

Sources: rust-examples/chapter5/src/section_5_3.rs:31-41

Garbage Collection Algorithms

The project implements two classical garbage collection algorithms to demonstrate manual memory management within the simulated memory space.

Stop-and-Copy GC

The StopAndCopyGC divides memory into two equal spaces: "working" and "free". When the working space is exhausted, reachable objects are copied to the free space, and the roles of the spaces are swapped.

The algorithm uses a "Broken Heart" marker to handle shared structures, where the original location of a moved object is replaced with a forwarding address to prevent redundant copies.
Sources: rust-examples/chapter5/src/section_5_3.rs:214-250, rust-examples/chapter5/src/section_5_3.rs:271-298

Mark-Sweep GC

The MarkSweepGC uses a two-phase approach:

1. Mark Phase: Traverses all reachable data from the root set and sets a bit in a marked vector.
2. Sweep Phase: Scans the entire memory, adding all unmarked indices back to a free_list.

Rust Ownership vs. Runtime GC

A key architectural insight provided in this chapter is the comparison between runtime GC and Rust's ownership model. While SICP focuses on implementing GC, Rust avoids it through:

• Ownership: Each value has a single owner that manages its lifecycle.
• RAII: The Drop trait ensures resources are cleaned up immediately when an owner goes out of scope.
• Iterators: Lazy evaluation in Rust (e.g., filter, map) avoids the creation of intermediate "garbage" data structures common in functional programming.

Summary

Chapter 5: Storage Allocation & Garbage Collection serves as a bridge between high-level functional concepts and low-level machine implementation. By simulating Lisp memory using Rust vectors, it provides a concrete implementation of how complex data structures are managed in hardware-like environments. The inclusion of both Stop-and-Copy and Mark-Sweep algorithms, alongside a discussion of Rust's ownership-based memory safety, illustrates the evolution of memory management from runtime software collectors to modern compile-time guarantees.
Sources: rust-examples/chapter5/src/section_5_3.rs:1-15, rust-examples/chapter5/src/lib.rs:1-12