Browse posts by category
Your reader's words evaporate while your writer's words endure. Markdown won the durability war by being boring. Every time we add interactivity, we drag back the database, and durability dies. There's a missing primitive: writes that are as durable …
Codecs are not ad-hoc bit formats. They are constructions on the algebraic structure of types.
Prefix-freeness is the property that lifts the free-monoid construction into bit space.
I tried closing the loop on retrieval-augmented generation with TD learning. A trivial baseline matched the full method. Here's the lesson.
Type real commands into a virtual filesystem. Five lessons from 'where am I?' to piping tools together.
An interactive introduction to fuzzy logic inference, from single facts to LLM-generated knowledge bases
An interactive explorable explanation of Monte Carlo Tree Search for LLM reasoning. Watch reasoning paths branch, dead-end, and backtrack.
I pointed Claude Code at the Erdős problem database with vague instructions to 'find interesting things.' It built 92 Python modules, ran 131 subagents, and computed exact Ramsey numbers nobody had computed before. I mostly watched.
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.
A homomorphism preserves structure. fold is the universal homomorphism from the free monoid. This is the algebraic reason that fold, evaluation, and parallelism work.
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.
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.
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.
When a problem is complex enough, the right move is to build a language for that problem. SICP's most powerful idea.
Many structures come in pairs: forward/reverse AD, push/pull iteration, encode/decode. Recognizing duality lets you transfer theorems and insights between domains.
A reflection on eleven explorations in generic programming, and how algorithms arise from algebraic structure.
A C++20 header-only library for algebraic text processing and compositional parsing with fuzzy matching.
AlgoGraph is an immutable graph library for Python with pipe-based transformers, declarative selectors, and lazy views.
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.
A framework for querying structured JSON documents using fuzzy logic, producing degree-of-membership scores instead of binary relevance.
A C++ header-only library that treats disjoint interval sets as proper mathematical objects with Boolean algebra operations.
A Python library for rule-based term rewriting with pattern matching, multiple input formats, and an interactive REPL.
I asked an AI to analyze 140+ repos and 50+ papers as a dataset. The unifying thesis it found: compositional abstractions for computing under ignorance.
A virtual POSIX-compliant filesystem using content-addressable DAG storage with SHA256 deduplication.
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.
In 2023 I drafted a paper on routing between a large and small LLM via KL-divergence thresholds. Speculative decoding had already solved the problem more rigorously. Here is the post-mortem.
27 image commands, one constraint: read JSON, write JSON. The closure property as a generative design principle.
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 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.
A streaming data processing system implementing boolean algebra over nested JSON structures, with lazy evaluation, S-expression queries, and memory-efficient windowed operations.
A command-line implementation of relational algebra for JSONL data with full support for nested structures, schema inference, and composable pipelines.
A composable ecosystem of tools for manipulating nested data structures. From a simple helper function to a full data algebra, guided by purity, pedagogy, and the principle of least power.
A Lisp-like functional language designed for network transmission. JSL makes JSON serialization a first-class design principle, so closures, continuations, and entire computation states can travel over the wire.
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.
An immutable-by-default tree library for Python with composable transformations, pipe-based pipelines, and pattern-matching selectors.
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.
A header-only C++20 library that achieves 3-10x compression with zero marshaling overhead using prefix-free codes and Stepanov-style generic programming.
When the problem is coordinating computation across parties who can't share data, the SICP move is to build a language for it. Apertures adds one primitive — holes — to a Lisp, and gets pausable, resumable evaluation for free.
A C++20 library for composing online statistical accumulators with numerically stable algorithms and algebraic composition.
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.
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.
Space bounds, entropy requirements, and cryptographic security properties of perfect hash functions.
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.
Adam, K-FAC, EWC, and natural gradient are all approximating the same thing at different fidelity levels. The math and the caveats.
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 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 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 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.
A C++ library for composable hash functions using algebraic structure over XOR, with template metaprogramming.
Define patterns, define replacements, repeat until done. Watch a 90-line rewrite engine learn to differentiate.
Your regex compiles into a state machine. Type a pattern, feed it a string, and watch the machine think — step by step.
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.
Choosing step size h for finite differences: small enough for a good approximation, not so small that floating-point errors eat your lunch.
Suleman et al. (2009) propose using one big core to run critical sections on behalf of many small cores. The idea is simple. The tradeoffs are not.
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.
Generalizing Peterson's mutual exclusion algorithm to N processors using a tournament tree structure, with a Java implementation.
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.
elementa is a linear algebra library built to teach. Every design decision prioritizes clarity over cleverness. Code that reads like a textbook and compiles.
Any length vector satisfying Kraft has a prefix-free code. Here is the construction.
The same GCD algorithm works for integers and polynomials because both are Euclidean domains. One structure, many types, same algorithms.
Which codeword-length vectors are achievable by prefix-free codes? Kraft's inequality is the answer.
Rational numbers give exact arithmetic where floating-point fails. The implementation connects GCD, the Stern-Brocot tree, and the algebraic structure of fields.
The Miller-Rabin primality test demonstrates how probabilistic algorithms achieve arbitrary certainty, trading absolute truth for practical efficiency.
Integers modulo N form a ring, an algebraic structure that determines which algorithms apply. Understanding this structure unlocks algorithms from cryptography to competitive programming.
The Russian peasant algorithm computes products, powers, Fibonacci numbers, and more, once you see the underlying algebraic structure.
What if containers wasted zero bits? A C++ library for packing arbitrary value types at the bit level using pluggable codecs.