Common Data Structures (Lists & Arenas)

Relevant source files

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

• rust-examples/sicp-common/src/lib.rs
• rust-examples/chapter3/SECTION_3_3_SUMMARY.md
• rust-examples/chapter3/STREAMS_GUIDE.md
• rust-examples/chapter2/src/section_2_5.rs
• rust-examples/sicp-common/Cargo.toml
• rust-examples/Cargo.toml

The "Common Data Structures (Lists & Arenas)" system provides a foundational framework for translating Scheme-based abstractions into idiomatic Rust. This module serves as a bridge between the flexible, garbage-collected environment of SICP and the strict, ownership-based model of Rust. Its primary purpose is to implement shared utilities such as arena allocation, persistent environments, and functional list patterns that minimize runtime overhead and avoid common pitfalls like circular reference cycles and excessive use of interior mutability.

The scope of these structures extends across several chapters of the project, facilitating everything from symbolic algebra in Chapter 2 to mutable modeling and stream processing in Chapter 3. By leveraging Rust-specific features like the Iterator trait and crates like im for immutable data structures, the system ensures memory safety while maintaining the functional expressiveness required for the SICP exercises.

Sources: rust-examples/sicp-common/src/lib.rs:1-12, rust-examples/chapter3/SECTION_3_3_SUMMARY.md:1-8

The Arena Allocation System

The project implements a type-safe arena allocation system designed to handle the complex graph-like structures common in Lisp implementations. Rather than relying on pointer-heavy Rc<RefCell<T>> patterns, the Arena module utilizes index-based references to manage memory.

Architecture and Components

The system is built around two primary types:

• Arena: A container that manages the storage of objects of a specific type. It provides a centralized location for allocation, which aids in deterministic cleanup and prevents memory leaks associated with reference cycles.
• ArenaId: A type-safe wrapper around a numeric index (e.g., usize) that acts as a handle for items stored within an Arena.

This approach allows the borrow checker to manage the lifetime of the Arena itself, while the internal elements are accessed via indices, effectively decoupling the storage from the ownership of individual nodes.

The diagram above illustrates the interaction between user code and the Arena system, where data is stored in a central buffer and accessed via safe numeric handles.

Sources: rust-examples/sicp-common/src/lib.rs:14-22, rust-examples/sicp-common/src/lib.rs:24-25

List Implementations and Mutable Data

The project provides multiple representations for lists, catering to both functional (immutable) and imperative (mutable) SICP concepts.

Functional Cons Cells

Functional list operations follow the standard cons cell pattern. These are used primarily for symbolic manipulation and are designed to be "Iterator-centric," leveraging Rust's powerful iterator combinators.
Sources: rust-examples/sicp-common/src/lib.rs:17-21

Mutable Pairs and List Structures

For Chapter 3.3, which focuses on mutable data modeling, the project introduces structures that support destructive operations.

Concept	Rust Implementation	Description
Mutable Pair	RefCell<T>	Provides interior mutability for pairs.
Shared Mutable List	Rc<RefCell<Cons<T>>>	Enables shared ownership of mutable nodes.
Queue	Weak rear pointers	Efficient O(1) insertion using a weak reference to the end of the list to prevent cycles.
Idiomatic Deque	VecDeque<T>	A modern Rust implementation of the SICP double-ended queue.

Sources: rust-examples/chapter3/SECTION_3_3_SUMMARY.md:15-30

Architecture of Mutable Propagation

In the digital circuit simulator and constraint propagation modules, these mutable structures form the backbone of the event-driven system.

The class diagram shows the relationship between basic mutable pairs and higher-level structures like Queues.

Sources: rust-examples/chapter3/SECTION_3_3_SUMMARY.md:32-38

Generic Arithmetic and Data Types

Chapter 2 implementations rely on enums and traits to handle generic operations, replacing Scheme's apply-generic mechanism.

The Number Hierarchy

The Number type is implemented as a tagged union (enum) to represent various numeric kinds.

• SchemeNumber: Represented by i64.
• Rational: A struct containing numer and denom.
• Complex: Supports both rectangular and polar forms.

The flow shows the type tower where lower types (Integers) can be raised to higher types (Complex).

Sources: rust-examples/chapter2/src/section_2_5.rs:13-73

Symbolic Algebra

Polynomials are implemented using generic coefficient types, requiring the coefficients to implement a Numeric trait.

pub struct Polynomial<T: Numeric> {
    variable: char,
    terms: Vec<Term<T>>,
}

pub struct Term<T: Numeric> {
    order: usize,
    coeff: T,
}

Sources: rust-examples/chapter2/src/section_2_5.rs:275-305

Lazy Evaluation and Streams

Rust's native Iterator trait is used as the primary mechanism for implementing SICP streams, effectively replacing the need for explicit delay and force.

Scheme Concept	Rust Equivalent	Implementation Detail
delay	Iterator (Lazy)	Evaluation happens only on demand.
force	.next() / .collect()	Triggers the iterator's logic.
cons-stream	std::iter::once().chain()	Composes a value with a lazy rest.
stream-map	.map()	Zero-cost abstraction for transformation.

Sources: rust-examples/chapter3/STREAMS_GUIDE.md:8-25

Stream Architecture

Streams are often implemented as custom structs that implement the Iterator trait, maintaining internal state between calls to next(). This is used for infinite sequences like Fibonacci numbers or the Sieve of Eratosthenes.

This sequence diagram illustrates the internal update loop of a lazy Sieve of Eratosthenes stream.

Sources: rust-examples/chapter3/STREAMS_GUIDE.md:35-80

Summary of Design Principles

The common data structures in this repository emphasize Memory Safety and Functional Purity. By utilizing:

1. Persistent Data Structures: Via im::HashMap for O(1) cloning of environments.
2. Ownership-based Modeling: Leveraging Rust's move semantics instead of GC.
3. Zero-Cost Abstractions: Using iterators for stream processing which compile to efficient machine code.

Sources: rust-examples/sicp-common/src/lib.rs:5-12, rust-examples/Cargo.toml:13-35