Chapter 2: Symbolic Data & Multiple Representations
Relevant source files
The following files were used as context for generating this wiki page:
Introduction
Chapter 2 of the SICP-Rust project focuses on Building Abstractions with Data. It introduces the ability to work with arbitrary symbols as data, moving beyond simple numerical computation to represent and manipulate complex algebraic structures, hierarchical sets, and encoding trees.
This module explores the transition from simple compound data to systems that support multiple representations through traits and enums. It establishes abstraction barriers and demonstrates how pattern matching and symbolic differentiation can be implemented using Rust's powerful type system. Key topics include symbolic differentiation, set representations (unordered, ordered, and binary trees), and Huffman encoding trees.
Sources: rust-examples/chapter2/src/lib.rs:1-12, rust-examples/chapter2/src/section_2_3.rs:1-10
Symbolic Differentiation
Symbolic differentiation involves computing the derivative of an algebraic expression with respect to a variable by applying formal rules. The implementation utilizes a recursive algebraic representation where expressions are represented as an enum.
Algebraic Expression Representation
The Expr enum is the core data structure for representing mathematical expressions. It supports constants, variables, sums, products, and exponentiation.
| Variant | Description | Data Contained |
|---|---|---|
Const | A constant number | f64 |
Var | A variable identifier | &'static str |
Sum | Addition of two expressions | Box<Expr>, Box<Expr> |
Product | Multiplication of two expressions | Box<Expr>, Box<Expr> |
Exponent | Base raised to an integer power | Box<Expr>, i32 |
Sources: rust-examples/chapter2/src/section_2_3.rs:39-48
Differentiation Logic
The deriv function recursively applies differentiation rules to an Expr. For example, the product rule $d(uv)/dx = u(dv/dx) + v(du/dx)$ is implemented by matching the Expr::Product variant and generating a new Expr::Sum of products.
Sources: rust-examples/chapter2/src/section_2_3.rs:136-166
The diagram shows the recursive logic flow for the symbolic differentiation engine.
Sources: rust-examples/chapter2/src/section_2_3.rs:136-166
Representing Sets
The project demonstrates three distinct ways to implement sets as data structures, each with different performance trade-offs for membership testing (element_of_set), intersection, and union.
Set Implementations Comparison
| Implementation | Membership (O) | Intersection (O) | Union (O) |
|---|---|---|---|
| Unordered List | $O(n)$ | $O(n^2)$ | $O(n^2)$ |
| Ordered List | $O(n)$ | $O(n)$ | $O(n)$ |
| Binary Tree | $O(\log n)$ | N/A | N/A |
Sources: rust-examples/chapter2/src/section_2_3.rs:191-344
Binary Tree Sets
Sets represented as binary trees utilize a recursive Tree<T> enum. This allows for logarithmic search times provided the tree remains balanced. The project includes a list_to_tree function that converts a sorted list into a balanced binary tree.
Sources: rust-examples/chapter2/src/section_2_3.rs:305-344
This diagram represents the recursive structure of the Binary Tree set.
Sources: rust-examples/chapter2/src/section_2_3.rs:305-313
Huffman Encoding Trees
Huffman encoding is a method for variable-length coding of symbols based on their frequency. Symbols that appear more frequently are represented by shorter bit sequences.
Tree Structure
The HuffmanTree is implemented as an enum with two variants: Leaf and Branch. Branches combine the symbols and weights of their subtrees.
Sources: rust-examples/chapter2/src/section_2_3.rs:374-386
Encoding and Decoding Flow
- Decoding: Traverse the tree starting from the root. Use the bits (0 for left, 1 for right) to move through branches until a leaf is reached.
- Encoding: Recursively search the tree for a symbol, accumulating 0s and 1s based on the path taken.
Sources: rust-examples/chapter2/src/section_2_3.rs:439-491
The sequence diagram illustrates the decoding process where bits drive navigation through the Huffman Tree to extract symbols.
Sources: rust-examples/chapter2/src/section_2_3.rs:439-465
Summary
Chapter 2 demonstrates the implementation of symbolic data manipulation in Rust. By using enums and recursive data structures, the project replicates Scheme's symbolic capabilities while leveraging Rust's type safety and pattern matching. The module covers essential computer science concepts including symbolic differentiation, various set implementations, and data compression via Huffman encoding, all organized behind clear abstraction barriers.
Sources: rust-examples/chapter2/src/lib.rs:1-12, rust-examples/chapter2/src/section_2_3.rs:1-10