Generic-Programming

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.

Seeing Structure First

A reflection on eleven explorations in generic programming—how algorithms arise from algebraic structure.

Alexander Stepanov: Efficient Programming with Components (A9 Lectures)

Notes

18-part lecture series on efficient programming. Covers the intellectual foundations behind STL.

Elements of Programming

Notes

Rigorous foundations of generic programming. Connects algebra and algorithms. Stepanov’s magnum opus.

From Mathematics to Generic Programming

Notes

History of mathematical ideas underlying generic programming. More accessible than EoP.

Sean Parent: C++ Seasoning (That's a Rotate)

Notes

Classic talk on recognizing algorithmic patterns. ‘No raw loops’ - shows how rotate solves many problems elegantly.

PFC: Zero-Copy Data Compression Through Prefix-Free Codecs and Generic Programming

PFC: Zero-Copy Data Compression Through Prefix-Free Codecs

A header-only C++20 library that achieves 3-10× compression with zero marshaling overhead. PFC makes compression an intrinsic type property through prefix-free codes (Elias Gamma/Delta, Fibonacci, Rice), algebraic types, and Stepanov's generic …

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.

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.

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.

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.

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.

How Iterators Give You N+M Instead of N×M

The problem is combinatorial. You have N algorithms (sort, search, find, copy) and M containers (array, list, tree, hash table). The naive approach: implement each algorithm for each container. That’s N×M implementations.

The insight is to …

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.

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.