Chapter 3: Modeling with Mutable Data

Relevant source files

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

• rust-examples/chapter3/SECTION_3_3_SUMMARY.md
• rust-examples/chapter3/src/lib.rs
• rust-examples/chapter3/STREAMS_GUIDE.md
• rust-examples/chapter3/examples/streams_demo.rs
• rust-examples/chapter3/Cargo.toml
• README.md

Chapter 3 explores the introduction of state and mutation into computer programs, moving away from the purely functional substitution model. In the context of the sicp-rust project, this chapter focuses on how Rust handles interior mutability, shared state, and concurrency while maintaining memory safety. The implementation specifically maps Scheme's mutable pairs and environmental models to Rust's ownership and lifetime system.

This chapter covers fundamental concepts such as assignment, local state, mutable data structures, and the transition to the environment model of evaluation. It provides the architectural foundation for more complex systems like the digital circuit simulator and constraint propagation networks implemented in the module.
Sources: rust-examples/chapter3/src/lib.rs:3-9, rust-examples/chapter3/SECTION_3_3_SUMMARY.md:3-9

Mutable List Structures and Interior Mutability

To replicate Scheme's mutable pairs (set-car!, set-cdr!), the implementation utilizes Rust's interior mutability patterns. The core structure, MutablePair, relies on RefCell<T> to allow mutation through shared references. Shared mutable linked lists are constructed using Rc<RefCell<Cons<T>>>.

Core Data Structure Mapping

Scheme Concept	Rust Implementation	Purpose
Mutable Pair	RefCell<T> / MutablePair	Enables mutation of data within a reference.
Shared List	Rc<RefCell<Cons<T>>>	Allows multiple owners to point to and mutate a list node.
Rear Pointer	Weak<RefCell<Cons<T>>>	Prevents reference cycles in queue implementations.

Sources: rust-examples/chapter3/SECTION_3_3_SUMMARY.md:13-25, rust-examples/chapter3/src/lib.rs:6-6

Reference Counting and Cycles

Because mutable structures often involve circular references (e.g., Exercise 3.18), the implementation uses Floyd's cycle-finding algorithm and HashSet for distinct pair counting to manage memory safety and detection in a non-GC environment.

The diagram illustrates a circular linked list where the Cdr points back to a previous RefCell, necessitating Rc for shared ownership and cycle detection logic.
Sources: rust-examples/chapter3/SECTION_3_3_SUMMARY.md:16-20

Representing Queues and Tables

The project implements standard data structures using a mix of SICP-style pairs and idiomatic Rust collections.

Queues (Section 3.3.2)

Queues are represented as a pair of pointers (front and rear). To optimize for Rust's ownership model, the rear pointer is often implemented as a Weak pointer to avoid memory leaks.

• Operations: insert, delete, and front all operate at $O(1)$ complexity.
• Idiomatic Deque: Exercise 3.23 is implemented using std::collections::VecDeque.

Tables (Section 3.3.3)

Tables are mapped to Rust's HashMap.

• 1D Tables: HashMap<K, V>.
• 2D Tables: HashMap<K1, HashMap<K2, V>>.
• Memoization: Handled via RefCell<HashMap> to support the stateful nature of Exercise 3.27.

Sources: rust-examples/chapter3/SECTION_3_3_SUMMARY.md:27-38, rust-examples/chapter3/Cargo.toml:10-12

Digital Circuit Simulator (Section 3.3.4)

The circuit simulator is an event-driven system comprising wires, gates, and an agenda (time scheduler).

System Components

• Wire: Holds a signal and a list of action callbacks (Vec<Box<dyn FnMut()>>).
• Agenda: An event scheduler that manages time segments and executes events.
• Gates: Functional units like inverter, and_gate, and or_gate.
• Composite Circuits: Complex structures like half_adder and full_adder.

This diagram shows the flow of signal propagation: a gate calculates a value, schedules an action on the agenda, and the agenda eventually updates the wire's signal state.
Sources: rust-examples/chapter3/SECTION_3_3_SUMMARY.md:40-48

Constraint Propagation (Section 3.3.5)

The constraint system allows for bidirectional computation, where values propagate through a network of connectors and constraints (e.g., a Celsius/Fahrenheit converter).

Architecture

1. Connector: A stateful object holding a value using RefCell for interior mutability.
2. Constraint Trait: Implemented by Adder, Multiplier, and Constant.
3. Propagation: When a connector is set, it notifies all attached constraints, which then attempt to calculate and set other connected values.

Implementation Challenge: The implementation notes that circular RefCell borrows can occur during propagation. In production Rust, the recommendation is to replace this SICP-style callback architecture with the Actor Model or Message Passing using tokio::sync::mpsc.
Sources: rust-examples/chapter3/SECTION_3_3_SUMMARY.md:50-62, rust-examples/chapter3/Cargo.toml:13-13

Streams (Section 3.5)

Streams are implemented as a way to model state without explicit assignment by using lazy evaluation.

Scheme to Rust Mapping

Rust's Iterator trait serves as the primary equivalent to Scheme's delay/force mechanism.

Scheme Concept	Rust Iterator Equivalent
delay	Iterators are lazy by default
cons-stream	std::iter::once(x).chain(rest)
stream-map	.map()
stream-filter	.filter()
the-empty-stream	std::iter::empty()

Sources: rust-examples/chapter3/STREAMS_GUIDE.md:7-17, rust-examples/chapter3/examples/streams_demo.rs:18-24

Signal Processing and Differential Equations

The stream paradigm allows for solving complex problems like differential equations ($\frac{dy}{dt} = f(y)$) using iterative approximation. The Integrator and solve functions demonstrate this by wrapping iterators to accumulate values over time.
Sources: rust-examples/chapter3/STREAMS_GUIDE.md:104-128, rust-examples/chapter3/examples/streams_demo.rs:163-176

Summary of Rust Trade-offs

The implementation of Chapter 3 highlights the tension between Scheme's flexible pointers and Rust's strict safety.

• Advantages: Explicit ownership makes data flow clear; deterministic cleanup without a Garbage Collector.
• Challenges: Circular data structures (like those in the circuit simulator) require complex Rc/Weak usage; RefCell incurs a runtime overhead for safety checks.
• Recommendations: For production, the project suggests using VecDeque for queues and channels/actors for event propagation rather than the direct pointer manipulation suggested by SICP.

Sources: rust-examples/chapter3/SECTION_3_3_SUMMARY.md:70-84