Chapter 3: Assignment and Local State
Relevant source files
The following files were used as context for generating this wiki page:
Introduction
Chapter 3 explores the introduction of assignment and mutable state into programming models, moving away from purely functional evaluation. In the context of the SICP-Rust project, this chapter demonstrates how Scheme's concepts of modularity, objects, and state map to Rust's ownership, lifetimes, and interior mutability patterns. The chapter covers assignment and local state, the environment model, mutable data structures, and the alternative approach of streams for modeling state without assignment.
The implementation utilizes Rust-specific primitives such as RefCell, Mutex, Rc, and Weak to replicate the dynamic behaviors described in the original text while adhering to Rust's safety guarantees.
Sources: rust-examples/chapter3/src/lib.rs, rust-examples/chapter3/SECTION_3_3_SUMMARY.md:3-10
Local State and Assignment
Local state is implemented in Rust using interior mutability patterns. This allows objects to maintain internal variables that can be modified even when the object is accessed through an immutable reference.
Interior Mutability Mechanics
To implement local state similar to Scheme's set!, the project utilizes RefCell<T> for single-threaded scenarios and potentially Mutex<T> for concurrent access. This bypasses the standard compile-time borrow checker rules, moving the checks to runtime.
Sources: rust-examples/chapter3/src/lib.rs:5, rust-examples/chapter3/SECTION_3_3_SUMMARY.md:15-18
Modeling with Mutable Data
Section 3.3 focuses on modeling with mutable data, specifically mutable lists and tables. In Rust, these are represented using Rc<RefCell<Cons<T>>> to allow for shared, mutable linked structures.
| Scheme Structure | Rust Implementation | Description |
|---|---|---|
| Mutable Pair | RefCell<T> / Rc<RefCell<Cons<T>>> | Enables destructive operations like set-car! and set-cdr! |
| Queue | Rc<RefCell<Cons<T>>> with Weak rear | Constant time insertion and deletion |
| 1D Table | HashMap<K, V> | Key-value storage |
| 2D Table | HashMap<K1, HashMap<K2, V>> | Multi-level lookup |
Sources: rust-examples/chapter3/SECTION_3_3_SUMMARY.md:23-45
The Environment Model
The Environment Model explains how procedures are evaluated in the context of frames and bindings. In Rust, this is often implemented through ownership and lifetimes, or through explicit environment structures like persistent im::HashMap used in the metacircular evaluator.
Structure of an Environment
An environment consists of a sequence of frames, each containing bindings of variables to values. Each frame (except the global one) points to an enclosing environment.
The diagram represents the hierarchical structure of environments where local frames point to parent environments for variable lookup.
Sources: rust-examples/chapter3/src/lib.rs:6, rust-examples/chapter4/examples/metacircular_evaluator.rs:186-190
Modeling Systems: Circuits and Constraints
The project implements two complex modeling systems based on mutable state: a digital circuit simulator and a constraint propagation network.
Digital Circuit Simulator
The simulator uses an event-driven architecture based on an Agenda.
- Wire: Holds a signal value and a list of action callbacks (
Vec<Box<dyn FnMut()>>). - Agenda: A time-ordered scheduler for events.
- Gates: Functions like
inverterandand_gatethat register actions on wires.
Sources: rust-examples/chapter3/SECTION_3_3_SUMMARY.md:47-52
Constraint Propagation
Constraint networks represent relations between quantities. For example, a Celsius to Fahrenheit converter is modeled as a network of Connector objects and Constraint traits.
This diagram shows a bidirectional constraint network where changing one value propagates through the multipliers and adders to update other connectors.
Sources: rust-examples/chapter3/SECTION_3_3_SUMMARY.md:57-63
Streams: An Alternative to Assignment
Streams provide a way to model state and time without using assignment, leveraging lazy evaluation. In Rust, this is mapped directly to the Iterator trait.
Concept Mappings
| Scheme Concept | Rust Equivalent |
|---|---|
delay | Lazy Iterator |
force | .next() / .collect() |
cons-stream | std::iter::once(x).chain(rest) |
stream-map | .map() |
stream-filter | .filter() |
Sources: rust-examples/chapter3/STREAMS_GUIDE.md:9-20
Stream Signal Processing
Streams are used to solve differential equations and perform signal processing. The Integrator is a key component that accumulates values over time segments dt.
The sequence diagram illustrates the flow of data in a lazy integration process where the integrator pulls the next value from the source stream and updates its internal accumulator.
Sources: rust-examples/chapter3/STREAMS_GUIDE.md:88-108, rust-examples/chapter3/examples/streams_demo.rs:163-175
Conclusion
Chapter 3 in the SICP-Rust project demonstrates the transition from functional purity to state-based modeling. By using Rust's RefCell and Rc types, the project successfully implements mutable data structures and environment models. Simultaneously, the extensive use of Rust Iterators as an equivalent to SICP Streams shows how lazy evaluation can achieve modularity without the complexities of side effects and explicit assignment.
Sources: rust-examples/chapter3/SECTION_3_3_SUMMARY.md:81-86, rust-examples/chapter3/examples/streams_demo.rs:205-212