Seeing Structure First
A reflection on eleven explorations in generic programming—how algorithms arise from algebraic structure.
Project
stepanov
Pedagogical blog posts on generic programming in C++, inspired by Alex Stepanov
Explore project →← All Series
Stepanov: Generic Programming in C++
A series exploring Alex Stepanov's insight that algorithms arise from algebraic structure
These posts explore the philosophy and practice of generic programming as taught by Alex Stepanov, architect of the C++ Standard Template Library.
The central insight: algorithms arise from algebraic structure. The same algorithm that works on integers works on matrices, polynomials, and modular integers—not by accident, but because they share algebraic properties. When you recognize “this is a monoid” or “this is a Euclidean domain,” you immediately know which algorithms apply.
Each post demonstrates one beautiful idea with minimal, pedagogical C++ code (~100-300 lines). The implementations prioritize clarity over cleverness—code that reads like a textbook that happens to compile.
Core Topics
- Monoids and exponentiation: The Russian peasant algorithm reveals the universal structure of repeated operations
- Rings and fields: Modular arithmetic teaches which algorithms apply where
- Euclidean domains: The same GCD algorithm works for integers and polynomials
- Generic concepts: C++20 concepts express algebraic requirements as compile-time contracts
Further Reading
- Stepanov & Rose, From Mathematics to Generic Programming
- Stepanov & McJones, Elements of Programming
Featured
Posts in this Series
Showing 14 of 14 posts
1
of 14
1
of 14
One Algorithm, Infinite Powers
The Russian peasant algorithm teaches us that one algorithm can compute products, powers, Fibonacci numbers, and more—once we see the underlying algebraic structure.
2
of 14
Modular Arithmetic as Rings
Integers modulo N form a ring—an algebraic structure that determines which algorithms apply. Understanding this structure unlocks algorithms from cryptography to competitive programming.
3
of 14
Is It Prime?
The Miller-Rabin primality test demonstrates how probabilistic algorithms can achieve arbitrary certainty, trading absolute truth for practical efficiency.
4
of 14
Exact Rational Arithmetic
Rational numbers give us exact arithmetic where floating-point fails. The implementation reveals deep connections to GCD, the Stern-Brocot tree, and the algebraic structure of fields.
5
of 14
Polynomials as Euclidean Domains
The same GCD algorithm works for integers and polynomials because both are Euclidean domains. This profound insight shows how algebraic structure determines algorithmic applicability.
6
of 14
Teaching Linear Algebra with C++20 Concepts
elementa is a pedagogical linear algebra library where every design decision prioritizes clarity over cleverness—code that reads like a textbook that happens to compile.
7
of 14
Forward-Mode Automatic Differentiation
Dual numbers extend our number system with an infinitesimal epsilon where epsilon^2 = 0. Evaluating f(x + epsilon) yields f(x) + epsilon * f'(x)—the derivative emerges automatically from the algebra.
8
of 14
Numerical Differentiation
The art of numerical differentiation lies in choosing step size h wisely—small enough that the approximation is good, but not so small that floating-point errors dominate.
9
of 14
Reverse-Mode Automatic Differentiation
Reverse-mode automatic differentiation powers modern machine learning. Understanding how it works demystifies PyTorch, JAX, and TensorFlow—it's just the chain rule applied systematically.
10
of 14
Numerical Integration with Generic Concepts
Numerical integration demonstrates both classical numerical analysis and Stepanov's philosophy: by identifying the minimal algebraic requirements, our quadrature routines work with dual numbers for automatic differentiation under the integral.
11
of 14
Runtime Polymorphism Without Inheritance
Sean Parent's type erasure technique provides value-semantic polymorphism without inheritance. Combined with Stepanov's algebraic thinking, we can type-erase entire algebraic structures.
12
of 14
Differentiation: Three Ways
Three approaches to computing derivatives—forward-mode AD, reverse-mode AD, and finite differences—each with different trade-offs. Understanding when to use each is essential for numerical computing and machine learning.
13
of 14
Duality: The Hidden Structure of Opposites
Many structures come in pairs: forward/reverse AD, push/pull iteration, encode/decode. Recognizing duality lets you transfer theorems and insights between domains.