C++

Synthesis: Codecs as Structure

The series closes by restating the codes-as-priors thesis across all twelve instances and connecting the wire-format side to the Stepanov type-algebra side.

Bits Follow Types

Codecs are not ad-hoc bit formats. They are constructions on the algebraic structure of types.

When Lists Become Bits

Prefix-freeness is the property that lifts the free-monoid construction into bit space.

Free Algebras: Why Lists and Polynomials Are Universal

The free monoid on a set is the type of lists over that set. The universal property says fold is the unique homomorphism from lists to any monoid. This explains why lists, multisets, and polynomials appear everywhere.

Homomorphisms: The Maps Between Structures

A homomorphism preserves structure. fold is the universal homomorphism from the free monoid. This is the algebraic reason that fold, evaluation, and parallelism work.

Lattices: Fixed Points and Iteration

A lattice has two operations, meet and join, satisfying absorption laws. Tarski's theorem gives a generic fixed-point algorithm. Lattice structure determines the iteration, just as monoid structure determines power-by-squaring.

Semirings: One Algorithm, Six Graph Problems

A semiring has two monoidal operations linked by distributivity. Matrix multiplication over different semirings gives shortest paths, longest paths, widest paths, reachability, and path counting, all from the same code.

Streaming Statistics, One Monoid at a Time

Online accumulators are monoids. Default construction is the identity, combination via += is the binary operation, and parallel composition gives the product monoid, computing arbitrary statistics in a single pass.

A Map of My Open Source Ecosystem

A guided tour through my open-source ecosystem: encrypted search theory, statistical reliability, Unix-philosophy CLI tools, AI research, and speculative fiction. How the projects connect and where to start.

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, and 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.

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.

RoaringBitmap

A hybrid compressed bitmap that picks the optimal sub-representation (array, bitmap, or run-length) per 64K-integer chunk based on density. No single prior dominates: Roaring commits to none and adapts per chunk.

Alga: Algebraic Text Processing with Fuzzy Matching

A C++20 header-only library for algebraic text processing and compositional parsing with fuzzy matching.

Choosing the Algebra

The Stepanov series showed that algorithms arise from algebraic structure. This post is about the flip side: sometimes you choose a different structure to make the algorithm trivial.

libdis: Disjoint Interval Sets as a Complete Boolean Algebra

A C++ header-only library that treats disjoint interval sets as proper mathematical objects with Boolean algebra operations.

ZeroIPC: Shared Memory as a Computational Substrate

ZeroIPC treats shared memory not as passive storage but as an active computational substrate, bringing futures, lazy evaluation, reactive streams, and CSP channels to IPC with zero-copy performance.

Algebraic Hashing A Modern C++20 Library for Composable Hash Functions Version 2.0

Cryptographic perfect hash functions: A theoretical analysis on space efficiency, time complexity, and entropy

maph: Maps Based on Perfect Hashing for Sub-Microsecond Key-Value Storage

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

Succinct Bit Vectors and Rank/Select

A bit vector with O(1) rank and O(log n) select using only n + o(n) bits of space. The auxiliary index is asymptotically negligible while enabling constant-time queries.

Differentiation: Three Ways

Three approaches to computing derivatives, forward-mode AD, reverse-mode AD, and finite differences, each with different trade-offs for numerical computing and machine learning.

Arithmetic Coding

Arithmetic coding closes the gap between Huffman's per-symbol integer lengths and true entropy. A single number in the unit interval encodes an entire sequence; 32-bit integer arithmetic makes it practical.

Huffman Coding

Given a finite distribution, Huffman's algorithm builds the prefix-free code with minimum expected length. It is the first entropy-optimal code in this series.

maph: Maps Based on Perfect Hashing for Sub-Microsecond Key-Value Storage

A key-value store built on memory-mapped I/O, approximate perfect hashing, and lock-free atomics. Sub-100ns median latency, 10M ops/sec single-threaded.

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

A header-only C++20 library that achieves 3-10x compression with zero marshaling overhead using prefix-free codes and Stepanov-style generic programming.

Accumux: Compositional Online Statistical Reductions in C++

A C++20 library for composing online statistical accumulators with numerically stable algorithms and algebraic composition.

VByte / Varint

VByte trades bit-level precision for byte-alignment, and that trade wins in practice. Most production columnar databases and network protocols use VByte for integer encoding.

Runtime Polymorphism Without Inheritance

Sean Parent's type erasure gives you value-semantic polymorphism without inheritance. Combined with Stepanov's algebraic thinking, you can type-erase entire algebraic structures.

Rice / Golomb

Rice and Golomb codes are parametric: a single parameter k (or m) tunes the code to a specific geometric distribution. Choosing k is choosing your prior precisely.

Numerical Integration with Generic Concepts

Numerical integration meets generic programming. By requiring only ordered field operations, the quadrature routines work with dual numbers, giving you differentiation under the integral for free.

Fibonacci Coding

Fibonacci coding uses Zeckendorf's representation to produce self-synchronizing codewords. Every codeword ends in two consecutive ones; a single bit flip corrupts at most two codewords.

Reverse-Mode Automatic Differentiation

Reverse-mode automatic differentiation is just the chain rule applied systematically. I built one in C++20 to understand what PyTorch and JAX are actually doing.

Elias Delta and Omega

Elias delta and omega extend Elias gamma by recursively encoding the length prefix. Each step yields shorter codewords for large integers at a small constant cost for small ones.

Algebraic Hashing: Composable Hash Functions Through XOR

A C++ library for composable hash functions using algebraic structure over XOR, with template metaprogramming.

Unary and Elias Gamma

Unary and Elias gamma are the two simplest universal codes. Unary encodes n in n bits; gamma in 2 log2(n)+1 bits. Each implies a different prior over the integers.

Numerical Differentiation

Choosing step size h for finite differences: small enough for a good approximation, not so small that floating-point errors eat your lunch.

Universal Codes as Priors

Every prefix-free code is a hypothesis about the source. The codeword lengths determine an implicit probability distribution; the code is optimal when that prior matches the true source.

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.

Teaching Linear Algebra with C++20 Concepts

elementa is a linear algebra library built to teach. Every design decision prioritizes clarity over cleverness. Code that reads like a textbook and compiles.

McMillan's Converse

Any length vector satisfying Kraft has a prefix-free code. Here is the construction.

Polynomials as Euclidean Domains

The same GCD algorithm works for integers and polynomials because both are Euclidean domains. One structure, many types, same algorithms.

Kraft's Inequality

Which codeword-length vectors are achievable by prefix-free codes? Kraft's inequality is the answer.

Exact Rational Arithmetic

Rational numbers give exact arithmetic where floating-point fails. The implementation connects GCD, the Stern-Brocot tree, and the algebraic structure of fields.

How Iterators Give You N+M Instead of NxM

Iterators reduce the NxM algorithm-container problem to N+M by interposing an abstraction layer, following Stepanov's generic programming approach.

Is It Prime?

The Miller-Rabin primality test demonstrates how probabilistic algorithms achieve arbitrary certainty, trading absolute truth for practical efficiency.

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 computes products, powers, Fibonacci numbers, and more, once you see the underlying algebraic structure.

Packed Containers: Zero-Waste Bit-Level Storage in C++

What if containers wasted zero bits? A C++ library for packing arbitrary value types at the bit level using pluggable codecs.