Chapter 2: Systems with Generic Operations

Relevant source files

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

• rust-examples/chapter2/src/section_2_5.rs
• rust-examples/chapter2/src/lib.rs
• rust-examples/chapter2/src/section_2_3.rs
• rust-examples/chapter2/Cargo.toml
• rust-examples/Cargo.toml

Introduction

Systems with Generic Operations represent the culmination of data abstraction techniques in the SICP-Rust project. This module demonstrates how to build programs that can handle multiple types of data—such as ordinary numbers, rational numbers, complex numbers, and polynomials—using a unified interface. While the original Scheme implementation relies on explicit dispatch tables and apply-generic procedures, the Rust implementation utilizes trait-based polymorphism, enums for tagged data, and the From/Into traits for type coercion.

The scope of this system covers the creation of generic arithmetic packages, the implementation of a type tower for coercion, and the extension of these concepts to symbolic algebra through generic polynomials. This architecture ensures that operations like add, sub, mul, and div work seamlessly across different numeric representations while maintaining type safety and modularity.

Sources: rust-examples/chapter2/src/lib.rs:8-12, rust-examples/chapter2/src/section_2_5.rs:6-10

Generic Arithmetic System

The core of the system is the Number enum, which acts as a tagged data structure encompassing various numeric types. This replaces the manual tagging and dispatching found in Lisp-based systems.

Data Structures

Structure	Description	Source
Number	Enum wrapping SchemeNumber(i64), Rational, and Complex.	section_2_5.rs:16-20
Rational	Representation of rational numbers using numer and denom.	section_2_5.rs:23-27
Complex	Complex numbers stored in rectangular form with real and imag parts.	section_2_5.rs:46-49

Architecture and Dispatch

In Rust, generic operations are implemented by providing trait implementations for the Number enum. When an operation like Add is called, the system uses pattern matching to dispatch the call to the appropriate internal type implementation.

The diagram shows the logic flow for a generic operation where Rust's pattern matching replaces Scheme's apply-generic table lookup.
Sources: rust-examples/chapter2/src/section_2_5.rs:77-91

Combining Different Types (Coercion)

To handle operations between different numeric types (e.g., adding an integer to a complex number), the system implements a Type Tower.

The Type Tower Hierarchy

The project establishes a hierarchy where lower types can be "raised" to higher types without loss of information:

1. Integer (SchemeNumber)
2. Rational
3. Real (Not explicitly a separate struct, often handled as Complex/f64)
4. Complex

Sources: rust-examples/chapter2/src/section_2_5.rs:207-213

Coercion Logic

Coercion is managed via the From trait and a utility function coerce_to_common. If types do not match, the system attempts to raise the type with the lower level in the tower to match the higher type.

fn coerce_to_common(a: Number, b: Number) -> (Number, Number) {
    use Number::*;
    match (&a, &b) {
        // Example: Scheme number + Complex -> both to Complex
        (SchemeNumber(n), Complex(_)) => (Number::Complex(self::Complex::from(*n)), b),
        (Complex(_), SchemeNumber(n)) => (a, Number::Complex(self::Complex::from(*n))),
        // ... other combinations
    }
}

Sources: rust-examples/chapter2/src/section_2_5.rs:231-252

Raise and Drop Operations

The system provides traits for moving data up and down the hierarchy:

• Raise: Moves a type one level up (e.g., i64 to Rational). Sources: section_2_5.rs:255-267
• Drop: Simplifies a type to its lowest possible representation in the tower if the conversion is exact (e.g., a Complex with imag == 0 and real == 5.0 drops to SchemeNumber(5)). Sources: section_2_5.rs:276-302

Symbolic Algebra

The system extends generic operations to polynomials. A Polynomial consists of a variable (a char) and a collection of Term objects.

Polynomial Architecture

Polynomials are generic over their coefficients, provided the coefficient type implements the Numeric trait. This allows for polynomials where coefficients are themselves other polynomials, rational numbers, or complex numbers.

This diagram illustrates the relationship between polynomials, terms, and the requirement for coefficients to satisfy the Numeric trait.
Sources: rust-examples/chapter2/src/section_2_5.rs:307-353

Key Polynomial Operations

1. Term List Addition: Merges two lists of terms, combining coefficients of like orders. Sources: section_2_5.rs:366-391
2. Term List Multiplication: Multiplies every term of the first polynomial by every term of the second. Sources: section_2_5.rs:402-411
3. Polynomial Division: Implements long division, returning both a quotient and a remainder polynomial. Sources: section_2_5.rs:444-478

Summary of Generic Traits

Trait	Purpose	Source
GenericEq	Implements the equ predicate for generic equality across types.	section_2_5.rs:177-190
GenericZero	Implements is_zero to check if a generic number or polynomial is null.	section_2_5.rs:193-202
Numeric	A composite trait (Add, Sub, Mul, Div, etc.) required for polynomial coefficients.	section_2_5.rs:307-317

Sources: rust-examples/chapter2/src/section_2_5.rs:177-317

Conclusion

Chapter 2's implementation of generic operations in Rust demonstrates the power of combining algebraic data types (enums) with traits. This approach provides the flexibility of Scheme's dynamic dispatch while ensuring compile-time safety and explicit control over type conversions and coercion through the type tower. The resulting system is capable of performing complex symbolic algebra and arithmetic across diverse numeric representations.