Chapter 3: Streams and Lazy Evaluation
Relevant source files
The following files were used as context for generating this wiki page:
The implementation of Chapter 3.5 in this project explores the concept of streams as a technique for modeling state without the use of assignment. In Scheme, streams are implemented using delay and force to provide lazy evaluation. In this Rust implementation, these concepts are mapped to the native Iterator trait, which provides lazy evaluation by default—elements are computed only when explicitly requested via the next() method.
Sources: rust-examples/chapter3/src/lib.rs:1-12, rust-examples/chapter3/STREAMS_GUIDE.md:1-10, rust-examples/chapter3/src/section_3_5.rs:1-12
Core Architecture and Concept Mappings
The project treats Rust's Iterator as a zero-cost abstraction for the stream paradigm. Unlike Scheme, where streams are explicitly delayed lists, Rust iterators compile to efficient machine code while maintaining the same lazy semantics.
Mapping Scheme to Rust
| Scheme Concept | Rust Equivalent | Example Implementation |
|---|---|---|
delay | Iterator trait (lazy by default) | (0..).filter(...) |
force | .next() or .collect() | iter.next() |
cons-stream | Iterator constructors | std::iter::once(x).chain(rest) |
stream-car | .next().unwrap() | stream.next() |
stream-cdr | The iterator itself | stream.skip(1) |
stream-map | .map() combinator | stream.map(|x| x * 2) |
the-empty-stream | std::iter::empty() | std::iter::empty::<i32>() |
Sources: rust-examples/chapter3/STREAMS_GUIDE.md:12-25, rust-examples/chapter3/src/section_3_5.rs:14-19
Lazy vs Eager Evaluation Flow
The following diagram illustrates the difference between eager evaluation (building full lists) and lazy evaluation (stream processing) as implemented in delayed_lists.
The lazy approach terminates immediately upon finding the required element, whereas the eager approach must compute and store every potential candidate in the range.
Sources: rust-examples/chapter3/src/section_3_5.rs:27-54, rust-examples/chapter3/examples/streams_demo.rs:19-33
Infinite Streams
Infinite sequences are implemented by defining custom structs that implement the Iterator trait. This allows the program to represent sequences that never terminate, such as the set of all integers or the Fibonacci sequence, without exhausting memory.
Key Implementation Structures
IntegersFrom: A simple structure maintaining acurrentstate that increments on each call tonext().Fibonacci: Maintains two state variables (currentandnext) to calculate the next value in the sequence on-demand.Sieve: Implements the Sieve of Eratosthenes. It utilizes aBox<dyn Iterator>to recursively filter candidates, effectively wrapping the remaining stream in a new filter for every prime discovered.
Sources: rust-examples/chapter3/src/section_3_5.rs:72-159, rust-examples/chapter3/STREAMS_GUIDE.md:29-84
// Example: Infinite Fibonacci stream
struct Fibonacci {
current: u64,
next: u64,
}
impl Iterator for Fibonacci {
type Item = u64;
fn next(&mut self) -> Option<Self::Item> {
let result = self.current;
let new_next = self.current + self.next;
self.current = self.next;
self.next = new_next;
Some(result)
}
}
Sources: rust-examples/chapter3/src/section_3_5.rs:97-123
Stream Applications and Sequence Acceleration
The stream paradigm is utilized for complex mathematical approximations. These implementations demonstrate how iterators can replace traditional state variables and loops.
Iterative Improvement and Convergence
The SqrtStream structure generates successive approximations of a square root. To determine when the approximation is sufficient, the stream_limit function monitors the stream until the difference between consecutive elements falls below a specified tolerance.
Sequence Acceleration
For alternating series (like the Pi approximation), the project implements the EulerTransform. This accelerates convergence by transforming a stream of partial sums into a new stream that approaches the limit more rapidly.
| Component | Description | Implementation Detail |
|---|---|---|
PartialSums | Accumulates a running sum of a stream | self.sum += value |
PiSummands | Generates terms for the Leibniz series | 1.0 / self.n where n increases by 2 |
EulerTransform | Applies sequence acceleration | s2 - (s2-s1)^2 / (s0-2s1+s2) |
stream_limit | Utility to truncate a stream based on delta | (current - prev).abs() < tolerance |
Sources: rust-examples/chapter3/src/section_3_5.rs:242-329, rust-examples/chapter3/STREAMS_GUIDE.md:155-182, rust-examples/chapter3/examples/streams_demo.rs:98-151
Signal Processing
The project demonstrates signal processing through Integrator and differential equation solvers. These models use streams to simulate the evolution of a system over discrete time steps (dt).
While Scheme uses explicit delay for feedback loops in differential equations, the Rust implementation uses SolveIterator and functional state threading.
Sources: rust-examples/chapter3/src/section_3_5.rs:396-455, rust-examples/chapter3/STREAMS_GUIDE.md:120-151, rust-examples/chapter3/examples/streams_demo.rs:175-207
Implementation Dependencies
The Chapter 3 module depends on external crates to handle concurrency and functional data structures.
| Dependency | Use Case in Streams |
|---|---|
tokio | Async runtime for potentially asynchronous streams |
parking_lot | Efficient synchronization for shared state |
sicp-common | Shared utilities for functional patterns |
Sources: rust-examples/chapter3/Cargo.toml:7-13, rust-examples/chapter3/src/lib.rs:4-10
Summary
The Chapter 3 implementation demonstrates that Rust's ownership model and Iterator trait provide a safe and performant foundation for lazy evaluation. By mapping SICP's stream operations to iterator combinators like map, filter, and zip, the project achieves the modularity of functional programming without sacrificing the memory safety and efficiency of a systems language.
Sources: rust-examples/chapter3/STREAMS_GUIDE.md:200-218, rust-examples/chapter3/examples/streams_demo.rs:228-235